遺傳算法求解01背包問題

《遺傳算法求解01背包問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、題中染色體的表示。用向量X來表示染色體，X=｛x1，x2，……，xn｝。，xi∈｛0,1｝，xi=1表示物品i裝入了背包，xi=0表示物品i未裝入背包。每個染色體對應其當前裝入背包的物品的總價值和總重量。背包中物品的中價值代表了該物品的適應度。程序中定義了這樣的一個結(jié)構(gòu)來表示染色體：typedefstruct{intWeight;//染色體代表的物品的總重量intFitness;//染色體代表的物品的價值（適應度）intGene[NUMG];//用元素取值于定義域｛0,1｝的數(shù)組表示染色體。}GENE;2、遺傳算法求解01背包問題時用到的參數(shù)。POPSIZE：種群大小，

4、即已知的可行解的個數(shù)。NUMG：染色體中基因的個數(shù)，即物品的總數(shù)。CAPACITY：背包的容量。MAXB：二進制表示的染色體換算之后的最大十進制整數(shù)。用于隨機產(chǎn)生一個整數(shù)，進而轉(zhuǎn)換作染色體。SIM：染色體之間的相似度閾值。當染色體之間的相似度達到閾值時，算法即停止運行。PC=1.0：交叉概率為100％。PM=0.2：變異概率為20％，變異可以保證種群的多樣性，從而防止算法收斂于某個局部解。3、選擇操作。選擇操作采用了賭輪選擇（Roulette-wheelselection）的方法。函數(shù)selectIndex()中包含了選擇染色體的具體過程。其流程圖如圖1所示。圖1賭輪選

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

6、ene[j];nextGenome[i+POPSIZE/2].Gene[j]=parentGenome[Mother].Gene[j];}for(;j

7、ateCapacity函數(shù)用于計算交叉操作后的染色體的容量。calculateFitness函數(shù)用于計算交叉操作后的染色體的適應度。checkCapacity函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這里沒有使后代死亡，而是隨機地調(diào)整了染色體中的基因。使得基因能夠適應環(huán)境（背包的容量）而繼續(xù)生存。5、精英策略精英策略為了不使最優(yōu)解在交叉的過程中，不會丟失最優(yōu)解而采取的策略。其思想是保存上一代中的適應性強的染色體。相應地取代下一代中適應性弱的染色體。程序中精英策略由keepBestParents函數(shù)和sortFi