基于均勻設計抽樣遺傳算法求解背包問題

陳明華, 任 哲, 周本達

(1.皖西學院數理系,安徽六安 237012; 2.合肥學院數理系,安徽合肥 230022)

基于均勻設計抽樣遺傳算法求解背包問題

陳明華1, 任 哲2, 周本達1

(1.皖西學院數理系,安徽六安 237012; 2.合肥學院數理系,安徽合肥 230022)

眾所周知,遺傳算法的運行機理及特點是具有定向制導的隨機搜索技術,其定向制導的原則是：導向以高適應度模式為祖先的“家族”方向.以此結論為基礎,利用均勻設計抽樣的理論和方法,對遺傳算法中的交叉操作進行了重新設計,給出了一個新的GA算法,稱之為均勻設計抽樣遺傳算法.最后將均勻設計抽樣遺傳算法應用于求解背包問題,并與簡單遺傳算法和文獻[2]中的佳點集遺傳算法進行比較.通過模擬比較,可以看出新的算法不但提高了算法的速度和精度,而且避免了其它方法常有的早期收斂現象.

遺傳算法(GA);均勻設計抽樣(UDS);均勻設計抽樣遺傳算法(UDSGA)

1 引 言

0/1背包問題(Knapsack Problem)是著名的NP完備類困難問題,許多理論和實際工作者對此問題作了深入的研究,提出了不少的求解這個問題的經典方法,用這些方法求解該問題時確實能得到很好的結果,但是這些傳統的優化方法在求解較大規模的0/1背包問題時,都存在計算量大、迭代時間長的弱點.近年來蓬勃發展起來的遺傳算法憑借它的全局最優性、可并行性、高效性,已被廣泛應用于組合優化領域.遺傳算法克服了傳統優化方法的缺點,借助了大自然的演化過程,是多線索而非單線索的全局優化方法,采用的是種群和隨機搜索機制.所以,如何運用遺傳算法求解大規模的0/1背包問題已成為當前研究的一個熱點.

2 0/1背包問題描述

式中xi為0/1決策變量,xi=1時表示將物品放入背包中,xi=0表示不將物品放入背包中.

解決0/1背包問題,一般是采取遞歸回溯法和貪婪法.遞歸回溯法是一種基于窮盡的思想,即問題的求解空間范圍從000…0(l個二進制位)到111…1(l個二進制位),共計2l種組合.用遞歸回溯法解決0/1背包問題的優點在于它算法簡單,而且它能完全遍及搜索空間,肯定能找到問題的最優解.由于此問題解的總組合數有2l個,隨著物件數l的增大,其解的空間將以指數級增長,當l大到一定程度時,用此算法解決0/1背包問題將是不現實的.貪婪法的基本思路是從問題的某一個初始解出發逐步逼近給定的目標,盡可能快地求得更好的解,當達到算法中的某一步不能再繼續前進時,算法停止.使用貪婪法求解時難以得到整體最優解,有時所得解與最優解相差甚遠,因此,不少學者探索使用遺傳算法解決物件數較大的背包問題.

3 均勻設計抽樣遺傳算法

文獻[1]對GA算法中的兩個理論基石“模式定理”和“隱性并行性質”進行了分析,指出GA算法的本質是：遺傳算法是一個具有定向制導的隨機搜索技術,其定向制導的原則是：導向以高適應度模式為祖先的“家族”方向.文獻[2]根據此機理,利用數論中的佳點集理論和方法[3]設計了一個新的交叉算法,提高了GA算法的效率.這種算法稱為佳點集遺傳算法.但佳點集的選取在n取定后是確定的,不帶隨機性.為了克服此不足,我們提出均勻設計抽樣遺傳算法.本文就是利用均勻設計抽樣[4]來設計一個新的交叉算法,以提高GA算法的效率,然后將之應用到0-1背包問題的求解.實驗證明無論是在求解精度上還是在求解速度上,均勻設計抽樣遺傳算法不僅優于GA算法,也優于佳點集遺傳算法.為此先簡單介紹一下文中要用的均勻設計抽樣理論方面的內容.

3.1 均勻設計抽樣.

均勻設計抽樣這樣進行[4]：

我們稱這樣的抽樣方法為均勻設計抽樣(Uniform Design Sampling(UDS)),所得到的樣本Xk=xk1,…,xkt,k=1,…,n稱為均勻設計抽樣的樣本,并記為

3.2 均勻設計抽樣遺傳算法.

1)均勻設計抽樣交叉操作

設在傳統的GA算法基礎上,在進行過復制后,對池中的元素按賭輪法選擇兩個元素A1,A2進行均勻設計抽樣交叉操作.

令

由A1,A2進行交叉(不管是單點交叉或是多點交叉)其子孫必屬于H,于是要在“高適應度模式為祖先的家族方向”上搜索出更好的樣本,就是要在H中搜索出更好的樣本.均勻設計抽樣遺傳算法就是在H上利用均勻設計抽樣方法找出好樣本來,其方法是[4]：

將H的前t個分量看成一個t維的立方體(仍記為H)然后在H上進行均勻設計抽樣.在t維空間中進行均勻設計抽樣交叉的方法如下：

〈a〉表示：若a的小數部分小于0.5,則〈a〉=0;否則〈a〉=1.

這樣,在其“家族”中,產生了n個后代,取其中適應值最大者(或最大的幾個),作為交叉后的后代.

上述交叉操作,稱為均勻設計抽樣交叉操作.

2)均勻設計抽樣遺傳算法

給定交叉概率pc和突變概率pm,均勻設計抽樣遺傳算法如下：

(i)每次進行遺傳操作,以概率fi/Σfi復制Ai,其中fi是Ai的適應度值.

(ii)以賭輪法隨機取兩個染色體,以概率pc對其進行均勻設計抽樣交叉操作(產生n個后代,n為待定參數).

(iii)以概率pm進行變異遺傳操作.

(iv)把經過遺傳操作后得到的染色體都放到染色體池中,對新得到的染色體,計算其適應度值.若假定染色體的容量一定,當染色體的個體超過容量時,就將適應度小的染色體從池中刪去(或按a%進行刪除).

(v)進行上述的遺傳算法至第T代后(T是預先給定的常數),在第T代的染色體中取適應度最大的染色體,即為所求的染色體.

4 0/1背包問題的均勻設計抽樣遺傳算法求解

4.10/1背包問題的均勻設計抽樣遺傳算法.

均勻設計抽樣遺傳算法解決0/1背包問題,采用傳統的二進制編碼,符號同2中,求解過程為

1)隨機產生初始群體X(0).

2)利用賭輪法隨機進行遺傳算法的選擇、復制,

3)利用均勻設計抽樣遺傳算法進行交叉、變異等遺傳操作.

4)重復2),3)步至第T代后(T是預先給定的常數),在第T代的染色體中取適應度最大的染色體,即為所求的染色體.

4.2 求解過程及實驗結果分析.

對均勻設計抽樣遺傳算法、佳點集遺傳算法、簡單遺傳算法在同樣條件下(只是利用各自的交叉操作)解決0/1背包問題,并比較、分析實驗結果.

在P4 3.0G PC機器上,在Matlab 7.0計算平臺上,利用遺傳算法工具箱中“簡單遺傳算法”、文獻[2]中的“佳點集遺傳算法”和這里的“均勻設計抽樣遺傳算法”按文獻[2]中提供的測試用例以及按文獻[5]提供的模擬用例生成方法生成測試算例進行了計算比較.

1)文獻[2]中算例的價值V,體積W,以及背包容量C如下：

用傳統的簡單遺傳算法、佳點集遺傳算法和均勻設計抽樣遺傳算法分別對問題進行1000次求解,其中取交叉概率Pc=0.9,變異概率Pm=0.001,懲罰系數β=2.5,群體規模為100,終止代數為500,佳點集中的佳點個數取10(即取10個中使適應度最大的).結果見表1.

表1

表1中GA表示簡單遺傳算法;GGA表示佳點集遺傳算法;UDSGA表示均勻設計抽樣遺傳算法.

由以上數據表和在線、離線性能比較圖可以得出：均勻設計抽樣遺傳算法在搜索能力、收斂速度以及避免早熟等各項指標上均好于簡單遺傳算法和佳點集遺傳算法.

2)模擬結果

下面結合實例將簡單、佳點、均勻設計抽樣遺傳算法進行有效比較,實例中問題規模為50個變量,隨機產生系數值,按以下步驟生成一個背包問題,共生成10個.

(i)50個系數vi,wi在區間(0,999]內隨機產生.

(iii)若wi＜C,(i=1,2,…,l.)則結束;否則轉第(i)步.

圖1 離線性能比較圖

圖2 在線性能比較圖

表2

從上表中可以看到,簡單遺傳算法對于模擬的10個背包問題都沒有得到貪心算法的解,而佳點集遺傳算法對于模擬的10個問題有部分超出貪心算法的解,但對于均勻設計抽樣遺傳算法全部超出貪心算法解,并且在提高率上大大高于佳點集遺傳算法,所以,可以說均勻設計抽樣遺傳算法的全局搜索能力大大強于簡單遺傳算法和佳點集遺傳算法.

5 結 論

遺傳算法是一個具有定向制導的隨機搜索技術,其定向制導的原則是：導向以高適應度模式為祖先的“家族”方向,所以任何一種交叉操作都無非是在以其父代為“祖先”的“家族”中尋找一個適應值高的后代.現有的交叉算法：如單點交叉、多點交叉、樹交叉[6]等,都只能保證求到的后代落在上述的家族中,但其搜索適應值高的后代的能力不強;佳點集法利用求得的子集的均勻散布性,使它們最能代表其“家族”的性能,所以佳點集遺傳算法構造的交叉操作提高了搜索適應值高的后代的能力,但佳點集布點有方向性,并且不是統計意義下的抽樣,這導致了其整體搜索能力仍不夠強.均勻設計抽樣就克服了此不足,均勻設計抽樣所得的樣本具有同佳點集一樣的均勻散布性,并且每次取得的樣本集是隨機均勻散布的,這樣可以取到所有的格子點.所以均勻設計抽樣遺傳算法具有極強的整體搜索能力.實驗證明不管在求解精度上還是在求解速度上,均勻設計抽樣遺傳算法不僅優于GA算法,也優于佳點集遺傳算法,并能較好地避免早熟現象,收斂到最優解.

[1] 張鈴,張鈸.遺傳算法機理的研究[J].軟件學報,2000,11(7)：945-952.

[2] 張鈴,張鈸.佳點集遺傳算法[J].計算機學報,2001,24(9)：917-922.

[3] 華羅庚,王元.數論在近似分析中的應用[M].北京：科學出版社,1978.

[4] 張潤楚,王兆軍.均勻設計抽樣及其優良性質[J].應用概率統計,1996,12(4)：337-347.

[5] 王小平,曹立明.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社,2002.

[6] 吳少巖,張青富,陳火旺.基于家族優生學的進化算法[J].軟件學報,1997,8(2)：137-144.

[7] 陳國良,等.遺傳算法及其應用[M].北京：人民郵電出版社,1996.

Based on Genetic Algorithm Uniform Design Sampling Solution Knapsack Question

CH EN Ming-hua1, R EN Zhe2, Z HOU Ben-da1
(1.Dept.of Mathematics and Physics,West Anhui University,Lu’an 237012,China;
2.Dept.of Mathematics and Physics,Hefei University,Hefei 230022,China)

It is well known that the GA is a guided random search and the guiding direction always aims at the family whose ancestors have schemata with high fitness.Based on the results,the crossover operation in GA is redesigned by using the principle of uniform design sampling.Then a new Gacalled Genetic Algorithm based on Uniform Design Sampling is presented.The new GA is applied to solve the knapsack question.Compared to simple GA and Good Point GA for solving this problem,the simulation results show that the new GA has superiority in speed,accuracy and overcoming premature.

genetic algorithm(GA);uniform design sampling(UDS);genetic algorithm based on uniform design sampling(UDSGA)

TP301

A

1672-1454(2011)03-0044-06

2008-08-28

安徽省高校省級自然科學研究項目(KJ2007B152);安徽省教育廳自然科學研究項目(2005KJ222, 2006KJ046B);安徽省高校青年教師資助計劃項目(2007jq1179)