遺傳算法的0-1背包問題c語言99250

1、基于遺傳算法的0-1背包問題的求解摘要：一、前言組合優(yōu)化問題的求解方法研究已經(jīng)成為了當前眾多科學關注的焦點，這不僅在于其內(nèi)在的復雜性有著重要的理論價值，同時也在于它們能在現(xiàn)實生活中廣泛的應用。比如資源分配、投資決策、裝載設計、公交車調(diào)度等一系列的問題都可以歸結(jié)到組合優(yōu)化問題中來。但是，往往由于問題的計算量遠遠超出了計算機在有效時間內(nèi)的計算能力，使問題的求解變?yōu)楫惓５睦щy。尤其對于NP完全問題，如何求解其最優(yōu)解或是近似最優(yōu)解便成為科學的焦點之一。遺傳算法已經(jīng)成為組合優(yōu)化問題的近似最優(yōu)解的一把鑰匙。它是一種模擬生物進化過程的計算模型，作為一種新的全局優(yōu)化搜索算法，它以其簡單、魯棒性強、適應并行處理

2、以及應用范圍廣等特點，奠定了作為21世紀關鍵智能計算的地位。背包問題是一個典型的組合優(yōu)化問題，在計算理論中屬于NP-完全問題，其計算復雜度為O（2n）,傳統(tǒng)上采用動態(tài)規(guī)劃來求解。設wi是經(jīng)營活動i所需要的資源消耗，M是所能提供的資源總量，pi是人們經(jīng)營活動i得到的利潤或收益，則背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。二、問題描述背包問題（KnapsackProblem用一般提法是：已知n個物品的重量（weight:）及其價值（或收益profit）分別為Wi0和Pi0,背包的容量（contain）假設設為G0,如何選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所

3、裝物品的價值最大？該問題的模型可以表示為下述0/1整數(shù)規(guī)劃模型：cixii1目標函數(shù)：maxf（x1,x2,xn）n7Wi為piS.ti1Xi0,1（i1,2,n）式中Xi為0-1決策變量，Xi1時表示將物品i裝入背包中，Xi0時則表示不將其裝入背包中。三、求解背包問題的一般方法解決背包問題一般是采取動態(tài)規(guī)劃、遞歸回溯法和貪心方法。動態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。它的主要缺點是用數(shù)值方法求解時會隨著狀態(tài)變量的個數(shù)呈指數(shù)級的增長，往往對于求解背包問題的實際問題是不現(xiàn)實

4、的。使用遞歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單，而且它能完全遍歷搜索空間，肯定能找到問題的最優(yōu)解；但是由于此問題解的總組合數(shù)有2n個，因此，隨著物件數(shù)n的增大，其解的空間將以2n級增長，當n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實的。使用貪心方法求解時計算的復雜度降低了很多，但是往往難以得到最優(yōu)解，有時所得解與最優(yōu)解相差甚遠。因此，我們可以探索使用遺傳算法解決物件數(shù)較大的背包問題。四、遺傳算法簡介遺傳算法(GeneticAlgorithms,GA)是在1975年首次由美國密西根大學的DoJoHolland教授和他的同事們借鑒生物界達爾文的自然選擇法則和孟德爾的遺傳進化機制基礎之上

5、提出的。經(jīng)過近30年的研究、應用，遺傳算法已被廣泛地應用于函數(shù)優(yōu)化、機器人系統(tǒng)、神經(jīng)網(wǎng)絡學習過程、模式識別、圖象處理、工業(yè)優(yōu)化控制等領域。遺傳算法是將問題的每一個可能性解看作是群體中的一個個體(染色體),并將每一個染色體編碼成用的形式，再根據(jù)預定的目標函數(shù)對每個個體進行評價，給出一個適應值。算法將根據(jù)適應度值進行它的尋優(yōu)過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個遺傳算子來具體實現(xiàn)的。它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問題空間的盡可能多的點，從而使其具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強壯性可由Holland提出的模式定理(SchemaTherem

6、)和隱式并行性得以解釋。在遺傳算法中，定義長度較短、低階且適應值超過平均適應值的模式在群體中數(shù)目的期望值按指數(shù)遞增，這個結(jié)論稱為遺傳算法的基本定理。遺傳算法是通過定義長度短、確定位數(shù)少、適應度值高的模式的反復抽樣、組合來尋找最佳點，稱這些使遺傳算法有效工作的模式為積木塊，是遺傳算法構造答案的基本材料。但歸根到底，要使遺傳算法有效工作必須按照遺傳算法的模式定理（或積木塊假設）根據(jù)具體問題設計合理的編碼方案。在運行遺傳算法程序時，需要對一些參數(shù)作事先選擇，它們包括種群的大小、染色體長、交叉率、變異率、最大進化代數(shù)等，這些參數(shù)對GA的性能都有很重要的影響。在試驗中參數(shù)一般選取如下：種群大小N=201

7、00,交叉概率pc=0.40.9,變異概率pm=0.0010.1,最大進化代數(shù)maxgen=100500.遺傳算法是具有“生成+檢測”的迭代過程的搜索算法。它的基本處理流程如圖1所示。圖1、遺傳算法的基本流程遺傳算法的基本流程描述如下:(1)編碼：將解空間的解數(shù)據(jù)進行二進制編碼，表達為遺傳空間的基因型用(即染色體)結(jié)構數(shù)據(jù)，如將數(shù)據(jù)9編碼為“1001”；(2)初始化種群：定義整數(shù)pop_size作為染色體的個數(shù)，并且隨機產(chǎn)生pop_size個染色體作為初始種群；(3)評估種群中個體適應度：評價函數(shù)對種群中的每個染色體(chromosome求得其個體適應度fi(fitness)；(4)選擇：選擇

8、把當前群體中適應度較高的個體按某種規(guī)則或者模型遺傳到下一代種群中，這里所用的規(guī)則是：染色體在種群中被選擇的可能性與其個體的適應度的大小成正比；(5)交叉：定義參數(shù)Pc作為交叉操作的概率，由(4)選擇得到的兩個個體以概率pc交換各自的部分染色體，得到新的兩個個體；(6)變異：定義參數(shù)Pm作為變異操作的概率，由(5)得到每個個體中的每個基因值都以概率Pm進行變異；(7)演化：經(jīng)過選擇、交叉和變異操作，得到一個新的種群，對上述步驟經(jīng)過給定的循環(huán)次數(shù)(maxgen)的種群演化，遺傳算法終止。五、背包問題的遺傳算法求解描述基于背包問題的模型(*),我們設計了針對于背包問題的染色體編碼方法：將待求解的各量

9、X表示成長為n的二進制字符串xj,j=1,2,，n。xj0表示物體j不放入背包內(nèi)，xj1表示物體j放入背包內(nèi)。例如：111001100000111代表一個解，它表示將第1、2、3、6、7-n-2,n-1,n號物體放入背包中，其它的物體則不放入。根據(jù)遺傳算法的基本流程，我們確定了求解背包問題的遺傳算法：步驟1、初始化過程1.1 確定種群規(guī)模popsizes雜交概率Pc、變異概率Pm、染色體長度lchrom及最大進化代數(shù)maxgen；1.2 讀入背包問題的相關信息，如每個物體的重量weightj、每個物體的收益profitj和背包的容量contain,其中j0,1,(Ichrom1)；1.3 取x

10、ju(0,1)j0,1,(Ichrom1),其中u(0,1)表示0-1整數(shù)的均勻分布函數(shù)，即隨機地生成數(shù)0或1,生成的xj用即可看為一個染色體個體。若不滿足模型(*)的約束條件，則拒絕接受，由1.2重新生成一個新的染色體個體chrom；如果產(chǎn)生的染色體可行，則接受它作為種群的一名成員，經(jīng)過有限次的1.2抽樣后，得到popsize個可行的染色體chrom,形成新的種群。1.4置種群的代數(shù)gen=0；步驟2、計算種群中個體適應度以及統(tǒng)計種群適應度情況2.1按照下列公式計算種群中個體適應度：lchrom1weightweightj*chromj(1);j0lchrom1profitj*chromji

11、fweightcontainfitnesslchro：1(2)profitj*chromjalpha*(weightcontain)ifweightcontainj0公式(2)的下半部分即為適應度的懲罰函數(shù)，其中參數(shù)alpha1.0。2.2按公式(3)計算種群的總體適應度，popsize1sumfitnessfitnessi(3)i0并且按照排序的方法統(tǒng)計出種群中的最大、最小適應度的染色體個體，分別標記為maxpop、minpop；步驟3、選擇操作3.1 生成一個隨機數(shù)randNumber,要求0randNuber1;3.2 按照賭輪法選擇個體，賭輪法的算法描述如下：intselection(

12、)(i=0;個體的編號sum=0；/部分個體適應度的累加和/根據(jù)隨機數(shù)和群體的總適應度確定賭輪的位置wheel-pos=rand_Number*sufitness;whilesum<wheel-pos&&i<=popsizei=i+1;sum=sum+fitnessi;/fitness為第i個個體的適應度returni-1;/選擇了個體i-13.3重復兩次操作3.1、3.2,生成兩個個體作為交叉操作的父代；步驟四、交叉操作4.1 根據(jù)事先定義女？的交叉概率pc,為了確定是否進行交叉操作，則生成0,1的隨機數(shù)pp,若pppc,則進行4.2交叉操作，否則將兩個父代保留為

13、下一代的兩個個體；4.2 隨機生成0,lchrom1的整數(shù)作為交叉點，對兩個父代個體交叉生成新的兩個個體；4.3 重復pop_size/2次4.1、4.2便可生成pop_size個個體組成新的種群；步驟五、變異操作5.1 根據(jù)事先定義女?的變異概率pm,為了確定新種群上的每個個體上的每個基因是否進行變異操作，則生成0,1的隨機數(shù)pp,若pppm,則進行5.2變異操作，否則基因不變異；5.2 基因變異操作為原基因若為1,則新基因則變異為0,若原基因為0,則新基因變異為0;步驟6、演化6.1 按步驟2的方法計算新種群的個體適應度和總體適應度情況，尤其是找出新種群中最大適應度的個體和最小適應度的個體

14、；6.2 若舊種群的最大個體適應度新種群的最大個體適應度，把舊種群的最大適應度的個體代替新種群中的最小適應度的個體，否則進行6.3;6.3 種群的代數(shù)gen=genm+1,若genMaxgen,則結(jié)束種群的演化，否則轉(zhuǎn)到步驟2六、遺傳算法求解的實現(xiàn)/種群的規(guī)模/雜交概率/變異概率/染色體長度1、遺傳算法的主要參數(shù)#definepopsize80#definepc0.7#definepm0.1#defineIchrom50#definemaxgen5000/最大進化代數(shù)doublealpha;/計算適應度時使用的懲罰函數(shù)系數(shù)2、數(shù)據(jù)結(jié)構(1)背包信息:/背包問題中物體重量、收益、背包容量intw

15、eightlchrom,profitlchrom,contain;(2)種群個體結(jié)構體structpopulationunsignedintchromlchrom;染色體doublefitness;適應度unsignedintparent1,parent2,cross;/雙親、交叉點;(3)父代種群和新生代種群/父代種群、新生代種群structpopulationoldpoppopsize,newpoppopsize;/pop_size為種群大/、(4)適應度信息/種群的總適應度、最小、最大適應度doublesumfitness,minfitness,maxfitness;/一個種群中最大和最

16、小適應度的個體編號intminpop,maxpop;3、主要函數(shù)說明(1)、intread_infor()收益、背包容量）功能：從文件knapsack.txt中讀出背包信息（物體重量、參數(shù)：無；返回值：返回讀取文件信息是否正確;流程圖：見圖2。圖2、read_infor()流程圖(2)doublecal_fit(unsignedint*chr)功能：種群中個體適應度計算;參數(shù)：unsignedint*chr是染色體個體的指針，根據(jù)指針所指向的染色體計算個體的適應度；返回值：染色體個體適應度的大小;流程圖：見圖3。圖3、函數(shù)cal_fit的流程圖(3)、voidstatistics(struct

17、population*pop)功能：群體適應度的最大最小值以及其他信息；參數(shù)：structpopulation*pop是種群指針，根據(jù)指針所指向的種群信息統(tǒng)計群體適應度的信息；返回值：無；流程圖：見圖4。(4)、voidreport(structpopulation*pop,intgen)功能：報告種群的適應度信息，尤其是最大個體適應度、最大適應度個體的染色體信息；參數(shù)：structpopulation*pop是種群指針，根據(jù)指針所指向的種群報告群體適應度的信息，gen是表示此種群所在的演化代數(shù)返回值：無；流程圖：見圖5圖4、函數(shù)statistics的流程圖圖5、函數(shù)report的流程圖(5)

18、、voidinitpop()功能：生成初始種群;參數(shù)：無；返回值：無；流程圖：見圖6。圖6、函數(shù)initpop流程圖(6)、intexecise(doubleprobability)功能：概率選擇試驗，以概率probability做隨機試驗，判斷是否進行交叉或變異操作；參數(shù)：doubleprobability為交叉概率或變異概率返回值：試驗是否成功，0代表不試驗成功，將不做交叉或者變異操作，1代表試驗成功，即進行交叉或者變異操作；流程圖：見圖7圖7、函數(shù)execise的流程圖(7)、intselection(intpop)功能：在父代種群中選擇個體，規(guī)則為適應度越大的個體被選擇的概率越大;參數(shù)

19、：intpop為父代種群；返回值：父體中被選擇的個體i;流程圖：見圖8。圖8、函數(shù)selection的流程圖(8)、intcrossover(unsignedint*parent1,unsignedint*parent2,inti)功能：兩個父代個體在染色體的第i個位置進行交叉，生成兩個新個體；i為新種群的個體編號;參數(shù)：unsignedint*parent1,unsignedint*parent2分別為兩個父代染色體指針，指針指向父代個體的染色體，返回值：交叉是否成功;流程圖：見圖9。圖9、函數(shù)crossover的流程圖(9)、intmutation(unsignedintalleles)功

20、能：根據(jù)變異概率進行變異操作；參數(shù)：unsignedintalleles是染色體上的基因型，在這里就是0或1的取值;返回值：變異后的基因型；流程圖：見圖10。(10)、voidgeneration()功能：綜合選擇、交叉、變異等操作，生成新的種群;參數(shù)：無；返回值：無；流程圖：見圖11。圖11、函數(shù)generation的流程圖(11)、voidmain()功能：遺傳算法的主函數(shù)；參數(shù)：無；返回值：無；流程圖：見圖11。調(diào)用read_infor,讀入背面言息70,66,50,55,25,32,22,60,30,32,28,30,22,50,30,65,20,25,30,10,10,4,4,2,1

21、180,165,162,160,158,118,115,110,105,101,90,88,82,80,77,66,65,63,60,58,10,8,5,3,1七、成果說明1、程序開發(fā)環(huán)境開發(fā)環(huán)境：VisualC+6.0（把Fortran程序改為VC）操作系統(tǒng)：Windows2003Professional2、程序性能對比運行時間與加速比（如表1所示）進程數(shù)p（個）124運行時間t（秒）129s78s38s加速比s1.653.38表1、運行時間與加速比3、程序運行結(jié)果:實例數(shù)據(jù)：假設物體的重量Weight、物體的收益Profit和背包的容量Contain分別為:Weight=80,82,85,

22、70,72,50,55,40,48,50,40,38,35,32,25,45,30,60,50,20,20,25,15,10,10,Profit=220,208,198,192,180,155,130,125,122,120,100,100,98,96,95,75,73,72,70,69,56,50,30,20,15,Contain=1000,如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內(nèi)所裝物品的總價值最大？傳統(tǒng)的算法（動態(tài)規(guī)劃、遞歸回溯法和貪心算法所得結(jié)果：總價值為3077，總重量為999。2001年張鈴，張錢教授在計算機學報上發(fā)表的佳點集遺傳算法所得結(jié)果總價值為3103,總重量

23、為1000。我們算法所得結(jié)果：總價值為3103,總重量為1000c我們所求得最優(yōu)解的個體分配情況為：11010101111011011011011111110100001010011000001000算法最大迭代次數(shù)總價值為總重量為傳統(tǒng)的算法4003077999佳點集算法7031031000遺傳算法7531031000八、收獲、體會和課題展望在本課題中，我們研究了如何用遺傳算法求解組合優(yōu)化問題中的背包問題。我們可以看出在求解背包問題上顯示了超出想象、良好的搜索能力，它具有收斂快、搜索速度快的特點，在試驗中取得了比動態(tài)規(guī)劃、遞歸回溯法和貪心法等更好的求解效果。然而在一般情況下，使用基本遺傳算法解

24、決背包問題時，得到問題的近似解也不能滿足逼近最優(yōu)解的要求。如何改進基本遺傳算法使它所求得的解逼近最優(yōu)解，成為我們當前亟待解決的問題，也是我們將來的課題中所要研究的重要問題。/knapsack.cpp:Definestheentrypointfortheconsoleapplication./#include"stda僅.h”#include<AfXWin.h>#include<stdlib.h>#include<math.h>#include<time.h>#include<conio.h>#include<stdio

25、.h>/重要常量參數(shù)# definepopsize200/種群的規(guī)模# definepc0.618雜交概率# definepm0.03變異概率# definelchrom50染色體長度# definemaxgen1000/最大進化代數(shù)structpopulation(unsignedintchromlchrom;染色體doubleweight;背包重量doublefitness;/適應度unsignedintparent1,parent2,cross;/雙親、交叉點;新生代種群、父代種群structpopulationoldpoppopsize,newpoppopsize;背包問題中物體

26、重量、收益、背包容量intweightlchrom,profitlchrom,contain;/種群的總適應度、最小、最大、平均適應度doublesumfitness,minfitness,maxfitness,avgfitness;計算適應度時使用的懲罰函數(shù)系數(shù)doublealpha;/一個種群中最大和最小適應度的個體intminpop,maxpop;/*讀入背包信息，并且計算懲罰函數(shù)系數(shù)*/voidread_infor()(FILE*fp;intj;/獲取背包問題信息文件if(fp=fopen("knapsack.txt","r")尸NULL)(/讀

27、取文件失敗AfxMessageBox("Thefileisnotfound",MB_OK,NULL);return;讀入物體收益信息for(j=0;j<lchrom;j+)(fscanf(fp,"%d",&profitj);讀入物體重量信息for(j=0;j<lchrom;j+)fscanf(fp,"%d",&weightj);)讀入背包容量fscanf(fp,"%d",&contain);fclose(fp);)根據(jù)計算的個體重量，判斷此個體是否該留在群體中doublecal_

28、weight(unsignedint*chr)(intj;doublepop_weight;/背包重量pop_weight=0;for(j=0;j<lchrom;j+)(pop_weight=pop_weight+(*chr)*weightj;chr+;)returnpop_weight;)/*種群中個體適應度計算*/doublecal_fit(unsignedint*chr)(intj;doublepop_profit;/適應度pop_profit=0;/pop_weight=0;for(j=0;j<lchrom;j+)(pop_profit=pop_profit+(*chr)*

29、profitj;/pop_weight=pop_weight+(*chr)*weightj;chr+;)returnpop_profit;/*群體適應度的最大最小值以及其他信息*/voidstatistics(structpopulation*pop)(inti;doubletmp_fit;sumfitness=pop0.fitness;minfitness=pop0.fitness;minpop=0;maxfitness=pop0.fitness;maxpop=0;for(i=1;i<popsize;i+)(/計算種群的總適應度sumfitness=sumfitness+popi.fi

30、tness;tmp_fit=popi.fitness;選擇種群中最大適應度的個體if(tmp_fit>maxfitness)&&(int)(tmp_fit*10)%10=0)(maxfitness=popi.fitness;maxpop=i;選擇種群中最小適應度的個體if(tmp_fit<minfitness)(minfitness=popi.fitness;minpop=i;計算平均適應度avgfitness=sumfitness/(float)popsize;/printf("nthemaxpop=%d;",maxpop);/printf(&

31、quot;ntheminpop=%d;",minpop);/printf("nthesumfitness=%fn",sumfitness);報告種群信息voidreport(structpopulation*pop,intgen)(intj;intpop_weight=0;printf("thegenerationis%d.n",gen);/輸出種群的代數(shù)輸出種群中最大適應度個體的染色體信息printf("Thepopulation'schromis:n");for(j=0;j<lchrom;j+)if(j%5

32、=0)printf("");printf("%1d",popmaxpop.chromj);輸出群體中最大適應度printf("nThepopulation'smaxfitnessis%d.",(int)popmaxpop.fitness);printf("nTheknapsackweightis%d.nn",(int)popmaxpop.weight);/*生成初始種群*/voidinitpop()inti,j,ispop;doubletmpWeight;/變量用于判斷是否為滿足條件的個體ispop=fal

33、se;/生成popsize個種群個體for(i=0;i<popsize;i+)while(!ispop)for(j=0;j<lchrom;j+)oldpopi.chromj=rand()%2;隨機生成個體的染色體oldpopi.parent1=0;/雙親oldpopi.parent2=0;oldpopi.cross=0;交叉點選擇重量小于背包容量的個體，即滿足條件tmpWeight=cal_weight(oldpopi.chrom);if(tmpWeight<=contain)oldpopi.fitness=cal_fit(oldpopi.chrom);oldpopi.wei

34、ght=tmpWeight;oldpopi.parent1=0;oldpopi.parent2=0;oldpopi.cross=0;ispop=true;)此個體可以加入到種群中ispop=false;)/*遺傳操作*/概率選擇試驗intexecise(doubleprobability)(doublepp;如果生成隨機數(shù)大于相應的概率則返回真，否則試驗不成功pp=(double)(rand()%20001/20000.0);if(pp<=probability)return1;return0;)/選擇進行交叉操作的個體intselection(intpop)(doublewheel_p

35、os,rand_Number,partsum;intparent;賭輪法選擇rand_Number=(rand()%2001)/2000.0;wheel_pos=rand_Number*sumfitness;賭輪大小partsum=0;parent=0;dopartsum=partsum+oldpopparent.fitness;parent=parent+1;while(partsum<wheel_pos&&parent<popsize);returnparent-1;/*交叉操作*/intcrossover(unsignedint*parent1,unsigne

36、dint*parent2,inti)intj,cross_pos;if(execise(pc)(生成交叉位置0,1,.(lchrom-2)cross_pos=rand()%(lchrom-1);elsecross_pos=lchrom-1;for(j=0;j<=cross_pos;j+)(保留復制；/包括在概率選擇不成功時，父體完全保留newpopi.chromj=parent1j;for(j=cross_pos+1;j<=(lchrom-1);j+)(/從交叉點開始交叉newpopi.chromj=parent2j;記錄交叉位置newpopi.cross=cross_pos;re

37、turn1;/*變異操作*/intmutation(unsignedintalleles)(if(execise(pm)(if(alleles)alleles=0;elsealleles=1;返回變異值，或者返回原值returnalleles;/*群體更新*/voidgeneration()(unsignedinti,j,mate1,mate2;doubletmpWeight;intispop;/記錄是否是符合條件的個體i=0;while(i<popsize)(ispop=false;while(!ispop)(/選擇mate1=selection(i);mate2=selection(i+1);/交叉crosso