朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學 自動化學院，廣州 510006）

遺傳大洪水演算法求解多維背包問題

朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學 自動化學院，廣州 510006）

由于遺傳算法具有較強的全局搜索能力，但在實際應用中容易產(chǎn)生早熟收斂現(xiàn)象，且進化后期搜索效率較低，而大洪水演算法是求解組合優(yōu)化問題的獨特算法，結合兩者的優(yōu)點，形成基于遺傳算法的大洪水演算法（Genetic Great Deluge Algorithm，GGDA），然后應用該混合算法求解不同規(guī)模的多維背包問題（Multidimensional Knapsack Rroblem，MKR），求解結果表明提出的算法是簡單有效的，優(yōu)于標準遺傳算法和大洪水演算法。

多維背包問題；大洪水演算法；遺傳算法

多維背包問題［1］已經(jīng)被證明是NR-hard問題，而且有廣泛的應用背景，包括資本預算、存儲分配、分布式計算系統(tǒng)中分配處理器和數(shù)據(jù)庫及貨物裝載等。所以本文研究的多維背包問題具有實際應用意義。目前，多維背包問題也得到了廣泛的研究。喻學才等人［2］提出了一種計算復雜性較低而求解性能較好的改進蟻群算法求解多維背包問題，實驗結果表明新算法耗用時間少且解的價值更高；冀俊忠等人［3］提出了一種高性能的蟻群求解算法，將信息素更新和隨機搜索機制的改進相融合，避免蟻群算法求解多維背包問題存在的迭代次數(shù)多和精度低的不足，實驗表明，新算法優(yōu)于蟻群算法；賀一等人［4］構造了基于雙禁忌表的禁忌搜索算法求解多維0-1背包問題，證明了算法是有效可行的；劉勇等人［5］將元胞及其鄰居解引入到算法中來保持種群的多樣性，且利用元胞的演化規(guī)則進行局部優(yōu)化，結果表明提出的元胞微粒群算法有良好的全局優(yōu)化能力；王凌等人［6］提出一種基于分布估計算法的混合求解算法求解多維背包問題，基于標準測試集的仿真結果和算法比較驗證了提出的混合算法的有效性和魯棒性；杜巍等人［7］針對遺傳算法求解復雜組合優(yōu)化問題時易出現(xiàn)早熟收斂和喪失種群多樣性，提出了二進制編碼小世界算法，應用該算法求解多維背包問題，結果表明具有解決復雜組合優(yōu)化問題的潛力；楊廣益等人［8］提出了一種改進的分布估計算法-松弛互補分布估計算法，求解多維背包問題的結果表明，算法在較短時間內(nèi)能找到最好解，證明了該算法是一種較好的演化算法；Chaitr S等人［9］應用禁忌搜索算法求解多選擇多維背包問題，將簡單的貪婪法則引入初始解，結果證明提出的算法優(yōu)于傳統(tǒng)的啟發(fā)式算法；Murat Ersen Berberler等人［10］應用提出的遺傳算法求解MKR，與傳統(tǒng)遺傳算法不同的是，其初始解并不是隨機產(chǎn)生的，實驗證明該算法能搜索到最優(yōu)解。

1 多維背包問題

多維背包問題可以這樣描述：假設我們需要從許多物品中選擇一些來填充一個背包。存在n個不同的物品可以使用，每個物品j具有重量wj、體積vj和費用cj。背包可以承重的上限是W，容積為V。問題是如何尋找最優(yōu)的方案在滿足背包承重和容積的約束條件下最大化總費用。

式（1）為目標函數(shù)，求所裝載的貨物總價值最大；式（2）為約束條件，有載重約束、容積約束及xj的取整非負約束。

2 遺傳大洪水演算法

2.1 大洪水演算法

大洪水演算法在1993年由Dueck［11-14］提出。若鄰居解的目標函數(shù)值小于當前的邊界值LEVEL，那么該鄰居解將被接受。初始的邊界值可以設定為初始解的目標函數(shù)值。在搜索過程中，邊界值的單調(diào)下降，每次下降的幅度UR是算法的重要參數(shù)，它象征水平面升高的速度。大洪水演算法最終獲取解的質(zhì)量和運算時間的長短只依賴于UR參數(shù)的選取。UR值太小，算法會耗費太長時間求出高質(zhì)量解；UR值太大，算法雖耗時短但求解質(zhì)量不高。一般將UR值設定小于當前解的目標函數(shù)值與邊界值LEVEL的平均差距的1%。

大洪水演算法的偽程序

INRUT：邊界值LEVEL

s=s0；

Choose the rain speed UR；

Choose the initialwater level LEVEL；

REREAT

Generate a random neighbor s'；

IF f（s'）＜LEVEL THEN s=s'；LEVEL=LEVEL-UR；

UNTIL stopping condition met

OUTRUT：已找到的最優(yōu)解

2.2 遺傳大洪水演算法流程圖

求解步驟如下：

1）設定控制參數(shù)，初始化種群。

2）計算各個體的適應度值。

3）進行遺傳操作：選擇、交叉和變異。此例中，采用輪盤賭選擇、均勻交叉和單點變異。

4）計算新種群的個體適應度值，并將其與大洪水演算法的邊界值相比較。

5）如果迭代次數(shù)達到最大，執(zhí)行6）；否則，執(zhí)行3）。

6）目標函數(shù)值小于邊界值，則接受當前解，結束，輸出結果；否則不斷下降邊界值，迭代次數(shù)加1，執(zhí)行3）。

遺傳大洪水演算法流程圖如圖1所示?？梢姡谶M化初期，應用遺傳算法對解空間進行搜索，在進化后期，應用大洪水演算法的邊界值與前期產(chǎn)生的新種群的目標函數(shù)值比較，將多維背包優(yōu)化問題的全局最優(yōu)解看作山峰最高的頂端，那么求解算法就是登山者在一片連綿的山峰中尋找最高頂端的策略。

2.3 遺傳大洪水演算法流程圖

求解步驟：

1）設定控制參數(shù)，初始化種群。

2）計算各個體的適應度值。

3）進行遺傳操作：選擇、交叉和變異。此例中，采用輪盤賭選擇、均勻交叉和單點變異。

4）計算新種群的個體適應度值，并將其與大洪水演算法的邊界值相比較。

5）如果迭代次數(shù)達到最大，執(zhí)行6）；否則，執(zhí)行3）。

6）目標函數(shù)值小于邊界值，則接受當前解，結束，輸出結果；否則不斷下降邊界值，迭代次數(shù)加1，執(zhí)行3）。

遺傳大洪水演算法流程圖如圖1所示?？梢?，在進化初期，應用遺傳算法對解空間進行搜索，在進化后期，應用大洪水演算法的邊界值與前期產(chǎn)生的新種群的目標函數(shù)值比較，將多維背包優(yōu)化問題的全局最優(yōu)解看作山峰最高的頂端，那么求解算法就是登山者在一片連綿的山峰中尋找最高頂端的策略。

3 仿真分析

3.1 實驗數(shù)據(jù)

已知：貨車載重為65 t，容積為55 m3，可裝載20種貨物，每種貨物最多6件，貨物的單位重量、單位價值和單位體積如表1所示。

建立數(shù)學模型：

（1）決策變量。

貨車裝載編號為i的貨物xi（i=1，2，...，20）。

（2）目標函數(shù)。

max z=3x1+7x2+x3+4x4+2x5+5x6+2x7+4x8+2x9+x10+3x11+7x12+11x13+14x14+ 3x15+5x16+2x17+3x18+4x19+x20

（3）約束條件。

3.2 應用三種算法求解MKP

GA的參數(shù)設置：初始種群pop-size=30，交叉概率pc=0.85，變異概率pm=0.01，最大迭代次數(shù)max gen=500，運行30次。

GDA的參數(shù)設置：UP=0.01，最大迭代次數(shù)max gen=500，運行30次。

GGDA的參數(shù)設置：初始種群pop-size=30，交叉概率pc=0.85，變異概率pm=0.01，最大迭代次數(shù)max gen=500，運行30次。

在Intel（R）CoreTMi3 CRU 2.53 GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7的RC機上采用Matlab R2010b編程實現(xiàn)。

求解結果：

1）裝載貨物的最大價值/千元：499.00；

2）裝載貨物的總重量/t：64.50；

3）裝載貨物的總體積/m3：54.90。

求解結果：三種算法求解MKR的結果如表3所示，三種算法求解的一次優(yōu)化過程如圖2所示，隨機產(chǎn)生不同規(guī)模的多維背包問題模型，求解結果如表4所示?？芍ㄟ^三種算法都可以求得最優(yōu)解，但是GGDA優(yōu)于GDA和GA，GGDA收斂速度高，穩(wěn)定性更強，且求解最優(yōu)解的耗時最少；表4更體現(xiàn)出了GGDA的優(yōu)勢。

4 結語

大洪水演算法是求解組合優(yōu)化問題的獨特算法，而遺傳算法具有較強的全局搜索能力，但在實際應用中容易產(chǎn)生早熟收斂現(xiàn)象，且進化后期搜索效率較低，結合兩者的優(yōu)點，取長補短，構成混合算法——基于遺傳算法的大洪水演算法，應用該混合算法求解不同規(guī)模的多維背包問題的結果表明所提出的算法是有效可行的，優(yōu)于標準遺傳算法和大洪水演算法。如何改進遺傳算法的操作算子、保持種群的多樣性、消除解空間的不可行解等問題，將是下一步研究的重點。

［1］ 玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學出版社，2003.

［2］ 喻學才，張?zhí)镂?多維背包問題的一個蟻群優(yōu)化算法［J］.計算機學報，2008，31（5）：810-819.

［3］ 冀俊忠，黃振，劉椿年.基于變異和信息素擴散的多維背包問題的蟻群算法［J］.計算機研究與發(fā)展，2009，46（4）：644-654.

［4］ 賀一，邱玉輝，劉光遠，等.多維背包問題的禁忌搜索求解［J］.計算機科學，2006，33（9）：169-172.

［5］ 劉勇，馬良.元胞微粒群算法及其在多維背包問題中的應用［J］.管理科學學報，2011，14（1）：86-96.

［6］ 王凌，王圣堯，方晨.一種求解多維背包問題的混合分布估計算法［J］.控制與決策，2011，26（8）：1121-1125.

［7］ 杜巍，李樹茁，陳煜聰.一種求解多維背包問題的小世界算法［J］.西安交通大學學報，2009，43（2）：10-14.

［8］ 楊廣益，歐陽智敏，全惠云.松弛互補的分布估計算法求解多維背包問題［J］.計算機工程與應用，2007，43（12）：77-80.

［9］ Hiremath C S，Hill R R.First-level tabu search approach for solving themultiple-choicemultidimensional knapsack problem［J］.International Journal of Metaheuristics，2013，2（2）：174-199.

［10］ Berberler M E，Guler A，Nur?yev U G.A gentic algorithm to solve themultidimensional knapsack problem［J］.Mathematical and Computational Applications，2013，18（3）：486-494.

［11］ 魏欣，馬良.多目標旅行商問題的大洪水算法求解［J］.系統(tǒng)工程，2009，27（7）：116-118.

［12］ 盛虹平.求解最小比率旅行商問題的大洪水算法［J］.杭州師范大學學報：自然科學版，2010，9（6）：401-405.

［13］ 盛虹平，馬良.混沌大洪水算法求解函數(shù)優(yōu)化問題［J］.計算機應用研究，2011，28（5）：1626-1630.

［14］ 趙秋紅，肖依永，Mladenovic N.基于單點搜索的元啟發(fā)式算法［M］.北京：科學出版社，2013.

Genetic Great Deluge Algorithm for Solving the Multidimensional Knapsack Problem

ZHU Jun CAIYan-guang TANG Ya-lian YANG Jun
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

The Genetic Algorithm（GA）has better global search ability，but is easily prone to have premature convergence phenomenon in the practical application，with the low search efficiency in late evolution，while the Great Deluge Algorithm（GDA）is a unique algorithm for solving combinatorial optimization problems.Combined the advantages of the both algorithms，we form the genetic great deluge algorithm（GGDA），and then apply the hybrid algorithm to solve differentscales ofMultidimensional Knapsack Rroblem（MKR）.The results show that the hybrid algorithm is simple and effective，superior to the standard GA and the GDA.

Multidimensional Knapsack Rroblem；Great Deluge Algorithm；Genetic Algorithm

TR3

：A

：1009-0312（2014）05-0023-05

2014-07-03

國家自然科學基金（61074147，61074185）；廣東省自然科學基金（S2011010005059，8351009001000002）；廣東省教育部產(chǎn)學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2010B090301042）。

朱君（1991—），男，江西新余人，碩士生，主要從事組合優(yōu)化、物流信息技術與應用研究。