用遗传算法解决0-1背包问题

1、实现遗传算法的0-1背包问题求解及其改进姓名：学号：班级：提交日期：201?年6月27旦_实现遗传算法的0-1背包问题求解摘要：研究了遗传算法解决0-1背包问题中的几个问题:1）对于过程中不满足重量限制条件的个体的处理，通过代换上代最优解保持种群的进化性2）对于交换率和变异率的理解和处理方法，采用逐个体和逐位判断的处理方法3）对于早熟性问题，引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。通过实际计其比较表明，本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的

2、遗传算法 关键词：遗传算法；背包问题；优化1. 基本实现原理：一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很 多可行解当屮求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为wi,其价值为vi,背包的容量为c。选择合适 的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重 量之和不能大于背的容量c。在选择装入背的物品时，对每种物品i只有两种选择：装 入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。其数学模型为：c 的餅下f=l其中 1 = ir2.r3.r40-

3、1背包问题传统的解决方法奋动态规划法、分支界限法、冋溯法等等。传统的方法不能奋 效地解决0-1背包问题。遗传算法（genetic algorithms）则是一种适合于在火量的可行解屮 搜索最优（或次优）解的有效算法。二、遗传算法特点介绍：遗传算法（genetic algorithm, ga是1962年holland教授首次提出了 ga算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观 点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。基本遗传算法求解步骤：step 1参数设置：在论域空间上定义一个适应度函数/（x）,给定种群规模w，

4、交叉率pc 和变异率pm，代数r;step 2初始种群：随机产生7中的w个染色体slz s2, sn，组成初始种群5=slz s2,sn， 置代数计数器step 3计算适应度：s中每个染色体的适应度f（）;step4判断：若终止条件满足，则取5中适应度最大的染色体作为所求结果，算法结束。 step 5选择复制：按选择概率pu,）所决定的选中机会，每次从s中随机选定1个染色体并 将其复制，共做/v次，然后将复制所得的w个染色体组成群体51;step 6交叉：按交叉率所决定的参加交叉的染色体数c，从中随机确定c个染色体， 配对进行交叉操作，并用产生的新染色体代替原染色体，得群体52;step 7变

5、异：按变异率pm所决定的变异次数m，从52中随机确定m个染色体，分别进行 变异操作，并用产生的新染色体代替原染色体，得群体53;step8更新：将群体53作为新一代种群，即用s3代替5,转步3;遗传算法是一种仿生算法，即模拟生命演化的算法，它从一个代表问题初始解的初始种 群出发，不断重复执行选择，杂交和变异的过程，使种群进化越来越接近某一目标既最优 解，如果视种群为超空间的一组点，选择、杂交和变异的过程即是在超空间中进行点集之间 的某种变换，通过信息交换使种群不断变化，遗传算法通过模拟达尔文“优胜劣汰，适者生 存”的原理激励好的结构，同时寻找更好的结构，作为一种随机的优化与搜索方法，遗传算 法

6、有着其鲜明的待点。一遗传算法一般是直接在解空间搜索，而不像图搜索那样一般是在问题空间搜索，最后 才找到解（如果搜索成功的话）。一遗传算法的搜索随机地始于搜索空间的一个点集，而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点，所以遗传算法是一种随机搜索算法。一遗传算法总是在寻找优解（最优解或次优解），而不像阁搜索那样并非总是耍求优解, 而一般是设法尽快找到解（当然包括优解b所以遗传算法乂是一种优化搜索算法。一遗传算法的搜索过程是从空间的一个点集（种群）到另一个点集（种群）的搜索，而不像图 搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索，适合大 规模并行计算，而且这种

7、种群到种群的搜索有能力跳出局部最优解。一遗传算法的适应性强，除需知适应度函数外，几乎不需要其他的先验知识。一遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，不要求连续性，能以 很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。3.程序步骤：一、使用基本遗传算法解决0-1背包问题：1：打开数据文件2:设罝程序运行主界面3:调用初始化种群模块3-1:按照一定的种群规模和染色体长度以基因为单位用随机产生的0-1对个体赋值3- 2:调用计算适应度函数4:以最大进化代数为循环终止条件开始进行循环4- 1:调用产生新一代个体的函数4-1-1:调用选择函数4-1-2:调用交叉函数4-

8、1- 3:调用变异函数4-1-4:调用计算适应度函数5:调用计算新一代种群统计数据函数6:调用输出新一代统计数据函数7:返冋到第四步，直至循环结束二、基本遗传算法解决0-1背包问题存在的不足：1. 对于过程中不满足重量限制条件的个体的处理在用基本遗传算法解决0-1竹包问题的时候，在初始化或者交叉变异后可能会产生不满 足重量约朿条件的伪解，而对于这些伪解，基木遗传算法没有给出一个很好的处理方法，而 只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算 法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体 来进行替换，这样，既使得种群中所有的

9、个体均满足重量的约束条件，又保留了较优解，符 合遗传算法的思想。具体做法为：在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如 果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。具体做法力：在每代遗传后通过函数findbestandworstlndividualo找到当前最优值并保存 bestindividual 中，在计算适应度函数 calculatefitnessvalueo中加入:if（w>kw） xi=bestindividual; /如果不是解，找最好的一个解代之其中w为当前个体的总重量，kw力背包最大承重量，xi表示种群中第i个个体，b

10、estindividual 为保存的个体最优解。2. 对于交换率和变异率的理解和处理方法根据遗传算法的基本步骤的交叉和变异操作step 6交叉：按交叉率所决定的参加交叉的染色体数c，从屮随机确定c个染色体， 配对进行交叉操作，并用产生的新染色体代替原染色体，得群体52;step 7变异：按变异率pm所决定的变异次数m，从52中随机确定m个染色体，分别进行 变异操作，并用产生的新染色体代替原染色体，得群体53;可以冇两种处理方法：其一，采用先确定数fi在随机选取的方法，步骤如下.对于交叉操作：1, 根据交叉率确定应该交叉的个体数目n2, 在种群屮进行n次循环2-1随机选中种群中的一个个体a 2-

11、2随机选中种群中昇于a的一个个体b2-3随机确定交叉位数 2-4进行交叉对于变异操作：1, 根据变异率确定应该变异的染色体数目n2, 在种群中进行n次循环2-1随机选中种群中的一个个体的染 色体a2-2随机选中染色体a的某位基因2-3对进行0-1互换变异其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下:对于交叉操作：1, 在种群屮进行s次循环，其屮s代表种群屮个体的 数量2, 对于每一个个体xj （x为种群数组）做如下操 作2-1生成随机数ps0,l,判断p与的大小关系2-2如果p：s外说明xi需要交换2-2-1随机在种群中找到异于xi的另一 个体进行交换2-3如果p>fe

12、说明xi不需要交换对于变异操作：1, 在种群屮进行s次循环，其屮s代表种群屮个体的 数量2, 对每一个个体xi】做n次循环，其屮n为染色体 位数2-1对染色体的每一位3-1生成随机数qs0,l,判断q与pm的大小关系3-2如果说明需要进行0-1互换变异2-3如果说明不谣要变分析这两种处理方法可知：方法一没冇很好地体现随机机会均等的思想，因为在步骤1中确 定的需要操作的数a n后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体 而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情 况，而如梁采用方法二，就体现了机会的均等性，即要求对每一个单元操作目标进行概率的

13、验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：void crossoveroperator(void)/交叉操作 for(i=0; i<s; i+)dop=rand(>%s;/两个0，s的随机数 q=rand()%s;while(p=q);int w=l+rand()%n;/l,n交换的位数 double p=(rand()%1001)/1000.0; if(p<=pc)for(j=0;j<w;j+)交换 w 位数据void mutationoperator(void)/变异操作 for (i=0; i<s; i+) for (j=0

14、; j<n; j+)if(q<pm) /对每一位都要考虑 if(xi.chromsomej=l)xi.chromsomej=0;else xi.chromsomej=l;q=(rand()%1001)/1000.0;/产生 qe0,l2.对于算法早熟性的分析及解决方法遗传算法中种群中的个体由初始化时的具有多样性，可能会由于在进化过程中一些超常 个体限制其它个体的进化一一这个个体的适应度大大优于种群内的其它值，由于适者生存原 则这个个体被不断复制从而充满y整个种群，使得种群的多样应大大降低，进化停滞，从而 出现算法收敛于局部最优解的现象，称为早熟现象。早熟现象的可能解法：1) 通过提

15、高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基木遗传算法 中不添加相关操作的情况下唯一的一种方法，然而这种方法冇明显的弊端：在提高变异 率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法 丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。2) 引入多样性衡量和处理基木思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。做法：1,判断是否达到早熟现象对于种群屮s个个体，判断等位基因的相等程度，即引入一个参数值same,如果 same达到一定的理论值大小就可以认为达到了早熟现象。2,早熟现象的处理，即引入新的个体。处理过程中应该不违反适者

16、生存的原则，所以应该保留较好的个体，所以首先 选中适应度最小的个体执行删除操作，然后随机生成一个新的符合重量限制且打破早熟现象的新个体。具体实现见函数:void checkalike(void)/相似度校验for( i=0;i<s;i+)for(j=0;j<n;j+)bool temp=xi.chromsomej;forfint k=l;k<s;k+)if(temp!=xk.chromsomej)break;if(j=n)same+;if(same>n*0.5>/大于50%作为判定为早熟/确定最小int minindex=0; for(intn=0;n<s;

17、n+)if(xn.fitness<xminindex.fitness)minindex=n/重新生成 for (j=0; j<n;j+)bool m=(rand()%10<5)?0:l;xminindex.chromsomej=m;xminindex.weight+=m*weightj；/个体的总重量xminindex.fjtness+=m*valuej;/个体的总价值3. 一种最优解只向更好进化方法的尝试基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近 似解都产生于这个特殊的个体，最优解只向更好进化方法中规定：每代中选出一个最优解 并做好相应的记

18、录或者标记，最优解参与交叉和变异，只是在交叉或者变异时对最优解进行 前后适应度的比较，如果发现交叉或者变异后适应度人于操作前适应度，则保存操作后的结 果，如果发现交叉或者变异后适应度小于操作前适应度，则禁止最优解的操作，而不禁止与 最优解进行交叉的个体的变化。这样，每一代中的最优解的特性可以通过交叉传递给同代中 的其它个体，而保证种群一定会向更好的方向进化。做法在交叉后和变异后调用以下函数判断：int comp(individual bestindividual,individual temp)/比较函数intfit=o,w=o;/第一种不变:操作后不满足重量函数，第二种韻作后适应度小于楝作前

19、for(int i=0;i<n;i+)fit+=temp.chromsomei*valuei;w+=temp.chromsomei*weighti if(w>kw)return -1;return (bestindividual.fitness>fit?-l:l;/如果小于原来值或者不满足重量函数，则返回-1#defines500/种群的规模#definepc0.8/交叉概率/definepm0.01/突变概率#definekw878/背包最大载重#definen20/物体总数#definet1000/最大换代数1、改进的遗传算法解决a 参数设置：1背包问题:2个体的表示和染

20、色体编码用变量i代表物件,i = 1, 2, ,n定义变量xi，其含义为：xi=l表示：第i个物件被选入竹 包,xi = o表示第i个物件没有被选入背包。考虑n个物件的选择与否，就可以得到一个长度 为n的0,1序列。由此可见遗传算法应用于上述背包问题吋，采用简单二进制编码较为适宜 1每一组编码即为某一个个体的基因表示，称其为染色体，染色体长度取决于待分配的物件 的个数n.在编码形式的表示方法中，形如二进制编码10010101表示为一个待分配的物件的 个数为8 (编码长度)的一个竹包问题的一个解，则该个体对应于选择了物件1,4, 6, 8,即 第1,4, 6, 8个物品被放入了背伍。用数据格式表

21、示为：struct individual/个体结构体bool chromsomen; double fitness; double weight;/染色体编码/适应度/即本问题中的个体所得价值 /总重量;2产生初始种群n个待分配的物件随机产生s个长度为n的二进制串，即种群中个体的染色体编码的每一位 按等概率在0与1中选择s指的是种群规模，即种群中的个体数目.void generatelnitialpopulation(void); /初始种群3适应度函数背包lal物件的总重量为alxl + a2x2 + ,anxn,物件的总价值为clxl + c2x2 +, + cn xn0-1背包问题中采用

22、每个个体的总价值作为适应度，在满足背包容量的条件下，价值越大，适应度越高。所以适应度求解方法为：f i = clxl + c2x2 +, + cnxn (当 t alxl + a2x 2 +, + anxn < = c , xj = 0,1)考虑到会有不不满足容量条件的个体则：f i = 0 (当 alxl + a2x2 +, + anxn > c, xj = 0,1)上述适应度函数基于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不 可能为零，所以当随机产生的某个个体违竹约束条件时，通过把其适应度函数值罚为0而达 到淘汰该个体的目的。4选择-复制操作参照适应度函数值

23、和约束条件用赌轮选择法进行模拟，具体为：(1) 根据适应度函数值和约束条件，罚掉部分个体(前述不满足容量条件的个体)(2) 对于满足约束条件的个体，根据适应度函数值计算个体被选中的概率，称为选择概率:公式力:p(xsdpfxj称为染色体x,(/=1, 2, .,n)的选择概率(3) 根据轮盘赌累，.计公式为：%称为染色体功'=1, 2,，n)的积累概率7-*(4) 对己得到的累计概率作如下处理，完成选择操作：1) 在0,1区间a产生一个均匀分布的伪随机数。赌轮选示例2) 若rql,则染色体xl被选中。3) 若qk-l<r<qk(2<k<n),则染色体xk被选中。

24、对于n个个体，要进行n次选择，所以产生n个0, 1之间的随机数，相当于转 动n次轮盘，获得n次转盘停止吋的指针位置，指针停止在某一 扇区，该扇区代表的个体既被选屮(如右图)，被选屮的个体进 行赋值操作进入下一代，复制过程耍进行s次(s为种群的规模)。5交叉操作：对于每一个个体，根据交叉率pe做如下操作：(1)随机产生一个交叉点的位置(2>随机选取当前代屮的两个个体作为父个体(3>根据交叉点的位置，做单点交叉 6变异操作：根据变异率pm(1>随机产生变异点的位置(2>在变异点位置作0-1翻转 8、算法终止程序中定义了一个最优值，stop=2=1h般情况下这个最优值达不到，

25、一旦程序在执行过程中达到此最优值，也就没冇必要在执行下去，因为这必定是最好的解，所以保存最优值和 最优解，结束。如果程序的最优值达不到理想情况下的stop，那么根据最大换代次数来结束程序，在结束后 的种群中找到一个最好的解作为本问题的最优解，程序结束。4算例(可以使用参考文献2中的典型算例1. 小规模问题的算例：算例1-1:设定物品价值value=5g,3q,6q,80,20重量weight35,40,40,20,15背包的最大承重量为100遗传算法中参数：群体大小s=5,交叉率pc=0.8,变异率pm=0.05,最大换代次数t=20,通过多次试验比较本文改进后遗传算法和其他得到结果如下表所示

26、：e:users算法达到全恸最优解未达到全埼嚴忧解紛改进遗传算法23750 经典遗传算法92130合计322860(右图中输出第一行数为最优价值；第二行数表1两种算法求赙小規模问题的计算结果对比为重量；第三行为最优解)190190959510110lanepresspress|190951011c pres 5190ps1011019095101101609511011909510111909510111190951011&pres pre;, |presj19095101101909510110press3j.e、.e: . .e卜.e心乇17 .e19095101101909519

27、09517010001110press1909510110 press anye:ui190190 1190959595101lwl01: t011017010001110190 9510110press19019095951011外10110presd press19019019095 i 1100 1011c 0111gppcsj; press95 10110 press95 10110 press95 101ie press190 f|l90 9595preslpress本文改进的遗传算法：实验总次数：30达到全局最优解次数：27未达到全局最优解：3效果截图由实验结果可知在小规模算例中，

28、本文改进的遗传算法优丁前两者。2. 较大规模问题求解算例：遗传算法中参数：群体大小s=5，交叉率pc=0.8、变异率pm=0.05,最大换代次数t=800，相似度取5%实例1:价值 value： 92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58重量 weight： 44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63背包的最大承重量：878实例2:价值value：220,208,198,192,180,180,165,162,160,158,155,130,1254

29、22,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,10,8,5,3,1；重量 weight:80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50 ,20,65,20,25,30,10,20,25、15,10,10,10,4,4,2,1;背包最大承重量：1000实例3:(说明：参考论文中的实

30、例3价值数组中缺少一个值，这里以0补上，使价值和重量一 一对应)价值value：597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482,478,475,475,466,462,459,458,4 54,451,449,443,442,421,410,409,395,394,390,377,375,366,361,347,334,322,315,313,311,309,296,295,294,28 9,285,279,277,276,272,248,246,245,238,237,232,231,230,225,19

31、2,184,183,176,171,169,165,165,154,153,150, 149,147,143,140,138,134,132，127，124,123,114,111，104,89,74,63,62,58,55,48,27,22,12,6,0;重量 weight:54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86,30,91,156,31,70,199,142,98,17 8,16,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,20

32、9,164,177,177,129,146,17,53,64,146,43,170, 180,171，130483,5，113,207,57，13,163,20,63，12,24,9,42,6，109,170，108,46,69,43，175,81,5,34,146，148,114,160,1 74,156,82,47,126,102,83,58,34,21,14;各运行30次后比较30次屮的最好值，比较结果如卜本文改进的遗传算法和先前算法结果如下：衰2两种w法求解大嫕檨算例的结果对比实例-经典遗传算法改进遗传真法算法所傳最好解染色体价位/容置算法所得最好解染色体价值/容量1101111110

33、100111111011 024/838100i111i1i11iii1ii011 037/s742110101i001001111i01100001111110100ioou11i1100i0112w5/999lioioouuioioououoiuo11111000010110010101011113 010/995jioinooiiiooinoiiiaoou11111111111001110111000113lniniiioiiiiioiooiiuoillllooholtllllllllolloil21 222/6 2531ui111h011ui0100ii11011111(x)11011

34、1111111101111123 245/6 714oouoioiuoooioooioioiooo1011010111000100010101000本文改进遗传算法实验结果：实例1:（输出第一行数为最优价值；第二行数为重量；第三行为最优解）104287810111111010111111101 press any key to continuee:usersadministratordesktopga_ 作业要求及参考资debug 背包问 ixexe"3044997100101press3035 i 13021 i 13084 1000 10001001111 100100jj 11

35、01000hpressc ,press akpi*ess any3026 9991100001 press ae:usersadministratordesktopga.30761000100101011111110110111111110110 press any key to continue实例2:e:usersadministratordesktopga作业要求及参考 s.debug背色卜抓3p033 i |3046|2955000 1000 h1000 l983ii00i0i0i010011u110110011111110i0011011111ill00000000001000100

36、1011 e:usersad mini stratordesktopgajkshdebugmfelbexe3108100011010101111010111011011111111000001010011000001011 press any key to continue实例3:根据得到最优解的情况本文改进的遗传算法所得最好值均好于先前两种算法，特别是实 例3屮，在缺少一个价值值补0的情况下得到的结果仍然优于前两种算法。由此得出结论：本文改进的遗传算法优于前两种。4.心得体会：遗传算法是一种模拟生物进化在解中求解最优值的方法，实现起来方便，适于处理人宗 数据，然而基于简单棊本遗传算法在求解不

37、同问题时应该具体问题具体分析，找的结合所解 问题的优化方法，例如本文分析的遗传算法解决0-1背包问题，虽然简单基本遗传算法可以 求出一个比较好的解出来，但是分析可知，结果并不令人满意，在对问题进行细致的分析、 查阅相关资料和深入思考后，我提岀了自己认为比较好的4点改进方法并通过实践结合具体 的算例把改进后的遗传算法和与原来的简单遗传算法和参考文献中的一种改进方法进行了 比较，结果显示本文改进的遗传算法无论在小规模数据处理还是较大规模数据处理方面均优 于前两者，这一点很令人高兴。另外，通过本次实践，我也深刻体会到对于算法分析和改进的重要性，往往一个算法经 过认真地分析和合理的改进后会获得性能上的

38、提高一一时间复杂度或者空间复杂度的降低，而且能够获得更好的解，本文就是一个很好的例证。6.参考文献：lm.h.aisuwaiyel著，方世昌等译算法设计技巧与分析电子工业出版社，北京，2009 2】闰丽用基本遗传算法解决0-1背包问题通化师范学院学报第26卷第4期，2005,7 3赵新超，韩宇，艾文宝求解背包问题的一种改进遗传算法计算机工程与应用2011, 47(24) 7.附】实现程序：已通过vc6.0编译后运行 #include <iostream.h> include <stdlib.h> include <math.h>/include <ti

39、me.h>/* ,j、夫见中兑 *#defines5/种群的规模#definen5/物体总数#definepc0.8/交义概率#definepm0.05/突变概率#definekw100/背包最大载重#definet20/最大换代数#definealike0.05/判定相似度#defines5/种群的规模#definen20/物体总数#definepc0.8/交叉概率#definepm0.05/突变概率#definekw878/背包最大载重/definet800/s大换代数#definealike0.05/判定相似度int stop=0;/初始化函数中初始化力所有价值之和int t=0;

40、/目前的代数int stop=0;int t=0;int weight=35,40,40,20z 15; int value】=50,30,60,80,20; /*实例1/初始化函数屮初始化为所有价值之和 /0前的代数 /物体重量 /物体价值*木*本*本*氺*本*木*本*本木本*本*本*本*int weight=44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63;/物体重量int value=92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58; /物体价值#defi

41、nes5/种群的规模#definepc0.8/交叉概率#definepm0.05/突变概率#definekw1000/背包最人载重1000#definen50/物体总数#definet800/最大换代数#definealike0.05/判定相似度intstop=0;/初始化函数中初始化为所有价值之和intt=0;/目前的代数/*实例2木木氺本木木木氺木氺木氺本氺本氺本木木木木木氺木氺木氺木氺木氺木木木木氺木氺木氺本氺氺木木木木木氺木氺本氺木氺氺木木木氺木氺木氺本氺木木木木木int vaue=220,208,198,192,180,180,165,162,160,158,155,130,125,

42、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,10,8,5,3,1;int weight=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65 ,20,25,30,10,20,25,15,10,10,10,4,4,2,1;/* '、) : /5| q本本氺本氺本本*

43、本*本氺本氺本*本本*本本本本本氺本*本本氺本*本本氺本氺本本本*本本*本本氺本氺本氺本/#defines5/种群的规模#definepc0.8/交叉概率#definepm0.05/突变概率#definekw6718/背包最大载重1000#definen100/物体总数/definet800/s大换代数#definealike0.05/判定相似度intstop=0;/初始化函数中初始化为所有价值之和intt=0;/目前的代数int vaue=597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482,478,475,4

44、75,466,462,459,458,454,45 1,449,443,442,421,410,409,395,394,390,377,375,366,361,347,334,322,315,313,311,309,296,295,294,289,285, 279,277,276,272,248,246,245,238,237,232,231,230,225,192,184,183,176,171,169,165,165,154,153,150,149,14 7,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,2

45、7,22,12,6,250;int weight=54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86,30,91,156,31,70,199,142,98,178,16,140,31,24，197，101,73,16,73,2,159,71,102,144,151，27，131，209，164,177,177,129，146，17,53,64,146,43，170，180，17 1,130,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69

46、,43,175,81,5,34,146,148,114,160,174,156 ,82,47,126,102,83,58,34,21,14;/木木本木本*木木*木*木本*木木*木本*木*木*本木本木*木本*木*木*木*木*本木本木本木本*木木木*本*本*本*木*本*struct individual/个体结构体bool chromsomen; double fitness; double weight;/染色体编码/适应度/即本问题中的个体所得价位 /总重簠;int best=o;int same=0;individual xslyslbestindividual;/氺木本木本木本*本木本木本

47、木本*本*本*本木本木本木本木本木本*氺本木本木本木本木本*本*本木*木*木本*本本木int comp(individual bestindividual,individual temp);void checkalike(void);void generatelnitialpopulation(void);void calculatefitnessvalue(void);void selectionoperator(void);void crossoveroperator(void);void mutationoperator(void);void findbestandworstlndivj

48、dual(void);void srand(unsigned int seed);/比较函数/检查相似度函数/初始种群/适应度/选择"交叉/变异/寻找最优解 /随机生成*本木*木木*氺*木本*木木*氺*木*木本*本*木木本木本*本木*木本*木*木*木*本木*木*氺*木木木*本*本*本*木木本*木int comp(individual bestindividual,individual temp)/比较函数int fit=o,w=o;/第一种不变:操作后不满足重w:函数，第二种:操作后适应度小于操作前 forfint i=0;i<n;i+)fit+=temp.chromsomei

49、*valuei;w+=temp.chromsomei*weighti; if(w>kw)return -1;return (bestindividual.fitness>fit?-l:l);/如果小于原来值或者不满足重量函数，贝!1返回-1/氺氺本氺本氺本*氺氺氺氺氺*氺本*氺氺氺氺氺氺氺*氺本氺*氺本氺本氺本氺本氺本氺氺*氺本氺本氺本氺本*本氺氺*氺*氺*氺本*本氺氺/void checkalike(void)int i=0,j=0;for( i=0;i<s;k+)/相似度校验 for(j=0;j<n;j+)bool temp=xi.chromsomej; for(i

50、nt k=l;k<s;k+)if(temp!=xk.chromsomej)break;if(j=n)same+;if(samen*alike)/大于alike作为判定为早熟 int minindex=o; for(int n=0;n<s;n+)if(xn.fitness<xminindex.fitness)minindex=n;/确记最小 for (j=0; j<n;j+>/重新生成 bool m=(rand()%10<5)?0:l;xminindex.chromsomej=m;xminindex.weight+=m*weightj;/个体的总重量 xmin

51、index.fitness+=m*valuej; /个体的总价值/*木木*木*木本木*木*木本*木*木*木*氺*本木*木*木*木*木本木*本*木/void generatelnjtialpopulation(void)/初始种群，保证每个值都在符合条件的解int i=0,j=0; bool k;for(i=0;i<n;i+>stop+=valuei;/设罝理论最优值 for (i=0; i<s; i+)int w=0,v=0; for (j=0; j<n;j+)k=(rand()%10<5)?0:l;xi.chromsomej=k; w+=k*weightj;/个

52、体的总重量 v+=k*valuej; /个体的总价值if(w>kw) i-;/如果不是解，重新生成elsexi.fitness=v;xi.weight=w;ifv=stop)bestindividual=xi】;return;/这种情况一般不会发生y木木木氺木氺本氺氺木木木木木氺本氺木木氺木木木木木氺本氺木木木木木氺氺木木木氺本氺本氺本氺木木木木氺木氺木氺木氺本氺木木木木氺木氺木氺本木木木氺yvoid calculatefitnessvalue()int i=0,j=0; for (i=0; i<s; i+)int w=0,v=0; for (j=0; j<n;j+)w+=x

53、i.chromsomej*weightj;/个体的总重量 v+=xi.chromsomej*valuej； /个体的总价值xi.fitness=v;xi.weight=w;jf(v=stop)bestindividual=xi;return;/符合条件情况下最优解这种情况一般不会发生 if(w>kw) xi=bestindividual; /如果不是解，找最好的一个解代之y木本木氺氺氺本本本氺本氺氺*木本木本本本氺本氺氺木氺本氺本木木氺本木本氺氺本氺本氺本氺本氺本氺本木氺本氺本氺本氺本氺本氺本木氺本氺*木本木本本void selectionoperator(void)int i, index; double p, sum=0.0; double cfitnesss;/选择、累积概率 individual newxs;for (i=0;i<s;i+) sum+=xi