陳明華, 任 哲, 周本達(dá)

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

基于均勻設(shè)計(jì)抽樣遺傳算法求解背包問(wèn)題

陳明華1, 任 哲2, 周本達(dá)1

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

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

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

1 引 言

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

2 0/1背包問(wèn)題描述

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

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

3 均勻設(shè)計(jì)抽樣遺傳算法

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

3.1 均勻設(shè)計(jì)抽樣.

均勻設(shè)計(jì)抽樣這樣進(jìn)行[4]：

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

3.2 均勻設(shè)計(jì)抽樣遺傳算法.

1)均勻設(shè)計(jì)抽樣交叉操作

設(shè)在傳統(tǒng)的GA算法基礎(chǔ)上,在進(jìn)行過(guò)復(fù)制后,對(duì)池中的元素按賭輪法選擇兩個(gè)元素A1,A2進(jìn)行均勻設(shè)計(jì)抽樣交叉操作.

令

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

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

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

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

上述交叉操作,稱為均勻設(shè)計(jì)抽樣交叉操作.

2)均勻設(shè)計(jì)抽樣遺傳算法

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

(i)每次進(jìn)行遺傳操作,以概率fi/Σfi復(fù)制Ai,其中fi是Ai的適應(yīng)度值.

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

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

(iv)把經(jīng)過(guò)遺傳操作后得到的染色體都放到染色體池中,對(duì)新得到的染色體,計(jì)算其適應(yīng)度值.若假定染色體的容量一定,當(dāng)染色體的個(gè)體超過(guò)容量時(shí),就將適應(yīng)度小的染色體從池中刪去(或按a%進(jìn)行刪除).

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

4 0/1背包問(wèn)題的均勻設(shè)計(jì)抽樣遺傳算法求解

4.10/1背包問(wèn)題的均勻設(shè)計(jì)抽樣遺傳算法.

均勻設(shè)計(jì)抽樣遺傳算法解決0/1背包問(wèn)題,采用傳統(tǒng)的二進(jìn)制編碼,符號(hào)同2中,求解過(guò)程為

1)隨機(jī)產(chǎn)生初始群體X(0).

2)利用賭輪法隨機(jī)進(jìn)行遺傳算法的選擇、復(fù)制,

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

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

4.2 求解過(guò)程及實(shí)驗(yàn)結(jié)果分析.

對(duì)均勻設(shè)計(jì)抽樣遺傳算法、佳點(diǎn)集遺傳算法、簡(jiǎn)單遺傳算法在同樣條件下(只是利用各自的交叉操作)解決0/1背包問(wèn)題,并比較、分析實(shí)驗(yàn)結(jié)果.

在P4 3.0G PC機(jī)器上,在Matlab 7.0計(jì)算平臺(tái)上,利用遺傳算法工具箱中“簡(jiǎn)單遺傳算法”、文獻(xiàn)[2]中的“佳點(diǎn)集遺傳算法”和這里的“均勻設(shè)計(jì)抽樣遺傳算法”按文獻(xiàn)[2]中提供的測(cè)試用例以及按文獻(xiàn)[5]提供的模擬用例生成方法生成測(cè)試算例進(jìn)行了計(jì)算比較.

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

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

表1

表1中GA表示簡(jiǎn)單遺傳算法;GGA表示佳點(diǎn)集遺傳算法;UDSGA表示均勻設(shè)計(jì)抽樣遺傳算法.

由以上數(shù)據(jù)表和在線、離線性能比較圖可以得出：均勻設(shè)計(jì)抽樣遺傳算法在搜索能力、收斂速度以及避免早熟等各項(xiàng)指標(biāo)上均好于簡(jiǎn)單遺傳算法和佳點(diǎn)集遺傳算法.

2)模擬結(jié)果

下面結(jié)合實(shí)例將簡(jiǎn)單、佳點(diǎn)、均勻設(shè)計(jì)抽樣遺傳算法進(jìn)行有效比較,實(shí)例中問(wèn)題規(guī)模為50個(gè)變量,隨機(jī)產(chǎn)生系數(shù)值,按以下步驟生成一個(gè)背包問(wèn)題,共生成10個(gè).

(i)50個(gè)系數(shù)vi,wi在區(qū)間(0,999]內(nèi)隨機(jī)產(chǎn)生.

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

圖1 離線性能比較圖

圖2 在線性能比較圖

表2

從上表中可以看到,簡(jiǎn)單遺傳算法對(duì)于模擬的10個(gè)背包問(wèn)題都沒(méi)有得到貪心算法的解,而佳點(diǎn)集遺傳算法對(duì)于模擬的10個(gè)問(wèn)題有部分超出貪心算法的解,但對(duì)于均勻設(shè)計(jì)抽樣遺傳算法全部超出貪心算法解,并且在提高率上大大高于佳點(diǎn)集遺傳算法,所以,可以說(shuō)均勻設(shè)計(jì)抽樣遺傳算法的全局搜索能力大大強(qiáng)于簡(jiǎn)單遺傳算法和佳點(diǎn)集遺傳算法.

5 結(jié) 論

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

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

[2] 張鈴,張鈸.佳點(diǎn)集遺傳算法[J].計(jì)算機(jī)學(xué)報(bào),2001,24(9)：917-922.

[3] 華羅庚,王元.數(shù)論在近似分析中的應(yīng)用[M].北京：科學(xué)出版社,1978.

[4] 張潤(rùn)楚,王兆軍.均勻設(shè)計(jì)抽樣及其優(yōu)良性質(zhì)[J].應(yīng)用概率統(tǒng)計(jì),1996,12(4)：337-347.

[5] 王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社,2002.

[6] 吳少巖,張青富,陳火旺.基于家族優(yōu)生學(xué)的進(jìn)化算法[J].軟件學(xué)報(bào),1997,8(2)：137-144.

[7] 陳國(guó)良,等.遺傳算法及其應(yīng)用[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

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