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

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

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

3、大？該問題的模型可以表示為下述0/1整數(shù)規(guī)劃模型：目標(biāo)函數(shù)： （*）式中為0-1決策變量，時(shí)表示將物品裝入背包中，時(shí)則表示不將其裝入背包中。三、求解背包問題的一般方法解決背包問題一般是采取動(dòng)態(tài)規(guī)劃、遞歸回溯法和貪心方法。動(dòng)態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對(duì)于背包問題可以對(duì)子過程用枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。它的主要缺點(diǎn)是用數(shù)值方法求解時(shí)會(huì)隨著狀態(tài)變量的個(gè)數(shù)呈指數(shù)級(jí)的增長，往往對(duì)于求解背包問題的實(shí)際問題是不現(xiàn)實(shí)的。使用遞歸回溯法解決背包問題的優(yōu)點(diǎn)在于它算法思想簡單， 而且它能完全遍歷搜索空間，肯定能找到問題的最優(yōu)解；但是由

4、于此問題解的總組合數(shù)有個(gè)，因此，隨著物件數(shù) n 的增大，其解的空間將以級(jí)增長，當(dāng) n 大到一定程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。使用貪心方法求解時(shí)計(jì)算的復(fù)雜度降低了很多，但是往往難以得到最優(yōu)解，有時(shí)所得解與最優(yōu)解相差甚遠(yuǎn)。因此， 我們可以探索使用遺傳算法解決物件數(shù)較大的背包問題。四、遺傳算法簡介遺傳算法( Genetic Algorithms，GA) 是在1975 年首次由美國密西根大學(xué)的D。J。Holland 教授和他的同事們借鑒生物界達(dá)爾文的自然選擇法則和孟德爾的遺傳進(jìn)化機(jī)制基礎(chǔ)之上提出的。經(jīng)過近30年的研究、應(yīng)用，遺傳算法已被廣泛地應(yīng)用于函數(shù)優(yōu)化、機(jī)器人系統(tǒng)、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)過程、模

5、式識(shí)別、圖象處理、工業(yè)優(yōu)化控制等領(lǐng)域。遺傳算法是將問題的每一個(gè)可能性解看作是群體中的一個(gè)個(gè)體(染色體)，并將每一個(gè)染色體編碼成串的形式，再根據(jù)預(yù)定的目標(biāo)函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，給出一個(gè)適應(yīng)值。算法將根據(jù)適應(yīng)度值進(jìn)行它的尋優(yōu)過程，遺傳算法的尋優(yōu)過程是通過選擇、雜交和變異三個(gè)遺傳算子來具體實(shí)現(xiàn)的。它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問題空間的盡可能多的點(diǎn)，從而使其具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強(qiáng)壯性可由Holland提出的模式定理( Schema Therem) 和隱式并行性得以解釋。在遺傳算法中，定義長度較短、低階且適應(yīng)值超過平均適應(yīng)值的模式在群體中數(shù)

6、目的期望值按指數(shù)遞增，這個(gè)結(jié)論稱為遺傳算法的基本定理。遺傳算法是通過定義長度短、確定位數(shù)少、適應(yīng)度值高的模式的反復(fù)抽樣、組合來尋找最佳點(diǎn)，稱這些使遺傳算法有效工作的模式為積木塊，是遺傳算法構(gòu)造答案的基本材料。但歸根到底，要使遺傳算法有效工作必須按照遺傳算法的模式定理(或積木塊假設(shè)) 根據(jù)具體問題設(shè)計(jì)合理的編碼方案。在運(yùn)行遺傳算法程序時(shí)，需要對(duì)一些參數(shù)作事先選擇，它們包括種群的大小、染色體長、交叉率、變異率、最大進(jìn)化代數(shù)等，這些參數(shù)對(duì)GA 的性能都有很重要的影響。在試驗(yàn)中參數(shù)一般選取如下：種群大小N= 20100 ，交叉概率 = 0.4 0.9 ，變異概率 = 0.0010.1 ，最大進(jìn)化代數(shù)m

7、axgen = 100500。遺傳算法是具有“生成+檢測(cè)”的迭代過程的搜索算法。它的基本處理流程如圖1所示。初始化種群評(píng)估種群中個(gè)體適應(yīng)度選 擇編 碼交 叉變 異演 化圖1、遺傳算法的基本流程遺傳算法的基本流程描述如下：（1）編碼：將解空間的解數(shù)據(jù)進(jìn)行二進(jìn)制編碼，表達(dá)為遺傳空間的基因型串（即染色體）結(jié)構(gòu)數(shù)據(jù)，如將數(shù)據(jù)9編碼為“1001”；（2）初始化種群：定義整數(shù)pop_size作為染色體的個(gè)數(shù)，并且隨機(jī)產(chǎn)生pop_size個(gè)染色體作為初始種群；（3）評(píng)估種群中個(gè)體適應(yīng)度：評(píng)價(jià)函數(shù)對(duì)種群中的每個(gè)染色體（chromosome）求得其個(gè)體適應(yīng)度；（4）選擇：選擇把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)

8、則或者模型遺傳到下一代種群中，這里所用的規(guī)則是：染色體在種群中被選擇的可能性與其個(gè)體的適應(yīng)度的大小成正比；（5）交叉：定義參數(shù)作為交叉操作的概率，由（4）選擇得到的兩個(gè)個(gè)體以概率交換各自的部分染色體，得到新的兩個(gè)個(gè)體；（6）變異：定義參數(shù)作為變異操作的概率，由（5）得到每個(gè)個(gè)體中的每個(gè)基因值都以概率進(jìn)行變異；（7）演化：經(jīng)過選擇、交叉和變異操作，得到一個(gè)新的種群，對(duì)上述步驟經(jīng)過給定的循環(huán)次數(shù)（maxgen）的種群演化，遺傳算法終止。五、背包問題的遺傳算法求解描述基于背包問題的模型（*），我們?cè)O(shè)計(jì)了針對(duì)于背包問題的染色體編碼方法：將待求解的各量表示成長為的二進(jìn)制字符串，j=1，2， ，n。表示物

9、體j不放入背包內(nèi)，表示物體j放入背包內(nèi)。例如：111001100100111代表一個(gè)解，它表示將第1、2、3、6、7n-2,n-1,n號(hào)物體放入背包中，其它的物體則不放入。根據(jù)遺傳算法的基本流程，我們確定了求解背包問題的遺傳算法：步驟1、初始化過程1.1 確定種群規(guī)模popsize、雜交概率、變異概率 、染色體長度lchrom 及最大進(jìn)化代數(shù)maxgen；1.2 讀入背包問題的相關(guān)信息，如每個(gè)物體的重量weightj、每個(gè)物體的收益profitj和背包的容量contain，其中；1.3 取，其中表示0-1整數(shù)的均勻分布函數(shù)，即隨機(jī)地生成數(shù)0或1，生成的串即可看為一個(gè)染色體個(gè)體。若不滿足模型（*

10、）的約束條件，則拒絕接受，由1.2重新生成一個(gè)新的染色體個(gè)體chrom；如果產(chǎn)生的染色體可行，則接受它作為種群的一名成員，經(jīng)過有限次的1.2抽樣后，得到popsize個(gè)可行的染色體chrom，形成新的種群。 1.4 置種群的代數(shù)gen=0； 步驟2、計(jì)算種群中個(gè)體適應(yīng)度以及統(tǒng)計(jì)種群適應(yīng)度情況 2.1 按照下列公式計(jì)算種群中個(gè)體適應(yīng)度： ；公式（2）的下半部分即為適應(yīng)度的懲罰函數(shù)，其中參數(shù)。2.2 按公式（3）計(jì)算種群的總體適應(yīng)度， 并且按照排序的方法統(tǒng)計(jì)出種群中的最大、最小適應(yīng)度的染色體個(gè)體，分別標(biāo)記為maxpop、minpop；步驟3、選擇操作3.1 生成一個(gè)隨機(jī)數(shù)rand_Number，要

11、求；3.2 按照賭輪法選擇個(gè)體，賭輪法的算法描述如下：int selection( ) i=0; /個(gè)體的編號(hào) sum=0； /部分個(gè)體適應(yīng)度的累加和 /根據(jù)隨機(jī)數(shù)和群體的總適應(yīng)度確定賭輪的位置 wheel-pos=rand_Number*sufitness; while sumwheel-pos & i=popsize i=i+1; sum=sum+fitnessi; /fitness為第i個(gè)個(gè)體的適應(yīng)度 return i-1; /選擇了個(gè)體i-1 3.3 重復(fù)兩次操作3.1、3.2，生成兩個(gè)個(gè)體作為交叉操作的父代；步驟四、交叉操作4.1 根據(jù)事先定義好的交叉概率，為了確定是否進(jìn)行交叉操作，

12、則生成0，1的隨機(jī)數(shù)pp，若，則進(jìn)行4.2交叉操作，否則將兩個(gè)父代保留為下一代的兩個(gè)個(gè)體；4.2 隨機(jī)生成的整數(shù)作為交叉點(diǎn)，對(duì)兩個(gè)父代個(gè)體交叉生成新的兩個(gè)個(gè)體；4.3 重復(fù)pop_size/2次4.1、4.2便可生成pop_size個(gè)個(gè)體組成新的種群；步驟五、 變異操作5.1 根據(jù)事先定義好的變異概率，為了確定新種群上的每個(gè)個(gè)體上的每個(gè)基因是否進(jìn)行變異操作，則生成0，1的隨機(jī)數(shù)pp，若，則進(jìn)行5.2變異操作，否則基因不變異；5.2 基因變異操作為原基因若為1，則新基因則變異為0，若原基因?yàn)?，則新基因變異為0；步驟6、 演化6.1 按步驟2的方法計(jì)算新種群的個(gè)體適應(yīng)度和總體適應(yīng)度情況，尤其是找

13、出新種群中最大適應(yīng)度的個(gè)體和最小適應(yīng)度的個(gè)體；6.2 若舊種群的最大個(gè)體適應(yīng)度新種群的最大個(gè)體適應(yīng)度，把舊種群的最大適應(yīng)度的個(gè)體代替新種群中的最小適應(yīng)度的個(gè)體，否則進(jìn)行6.3；6.3 種群的代數(shù)gen=genm+1，若genMaxgen，則結(jié)束種群的演化，否則轉(zhuǎn)到步驟2。六、遺傳算法求解的實(shí)現(xiàn)1、遺傳算法的主要參數(shù)#define popsize 80 /種群的規(guī)模#define pc 0.7 /雜交概率#define pm 0.1 /變異概率#define lchrom 50 /染色體長度#define maxgen 5000 /最大進(jìn)化代數(shù)double alpha; /計(jì)算適應(yīng)度時(shí)使用的 懲

14、罰函數(shù)系數(shù)2、數(shù)據(jù)結(jié)構(gòu)（1）背包信息： /背包問題中物體重量、收益、背包容量int weightlchrom,profitlchrom,contain;（2）種群個(gè)體結(jié)構(gòu)體 struct population unsigned int chromlchrom; /染色體 double fitness; /適應(yīng)度 unsigned int parent1,parent2,cross; /雙親、交叉點(diǎn);（3）父代種群和新生代種群/父代種群、新生代種群struct population oldpoppopsize,newpoppopsize; /pop_size為種群大?。?）適應(yīng)度信息/種群的總適

15、應(yīng)度、最小、最大適應(yīng)度 double sumfitness,minfitness,maxfitness;/一個(gè)種群中最大和最小適應(yīng)度的個(gè)體編號(hào)int minpop,maxpop;3、主要函數(shù)說明（1）、int read_infor( ) 功能：從文件knapsack.txt中讀出背包信息（物體重量、收益、背包容量）；參數(shù)：無；返回值：返回讀取文件信息是否正確；流程圖：見圖2。獲取文件指針成功返回是否打開文件讀出物體重量信息讀出物體收益信息讀出背包容量信息圖2、read_infor( )流程圖（2）double cal_fit(unsigned int *chr)功能：種群中個(gè)體適應(yīng)度計(jì)算；參數(shù)

16、：unsigned int *chr是染色體個(gè)體的指針，根據(jù)指針?biāo)赶虻娜旧w計(jì)算個(gè)體的適應(yīng)度；返回值：染色體個(gè)體適應(yīng)度的大?。涣鞒虉D：見圖3。適應(yīng)度和總重量置0累加計(jì)算個(gè)體適應(yīng)度和背包的總重量總重量背包容量使用懲罰函數(shù)對(duì)個(gè)體適應(yīng)度進(jìn)行處理是返回個(gè)體適應(yīng)度圖3、函數(shù)cal_fit的流程圖（3）、void statistics(struct population *pop)功能：群體適應(yīng)度的最大最小值以及其他信息；參數(shù)：struct population *pop是種群指針，根據(jù)指針?biāo)赶虻姆N群信息統(tǒng)計(jì)群體適應(yīng)度的信息；返回值：無；流程圖：見圖4。（4）、void report(struct p

17、opulation *pop,int gen)功能：報(bào)告種群的適應(yīng)度信息，尤其是最大個(gè)體適應(yīng)度、最大適應(yīng)度個(gè)體的染色體信息；參數(shù)：struct population *pop是種群指針，根據(jù)指針?biāo)赶虻姆N群報(bào)告群體適應(yīng)度的信息，gen是表示此種群所在的演化代數(shù)返回值：無；流程圖：見圖5。適應(yīng)度和總重量置0累加計(jì)算個(gè)體適應(yīng)度和背包的總重量總重量背包容量使用懲罰函數(shù)對(duì)個(gè)體適應(yīng)度進(jìn)行處理是返回個(gè)體適應(yīng)度最大最小總適應(yīng)度都置為首個(gè)體的適應(yīng)度計(jì)數(shù)器i=1置最大適應(yīng)度的編號(hào)為i總適應(yīng)度=總適應(yīng)度+個(gè)體i的適應(yīng)度ilchrom-1是I的適應(yīng)度最大適應(yīng)度置最小適應(yīng)度的編號(hào)為iI的適應(yīng)度最小適應(yīng)度i=i+1返回

18、圖4、函數(shù)statistics的流程圖輸出種群的代數(shù)gen輸出最大適應(yīng)度個(gè)體的染色體信息chrom輸出最大個(gè)體適應(yīng)度maxfitness圖5、函數(shù)report的流程圖（5）、void initpop( )功能：生成初始種群；參數(shù)：無；返回值：無；流程圖：見圖6。個(gè)體計(jì)數(shù)器i=0隨機(jī)生成個(gè)體i染色體計(jì)算生成個(gè)體的適應(yīng)度若背包不超重接受個(gè)體，i=i+1ipop_size?是是否否返回圖6、函數(shù)initpop流程圖（6）、int execise(double probability)功能：概率選擇試驗(yàn)，以概率probability做隨機(jī)試驗(yàn)，判斷是否進(jìn)行交叉或變異操作；參數(shù)：double proba

19、bility為交叉概率或變異概率返回值：試驗(yàn)是否成功，0代表不試驗(yàn)成功，將不做交叉或者變異操作，1代表試驗(yàn)成功，即進(jìn)行交叉或者變異操作；流程圖：見圖7。生成0，1之間的小數(shù)pp若ppprobability返回實(shí)驗(yàn)成功1返回實(shí)驗(yàn)不成功0是否圖7、函數(shù)execise的流程圖（7）、int selection(int pop)功能：在父代種群中選擇個(gè)體，規(guī)則為適應(yīng)度越大的個(gè)體被選擇的概率越大；參數(shù)：int pop為父代種群；返回值：父體中被選擇的個(gè)體i； 流程圖：見圖8。個(gè)體編號(hào)i=0，部分適應(yīng)度之和partsum=0產(chǎn)生隨機(jī)數(shù)rand_Number計(jì)算賭輪所在位置wheel_pospartsumw

20、heel-pos & i=popsize?Partsum=partsum+個(gè)體i的適應(yīng)度個(gè)體計(jì)數(shù)器i=i+1返回被選擇的個(gè)體i-1圖8、函數(shù)selection的流程圖（8）、int crossover(unsigned int *parent1,unsigned int *parent2,int i)功能：兩個(gè)父代個(gè)體在染色體的第i個(gè)位置進(jìn)行交叉，生成兩個(gè)新個(gè)體；參數(shù)：unsigned int *parent1,unsigned int *parent2分別為兩個(gè)父代染色體指針，指針指向父代個(gè)體的染色體，i為新種群的個(gè)體編號(hào)；返回值：交叉是否成功； 流程圖：見圖9。否是隨機(jī)生成交叉位置cros

21、s_pos兩個(gè)父代個(gè)體按照交叉位置進(jìn)行交叉，生成新的兩個(gè)個(gè)體概率選擇試驗(yàn)成功保留兩個(gè)父體成為新種群中的個(gè)體圖9、函數(shù)crossover的流程圖（9）、int mutation(unsigned int alleles)功能：根據(jù)變異概率進(jìn)行變異操作；參數(shù)：unsigned int alleles是染色體上的基因型，在這里就是0或1的取值；返回值：變異后的基因型； 流程圖：見圖10。否是進(jìn)行變異返回變異或者原值概率選擇試驗(yàn)成功圖10、函數(shù)mutation的流程圖（10）、void generation()功能：綜合選擇、交叉、變異等操作，生成新的種群；參數(shù)：無；返回值：無； 流程圖：見圖11。是

22、置個(gè)體編號(hào)i=0ipop_size?調(diào)用selection生成兩個(gè)父體調(diào)用crossover，交叉生成兩個(gè)新個(gè)體對(duì)每個(gè)個(gè)體的基因調(diào)用mutation進(jìn)行變異置個(gè)體編號(hào)i=i+2生成新的種群完畢圖11、函數(shù)generation的流程圖（11）、void main( )功能：遺傳算法的主函數(shù)；參數(shù)：無；返回值：無； 流程圖：見圖11。是是調(diào)用 read_infor，讀入背包信息調(diào)用initpop( )生成初始種群置演化代數(shù)gen=0調(diào)用statistics ( )統(tǒng)計(jì)種群的適應(yīng)度GenMaxgen?調(diào)用generation()生成新種群調(diào)用statistics ( )統(tǒng)計(jì)種群的適應(yīng)度新種群的最大適

23、應(yīng)度舊種群的復(fù)制舊種群的最大適應(yīng)度個(gè)體到新種群中最小個(gè)體置演化代數(shù)gen=gen+1調(diào)用report( )，輸出結(jié)果信息圖12、主函數(shù)main的流程圖七、成果說明1、程序開發(fā)環(huán)境 開發(fā)環(huán)境：Visual C+6.0 (把Fortran程序改為VC) 操作系統(tǒng)：Windows 2003 Professional2、程序性能對(duì)比 運(yùn)行時(shí)間與加速比（如表1所示）進(jìn)程數(shù)p（個(gè)）124運(yùn)行時(shí)間t（秒）129s78s38s加速比s1.653.38表1、運(yùn)行時(shí)間與加速比3、程序運(yùn)行結(jié)果： 實(shí)例數(shù)據(jù)：假設(shè)物體的重量Weight、物體的收益Profit和背包的容量Contain 分別為：Weight= 80，8

24、2，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，50，30 ，45，30，60，50，20 ， 65，20，25，30，10 ，20，25，15，10，10 ， 10，4， 4， 2， 1 Profit= 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，

25、 70， 69， 66， 65， 63， 60， 58，56， 50， 30， 20， 15， 10， 8， 5， 3， 1Contain=1000，如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內(nèi)所裝物品的總價(jià)值最大?傳統(tǒng)的算法（動(dòng)態(tài)規(guī)劃、遞歸回溯法和貪心算法所得結(jié)果： 總價(jià)值為3077 , 總重量為999。2001年張鈴，張鈸教授在計(jì)算機(jī)學(xué)報(bào)上發(fā)表的佳點(diǎn)集遺傳算法所得結(jié)果總價(jià)值為3103, 總重量為1000。我們算法所得結(jié)果： 總價(jià)值為3103, 總重量為1000。我們所求得最優(yōu)解的個(gè)體分配情況為：11010 10111 10110 11011 01111 11101 00001

26、01001 10000 01000算法最大迭代次數(shù)總價(jià)值為總重量為傳統(tǒng)的算法4003077999佳點(diǎn)集算法7031031000遺傳算法7531031000八、收獲、體會(huì)和課題展望在本課題中，我們研究了如何用遺傳算法求解組合優(yōu)化問題中的背包問題。我們可以看出在求解背包問題上顯示了超出想象、良好的搜索能力，它具有收斂快、搜索速度快的特點(diǎn)，在試驗(yàn)中取得了比動(dòng)態(tài)規(guī)劃、遞歸回溯法和貪心法等更好的求解效果。然而在一般情況下，使用基本遺傳算法解決背包問題時(shí)，得到問題的近似解也不能滿足逼近最優(yōu)解的要求。如何改進(jìn)基本遺傳算法使它所求得的解逼近最優(yōu)解，成為我們當(dāng)前亟待解決的問題，也是我們將來的課題中所要研究的重要

27、問題。 / knapsack.cpp : Defines the entry point for the console application./#include stdafx.h#include #include #include #include #include #include / 重要常量參數(shù)#define popsize 200 /種群的規(guī)模#define pc 0.618 /雜交概率#define pm 0.03 /變異概率#define lchrom 50 /染色體長度#define maxgen 1000 /最大進(jìn)化代數(shù)struct population unsigned

28、int chromlchrom; /染色體 double weight; /背包重量 double fitness; /適應(yīng)度 unsigned int parent1,parent2,cross; /雙親、交叉點(diǎn);/新生代種群、父代種群struct population oldpoppopsize,newpoppopsize; /背包問題中物體重量、收益、背包容量int weightlchrom,profitlchrom,contain; /種群的總適應(yīng)度、最小、最大、平均適應(yīng)度 double sumfitness,minfitness,maxfitness,avgfitness;/計(jì)算適應(yīng)

29、度時(shí)使用的 懲罰函數(shù)系數(shù)double alpha;/一個(gè)種群中最大和最小適應(yīng)度的個(gè)體int minpop,maxpop; /* 讀入背包信息,并且計(jì)算懲罰函數(shù)系數(shù) */void read_infor()FILE *fp;int j; /獲取背包問題信息文件if (fp=fopen(knapsack.txt,r)=NULL) /讀取文件失敗AfxMessageBox(The file is not found,MB_OK,NULL); return;/讀入物體收益信息 for (j=0;jlchrom;j+) fscanf(fp,%d,&profitj); /讀入物體重量信息 for (j=0;

30、jlchrom;j+) fscanf(fp,%d,&weightj); /讀入背包容量 fscanf(fp,%d,&contain); fclose(fp);/根據(jù)計(jì)算的個(gè)體重量,判斷此個(gè)體是否該留在群體中double cal_weight(unsigned int *chr) int j; double pop_weight;/背包重量 pop_weight=0; for (j=0;jlchrom;j+) pop_weight=pop_weight+(*chr)*weightj;chr+; return pop_weight;/* 種群中個(gè)體適應(yīng)度計(jì)算*/double cal_fit(uns

31、igned int *chr) int j; double pop_profit;/適應(yīng)度 pop_profit=0;/ pop_weight=0; for (j=0;jlchrom;j+) pop_profit=pop_profit+(*chr)*profitj;/pop_weight=pop_weight+(*chr)*weightj;chr+; return pop_profit;/* 群體適應(yīng)度的最大最小值以及其他信息 */void statistics(struct population *pop)int i;double tmp_fit;sumfitness=pop0.fitnes

32、s;minfitness=pop0.fitness; minpop=0;maxfitness=pop0.fitness;maxpop=0;for (i=1;imaxfitness)&(int)(tmp_fit*10)%10=0)maxfitness=popi.fitness;maxpop=i; /選擇種群中最小適應(yīng)度的個(gè)體if (tmp_fitminfitness)minfitness=popi.fitness;minpop=i;/計(jì)算平均適應(yīng)度avgfitness=sumfitness/(float)popsize;/ printf(nthe max pop = %d;,maxpop);/

33、printf(nthe min pop = %d;,minpop);/ printf(nthe sumfitness = %fn,sumfitness);/報(bào)告種群信息void report(struct population *pop,int gen) int j; int pop_weight=0; printf(the generation is %d.n,gen); /輸出種群的代數(shù) /輸出種群中最大適應(yīng)度個(gè)體的染色體信息 printf(The populations chrom is: n); for (j=0;jlchrom;j+) if (j%5=0) printf( );pri

34、ntf(%1d,popmaxpop.chromj); /輸出群體中最大適應(yīng)度 printf(nThe populations max fitness is %d.,(int)popmaxpop.fitness); printf(nThe knapsack weight is %d.nn,(int)popmaxpop.weight);/* 生成初始種群 */void initpop() int i,j,ispop; double tmpWeight; /變量用于判斷是否為滿足條件的個(gè)體 ispop=false; /生成popsize個(gè)種群個(gè)體 for(i=0;ipopsize;i+) while

35、 (!ispop) for(j=0;jlchrom;j+) oldpopi.chromj=rand()%2; /隨機(jī)生成個(gè)體的染色體 oldpopi.parent1=0; /雙親 oldpopi.parent2=0; oldpopi.cross=0; /交叉點(diǎn) /選擇重量小于背包容量的個(gè)體,即滿足條件 tmpWeight=cal_weight(oldpopi.chrom); if (tmpWeight=contain) oldpopi.fitness=cal_fit(oldpopi.chrom); oldpopi.weight=tmpWeight; oldpopi.parent1=0; old

36、popi.parent2=0; oldpopi.cross=0; ispop=true; /此個(gè)體可以加入到種群中 ispop=false; /* 遺傳操作 */概率選擇試驗(yàn)int execise(double probability)double pp; /如果生成隨機(jī)數(shù)大于相應(yīng)的概率則返回真，否則試驗(yàn)不成功pp=(double)(rand()%20001/20000.0);if (pp=probability) return 1;return 0;/ 選擇進(jìn)行交叉操作的個(gè)體 int selection(int pop) double wheel_pos,rand_Number,partsu

37、m; int parent; /賭輪法選擇 rand_Number=(rand()%2001)/2000.0; wheel_pos=rand_Number*sumfitness; /賭輪大小 partsum=0; parent=0; do partsum=partsum+oldpopparent.fitness; parent=parent+1; while (partsumwheel_pos & parentpopsize); return parent-1;/* 交叉操作 */int crossover(unsigned int *parent1,unsigned int *parent2

38、,int i)int j,cross_pos;if (execise(pc)/生成交叉位置0,1,.(lchrom-2)cross_pos=rand()%(lchrom-1);else cross_pos=lchrom-1; for (j=0;j=cross_pos;j+) /保留復(fù)制；/包括在概率選擇不成功時(shí)，父體完全保留newpopi.chromj=parent1j;for(j=cross_pos+1;j=(lchrom-1);j+)/從交叉點(diǎn)開始交叉newpopi.chromj=parent2j; /記錄交叉位置newpopi.cross=cross_pos;return 1;/* 變異操作 */int mutation(unsigned int alleles)