一種有效求解多維背包問題的遺傳算法

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

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

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

4、與wij有聯(lián)系，pj=E nj=1wij/m+500qi,j=1,n。qi是隨機產(chǎn)生的一個范圍為（0，1）的實 數(shù)。3.2MKPGA的計算結(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）上對每 一個實例求解10次，每次產(chǎn)生106個個體后終止，即算法3中的 tmax=106，取10次中最好1次的解作為MKPGA的所求解，且把該 次求解所花時間作為計算時間。表1根據(jù)不同的m、n

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

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

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

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

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

10、題都是 有效的，且都能獲得高質(zhì)量的解。計算結(jié)果的平均%gap為0.543，僅 比同樣使用遺傳算法的BCGA大0.002，而優(yōu)于其它算法或軟件的計 算結(jié)果，這也說明了 GA對多維背包問題求解十分有效。雖然MKPGA計算結(jié)果的平均%gap僅為0.543，但還有大部分 背包問題的實例不能求出最優(yōu)解，這說明多維背包問題仍難以解決。 遺傳參數(shù)對遺傳算法影響很大，如果參數(shù)選擇適當，會使MKPGA的 性能更加優(yōu)越，所以對遺傳參數(shù)的研究將會是探討MKPGA求解多維 背包問題的下一步工作。參考文獻：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é)報，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