搜索
01背包遗传算法一、算法说明：遗传算法是具有“生成+检测”的迭代的搜索算法。它的基本处理流程如图所示。使用基本遗传算法解决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:返回到第四步,直至循环结束初始化种群评估种群中个体适应度选择编码交叉变异演化二、结果分析蓝色字表示输出结果运行时间表示算法复杂度1)数据集一:物体总个数为30时物品价值：2202081981921801801651621601581551301251221201181151101051011001009896959088828077物品重量:808285707270665055255055404850322260303240383532252830222530背包容量1000-----------------------------最优值2984.000000对应重量995.000000线性解：110111011111110110111101100110运行时间:16ms2)数据集二:物体总个数为50时物品价值：2202081981921801801651621601581551301251221201181151101051011001009896959088828077757372706966656360585650302015108531物品重量:808285707270665055255055404850322260303240383532252830222530453060502065202530102025151010104421背包容量1000-----------------------------最优值3010.000000对应重量993.000000线性解：10011101011111011111001111111000001010010000001110运行时间:31ms3)数据集三:物体总个数为60时物品价值：597596593586581568567560549548547529529527520491482478475475466462459458454451449443442421410409395394390377375366361347334322315313311309296295294289285279277276272248246245238237物品重量:541831068230587116611719090191205128110896361408630911563170199142981781614031241971017316732159711021441512713120916417717712914617536414643170180171背包容量1000-----------------------------最优值9738.000000对应重量997.000000线性解：100111100010000111001001100001011000111000001000000011100000运行时间:19297ms代码：#includewindows.h#includestdio.h#includestdlib.h#includemath.h#includetime.h/*数据集一**********************************************************************#defineS5//种群的规模#definePc0.8//交叉概率#definePm0.05//突变概率#defineKW1000//背包最大载重1000#defineN30//物体总数#defineT800//最大换代数#defineALIKE0.05//判定相似度intstop=0;//初始化函数中初始化为所有价值之和intt=0;//目前的代数intvalue[]={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,10,8,5,3,1};intweight[]={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};/*数据集二***********************************************************************/#defineS5//种群的规模#definePc0.8//交叉概率#definePm0.05//突变概率#defineKW1000//背包最大载重1000#defineN50//物体总数#defineT800//最大换代数#defineALIKE0.05//判定相似度intstop=0;//初始化函数中初始化为所有价值之和intt=0;//目前的代数intvalue[]={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,10,8,5,3,1};intweight[]={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};/*数据集三***********************************************************************#defineS5//种群的规模#definePc0.8//交叉概率#definePm0.05//突变概率#defineKW1000//背包最大载重1000#defineN60//物体总数#defineT800//最大换代数#defineALIKE0.05//判定相似度intstop=0;//初始化函数中初始化为所有价值之和intt=0;//目前的代数intvalue[]={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,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};intweight[]={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,171,130,183,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,174,156,82,47,126,102,83,58,34,21,14};/************************************************************************/structindividual//个体结构体{boolchromsome[N];//染色体编码doublefitness;//适应度//即本问题中的个体所得价值doubleweight;//总重量};intbest=0;intsame=0;individualX[S],Y[S],bestindividual;/************************************************************************/intcomp(individualbestindividual,individualtemp);//比较函数voidcheckalike(void);//检查相似度函数voidGenerateInitialPopulation(void);//初始种群voidCalculateFitnessValue(void);//适应度voidSelectionOperator(void);//选择voidCrossoverOperator(void);//交叉voidMutationOperator(void);//变异voidFindBestandWorstIndividual(void);//寻找最优解voidsrand(unsignedintseed);//随机生成/************************************************************************/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}/************************************************************************/voidCheckalike(void){inti=0,j=0;for(i=0;iS;i++)//相似度校验{for(j=0;jN;j++){booltemp=X[i].chromsome[j];for(intk=1;kS;k++){if(temp!=X[k].chromsome[j]