1、一種有效求解多維背包問題的遺傳算法摘要：就多維背包問題的求解，提出一個(gè)基于遺傳算法的啟發(fā)式算法 (MKPGA)。該算法中加入了一個(gè)利用問題特性知識的啟發(fā)式修復(fù)算 子以幫助求解。測試實(shí)例使用270個(gè)不同特性的多維背包問題，實(shí)驗(yàn) 結(jié)果表明，該算法對多維背包問題的求解十分有效，能獲得不同特性 問題的高質(zhì)量解。關(guān)鍵詞：遺傳算法;多維背包問題;貪婪算法遺傳算法，是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過 程的計(jì)算模型，對它的研究起源于20世紀(jì)70年代初，由美國Michigan 大學(xué)的J.Holland教授于1975年正式提出GA的主要特點(diǎn)是群體搜索 策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息

2、。它尤其 適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于 組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域，是 21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。2求解MKP的遺傳算法設(shè) 計(jì)MKPGA使用了一個(gè)基于簡單貪婪算法的修復(fù)算子來修復(fù)交 叉、變異操作后可能產(chǎn)生違反背包約束的不可行解。雖然在標(biāo)準(zhǔn)遺傳 算法中并未提到修復(fù)算子的使用，但根據(jù)不同問題特性設(shè)計(jì)的修復(fù)算 子被廣泛應(yīng)用在解決不同問題的遺傳算法中。MKPGA所采用的策略 描述如下：聯(lián)賽選擇方法；一致交叉；物品數(shù)小于500時(shí)變異 概率取2/個(gè)體基因串長位，當(dāng)物品數(shù)等于500時(shí)，變異概率取3/個(gè) 體串長度；不允許種群中有相同的個(gè)

3、體；每次迭代只產(chǎn)生一個(gè)不 同于當(dāng)前種群的新個(gè)體，如果新個(gè)體比當(dāng)前種群中最差的個(gè)體好，則 替換掉該最差個(gè)體。3計(jì)算實(shí)驗(yàn)3.1實(shí)例本文使用的測試實(shí)例是由Beasley和Chu所提供的270個(gè)多維 背包問題。其中約束個(gè)數(shù)m包括5、10和30，物品數(shù)量n包括100、 250和500，每一組m-n各有30個(gè)問題。下面介紹這270個(gè)實(shí)例的生 成方法。物品j消耗資源i的量wij為一個(gè)均勻分布在區(qū)間（0，1 000） 上的整數(shù)。對于每一個(gè)m-n的組合，每個(gè)資源約束bi=a E nj=1wij， a是問題的緊密比，前十個(gè)問題的a取0.25,接下來十個(gè)問題的a取 0.50，最后十個(gè)問題的a取0.75。物品的價(jià)值p

4、與wij有聯(lián)系，pj=E nj=1wij/m+500qi,j=1,n。qi是隨機(jī)產(chǎn)生的一個(gè)范圍為（0，1）的實(shí) 數(shù)。3.2MKPGA的計(jì)算結(jié)果由于很多問題的最優(yōu)解還不知道，所以采用100 （松弛LP最 優(yōu)解-所求最優(yōu)解）/（松弛LP最優(yōu)解）的值對所求解的評估，記 %gap。顯然，%gap越小，該解就越接近最優(yōu)解。使用MKPGA在 普通PC （CPU為AMD速龍64位3 000+ 1.8GHz，內(nèi)存512M）上對每 一個(gè)實(shí)例求解10次，每次產(chǎn)生106個(gè)個(gè)體后終止，即算法3中的 tmax=106，取10次中最好1次的解作為MKPGA的所求解，且把該 次求解所花時(shí)間作為計(jì)算時(shí)間。表1根據(jù)不同的m、n

5、和a對MKPGA 的計(jì)算時(shí)間進(jìn)行統(tǒng)計(jì)，表中的有關(guān)數(shù)據(jù)為m、n和a相同的10個(gè)實(shí) 例的平均值（下同）。3.2.1與Beasley和Chu的結(jié)果比較表1將MKPGA與Beasley和Chu的GA（BCGA）的計(jì)算結(jié)果進(jìn) 行比較，前三列是問題的規(guī)模（m-n）和緊密率a，接下來兩列是BCGA 計(jì)算結(jié)果，最后兩列是MKPGA計(jì)算結(jié)果。觀察表1可知，隨著m、 n的增大，問題的難度也隨著增大，且%gap與緊密率a有關(guān)，當(dāng)。 越大時(shí)，%gap越小。MKPGA計(jì)算結(jié)果的平均%gap僅為0.543，表2 的對比說明了 MKPGA同BCGA 一樣，對求解大規(guī)模的MKP實(shí)例十分 有效。在這270個(gè)實(shí)例中，MKPGA的

6、計(jì)算結(jié)果有64個(gè)比BCGA的好， 67個(gè)比BCGA的差，相等的有139個(gè)。其中MKPGA比BCGA差的解 主要集中在物品數(shù)為500的90表1MKPGA與BCGA的計(jì)算結(jié)果對比 表問題MNa BCGA平均%gap最優(yōu)解個(gè)數(shù)MKPGA平均%gap最優(yōu)解個(gè) 數(shù) 51000.25從表1可以看出，對物品數(shù)n小于500的6組實(shí)例的求解，MKPGA 要略優(yōu)于BCGA。由于5-100這組實(shí)例由于規(guī)模相對較小，MKPGA和 BCGA都能找到全部最優(yōu)解。對于5-250和10-100這兩組實(shí)例，MKPGA 找到的最優(yōu)解都比BCGA多，性能要好于BCGA。對于其它三組實(shí)例， 雖然不能確定MKPGA找到的就是最優(yōu)解，但

7、從%gap的對比可以看出， MKPGA的%gap小于BCGA的%gap，說明MKPGA的解更接近于最優(yōu) 解。對物品數(shù)n等于500這三組實(shí)例的求解，MKPGA則不如BCGA，特別是30-500這組實(shí)例，MKPGA與BCGA的差距相對于其它各組大，對于5-500這組實(shí)例，MKPGA的平均%gap略高于BCGA,而對于10-500 這組實(shí)例，MKPGA和BCGA的平均%gap 一樣。綜上所述，MKPGA對大規(guī)模背包問題的求解要略優(yōu)于BCGA，而 對于超大規(guī)模的背包問題，MKPGA的性能則不如BCGA。雖然MKPGA 的平均%gap比BCGA的大0.002,但在部分實(shí)例的求解中，MKPGA能 找到比B

8、CGA好的解，只是在求解物品數(shù)為500的實(shí)例上略差于 BCGA，可以說MKPGA與BCGA的整體性能基本一樣。3.2.2與數(shù)學(xué)軟件Lingo8的結(jié)果比較Lingo是用來求解線性和非線性優(yōu)化問題的簡易工具。利用 Lingo高效的求解器可快速求解并分析結(jié)果。使用Lingo8對270個(gè)多 維背包問題進(jìn)行求解，如果運(yùn)算時(shí)間等于900秒時(shí)還沒找到最優(yōu)解， 則停止運(yùn)算，用當(dāng)前的解作為Lingo8的求解。表2是MKPGA與Lingo8 計(jì)算結(jié)果的比較。從表2可以看出，對于相同的實(shí)例，MKPGA的計(jì) 算結(jié)果都比Lingo8的計(jì)算結(jié)果好，整體性能優(yōu)于Lingo8。4.3與其它啟發(fā)式算法的結(jié)果比較文獻(xiàn)1中還提到運(yùn)

9、用其它啟發(fā)式算法對這270個(gè)實(shí)例進(jìn)行求 解的計(jì)算結(jié)果。本文引用了文獻(xiàn)1中的有關(guān)數(shù)據(jù)與MKPGA的計(jì)算結(jié) 果進(jìn)行比較，并列于表3中。這些算法包括：M&Q(Magazine and Oguz， 1984)、V&Z(Volgenant and Zoon，1990)、MKHEUR(Pirkul，1987)。由表4可知，MKPGA的解都比這些啟發(fā)式算法的解要好得多。 說明MKPGA對多維背包問題的求解其它啟發(fā)式算法有效。5結(jié)束語本文針對多維背包問題的特性，設(shè)計(jì)了一個(gè)帶有修復(fù)算子的遺 傳算法MKPGA。并使用該算法對270個(gè)大規(guī)模的多維背包問題進(jìn)行 求解，計(jì)算結(jié)果表明，該算法對于不同m-n組合的多維背包問

10、題都是 有效的，且都能獲得高質(zhì)量的解。計(jì)算結(jié)果的平均%gap為0.543，僅 比同樣使用遺傳算法的BCGA大0.002，而優(yōu)于其它算法或軟件的計(jì) 算結(jié)果，這也說明了 GA對多維背包問題求解十分有效。雖然MKPGA計(jì)算結(jié)果的平均%gap僅為0.543，但還有大部分 背包問題的實(shí)例不能求出最優(yōu)解，這說明多維背包問題仍難以解決。 遺傳參數(shù)對遺傳算法影響很大，如果參數(shù)選擇適當(dāng)，會(huì)使MKPGA的 性能更加優(yōu)越，所以對遺傳參數(shù)的研究將會(huì)是探討MKPGA求解多維 背包問題的下一步工作。參考文獻(xiàn)：P C CHU,J E BEASLEY . A Genetic Algorithm for the Multidi

11、mensional Knapsack Problem J. Journal of Heuristics， 1998(4)： 63-86.姚瑞楓.多維0_1背包問題的遺傳算法研究J.武漢科技學(xué)院 學(xué)報(bào)，2003 (2).陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用M.北京: 人民郵電出版社，1996.劉勇，康立山，陳毓屏.非數(shù)值并行算法(第2冊)M.北京: 科學(xué)出版社，1997.J PUCHINGER，G R RAIDL，ULRICH PFERSCHY. The Core Concept for the Multidimensional Knapsack Problem M. Lecture Notes inComputer Science, USA, Springer Berlin / Heidelberg, 2