资源描述：
《最新基于遗传算法的0-1背包问题的求解-药学医学精品资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最新基于遗传算法的0-1背包问题的求解-药学医学精品资料研究背景及意义组合优化问题的求解方法研究成为了当前众多科学关注的焦点。内在的复杂性有着重要的理论价值。现实生活中广泛的应用。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。对于NP完全问题，如何求解其最优解或是近似最优解成为科学的焦点之一。研究背景及意义遗传算法成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。算法思路可
2、能性解---群体中的个体(染色体)染色体---编码成串目标函数---个体评价---适应值算法将根据适应度值进行它的寻优过程。遗传算法的寻优过程：选择---杂交---变异参数事先选择：种群的大小、染色体长、交叉概率、变异概率、最大进化代数等。在试验中参数一般选取如下：种群大小N=20~100交叉概率Pc=0.4~0.9，变异概率Pm=0.001~0.1最大进化代maxgen=100~500处理流程处理流程编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型串（即染色体）结构数据，如将数据9编码为“1001”；初始化种群：定义整数pop_size作为染色体的个数
3、，并且随机产生pop_size个染色体作为初始种群；评估种群中个体适应度：评价函数对种群中的每个染色体（chromosome）求得其个体适应度；选择：选择把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；处理流程交叉：定义参数Pc作为交叉操作的概率，由选择得到的两个个体以概率Pc交换各自的部分染色体，得到新的两个个体；变异：定义参数Pm作为变异操作的概率，由交叉得到每个个体中的每个基因值都以概率Pm进行变异；演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定
4、的循环次数（maxgen）的种群演化，遗传算法终止。0/1背包问题描述已知n个物品的重量（weight）及其价值（或收益profit）分别为Wi>0和Pi>0，背包的容量（contain）假设设为Ci>0，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？目标函数：maxf(x1,x2,...xn)=∑CiXiS.t∑WiXi≤Pi(*)其中Xi∈﹛0,1﹜(i=1,2,...n)其中Xi为决策变量，1表示装入，0表示不装入解决背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。动态规划--可以把困难的多阶段决策变换为一
5、系列相互联系比较容易的单阶段问题。--用数值方法求解时会随着状态变量的个数呈指数级的增长。解决背包问题的一般方法递归回溯--算法思想简单，完全遍历搜索空间，肯定能找到问题的最优解。--由于此问题解的总组合数有2n多个，因此，随着物件数n的增大，其解的空间将以2n级增长，当n大到一定程度上，用此算法解决背包问题是不现实的。解决背包问题的一般方法贪心--求解时计算复杂度降低了很多。--难以得到最优解，有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较多的背包问题。运行结果及分析实例数据：Weight={80,82,85,70,72,70,66,50,
6、55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,1020,25,15,10,10,10,4,4,2,1}Profit={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,
7、10,8,5,3,1}如何选择物品使在背包容量限制之内所装物品价值最大？运行结果及分析算法结果比较算法总价值总重量动态规划30821000贪心法3095996遗传算法31031000总结与展望遗传算法在求解背包问题上显示了超出想象、良好的搜索能力，它具有收敛快、搜索速度快的特点，在试验中取得了比动态规划、贪心法等更好的求解效果。然而在一般情况下，使用遗传算法解决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。如何改进基本遗传算法使它所求得的解逼近最优解，成为当前研究的重要问题。Theend！妊娠期甲状腺功能减退症（妊娠期甲减）东莞市常平医院内分泌代谢科唐
