遺傳算法求解01背包問題

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

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

2、等。傳統(tǒng)的方法不能有效地解決01背包問題。遺傳算法（GeneticAlgorithms）則是一種適合于在大量的可行解中搜索最優(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=｛x1，x2，……，xn｝。，xi∈｛0,1｝，xi=1表示物品i裝入了背包，xi=0表示物品i未裝入背包。每個(gè)染色體對應(yīng)其當(dāng)前裝入背包的物品的總價(jià)值和總重量。背包中物品的中價(jià)值代表了該物品的適應(yīng)度。程序中定義了這樣的一個(gè)結(jié)構(gòu)來表示染色體：typedefstruct{intWeight;//染色體代表的物品的總重量intFitness;//染色體代表的物品的價(jià)值（適應(yīng)度）intGene[NUMG];//用元素取值于定義域｛0,1｝的數(shù)組表示染色體。}GENE;2、遺傳算法求解01

4、背包問題時(shí)用到的參數(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-wheelselection）的方法。函數(shù)selectIndex

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

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

7、置之前的基因遺傳給一個(gè)后代，而第二個(gè)循環(huán)則將partPos位置之后的基因進(jìn)行了交換。calculateCapacity函數(shù)用于計(jì)算交叉操作后的染色體的容量。calculateFitness函數(shù)用于計(jì)算交叉操作后的染色體的適應(yīng)度。checkCapacity函數(shù)則用于檢查交叉后的染色體的合理性，容量超出背包的染色體是不合理的。這里沒有使后代死亡，而是隨機(jī)地調(diào)整了染色體中的基因。使得基因能夠適應(yīng)環(huán)境（背包的容量）而繼續(xù)生存。5、精英策略精英策略為了不使最優(yōu)解在交叉的過程中，不會丟失最優(yōu)解而采取的策略。其思想是保存上一代中的適應(yīng)性強(qiáng)的染色體。相應(yīng)地取代下一代中適

8、應(yīng)性弱的染色體。程序中精英策略由keepBestParents函數(shù)和sortFi