遺傳算法求解01背包問題

1、遺傳算法求解 01 背包問題一、問題描述01 背包問題屬于組合優(yōu)化問題的一個(gè)例子， 求解 01 背包問題的過程可以被視作在很多可行解當(dāng)中 求解一個(gè)最優(yōu)解。 01 背包問題的一般描述如下：給定n個(gè)物品和一個(gè)背包，物品i的重量為W/,其價(jià)值為V,背包的容量為C。選擇合適的物品裝 入背包， 使得背包中裝入的物品的總價(jià)值最大。 注意的一點(diǎn)是， 背包內(nèi)的物品的重量之和不能大于背包 的容量C。在選擇裝入背包的物品時(shí)，對(duì)每種物品 i只有兩種選擇：裝入背包或者不裝入背包，即只能 將物品 i 裝入背包一次。稱此類問題為 0/1 背包問題。01 背包問題是 NP 問題, 傳統(tǒng)的解決方法有動(dòng)態(tài)規(guī)劃法、 分支界限法、

2、 回溯法等等。 傳統(tǒng)的方法不 能有效地解決01背包問題。遺傳算法（Genetic Algorithms ）則是一種適合于在大量的可行解中搜索最 優(yōu)（或次優(yōu)）解的有效算法。二、遺傳算法1 、遺傳算法的基本思想遺傳算法的搜索從一個(gè)被稱作種群的候選解集開始, 新的種群由舊的種群中產(chǎn)生以期得到更好的種 群。從舊種群中按照解的適應(yīng)度來選擇解以產(chǎn)生新的解； 適應(yīng)度越大, 解被選擇生成后代的機(jī)率也越大。 這個(gè)從已有種群中選擇雙親并產(chǎn)生后代的迭代過程持續(xù)到遺傳算法的停止條件滿足為止。2、遺傳算法的基本元素。 遺傳算法由以下幾個(gè)原素組成：由染色體組成的種群,根據(jù)適應(yīng)度進(jìn)行選擇以及交叉產(chǎn)生后代。三、用遺傳算法求解

3、 01 背包問題1、01 背包問題中染色體的表示。用向量 X 來表示染色體,X = xi, X2, , Xno, Xi 0,1,xi=1 表示物品 i 裝入了背包， xi =0 表示物品 i 未裝入背包。每個(gè)染色體對(duì)應(yīng)其當(dāng)前裝入背包的物品的總價(jià)值和總重量。 背包中物品的中價(jià)值代表了該物品的適 應(yīng)度。程序中定義了這樣的一個(gè)結(jié)構(gòu)來表示染色體：typedef structint Weight;/染色體代表的物品的總重量int Fitness;/染色體代表的物品的價(jià)值（適應(yīng)度）int GeneNUMG; /用元素取值于定義域 0,1的數(shù)組表示染色體。GENE;2、遺傳算法求解 01 背包問題時(shí)用到的參

4、數(shù)。POPSIZE :種群大小，即已知的可行解的個(gè)數(shù)。NUMG ：染色體中基因的個(gè)數(shù)，即物品的總數(shù)。CAPACITY ：背包的容量。MAXB ：二進(jìn)制表示的染色體換算之后的最大十進(jìn)制整數(shù)。 用于隨機(jī)產(chǎn)生一個(gè)整數(shù)， 進(jìn)而轉(zhuǎn)換作染 色體。SIM ：染色體之間的相似度閾值。當(dāng)染色體之間的相似度達(dá)到閾值時(shí)，算法即停止運(yùn)行。PC=1.0 ：交叉概率為 100。PM=0.2 :變異概率為20%，變異可以保證種群的多樣性，從而防止算法收斂于某個(gè)局部解。3、選擇操作。選擇操作采用了賭輪選擇(Roulette-wheel selection的方法。函數(shù) select In dex()中包含了選擇染色體的具體過程

5、。其流程圖如圖 1所示。圖1賭輪選擇流程圖程序中用一個(gè) Begin來代表當(dāng)前賭輪上的指針的位置，End則用來使賭輪循環(huán)轉(zhuǎn)動(dòng)。用summaryBE表示當(dāng)前賭輪上的指針轉(zhuǎn)過的染色體的總價(jià)值。用summaryF表示當(dāng)前全部染色體的價(jià)值總和。用randProb作為染色體選擇的閾值。randProb為介于0,1之間的隨機(jī)數(shù)。選擇使summaryBE/summaryF大于閾值randProb的染色體作為要選擇的染色體。4、交叉操作程序中采用了單點(diǎn)交叉的策略。如下程序代碼所示：for(int j=0; jvpartPos ;j+)nextGenomei.Genej = parentGenomeFather.

6、Genej; nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;for(;jvNUMG;j+)nextGenomei.Genej = parentGenomeFather.Genej; nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;partPos為隨機(jī)產(chǎn)生的整數(shù)，代表交叉的位置。第一個(gè)for循環(huán)將partPos位置之前的基因遺傳給一個(gè)后代，而第二個(gè)循環(huán)則將partPos位置之后的基因進(jìn)行了交換。calculateCapacity函數(shù)用于計(jì)算交叉操作后的染色體的容量。cal

7、culateFitness函數(shù)用于計(jì)算交叉操作后的染色體的適應(yīng)度。checkCapacity函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這 里沒有使后代死亡，而是隨機(jī)地調(diào)整了染色體中的基因。使得基因能夠適應(yīng)環(huán)境(背包的容量)而繼續(xù)生存。5、精英策略精英策略為了不使最優(yōu)解在交叉的過程中，不會(huì)丟失最優(yōu)解而采取的策略。其思想是保存上一代中 的適應(yīng)性強(qiáng)的染色體。相應(yīng)地取代下一代中適應(yīng)性弱的染色體。程序中精英策略由 keepBestParents 函數(shù)和 sortFiness 函數(shù)來實(shí)現(xiàn)。需要說明的是 sortFitness 僅僅對(duì) 種群的索引進(jìn)行了排序。然后用父代中20%的適

8、應(yīng)度較大的優(yōu)秀染色體替換子代中20%的適應(yīng)性弱的染色體。6、變異操作 染色體的變異可以保持種群的多樣性，防止最優(yōu)解的丟失以及算法收斂到局部最優(yōu)解。 變異操作由 mutation 函數(shù)實(shí)現(xiàn)。首先產(chǎn)生一個(gè)介于 0 和 1 之間的隨機(jī)數(shù) prob ，若 prob 小于 MP 則進(jìn)行變異操作：隨機(jī)產(chǎn)生一個(gè)位 置partPos，然后變異前染色體的partPos位置的基因?yàn)?,則變異為0,否則變異為1;相應(yīng)地要進(jìn)行適應(yīng)度和染色體容量的變化。7、代際更新代際之間的更新， 即用新生成的種群代替取代舊的種群。 這個(gè)操作在 updateGeneration 函數(shù)中實(shí)現(xiàn)， 同時(shí)這個(gè)操作使用了前面提及的精英策略。實(shí)際

9、上， 父代種群中優(yōu)秀的染色體已被保留， updateGeneration 中只是用新種群中的優(yōu)秀染色體來代替父代中的染色體。由于對(duì)父代和子代的染色體都進(jìn)行了排序， 因此程序中將子代的 80 視作優(yōu)秀， 將父代中的前 20 視作優(yōu)秀。8 、算法的終止程序中采用了一個(gè) HASH 表來對(duì)子代種群的適應(yīng)度進(jìn)行 HASH 操作。 HASH 表中的頭結(jié)點(diǎn)紀(jì)錄了 頭結(jié)點(diǎn)所指向的單鏈表的信息。如下代碼中的注釋：typedef struct Headint maxFitness; /單鏈表中的最大的 Fitnessint Count; int Diff;/HASH 到該結(jié)點(diǎn)的染色體的數(shù)目/ 單鏈表中有多少不同的

10、FitnessHASHNODE *Next;HEAD;用這樣的一個(gè) HASH 表結(jié)構(gòu)可以只需遍歷 HASH 表中的頭結(jié)點(diǎn)，即可知當(dāng)前的種群的適應(yīng)度最大 的染色體是否集中。具體地，如 checkFitness 函數(shù)中的下面幾行代碼：index = maxFitness(hashTable);double CPount = hashTableindex.Count/(double)POPSIZE;double pDiff = hashTableindex.Diff/(double)POPSIZE;if(CPount>=0.9 && pDiff<=0.1)sameFlag

11、 =false;如果當(dāng)前 maxFitness 最大的頭結(jié)點(diǎn)滿足 if 語句中的判斷條件，則 sameFlag 置為真，即算法停止迭 代的條件得到了滿足。TraverseHashTable 函數(shù)則用于遍歷 HASH 表。 算法終止的另一個(gè)條件是迭代的次數(shù)。程序中設(shè)定了算法的最大迭代次數(shù)為1000。四、實(shí)驗(yàn)結(jié)果。試驗(yàn)中用到的物品的重量和價(jià)值分別存儲(chǔ)于以下兩個(gè)數(shù)組之中。int WeightNUMG=6,9,8,8,6, 1, 10,5,7, 1;int ValueNUMG=2,20,5,4,19,14,18,8,11,6;父代種群存儲(chǔ)于 parentGenomeNUMG 中，子代種群存儲(chǔ)于 nex

12、tGenomeNUMG 中。程序的初始狀 態(tài)和結(jié)束狀態(tài)如下面的表格所示：初始的種群WeightValue染色體中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表頭結(jié)點(diǎn)索引maxFitnessCountDiff單鏈表中的結(jié)點(diǎn)內(nèi)容0521152:1534253:40:3291129:6451145:9481148:10231123:12251125:程序在運(yùn)行了 16次后停止運(yùn)行。停止時(shí)的種群WeightValue染色體中的基因297801001101112978010011011129780100110111297801001101112978010011011