01背包遺傳算法代碼說明

1、01背包遺傳算法一、算法說明:遺傳算法是具有“生成+檢測”的迭代的搜索算法。它的基本處理流程如圖 所示。編碼1F初始化匕種群評估種群中個(gè)體適應(yīng)度演化1r選擇1!交叉1r變異使用基本遺傳算法解決0- 1背包問題的程序步驟如下1:設(shè)置種群的規(guī)模、交叉概率、突變概率、背包最大載重等常數(shù)2:設(shè)置物品的重量和價(jià)值3:調(diào)用初始化種群模塊3- 1:按照一定的種群規(guī)模和染色體長度以基因?yàn)閱挝挥秒S機(jī)產(chǎn)生的0- 1對個(gè)體賦值2:調(diào)用計(jì)算適應(yīng)度函數(shù)4:以最大進(jìn)化代數(shù)為循環(huán)終止條件開始進(jìn)行循環(huán)1:調(diào)用產(chǎn)生新一代個(gè)體的函數(shù)4- 1- 1:調(diào)用選擇函數(shù)4- 1- 2:調(diào)用交叉函數(shù)4- 1- 3:調(diào)用變異函數(shù)4- 1- 4

2、:調(diào)用計(jì)算適應(yīng)度函數(shù)5:調(diào)用計(jì)算新一代種群統(tǒng)計(jì)數(shù)據(jù)函數(shù)6:調(diào)用輸出新一代統(tǒng)計(jì)數(shù)據(jù)函數(shù)7:返回到第四步，直至循環(huán)結(jié)束二、結(jié)果分析藍(lán)色字表示 輸出結(jié)果 運(yùn)行時(shí)間表示 算法復(fù)雜度1）數(shù)據(jù)集一: 物體總個(gè)數(shù)為 30時(shí)物品價(jià)值： 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最優(yōu)值 2984.000000對應(yīng)重量 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運(yùn)行時(shí)間 : 16 ms2）數(shù)據(jù)集二: 物體總個(gè)數(shù)為 50時(shí)物品價(jià)值： 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最優(yōu)值 3010.000000對應(yīng)重量 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運(yùn)行時(shí)間 : 31 ms3）數(shù)

5、據(jù)集三: 物體總個(gè)數(shù)為 60時(shí) 物品價(jià)值： 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最優(yōu)值 9738.000000對應(yīng)重量 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 運(yùn)行時(shí)間 : 19297 ms代碼：#include #include#include #include #include/* 數(shù) 據(jù) 集*#define S5/ 種群的規(guī)模#definePc0.8/ 交叉概率#definePm0.05/ 突變概率#defineKW1000/ 背包最大載重 1000#defineN30/ 物體總數(shù)#defineT800/ 最大換代數(shù)#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函數(shù)中初始化為所有價(jià)值之和intt=0;/ 目前的代數(shù)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;/* 數(shù) 據(jù) 集*#define S5/ 種群的規(guī)模#definePc0.8/ 交叉概率#definePm0.05/ 突變概率#defineKW1000/ 背包最大載重 1000#defineN50/ 物體總數(shù)#defineT800/ 最大換代數(shù)#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函數(shù)中初始化為所有價(jià)值之和intt=0;/ 目前的代數(shù)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;/* 數(shù) 據(jù) 集*#define S5/ 種群的規(guī)模#definePc0.8/ 交叉概率#definePm0.05/

11、 突變概率#defineKW1000/ 背包最大載重 1000#defineN60/ 物體總數(shù)#defineT800/ 最大換代數(shù)#defineALIKE 0.05/ 判定相似度intstop=0;/ 初始化函數(shù)中初始化為所有價(jià)值之和intt=0;/ 目前的代數(shù)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;/ 個(gè)體結(jié)構(gòu)體/ 染色體編碼/ 適應(yīng)度 / 即本問題中的個(gè)體所得價(jià)值 / 總重量*/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);/ 比較函數(shù)/ 檢查相似度函數(shù)/ 初始種群/ 適應(yīng)度/ 選擇/ 交叉/ 變異/ 尋找最優(yōu)解/ 隨機(jī)生成individual XS,YS,bestindividual;*/ int comp(individual bestindividual,individual temp)/ 比較函數(shù)int fit=0,w=0;/ 第一種不變 : 操作后不滿足重量函數(shù)，第二種 :

16、操作后適應(yīng) 度小于操作前for(int i=0;iKW)return -1;如果小于原來值或者不滿return (bestindividual.fitnessfit?-1:1);/ 足重量函數(shù)，則返回 -1/*/void Checkalike(void)int i=0,j=0;for( i=0;iS;i+)/相似度校驗(yàn)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;/ 個(gè)體的總重量 Xminindex.fitness+=m*valuej; / 個(gè)體的總價(jià)值 /*/void GenerateInitialPopulation(void)/ 初始種群 , 保證每個(gè)值都在符合條件 的解int i=0,j=0; bool k; for(i=0;iN;i+)stop+=valuei;/ 設(shè)置理論最優(yōu)值 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;/ 這種情況一般不會(huì)發(fā)生 /*/void CalculateFitnessValue()int i=0,j=0;for (i=0; iS; i+)int w=0,v=0;for (j=0; jKW) Xi=bestindividual;/ 如果不是解，找最好的一個(gè)解代之 /*/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;/ 適應(yīng)度求和for (i=0;iS; i+) cfitnessi=Xi.fitness/sum; / 選擇概率for (i=1;iS; i+) cfitnessi=cfitnessi-1+cfitnessi;/ 累積概率for (i=0;icfitnessindex)/ 輪盤賭進(jìn)行選擇 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;產(chǎn)生兩個(gè)0 , S的隨機(jī)數(shù)q=rand()%S;while(p=q);int w=1+rand()%N;/1,N 表示交換的位數(shù)double r=(rand()%1001)/1000.0;/0,1if(r=Pc)for(j=0;jw;j+) temp.chromsomej=Xp.chromsomej;/ 將要交換的位先放 入臨時(shí)空間Xp.chromsomej=Xq.c

21、hromsomej; Xq.chromsomej=temp.chromsomej;if(p=best)if(-1=comp(bestindividual,Xp)/如果變異后適應(yīng)度變小Xp=bestindividual;if(q=best)if(-1=comp(bestindividual,Xq)/如果變異后適應(yīng)度變小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)/ 如果變異后適應(yīng)度變小 Xi=bestindividual; /* / void FindBestandWorstIndividual(void)int i;bestindividual=X0;for (i=1;ibestindividual.fitness)bestindividual=Xi;best=i;/*int main()程序開始時(shí)間DWORD start, stop; start = GetTickCount();/srand(unsigned)time(0);t=0;GenerateInit