求解背包問題的基因?qū)傩员Ａ暨z傳算法

馬豐寧，謝 龍，鄭 重

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

求解背包問題的基因?qū)傩员Ａ暨z傳算法

馬豐寧，謝 龍，鄭 重

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

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

遺傳算法；簡(jiǎn)單群體；基因?qū)傩员Ａ?；精英保留策略；背包問題

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

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

筆者在對(duì)諸多不同遺傳算法深入研究基礎(chǔ)上，通過大量試驗(yàn)提出基因?qū)傩员Ａ暨z傳算法(attribute gene-reserved genetic algorithm，AGGA).通過實(shí)例可以證明，設(shè)背包數(shù)量為n(即染色體的串長(zhǎng)為n)，取初始群體容量為 L = 2 n，迭代次數(shù)取 K = 4 n，本算法可以得到好的效果.

1 改進(jìn)的算法(AGGA)

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

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

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

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

(1) 步驟1基因?qū)傩员Ａ羧后w，能很好解決GA欺騙問題，其實(shí)質(zhì)是對(duì)染色體編碼的一種修正過程，這種修正是每1位染色體都得有差異特征，從而避免在進(jìn)化中有某位染色體缺少差異而導(dǎo)致不能繼續(xù)進(jìn)化.

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

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

2 實(shí) 證

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

1)KP問題實(shí)例1(50個(gè)物品)

物品的價(jià)值集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問題實(shí)例2(100個(gè)物品)

物品的價(jià)值集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問題實(shí)例3(150個(gè)物品)

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

物品的價(jià)值集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.

對(duì)上述3個(gè)實(shí)例進(jìn)行迭代計(jì)算，AGGA算法及其他算法的計(jì)算結(jié)果如表1所示.

表1 3種算法計(jì)算結(jié)果的比較Tab.1 Comparisons of computing results of three algorithms

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

3 結(jié) 語

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

［1］寧愛兵，馬 良. 0/1背包問題快速降價(jià)法及其應(yīng)用[J].系統(tǒng)工程理論方法應(yī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]. 武漢測(cè)繪科技大學(xué)學(xué)報(bào)，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]. 運(yùn)籌學(xué)學(xué)報(bào)，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］賀毅朝，劉坤起，張翠軍，等. 求解背包問題的貪心遺傳算法及其應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(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］張 鈴，張 鈸. 佳點(diǎn)集遺傳算法[J]. 計(jì)算機(jī)學(xué)報(bào)，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背包問題的主動(dòng)進(jìn)化遺傳算法[J]. 計(jì)算機(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］李敏強(qiáng)，寇紀(jì)淞，林 丹，等.遺傳算法的基本理論與應(yīng)用[M]. 北京：科學(xué)出版社，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ìn). 背包問題的遺傳算法求解[J]. 華中科技大學(xué)學(xué)報(bào)，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]. 華僑大學(xué)學(xué)報(bào)：自然科學(xué)版，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]. 計(jì)算機(jī)科學(xué)，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)，許 進(jìn)，保 錚. 基于遺傳算法的 0/1背包問題求解[J]. 西安電子科技大學(xué)學(xué)報(bào)，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ìn)的遺傳算法[J]. 計(jì)算機(jī)科學(xué)，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］馬豐寧，寇紀(jì)淞. 遺傳算法中滿意度與最優(yōu)距[J]. 系統(tǒng)工程理論與實(shí)踐，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.

國(guó)家自然科學(xué)基金資助項(xiàng)目（70571057）.

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

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