遺傳算法的0-1背包問(wèn)題(c語(yǔ)言)

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

2、算法，它以其簡(jiǎn)單、魯棒性強(qiáng)、適應(yīng)并行處理以及應(yīng)用范圍廣等特點(diǎn)， 奠定了作為 21 世紀(jì)關(guān)鍵智能計(jì)算的地位。背包問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，在計(jì)算理論中屬于NP- 完全問(wèn)題， 其計(jì)算復(fù)雜度為 O(2n ) ，傳統(tǒng)上采用動(dòng)態(tài)規(guī)劃來(lái)求解。設(shè) wi 是經(jīng)營(yíng)活動(dòng) i 所需要的資源消耗， M 是所能提供的資源總量， pi 是人們經(jīng)營(yíng)活動(dòng) i 得到的利潤(rùn)或收益，-WORD格式 - 可編輯 -則背包問(wèn)題就是在資源有限的條件下，追求總的最大收益的資源有效分配問(wèn)題。二、問(wèn)題描述背包問(wèn)題 ( Knapsack Problem)的一般提法是：已知n個(gè)物品的重量（ weight ）及其價(jià)值（或收益 profit ）分

3、別為 wi 0 和 pi 0 ，背包的容量（ contain ）假設(shè)設(shè)為 ci 0 ，如何選擇哪些物品裝入背包可以使得在背包的容量約束限制之內(nèi)所裝物品的價(jià)值最大？該問(wèn)題的模型可以表示為下述0/1 整數(shù)規(guī)劃模型：n目標(biāo)函數(shù)： maxf ( x1 , x2 , xn )ci xii 1ns.twi xipii 1xi 0,1(i1,2, n)（ * ）式中 xi 為 0-1 決策變量， xi1時(shí)表示將物品i 裝入背包中， xi0時(shí)則表示不將其裝入背包中。三、求解背包問(wèn)題的一般方法解決背包問(wèn)題一般是采取動(dòng)態(tài)規(guī)劃、遞歸回溯法和貪心方法。動(dòng)態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段

4、問(wèn)題。對(duì)于背包問(wèn)題可以對(duì)子過(guò)程用-WORD格式 - 可編輯 -枚舉法求解，而且約束條件越多，決策的搜索范圍越小，求解也越容易。它的主要缺點(diǎn)是用數(shù)值方法求解時(shí)會(huì)隨著狀態(tài)變量的個(gè)數(shù)呈指數(shù)級(jí)的增長(zhǎng)，往往對(duì)于求解背包問(wèn)題的實(shí)際問(wèn)題是不現(xiàn)實(shí)的。使用遞歸回溯法解決背包問(wèn)題的優(yōu)點(diǎn)在于它算法思想簡(jiǎn)單，而且它能完全遍歷搜索空間，肯定能找到問(wèn)題的最優(yōu)解；但是由于此問(wèn)題解的總組合數(shù)有2n 個(gè)，因此，隨著物件數(shù) n 的增大， 其解的空間將以 2 n 級(jí)增長(zhǎng)， 當(dāng) n 大到一定程度上，用此算法解決背包問(wèn)題將是不現(xiàn)實(shí)的。使用貪心方法求解時(shí)計(jì)算的復(fù)雜度降低了很多，但是往往難以得到最優(yōu)解，有時(shí)所得解與最優(yōu)解相差甚遠(yuǎn)。因此，我

5、們可以探索使用遺傳算法解決物件數(shù)較大的背包問(wèn)題。四、遺傳算法簡(jiǎn)介遺傳算法 ( Genetic Algorithms ，GA) 是在 1975 年首次由美國(guó)密西根大學(xué)的 D 。 J 。 Holland 教授和他的同事們借鑒生物界達(dá)爾文的自然選擇法則和孟德?tīng)柕倪z傳進(jìn)化機(jī)制基礎(chǔ)之上提出的。經(jīng)過(guò)近 30 年的研究、應(yīng)用，遺傳算法已被廣泛地應(yīng)用于函數(shù)優(yōu)化、 機(jī)器人系統(tǒng)、 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)過(guò)程、模式識(shí)別、圖象處理、工業(yè)優(yōu)化控制等領(lǐng)域。-WORD格式 - 可編輯 -遺傳算法是將問(wèn)題的每一個(gè)可能性解看作是群體中的一個(gè)個(gè)體 (染色體 )，并將每一個(gè)染色體編碼成串的形式，再根據(jù)預(yù)定的目標(biāo)函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，給出一

6、個(gè)適應(yīng)值。算法將根據(jù)適應(yīng)度值進(jìn)行它的尋優(yōu)過(guò)程，遺傳算法的尋優(yōu)過(guò)程是通過(guò)選擇、雜交和變異三個(gè)遺傳算子來(lái)具體實(shí)現(xiàn)的。它的搜索能力由選擇算子和雜交算子決定，變異算子則保證了算法能夠搜索到問(wèn)題空間的盡可能多的點(diǎn)，從而使其具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強(qiáng)壯性可由Holland提出的模式定理( Schema Therem)和隱式并行性得以解釋。在遺傳算法中，定義長(zhǎng)度較短、低階且適應(yīng)值超過(guò)平均適應(yīng)值的模式在群體中數(shù)目的期望值按指數(shù)遞增，這個(gè)結(jié)論稱(chēng)為遺傳算法的基本定理。遺傳算法是通過(guò)定義長(zhǎng)度短、確定位數(shù)少、適應(yīng)度值高的模式的反復(fù)抽樣、組合來(lái)尋找最佳點(diǎn)，稱(chēng)這些使遺傳算法有效工作的模式為積木塊，是遺傳

7、算法構(gòu)造答案的基本材料。但歸根到底，要使遺傳算法有效工作必須按照遺傳算法的模式定理(或積木塊假設(shè) )根據(jù)具體問(wèn)題設(shè)計(jì)合理的編碼方案。在運(yùn)行遺傳算法程序時(shí)，需要對(duì)一些參數(shù)作事先選擇，它們包括種群的大小、染色體長(zhǎng)、交叉率、變異率、最大進(jìn)-WORD格式 - 可編輯 -化代數(shù)等，這些參數(shù)對(duì)GA的性能都有很重要的影響。在試驗(yàn)中參數(shù)一般選取如下：種群大小 N= 20100，交叉概率 p c= 0.4 0.9，變異概率 p m = 0.0010.1，最大進(jìn)化代數(shù)maxgen = 100500。遺傳算法是具有“生成+ 檢測(cè)”的迭代過(guò)程的搜索算法。它的基本處理流程如圖1 所示。編碼初始化種群演化評(píng)估種群中個(gè)體適

8、應(yīng)度選擇交叉變異圖1、遺傳算法的基本流程遺傳算法的基本流程描述如下：（1 ）編碼：將解空間的解數(shù)據(jù)進(jìn)行二進(jìn)制編碼， 表達(dá)為遺傳空間的基因型串 （即染色體） 結(jié)構(gòu)數(shù)據(jù)， 如將數(shù)據(jù) 9-WORD格式 - 可編輯 -編碼為“ 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)度f(wàn) i ( fitness) ；（4 ）選擇：選擇把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或者模型遺傳到下一代種群中，這里所用的規(guī)則是：染色體在種群中被

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

10、串 x j ， j=1 ， 2 ， ， n 。 x j0 表示物體 j 不放入 背 包 內(nèi) ， x j 1 表 示 物 體 j 放 入 背 包 內(nèi) 。 例 如 ：111001100000111代表一個(gè)解， 它表示將第1 、2 、3 、6、7 n-2,n-1,n 號(hào)物體放入背包中，其它的物體則不放入。根據(jù)遺傳算法的基本流程，我們確定了求解背包問(wèn)題的遺傳算法：步驟 1、初始化過(guò)程1.1 確定種群規(guī)模popsize、雜交概率pc 、變異概率pm、染色體長(zhǎng)度lchrom及最大進(jìn)化代數(shù)maxgen ；1.2 讀入背包問(wèn)題的相關(guān)信息，如每個(gè)物體的重量weightj、 每 個(gè) 物 體 的 收 益profit

11、j和 背 包 的 容 量contain，其中j0,1,(lchrom1) ；1.3 取 x ju(0,1)j0,1,(lchrom1) ，其中 u(0,1) 表示 0-1整數(shù)的均勻分布函數(shù)，即隨機(jī)地生成數(shù)0 或 1，生成的 x j 串即可看為一個(gè)染色體個(gè)體。若不滿(mǎn)足模型 （*）的約束條件， 則拒絕接受， 由 1.2 重新生成一個(gè)新的染色體個(gè)體 chrom ；如果產(chǎn)生的染色體-WORD格式 - 可編輯 -可行，則接受它作為種群的一名成員，經(jīng)過(guò)有限次的1.2抽樣后，得到popsize個(gè)可行的染色體chrom ，形成新的種群。1.4置種群的代數(shù)gen=0 ；步驟 2 、計(jì)算種群中個(gè)體適應(yīng)度以及統(tǒng)計(jì)種

12、群適應(yīng)度情況2.1按照下列公式計(jì)算種群中個(gè)體適應(yīng)度：lchrom 1(1) ；weightweight j * chrom jj0lchrom 1profit j * chrom jifweightcontainfitnessj 0(2)lchrom 1profit j * chrom j alpha* (weight contain)ifweightcontainj 0公式（ 2 ）的下半部分即為適應(yīng)度的懲罰函數(shù)，其中參數(shù)alpha1.0 。2.2按公式（ 3 ）計(jì)算種群的總體適應(yīng)度，popsize1sumfitnessfitnessi (3)i 0并且按照排序的方法統(tǒng)計(jì)出種群中的最大、最小

13、適應(yīng)度的染色體個(gè)體，分別標(biāo)記為maxpop、 minpop；步驟 3、選擇操作3.1 生成一個(gè)隨機(jī)數(shù)rand_Number，要求 0rand _ Nuber1 ；3.2 按照賭輪法選擇個(gè)體，賭輪法的算法描述如下：-WORD格式 - 可編輯 -int selection( )i=0;/個(gè)體的編號(hào)sum=0 ；/部分個(gè)體適應(yīng)度的累加和/ 根據(jù)隨機(jī)數(shù)和群體的總適應(yīng)度確定賭輪的位置wheel-pos=rand_Number*sufitness;while sum<wheel-pos && i<=popsize i=i+1;sum=sum+fitnessi;/fitness為

14、第 i 個(gè)個(gè)體的適應(yīng)度return i-1;/選擇了個(gè)體i-13.3重復(fù)兩次操作3.1 、 3.2 ，生成兩個(gè)個(gè)體作為交叉操作的父代；步驟四、交叉操作4.1根據(jù)事先定義好的交叉概率pc ，為了確定是否進(jìn)行交叉操作，則生成 0 ，1 的隨機(jī)數(shù)pp ，若 pppc ，則進(jìn)行4.2交叉操作，否則將兩個(gè)父代保留為下一代的兩個(gè)個(gè)體；-WORD格式 - 可編輯 -4.2隨機(jī)生成 0, lchrom1 的整數(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ù)事先定義好的變異概率p m ，為

15、了確定新種群上的每個(gè)個(gè)體上的每個(gè)基因是否進(jìn)行變異操作，則生成0，1的隨機(jī)數(shù) pp ，若 pppm ，則進(jìn)行5.2 變異操作，否則基因不變異；5.2基因變異操作為原基因若為1 ，則新基因則變異為0 ，若原基因?yàn)?，則新基因變異為0；步驟 6、 演化6.1按步驟2 的方法計(jì)算新種群的個(gè)體適應(yīng)度和總體適應(yīng)度情況，尤其是找出新種群中最大適應(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，若gen Maxgen ，則-WORD格式 - 可編輯 -結(jié)束種群的演

16、化，否則轉(zhuǎn)到步驟2。六、遺傳算法求解的實(shí)現(xiàn)1、遺傳算法的主要參數(shù)#define popsize 80/種群的規(guī)模#define pc 0.7/雜交概率#define pm 0.1/變異概率#define lchrom 50/染色體長(zhǎng)度#define maxgen 5000/最大進(jìn)化代數(shù)double alpha;/計(jì)算適應(yīng)度時(shí)使用的懲罰函數(shù)系數(shù)2、數(shù)據(jù)結(jié)構(gòu)（1 ）背包信息：/ 背包問(wèn)題中物體重量、收益、背包容量int weightlchrom,profitlchrom,contain;（2 ）種群個(gè)體結(jié)構(gòu)體struct populationunsigned int chromlchrom;/染色

17、體double fitness;/適應(yīng)度unsigned int parent1,parent2,cross;/雙親、交叉點(diǎn)-WORD格式 - 可編輯 -;（3 ）父代種群和新生代種群/ 父代種群、新生代種群structpopulationoldpoppopsize,newpoppopsize;/pop_size為種群大?。? ）適應(yīng)度信息/ 種群的總適應(yīng)度、最小、最大適應(yīng)度doublesumfitness,minfitness,maxfitness;/ 一個(gè)種群中最大和最小適應(yīng)度的個(gè)體編號(hào)intminpop,maxpop;3、主要函數(shù)說(shuō)明（ 1 ）、 int read_infor( )功能：

18、從文件knapsack.txt中讀出背包信息（物體重量、收益、背包容量） ；參數(shù)：無(wú)；返回值：返回讀取文件信息是否正確；流程圖：見(jiàn)圖2。-WORD格式 - 可編輯 -打開(kāi)文件否獲取文件指針成功是讀出物體重量信息讀出物體收益信息讀出背包容量信息返回圖 2 、 read_infor( ) 流程圖（ 2 ） double cal_fit(unsigned int *chr)功能：種群中個(gè)體適應(yīng)度計(jì)算；參數(shù)： unsigned int *chr是染色體個(gè)體的指針，根據(jù)指針?biāo)赶虻娜旧w計(jì)算個(gè)體的適應(yīng)度；返回值：染色體個(gè)體適應(yīng)度的大??；流程圖：見(jiàn)圖3。-WORD格式 - 可編輯 -適應(yīng)度和總重量置0累加

19、計(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)度的信息；返回值：無(wú)；流程圖：見(jiàn)圖4。（ 4 ）、 void report(struct population *pop,int gen)功能：報(bào)告種群的適應(yīng)度信息，尤其是最大個(gè)體適應(yīng)度、最大適應(yīng)度個(gè)體的染色體信息；參數(shù)： struct

20、 population *pop是種群指針，根據(jù)指針?biāo)甘鞘褂脩土P函數(shù)對(duì)個(gè)體-WORD格式 - 可編輯 -適應(yīng)度進(jìn)行處理向的種群報(bào)告群體適應(yīng)度的信息，gen 是表示此種群返回個(gè)體適應(yīng)度所在的演化代數(shù)返回值：無(wú)；流程圖：見(jiàn)圖5。最大最小總適應(yīng)度都置為首個(gè)體的適應(yīng)度計(jì)數(shù)器 i=1i<lchrom-1返回是總適應(yīng)度 =總適應(yīng)度 +個(gè)體 i 的適應(yīng)度I 的適應(yīng)度I 的適應(yīng)度 <最大適應(yīng)度最小適應(yīng)度置最大適應(yīng)度的編置最小適應(yīng)度的編號(hào)為 i號(hào)為 ii=i+1圖 4 、函數(shù) statistics的流程圖-WORD格式 - 可編輯 -輸出種群的代數(shù)gen輸出最大適應(yīng)度個(gè)體的染色體信息 chrom輸

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

22、異概率返回值：試驗(yàn)是否成功，0 代表不試驗(yàn)成功，將不做交叉或者變異操作， 1 代表試驗(yàn)成功，即進(jìn)行交叉或者變異操作；流程圖：見(jiàn)圖7。生成 0，1之間的小數(shù) pp是否若 pp< probability返回實(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 ；-WORD格式 - 可編輯 -流程圖：見(jiàn)圖8。個(gè)體編號(hào) i=0，部分適應(yīng)度之和 partsum=0產(chǎn)生隨機(jī)數(shù) rand_Numbe

23、r計(jì)算賭輪所在位置wheel_pospartsum<wheel-pos&& i<=popsize?Partsum=partsum+個(gè)體 i 的適應(yīng)度個(gè)體計(jì)數(shù)器 i=i+1返回被選擇的個(gè)體i-1圖 8 、函數(shù) selection 的流程圖（ 8 ）、 intcrossover(unsignedint*parent1,unsignedint *parent2,int i)功能：兩個(gè)父代個(gè)體在染色體的第i 個(gè)位置進(jìn)行交叉，生成兩個(gè)新個(gè)體；參數(shù)： unsigned int *parent1,unsigned int *parent2分別為兩個(gè)父代染色體指針，指針指向父代個(gè)體

24、的染色-WORD格式 - 可編輯 -體， i 為新種群的個(gè)體編號(hào)；返回值：交叉是否成功；流程圖：見(jiàn)圖9。概率選擇試驗(yàn)成功否是隨機(jī)生成交叉位置cross_pos兩個(gè)父代個(gè)體按照交叉位置進(jìn)行交叉，生成新的兩個(gè)個(gè)體保留兩個(gè)父體成為新種群中的個(gè)體圖 9 、函數(shù) crossover 的流程圖（ 9 ）、 int mutation(unsigned int alleles)功能：根據(jù)變異概率進(jìn)行變異操作；參數(shù)： unsigned int alleles是染色體上的基因型，在這里就是 0或1的取值；返回值：變異后的基因型；流程圖：見(jiàn)圖10 。-WORD格式 - 可編輯 -否概率選擇試驗(yàn)成功是進(jìn)行變異返回變異

25、或者原值圖 10 、函數(shù) mutation的流程圖（ 10 ）、 void generation()功能：綜合選擇、交叉、變異等操作，生成新的種群；參數(shù)：無(wú)；返回值：無(wú)；流程圖：見(jiàn)圖11 。-WORD格式 - 可編輯 -置個(gè)體編號(hào) i=0i<pop_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ù)：無(wú)；返回值：無(wú)；流程圖：見(jiàn)圖11 。-WORD格

26、式 - 可編輯 -調(diào)用 read_infor，讀入背包信息置演化代數(shù) gen=0調(diào)用 initpop( ) 生成初始種群調(diào)用 statistics ( )統(tǒng)計(jì)種群的適應(yīng)度Gen<Maxgen?是調(diào)用 generation()調(diào)用 report( )，生成新種群輸出結(jié)果信息調(diào)用 statistics ( )統(tǒng)計(jì)種群的適應(yīng)度新種群的最大適應(yīng)度 <舊種群的是復(fù)制舊種群的最大適應(yīng)度個(gè)體到新種群中最小個(gè)體置演化代數(shù) gen=gen+1圖 12 、主函數(shù) main的流程圖-WORD格式 - 可編輯 -七、成果說(shuō)明1、程序開(kāi)發(fā)環(huán)境開(kāi)發(fā)環(huán)境： Visual C+6.0 (把 Fortran程序改為

27、 VC)操作系統(tǒng)： Windows 2003 Professional2、程序性能對(duì)比運(yùn)行時(shí)間與加速比（如表1 所示）進(jìn)程數(shù) p124（個(gè)）運(yùn)行時(shí)間 t129s78s38s（秒）加速比 s1.653.38表 1、運(yùn)行時(shí)間與加速比3、程序運(yùn)行結(jié)果：實(shí)例數(shù)據(jù)：假設(shè)物體的重量Weight 、物體的收益Profit和背包的容量 Contain 分別為：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 ，50 ，3

28、0 ，45 ，30 ，60 ，50 ，20，65 ，20 ，25 ，30 ，-WORD格式 - 可編輯 -10 ，20 ，25 ，15 ，10 ，10 ，10 ，4， 4， 2， 1Profit=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，

29、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)集遺傳算法所-WORD格式 - 可編輯 -得結(jié)果總價(jià)值為3103,總重量為1000 。我們算法所得結(jié)果：總價(jià)值為3103,總重量為 1000 。我們所求得最優(yōu)解的個(gè)體分配情況為：11010101111011011011011111110100001010011000001000算法最大迭代次總價(jià)值為總重量為數(shù)傳統(tǒng)的算法4003077999佳點(diǎn)集算法

30、7031031000遺傳算法7531031000八、收獲、體會(huì)和課題展望在本課題中，我們研究了如何用遺傳算法求解組合優(yōu)化問(wèn)題中的背包問(wèn)題。我們可以看出在求解背包問(wèn)題上顯示了超出想象、良好的搜索能力，它具有收斂快、搜索速度快的特點(diǎn)，在試驗(yàn)中取得了比動(dòng)態(tài)規(guī)劃、遞歸回溯法和貪心法等-WORD格式 - 可編輯 -更好的求解效果。然而在一般情況下，使用基本遺傳算法解決背包問(wèn)題時(shí)，得到問(wèn)題的近似解也不能滿(mǎn)足逼近最優(yōu)解的要求。如何改進(jìn)基本遺傳算法使它所求得的解逼近最優(yōu)解，成為我們當(dāng)前亟待解決的問(wèn)題，也是我們將來(lái)的課題中所要研究的重要問(wèn)題。/knapsack.cpp: Definestheentrypoint

31、fortheconsole application./#include "stdafx.h"#include <AfxWin.h>#include <stdlib.h>#include <math.h>#include <time.h>#include <conio.h>#include <stdio.h>/ 重要常量參數(shù)#define popsize 200/ 種群的規(guī)模#define pc 0.618/雜交概率#define pm 0.03/變異概率#define lchrom 50/染色體長(zhǎng)度-W

32、ORD格式 - 可編輯 -#define maxgen 1000/最大進(jìn)化代數(shù)struct populationunsigned int chromlchrom; double weight; double fitness;/染色體/背包重量/適應(yīng)度unsigned int parent1,parent2,cross;/雙親、交叉點(diǎn);/ 新生代種群、父代種群struct population oldpoppopsize,newpoppopsize;/ 背包問(wèn)題中物體重量、收益、背包容量int weightlchrom,profitlchrom,contain;/ 種群的總適應(yīng)度、最小、最大、平

33、均適應(yīng)度double sumfitness,minfitness,maxfitness,avgfitness;/ 計(jì)算適應(yīng)度時(shí)使用的 懲罰函數(shù)系數(shù) double alpha;/ 一個(gè)種群中最大和最小適應(yīng)度的個(gè)體intminpop,maxpop;/*讀入背包信息 , 并且計(jì)算懲罰函數(shù)系數(shù)*/void read_infor()-WORD格式 - 可編輯 -FILE *fp;int j;/ 獲取背包問(wèn)題信息文件if (fp=fopen("knapsack.txt","r")=NULL)/ 讀取文件失敗AfxMessageBox("Thefileisn

34、otfound",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ù)計(jì)算的個(gè)體重量 , 判斷此個(gè)體是否該留在群體中double cal_weight(unsigned int *chr)

35、-WORD格式 - 可編輯 -int j;double pop_weight;/背包重量pop_weight=0;for (j=0;j<lchrom;j+)pop_weight=pop_weight+(*chr)*weightj; chr+;return pop_weight;/*種群中個(gè)體適應(yīng)度計(jì)算*/double cal_fit(unsigned int *chr)int j;double pop_profit;/適應(yīng)度pop_profit=0;/ pop_weight=0;for (j=0;j<lchrom;j+)pop_profit=pop_profit+(*chr)*pr

36、ofitj;/ pop_weight=pop_weight+(*chr)*weightj; chr+;-WORD格式 - 可編輯 -return pop_profit;/* 群體適應(yīng)度的最大最小值以及其他信息 */ void statistics(struct population *pop) int i;double tmp_fit;sumfitness=pop0.fitness;minfitness=pop0.fitness;minpop=0;maxfitness=pop0.fitness;maxpop=0;for (i=1;i<popsize;i+)/ 計(jì)算種群的總適應(yīng)度sumfi

37、tness=sumfitness+popi.fitness;tmp_fit=popi.fitness;/ 選擇種群中最大適應(yīng)度的個(gè)體if(tmp_fit>maxfitness)&&(int)(tmp_fit*10)%10=0)maxfitness=popi.fitness;maxpop=i;-WORD格式 - 可編輯 -/ 選擇種群中最小適應(yīng)度的個(gè)體if (tmp_fit<minfitness)minfitness=popi.fitness;minpop=i;/ 計(jì)算平均適應(yīng)度avgfitness=sumfitness/(float)popsize;/ printf

38、("nthe max pop = %d;",maxpop);/ 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(

39、"The population's chrom is:n");for (j=0;j<lchrom;j+)if (j%5=0) printf(" ");-WORD格式 - 可編輯 -printf("%1d",popmaxpop.chromj);/ 輸出群體中最大適應(yīng)度printf("nThepopulation'smaxfitnessis %d.",(int)popmaxpop.fitness);printf("nTheknapsackweightis %d.nn",(int

40、)popmaxpop.weight);/*生成初始種群*/void initpop()int i,j,ispop;double tmpWeight;/ 變量用于判斷是否為滿(mǎn)足條件的個(gè)體ispop=false;/ 生成 popsize 個(gè)種群個(gè)體for(i=0;i<popsize;i+)while (!ispop)for(j=0;j<lchrom;j+)oldpopi.chromj=rand()%2;/隨機(jī)生成個(gè)體的染色體oldpopi.parent1=0;/雙親oldpopi.parent2=0;-WORD格式 - 可編輯 -oldpopi.cross=0;/交叉點(diǎn)/ 選擇重量小于

41、背包容量的個(gè)體 ,即滿(mǎn)足條件tmpWeight=cal_weight(oldpopi.chrom); if (tmpWeight<=contain) oldpopi.fitness=cal_fit(oldpopi.chrom);oldpopi.weight=tmpWeight;oldpopi.parent1=0;oldpopi.parent2=0;oldpopi.cross=0;ispop=true;/ 此個(gè)體可以加入到種群中ispop=false;/*遺傳操作*/ 概率選擇試驗(yàn)int execise(double probability)double pp;/如果生成隨機(jī)數(shù)大于相應(yīng)的概

42、率則返回真，否則試驗(yàn)不成功pp=(double)(rand()%20001/20000.0);-WORD格式 - 可編輯 -if (pp<=probability) return 1;return 0;/ 選擇進(jìn)行交叉操作的個(gè)體int selection(int pop)double wheel_pos,rand_Number,partsum; int parent;/ 賭輪法選擇rand_Number=(rand()%2001)/2000.0;wheel_pos=rand_Number*sumfitness;/賭輪大小partsum=0;parent=0;dopartsum=partsum+oldpop