馬豐寧，謝 龍，鄭 重

(天津大學管理學院，天津 300072)

求解背包問題的基因屬性保留遺傳算法

馬豐寧，謝 龍，鄭 重

(天津大學管理學院，天津 300072)

遺傳算法是解決大規(guī)模背包問題的有效方法，在研究幾種有效的遺傳算法求解背包問題基礎上，注意到遺傳算法的進化代數(shù)對求解結果的影響大于群體規(guī)模，保持基因位數(shù)據(jù)的有效性，對進化效率有重大影響.提出了基因屬性保留遺傳算法(attribute gene-reserved genetic algorithm，AGGA)，將每一位基因的屬性差異，在不同代遺傳中加以保留，結合精英保留方法，很好地解決了提前收斂、GA欺騙問題，從很少的群體出發(fā)，就可以達到好的結果，實證了AGGA對背包問題的高效性，得到好于參考文獻的結果，并構造了150個物體的背包問題實例.

遺傳算法；簡單群體；基因屬性保留；精英保留策略；背包問題

背包問題(knapsack problem，KP)是計算科學中的一類非常經(jīng)典的NP-hard問題.對該問題的研究既有理論價值，又有實際應用背景，如項目選擇、投資組合、資源分配和貨物裝載等.求解 0-1背包問題的方法有許多種，由于該問題的解空間規(guī)模同問題規(guī)模呈指數(shù)關系，用動態(tài)規(guī)劃、回溯法、分支限界法等確定性算法不適合求解規(guī)模較大的 0-1背包問題[1-3].遺傳算法作為一種優(yōu)化算法，在大規(guī)模 0-1背包問題的求解上得到有效的應用，并有多種改進算法，如貪心算法[4]、佳點集算法[5]和主動進化算法[6]等.

目前各種改進的遺傳算法，是對交換、選擇和變異方法的改進，這些改進確實在提高算法效率上成果很大[7].筆者在研究各種有效的遺傳算法求解背包問題基礎上，注意到遺傳算法的進化代數(shù)對所述結果的影響大于群體規(guī)模，保持基因位數(shù)據(jù)差異的有效性，對進化效率有重大影響[8-12].

筆者在對諸多不同遺傳算法深入研究基礎上，通過大量試驗提出基因屬性保留遺傳算法(attribute gene-reserved genetic algorithm，AGGA).通過實例可以證明，設背包數(shù)量為n(即染色體的串長為n)，取初始群體容量為 L = 2 n，迭代次數(shù)取 K = 4 n，本算法可以得到好的效果.

1 改進的算法(AGGA)

KP問題的一般提法為：已知n個物品的容積及價值分別為 wi和 ci(1 ≤i≤n)，背包的最大容量限制為M，如何選擇物品裝入背包，使得在背包最大容量限制之內(nèi)，所裝入的物品的總價值最大，其嚴格的數(shù)學描述為新一代群體保留上一代的最佳解的選擇策略，稱為精英保留策略.

在以上定義的基礎上，AGGA具體實現(xiàn)方法描述如下：

(3) 輸出前 2L 項，比較結果(有時不同樣本可以得到相同最優(yōu)解)，結束.

以上算法有如下優(yōu)點：算法簡潔，保持優(yōu)化結果的群體優(yōu)勢，避免提前收斂，進化效率高.

(1) 步驟1基因屬性保留群體，能很好解決GA欺騙問題，其實質是對染色體編碼的一種修正過程，這種修正是每1位染色體都得有差異特征，從而避免在進化中有某位染色體缺少差異而導致不能繼續(xù)進化.

(2) 步驟3簡單群體能夠保持非冗余性，解決早熟問題，GA早熟的本質特征是指群體中的各個個體非常相似，導致搜索結果的不優(yōu).

(3) 步驟 5中，使用精英保留的策略，保留了進化的優(yōu)勢群體，而不僅是一個第t代的最優(yōu)解.本文方法保留了前 2L 個個體，這將大大提高進化效率.

2 實 證

為了比較 GGA[4]算法與 AGGA算法在求解 KP問題時表現(xiàn)出的不同性能，下面給出了3個KP問題實例，其中實例 1、2取自文獻[4]，該實例是一個被廣為引用的著名的問題實例，常用它來比較演化算法的優(yōu)劣；另一個關于150個物品的實例是按前2個實例的數(shù)據(jù)構建的.

1)KP問題實例1(50個物品)

物品的價值集C ＝{220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，72，70，69，66，65，63，60，58，56，50，30，20，15，10，8，5，3，1}.

物品的容積集W ＝{80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，25，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1}，背包的最大容量1,000，規(guī)模為d＝50.

2)KP問題實例2(100個物品)

物品的價值集C ＝{597，596，593，586，581，568，567，560，549，548，547，529，529，527，520，491，482，478，475，475，466，462，459，458，454，451，449，443，442，421，410，409，395，394，390，377，375，366，361，347，334，322，315，313，311，309，296，295，294，289，285，279，277，276，272，248，246，245，238，237，232，231，230，225，192，184，183，176，174，171，169，165，165，154，153，150，149，147，143，140，138，134，132，127，124，123，114，111，104，89，74，63，62，58，55，48，27，22，12，6}.

物品的容積集W ＝{54，183，106，82，30，58，71，166，117，190，90，191，205，128，110，89，63，6，140，86，30，91，156，31，70，199，142，98，178，16，140，31，24，197，101，73，169，73，92，159，71，102，144，151，27，131，209，164，177，177，129，146，17，53，164，146，43，170，180，171，130，183，5，113，207，57，13，163，20，63，12，24，9，42，6，109，170，108，46，69，43，175，81，5，34，146，148，114，160，174，156，82，47，126，102，83，58，34，21，14}，背包的最大容量 6 718，規(guī)模為d＝100.

3)KP問題實例3(150個物品)

該實例是用實例 1和實例 2的數(shù)據(jù)構造出 150個物體的背包問題.

物品的價值集C ＝{597，596，593，586，581，568，567，560，549，548，547，529，529，527，520，491，482，478，475，475，466，462，459，458，454，451，449，443，442，421，410，409，395，394，390，377，375，366，361，347，334，322，315，313，311，309，296，295，294，289，285，279，277，276，272，248，246，245，238，237，232，231，230，225，192，184，183，176，174，171，169，165，165，154，153，150，149，147，143，140，138，134，132，127，124，123，114，111，104，89，74，63，62，58，55，48，27，22，12，6，220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，72，70，69，66，65，63，60，58，56，50，30，20，15，10，8，5，3，1}.

物品的容積集W ＝{54，183，106，82，30，58，71，166，117，190，90，191，205，128，110，89，63，6，140，86，30，91，156，31，70，199，142，98，178，16，140，31，24，197，101，73，169，73，92，159，71，102，144，151，27，131，209，164，177，177，129，146，17，53，164，146，43，170，180，171，130，183，5，113，207，57，13，163，20，63，12，24，9，42，6，109，170，108，46，69，43，175，81，5，34，146，148，114，160，174，156，82，47，126，102，83，58，34，21，14，80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，25，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1}，背包的最大容量7,718，規(guī)模為d＝150.

對上述3個實例進行迭代計算，AGGA算法及其他算法的計算結果如表1所示.

表1 3種算法計算結果的比較Tab.1 Comparisons of computing results of three algorithms

表1列出了AGGA、GGA、SRA對實例1、實例2的計算結果比較.從表1中可以看出：對于實例1，本文給出的計算結果 3,119/1,000比文獻[4]中的 GGA算法和文獻[13]中的 SRA算法求得的結果更優(yōu).對于實例3，運用本文提出的AGGA算法的最優(yōu)計算結果為 30,081/7,718，將本例 3在專業(yè)線性規(guī)劃軟件Lingo9.0上面進行計算，計算結果為 30,085/7,718，本文結果與最優(yōu)解差為 0.1%.用遺傳算法最優(yōu)距[14]概念來看本文結果“優(yōu)”的程度，其最優(yōu)距為 4 ×2-150，是相當滿意的解.遺傳算法與其他算法相比，構造簡單，由于是并行計算，可以同時得到一批好的解，限于篇幅，在表1中只列出了每個問題的前3個解.

3 結 語

本文中提出的基因屬性保留遺傳算法AGGA，在計算背包問題時很好地解決了提前收斂和 GA欺騙問題，從很少的群體出發(fā)，就可以達到好的結果.本文中給出了背包問題規(guī)模與初始群體、進化代數(shù)的確定關系，即設背包的物體數(shù)量為n，可取初始群體為2n，進化次數(shù)為4n，這是非常高效的遺傳算法計算參數(shù).本文研究方法對其他類似問題有很好的借鑒意義.

［1］寧愛兵，馬 良. 0/1背包問題快速降價法及其應用[J].系統(tǒng)工程理論方法應用，2005，14(4)：373-374.

Ning Aibing，Ma Liang. A quick reduction algorithm and its applications for 0/1-knapsack problem [J].Systems Engineering Theory Methodology Application，2005，14(4)：373-374(in Chinese).

［2］李鳴山，鄭海虹. 0-1背包問題的多重分支-限界算法[J]. 武漢測繪科技大學學報，1995，20(1)：84-85.

Li Mingshan，Zheng Haihong. A multi-branch-and-bound algorithm for 0-1 knapsack problems [J].Journal of Wuhan Technical University of Surveying and Mapping，1995，20(1)：84-85(in Chinese).

［3］王粉蘭，孫小玲. 不可分離凸背包問題的拉格朗日分解和區(qū)域分割方法[J]. 運籌學學報，2004，8(4)：46-47.

Wang Fenlan，Sun Xiaoling. A Lagrangian decomposition and domain cut algorithm for nonseparable convex knapsack problems [J].OR Transactions，2004，8(4)：46-47(in Chinese).

［4］賀毅朝，劉坤起，張翠軍，等. 求解背包問題的貪心遺傳算法及其應用[J]. 計算機工程與設計，2007，28(11)：2656-2657.

He Yichao，Liu Kunqi，Zhang Cuijun，et al. Greedy genetic algorithm for solving knapsack problems and its applications [J].Computer Engineering and Design，2007，28(11)：2656-2657(in Chinese).

［5］張 鈴，張 鈸. 佳點集遺傳算法[J]. 計算機學報，2001，24(9)：918-921.

Zhang Ling，Zhang Bo. Good point set based genetic algorithm [J].Chinese Journal of Computers，2001，24(9)：918-921(in Chinese).

［6］史 亮，董槐林，龍 飛，等. 求解大規(guī)模 0-1背包問題的主動進化遺傳算法[J]. 計算機工程，2007，33(13)：31-33.

Shi Liang，Dong Huailin，Long Fei，et al. Genetic algorithm based on active evolution for large scale 0-1 knapsack problem[J].Computer Engineering，2007，33(13)：31-33(in Chinese).

［7］李敏強，寇紀淞，林 丹，等.遺傳算法的基本理論與應用[M]. 北京：科學出版社，2002.

Li Minqiang，Kou Jisong，Lin Dan，et al.The Basic Theory of Genetic Algorithm and Application[M]. Beijing：Science Press，2002(in Chinese).

［8］劉西奎，李 艷，許 進. 背包問題的遺傳算法求解[J]. 華中科技大學學報，2002，30(6)：90.

Liu Xikui，Li Yan，Xu Jin. Solve knapsack problem by semi-feasible genetic algorithm[J].Journal of HuazhongUniversity of Science and Technology，2002，30(6)：90(in Chinese).

［9］宋海洲，魏旭真. 求解 0-1背包問題的混合遺傳算法[J]. 華僑大學學報：自然科學版，2006，27(1)：16-19.

Song Haizhou，Wei Xuzhen. A hybrid genetic algorithm for solving 0-1 knapsack problem[J].Journal of Huaqiao University：Natural Science，2006，27(1)：16-19(in Chinese).

［10］李慶華，潘 軍，李肯立. 背包問題的二分網(wǎng)格算法[J]. 計算機科學，2005，32(6)：217-220.

Li Qinghua，Pan Jun，Li Kenli. A dimidiate grid algorithm for the unbounded knapsack problem[J].Computer Science，2005，32(6)：217-220(in Chinese).

［11］霍紅衛(wèi)，許 進，保 錚. 基于遺傳算法的 0/1背包問題求解[J]. 西安電子科技大學學報，1999，26(4)：494-496.

Huo Hongwei，Xu Jin，Bao Zheng. Solving 0/1 knapsack problem by using genetic algorithm[J].Journal of Xidian University，1999，26(4)：494-496(in Chinese).

［12］曾 智，楊小帆，陳 靜，等. 求解多維 0-1背包問題的一種改進的遺傳算法[J]. 計算機科學，2006，33(7)：220-221.

Zeng Zhi，Yang Xiaofan，Chen Jing，et al. An improved genetic algorithm for the multidimensional 0-1 knapsack problem[J].Computer Science，2006，33(7)：220-221(in Chinese).

［13］Li Kangshun，Jia Yuzhen，Zhang Wensheng，et al. A new method for solving 0/1 Knapsack problem based on evolutionary algorithm with schema replaced [C]//Proceedings of the IEEE International Conference on Automation and Logistics. Qingdao，China，2008：2569-2571.

［14］馬豐寧，寇紀淞. 遺傳算法中滿意度與最優(yōu)距[J]. 系統(tǒng)工程理論與實踐，1998，18(1)：18-21.

Ma Fengning，Kou Jisong. The “satisfactory degree” and“optimum radius” in genetic algorithms theory [J].Systems Engineering Theory and Practice，1998，18(1)：18-21(in Chinese).

Attribute Gene-Reserved Genetic Algorithm for Solving Knapsack Problem

MA Feng-ning，XIE Long，ZHENG Zhong
(School of Management，Tianjin University，Tianjin 300072，China)

The genetic algorithm is an effective means to solve the large-scale knapsack problem. By studying several effective genetic algorithms，we find that the evolutional algebra of genetic algorithm has much more impact on optimal results than population size does. In addition，maintaining the effectiveness of gene-bit data also has a significant impact on the efficiency of evolution. In this paper，we propose the attribute gene-reserved genetic algorithm(AGGA)，which，combined with the genetic algorithm of elitist strategy，can reserve the difference of each genebit data attribute in genetics of different generations，and easily solve the early convergence and GA deceptive problem. Just from a very small number of groups，we can finally achieve good results，justify the high efficiency of improved algorithm and gain a calculation result better than the ones in relevant references. Then we construct a calculation example which contains 150 backpacks.

genetic algorithm；simple colony；attribute gene-reserved；elite reservation strategy；knapsack problem

TP301.6

A

0493-2137(2010)11-1020-05

2009-04-01；

2009-07-19.

國家自然科學基金資助項目（70571057）.

馬豐寧（1958— ），男，博士，副教授.

馬豐寧，fnmmm@vip.sina.com.