01背包遗传算法代码说明

1、01背包遗传算法一、算法说明:遗传算法是具有“生成+检测”的迭代的搜索算法。它的基本处理流程如图 所示。编码1F初始化匕种群评估种群中个体适应度演化1r选择1!交叉1r变异使用基本遗传算法解决0- 1背包问题的程序步骤如下1:设置种群的规模、交叉概率、突变概率、背包最大载重等常数2:设置物品的重量和价值3:调用初始化种群模块3- 1:按照一定的种群规模和染色体长度以基因为单位用随机产生的0- 1对个体赋值2:调用计算适应度函数4:以最大进化代数为循环终止条件开始进行循环1:调用产生新一代个体的函数4- 1- 1:调用选择函数4- 1- 2:调用交叉函数4- 1- 3:调用变异函数4- 1- 4

2、:调用计算适应度函数5:调用计算新一代种群统计数据函数6:调用输出新一代统计数据函数7:返回到第四步，直至循环结束二、结果分析蓝色字表示 输出结果 运行时间表示 算法复杂度1）数据集一: 物体总个数为 30时物品价值： 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物品重量 : 80 82 85 70 72 70 66 50 55 25 50 5540 48 50 32 22 60 30 32 40 38 35 32 2

3、5 2830 22 25 30 背包容量 1000最优值 2984.000000对应重量 995.000000线性解： 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 11 0 1 1 0 0 1 1 0运行时间 : 16 ms2）数据集二: 物体总个数为 50时物品价值： 220 208 198 192 180 180 165 162 160 158 155 130125 122 120 118 115 110 105 101 100 100 98 96 95 90 8882 80 77 75 73 72 70 69 66 65 63 60 58 56 50

4、30 2015 10 8 5 3 1 TOC o 1-5 h z 物品重量 :80828570 72706650552550 5540 485032226030 3240383532252830 222530453060 5020652025301020 25151010104 4 21背包容量 1000最优值 3010.000000对应重量 993.000000线性解： 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 00 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 00 0 1 1 1 0运行时间 : 31 ms3）数

5、据集三: 物体总个数为 60时 物品价值： 597 596 593 586 581 568 567 560 549 548 547 529 TOC o 1-5 h z 529 527 520491 482 478475 475466 462 459458 454451449 443 442421 410 409395 394390 377 375366 361347334 322 315313 311 309296 295294 289 285279 277276272 248 246245 238 237物品重量 : 54 183 106 82 30 58 71 166 117 190 90

6、191 205 128 110 89 63 6 140 86 30 91 156 3170 199 142 98 178 16 140 31 24 197 101 73 1673 2 159 71 102 144 151 27 131 209 164 177177 129 146 17 53 64 146 43 170 180 171 背包容量 1000最优值 9738.000000对应重量 997.000000线性解： 1 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 10 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 01

7、 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 运行时间 : 19297 ms代码：#include #include#include #include #include/* 数 据 集*#define S5/ 种群的规模#definePc0.8/ 交叉概率#definePm0.05/ 突变概率#defineKW1000/ 背包最大载重 1000#defineN30/ 物体总数#defineT800/ 最大换代数#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函数中初始化为所有价值之和intt=0;/ 目前的代数int value=220,208,1

8、98,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,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,

9、10,10,10, 4,4,2,1;/* 数 据 集*#define S5/ 种群的规模#definePc0.8/ 交叉概率#definePm0.05/ 突变概率#defineKW1000/ 背包最大载重 1000#defineN50/ 物体总数#defineT800/ 最大换代数#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函数中初始化为所有价值之和intt=0;/ 目前的代数int value=220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100

10、,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;/* 数 据 集*#define S5/ 种群的规模#definePc0.8/ 交叉概率#definePm0.05/

11、 突变概率#defineKW1000/ 背包最大载重 1000#defineN60/ 物体总数#defineT800/ 最大换代数#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函数中初始化为所有价值之和intt=0;/ 目前的代数int 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,454,451,449,443,442,421,410,409,395,394,390,377,375,366,361,347

12、,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,147,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,250;int weight=54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,

13、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,1 71,130,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69,4 3,175,81,5,34,146,148,114,160,174,156,82,47,126,102,83,58,34,21,14;/* /struct ind

14、ividualbool chromsomeN; double fitness;double weight;int best=0;int same=0;/ 个体结构体/ 染色体编码/ 适应度 / 即本问题中的个体所得价值 / 总重量*/int comp(individual bestindividual,individual temp); void checkalike(void);void GenerateInitialPopulation(void);void CalculateFitnessValue(void);void SelectionOperator(void);void Cros

15、soverOperator(void);void MutationOperator(void);void FindBestandWorstIndividual(void);void srand(unsigned int seed);/ 比较函数/ 检查相似度函数/ 初始种群/ 适应度/ 选择/ 交叉/ 变异/ 寻找最优解/ 随机生成individual XS,YS,bestindividual;*/ int comp(individual bestindividual,individual temp)/ 比较函数int fit=0,w=0;/ 第一种不变 : 操作后不满足重量函数，第二种 :

16、操作后适应 度小于操作前for(int i=0;iKW)return -1;如果小于原来值或者不满return (bestindividual.fitnessfit?-1:1);/ 足重量函数，则返回 -1/*/void Checkalike(void)int i=0,j=0;for( i=0;iS;i+)/相似度校验for(j=0;jN;j+)bool temp=Xi.chromsomej;for(int k=1;kN*ALIKE)/ 大于 ALIKE 作为判定为早熟int minindex=0;for(int n=0;nS;n+) if(Xn.fitnessXminindex.fitnes

17、s) minindex=n;/ 确定最小 for (j=0; jN;j+)/ 重新生成 bool m=(rand()%105)?0:1; Xminindex.chromsomej=m; Xminindex.weight+=m*weightj;/ 个体的总重量 Xminindex.fitness+=m*valuej; / 个体的总价值 /*/void GenerateInitialPopulation(void)/ 初始种群 , 保证每个值都在符合条件 的解int i=0,j=0; bool k; for(i=0;iN;i+)stop+=valuei;/ 设置理论最优值 for (i=0; iS

18、; i+)int w=0,v=0;for (j=0; jN;j+) k=(rand()%10KW) i-; / 如果不是解，重新生成elseXi.fitness=v;Xi.weight=w;if(v=stop) bestindividual=Xi; return;/ 这种情况一般不会发生 /*/void CalculateFitnessValue()int i=0,j=0;for (i=0; iS; i+)int w=0,v=0;for (j=0; jKW) Xi=bestindividual;/ 如果不是解，找最好的一个解代之 /*/void SelectionOperator(void)i

19、nt i, index;double p, sum=0.0;double cfitnessS;/ 选择、累积概率 individual newXS;for (i=0;iS;i+) sum+=Xi.fitness;/ 适应度求和for (i=0;iS; i+) cfitnessi=Xi.fitness/sum; / 选择概率for (i=1;iS; i+) cfitnessi=cfitnessi-1+cfitnessi;/ 累积概率for (i=0;icfitnessindex)/ 轮盘赌进行选择 index+;newXi=Xindex;for (i=0; iS; i+) Xi=newXi;/

20、新的种群/*/void CrossoverOperator(void)/ 交叉操作int i=0, j=0,k=0;individual temp;for(i=0; iS; i+)int p=0,q=0;dop=rand()%S;产生两个0 , S的随机数q=rand()%S;while(p=q);int w=1+rand()%N;/1,N 表示交换的位数double r=(rand()%1001)/1000.0;/0,1if(r=Pc)for(j=0;jw;j+) temp.chromsomej=Xp.chromsomej;/ 将要交换的位先放 入临时空间Xp.chromsomej=Xq.c

21、hromsomej; Xq.chromsomej=temp.chromsomej;if(p=best)if(-1=comp(bestindividual,Xp)/如果变异后适应度变小Xp=bestindividual;if(q=best)if(-1=comp(bestindividual,Xq)/如果变异后适应度变小Xq=bestindividual;/* / void MutationOperator(void)int i=0, j=0,k=0,q=0; double p=0;for (i=0; iS; i+)for (j=0; jN; j+)p=(rand()%1001)/1000.0;i

22、f (pPm)/ 对每一位都要考虑 if(Xi.chromsomej=1)Xi.chromsomej=0;else Xi.chromsomej=1; if(i=best) if(-1=comp(bestindividual,Xi)/ 如果变异后适应度变小 Xi=bestindividual; /* / void FindBestandWorstIndividual(void)int i;bestindividual=X0;for (i=1;ibestindividual.fitness)bestindividual=Xi;best=i;/*int main()程序开始时间DWORD start, stop; start = GetTickCount();/srand(unsigned)time(0);t=0;GenerateInit