实现遗传算法的0-1背包问题

实现遗传算法的0-1背包问题求解及其改进学校：学院：专业：姓名：学号：课程名称：指导老师：一、问题陈述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。其数学模型为：在满足∑𝑤𝑖𝑥𝑖≤𝐶𝑛𝑖=1的条件下求解𝑚𝑎𝑥∑𝑣𝑖𝑥𝑖𝑛𝑖=1，其中i=1,2,3,4…,n0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（GeneticAlgorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。二、遗传算法分析与实现1、遗传算法概述遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰）演化而来的随机化搜索方法。算法根据问题的目标函数构造一个适值函数，对一个由多个解（每个解对应一个染色体）构成的和种群进行评估、遗传、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。其特点是具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。•遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解(如果搜索成功的话)。•遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。•遗传算法总是在寻找优解(最优解或次优解),而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解(当然包括优解),所以遗传算法又是一种优化搜索算法。•遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。•遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。•遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。2、遗传算法流程Step1参数设置：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；Step2初始种群：随机产生U中的N个染色体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；Step3计算适应度：S中每个染色体的适应度f(𝑥𝑖)；Step4判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step5选择-复制：按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；Step6交叉：按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；Step7变异：按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；Step8更新：将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；停止产生初始种群判断停止条件选择遗传运算更新种群输出开始计算适值函数YN3.程序步骤：一、使用基本遗传算法解决0-1背包问题：1:打开数据文件2:设置程序运行主界面3:调用初始化种群模块3-1:按照一定的种群规模和染色体长度以基因为单位用随机产生的0-1对个体赋值3-2:调用计算适应度函数4:以最大进化代数为循环终止条件开始进行循环4-1:调用产生新一代个体的函数4-1-1:调用选择函数4-1-2:调用交叉函数4-1-3:调用变异函数4-1-4:调用计算适应度函数5:调用计算新一代种群统计数据函数6:调用输出新一代统计数据函数7:返回到第四步,直至循环结束二、基本遗传算法解决0-1背包问题存在的不足：1.对于过程中不满足重量限制条件的个体的处理在用基本遗传算法解决0-1背包问题的时候，在初始化或者交叉变异后可能会产生不满足重量约束条件的伪解，而对于这些伪解，基本遗传算法没有给出一个很好的处理方法，而只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体来进行替换，这样，既使得种群中所有的个体均满足重量的约束条件，又保留了较优解，符合遗传算法的思想。具体做法为：在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存bestindividual中，在计算适应度函数CalculateFitnessValue()中加入：if(wKW)X[i]=bestindividual;//如果不是解，找最好的一个解代之其中w为当前个体的总重量，KW为背包最大承重量，X[i]表示种群中第i个个体，bestindividual为保存的个体最优解。2.对于交换率和变异率的理解和处理方法根据遗传算法的基本步骤的交叉和变异操作Step6交叉：按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；Step7变异：按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；可以有两种处理方法：其一，采用先确定数目在随机选取的方法，步骤如下：对于交叉操作：1,根据交叉率确定应该交叉的个体数目n2,在种群中进行n次循环2-1随机选中种群中的一个个体a2-2随机选中种群中异于a的一个个体b2-3随机确定交叉位数2-4进行交叉对于变异操作：1,根据变异率确定应该变异的染色体数目n2,在种群中进行n次循环2-1随机选中种群中的一个个体的染色体a2-2随机选中染色体a的某位基因𝑎𝑗2-3对𝑎𝑗进行0-1互换变异其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下：对于交叉操作：1,在种群中进行S次循环,其中S代表种群中个体的数量2,对于每一个个体X[i]（X为种群数组）做如下操作2-1生成随机数p∈[0,1],判断p与𝑝𝑐的大小关系2-2如果p≤𝑝𝑐说明X[i]需要交换2-2-1随机在种群中找到异于X[i]的另一个体进行交换2-3如果p𝑝𝑐说明X[i]不需要交换对于变异操作：1,在种群中进行S次循环,其中S代表种群中个体的数量2,对每一个个体X[i]做N次循环，其中N为染色体位数2-1对染色体的每一位𝑎𝑗3-1生成随机数q∈[0,1],判断q与𝑝𝑚的大小关系3-2如果q≤𝑝𝑚说明𝑎𝑗需要进行0-1互换变异2-3如果q𝑝𝑚说明𝑎𝑗不需要变分析这两种处理方法可知：方法一没有很好地体现随机机会均等的思想，因为在步骤1中确定的需要操作的数目n后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情况，而如果采用方法二，就体现了机会的均等性，即要求对每一个单元操作目标进行概率的验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：voidCrossoverOperator(void)//交叉操作for(i=0;iS;i++)do{p=rand()%S;//两个[0，S]的随机数q=rand()%S;}while(p==q);intw=1+rand()%N;//[1,N]交换的位数doublep=(rand()%1001)/1000.0;if(p=Pc)for(j=0;jw;j++)交换w位数据voidMutationOperator(void)//变异操作for(i=0;iS;i++)for(j=0;jN;j++)q=(rand()%1001)/1000.0;//产生q∈[0,1]if(qPm)//对每一位都要考虑if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;elseX[i].chromsome[j]=1;3.对于算法早熟性的分析及解决方法遗传算法中种群中的个体由初始化时的具有多样性，可能会由于在进化过程中一些超常个体限制其它个体的进化——这个个体的适应度大大优于种群内的其它值，由于适者生存原则这个个体被不断复制从而充满了整个种群，使得种群的多样应大大降低，进化停滞，从而出现算法收敛于局部最优解的现象，称为早熟现象。早熟现象的可能解法：1）通过提高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基本遗传算法中不添加相关操作的情况下唯一的一种方法，然而这种方法有明显的弊端：在提高变异率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。2）引入多样性衡量和处理基本思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。做法：1,判断是否达到早熟现象对于种群中S个个体，判断等位基因的相等程度，即引入一个参数值same,如果same达到一定的理论值大小就可以认为达到了早熟现象。2,早熟现象的处理，即引入新的个体。处理过程中应该不违反适者生存的原则，所以应该保留较好的个体，所以首先选中适应度最小的个体执行删除操作，然后随机生成一个新的符合重量限制且打破早熟现象的新个体。4.一种最优解只向更好进化方法的尝试基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近似解都产生于这个特殊的个体，最优解只向更好进化方法中规定：每代中选出一个最优解并做好相应的记录或者标记，最优解参与交叉和变异，只是在交叉或者变异时对最优解进行前后适应度的比较，如果发现交叉或者变异后适应度大于操作前适应度，则保存操作后的结果，如果发现交叉或者变异后适应度小于操作前适应度，则禁止最优解的操作，而不禁止与最优解进行交叉的个体的变化。这样，每一代中的最优解的特性可以通过交叉传递给同代中的其它个体，而保证种群一定会向更好的方向进化。做法在交叉后和变异后调用以下函数判断：intcomp(individualbestindividual,individualtemp)//比较函数{intfit=0,w=0;//第一种不变:操作后不满足重量函数，第二种:操作后适应度小于操作前for(inti=0;iN;i++){fit+=temp.chromsome[i]*value[i];w+=temp.chromsome[i]*weight[i]}if(wKW)return-1;return(bestindividual.fitnessfit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1}三、改进的遗传算法解决0-1背包问题：1、参数设置：#defineS500//种群的规模#definePc0.8//交叉概率#definePm0.01//突变概率#defineKW878//背包最大载重#defineN20//物体总数#defineT1000//最大换代数2个体的表示和染色体编码用变量i代表物件,i=1,2,