背包遗传算法代码说明.docx

背包遗传算法代码说明.docx

《背包遗传算法代码说明.docx》由会员分享，可在线阅读，更多相关《背包遗传算法代码说明.docx（17页珍藏版）》请在冰点文库上搜索。

背包遗传算法代码说明

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:

返回到第四步,直至循环结束

2、结果分析

蓝色字表示输出结果

运行时间表示算法复杂度

1）数据集一:

物体总个数为30时

物品价值：

2202081981921801801651621601581551301251221201181151101051011001009896959088828077

物品重量:

808285707270665055255055404850322260303240383532252830222530

背包容量1000

-----------------------------

最优值2984.000000

对应重量995.000000

线性解：

110111011111110110111101100110

运行时间:

16ms

2）数据集二:

物体总个数为50时

物品价值：

2202081981921801801651621601581551301251221201181151101051011001009896959088828077757372706966656360585650302015108531

物品重量:

808285707270665055255055404850322260303240383532252830222530453060502065202530102025151010104421

背包容量1000

-----------------------------

最优值3010.000000

对应重量993.000000

线性解：

10011101011111011111001111111000001010010000001110

运行时间:

31ms

3）数据集三:

物体总个数为60时

物品价值：

597596593586581568567560549548547529529527520491482478475475466462459458454451449443442421410409395394390377375366361347334322315313311309296295294289285279277276272248246245238237

物品重量:

541831068230587116611719090191205128110896361408630911563170199142981781614031241971017316732159711021441512713120916417717712914617536414643170180171

背包容量1000

-----------------------------

最优值9738.000000

对应重量997.000000

线性解：

100111100010000111001001100001011000111000001000000011100000

运行时间:

19297ms

代码：

#include

#include

#include

#include

#include

/*数据集一**********************************************************************

#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;i

fit+=temp.chromsome[i]*value[i];

w+=temp.chromsome[i]*weight[i];

}

if（w>KW）return-1;

return（bestindividual.fitness>fit?

-1:

1）;//如果小于原来值或者不满足重量函数，则返回-1

}

/************************************************************************/

voidCheckalike（void）

{

inti=0,j=0;

for（i=0;i

{

for（j=0;j

{

booltemp=X[i].chromsome[j];

for（intk=1;k

{

if（temp!

=X[k].chromsome[j]）

break;

}

}

if（j==N）

same++;

}

if（same>N*ALIKE）//大于ALIKE作为判定为早熟

{

intminindex=0;

for（intn=0;n

if（X[n].fitness

minindex=n;//确定最小

for（j=0;j

{

boolm=（rand（）%10<5）?

0:

1;

X[minindex].chromsome[j]=m;

X[minindex].weight+=m*weight[j];//个体的总重量

X[minindex].fitness+=m*value[j];//个体的总价值

}

}

}

/************************************************************************/

voidGenerateInitialPopulation（void）//初始种群,保证每个值都在符合条件的解

{

inti=0,j=0;boolk;

for（i=0;i

for（i=0;i

{

intw=0,v=0;

for（j=0;j

{

k=（rand（）%10<5）?

0:

1;

X[i].chromsome[j]=k;

w+=k*weight[j];//个体的总重量

v+=k*value[j];//个体的总价值

}

if（w>KW）i--;//如果不是解，重新生成

else

{

X[i].fitness=v;

X[i].weight=w;

if（v==stop）

{

bestindividual=X[i];

return;

}//这种情况一般不会发生

}

}

}

/************************************************************************/

voidCalculateFitnessValue（）

{

inti=0,j=0;

for（i=0;i

{

intw=0,v=0;

for（j=0;j

{

w+=X[i].chromsome[j]*weight[j];//个体的总重量

v+=X[i].chromsome[j]*value[j];//个体的总价值

}

X[i].fitness=v;

X[i].weight=w;

if（v==stop）

{

bestindividual=X[i];

return;

}//符合条件情况下最优解这种情况一般不会发生

if（w>KW）X[i]=bestindividual;//如果不是解，找最好的一个解代之

}

}

/************************************************************************/

voidSelectionOperator（void）

{

inti,index;

doublep,sum=0.0;

doublecfitness[S];//选择、累积概率

individualnewX[S];

for（i=0;i

sum+=X[i].fitness;//适应度求和

for（i=0;i

cfitness[i]=X[i].fitness/sum;//选择概率

for（i=1;i

cfitness[i]=cfitness[i-1]+cfitness[i];//累积概率

for（i=0;i

{

p=（rand（）%1001）/1000.0;//产生一个[0,1]之间的随机数

index=0;

while（p>cfitness[index]）//轮盘赌进行选择

{

index++;

}

newX[i]=X[index];

}

for（i=0;i

X[i]=newX[i];//新的种群

}

/************************************************************************/

voidCrossoverOperator（void）//交叉操作

{

inti=0,j=0,k=0;individualtemp;

for（i=0;i

{

intp=0,q=0;

do

{

p=rand（）%S;//产生两个[0，S]的随机数

q=rand（）%S;

}while（p==q）;

intw=1+rand（）%N;//[1,N]表示交换的位数

doubler=（rand（）%1001）/1000.0;//[0,1]

if（r<=Pc）

{

for（j=0;j

{

temp.chromsome[j]=X[p].chromsome[j];//将要交换的位先放入临时空间

X[p].chromsome[j]=X[q].chromsome[j];

X[q].chromsome[j]=temp.chromsome[j];

}

}

if（p==best）

if（-1==comp（bestindividual,X[p]））//如果变异后适应度变小

X[p]=bestindividual;

if（q==best）

if（-1==comp（bestindividual,X[q]））//如果变异后适应度变小

X[q]=bestindividual;

}

}

/************************************************************************/

voidMutationOperator（void）

{

inti=0,j=0,k=0,q=0;

doublep=0;

for（i=0;i

{

for（j=0;j

{

p=（rand（）%1001）/1000.0;

if（p

{

if（X[i].chromsome[j]==1）X[i].chromsome[j]=0;

elseX[i].chromsome[j]=1;

}

}

if（i==best）

if（-1==comp（bestindividual,X[i]））//如果变异后适应度变小

X[i]=bestindividual;

}

}

/************************************************************************/

voidFindBestandWorstIndividual（void）

{

inti;

bestindividual=X[0];

for（i=1;i

{

if（X[i].fitness>bestindividual.fitness）

{

bestindividual=X[i];

best=i;

}

}

}

/*主函数*****************************************************************/

intmain（）

{

DWORDstart,stop;

start=GetTickCount（）;//程序开始时间

srand（（unsigned）time（0））;

t=0;

GenerateInitialPopulation（）;//初始群体包括产生个体和计算个体的初始值

while（t<=T）

{

FindBestandWorstIndividual（）;//保存当前最优解

SelectionOperator（）;//选择

CrossoverOperator（）;//交叉

MutationOperator（）;//变异

Checkalike（）;//检查相似度

CalculateFi