朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

遺傳大洪水演算法求解多維背包問(wèn)題

朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

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

多維背包問(wèn)題；大洪水演算法；遺傳算法

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

1 多維背包問(wèn)題

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

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

2 遺傳大洪水演算法

2.1 大洪水演算法

大洪水演算法在1993年由Dueck［11-14］提出。若鄰居解的目標(biāo)函數(shù)值小于當(dāng)前的邊界值LEVEL，那么該鄰居解將被接受。初始的邊界值可以設(shè)定為初始解的目標(biāo)函數(shù)值。在搜索過(guò)程中，邊界值的單調(diào)下降，每次下降的幅度UR是算法的重要參數(shù)，它象征水平面升高的速度。大洪水演算法最終獲取解的質(zhì)量和運(yùn)算時(shí)間的長(zhǎng)短只依賴(lài)于UR參數(shù)的選取。UR值太小，算法會(huì)耗費(fèi)太長(zhǎng)時(shí)間求出高質(zhì)量解；UR值太大，算法雖耗時(shí)短但求解質(zhì)量不高。一般將UR值設(shè)定小于當(dāng)前解的目標(biāo)函數(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è)定控制參數(shù)，初始化種群。

2）計(jì)算各個(gè)體的適應(yīng)度值。

3）進(jìn)行遺傳操作：選擇、交叉和變異。此例中，采用輪盤(pán)賭選擇、均勻交叉和單點(diǎn)變異。

4）計(jì)算新種群的個(gè)體適應(yīng)度值，并將其與大洪水演算法的邊界值相比較。

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

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

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

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

求解步驟：

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

2）計(jì)算各個(gè)體的適應(yīng)度值。

3）進(jìn)行遺傳操作：選擇、交叉和變異。此例中，采用輪盤(pán)賭選擇、均勻交叉和單點(diǎn)變異。

4）計(jì)算新種群的個(gè)體適應(yīng)度值，并將其與大洪水演算法的邊界值相比較。

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

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

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

3 仿真分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

建立數(shù)學(xué)模型：

（1）決策變量。

貨車(chē)裝載編號(hào)為i的貨物xi（i=1，2，...，20）。

（2）目標(biāo)函數(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 應(yīng)用三種算法求解MKP

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

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

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

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

求解結(jié)果：

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

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

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

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

4 結(jié)語(yǔ)

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

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

［2］ 喻學(xué)才，張?zhí)镂?多維背包問(wèn)題的一個(gè)蟻群優(yōu)化算法［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31（5）：810-819.

［3］ 冀俊忠，黃振，劉椿年.基于變異和信息素?cái)U(kuò)散的多維背包問(wèn)題的蟻群算法［J］.計(jì)算機(jī)研究與發(fā)展，2009，46（4）：644-654.

［4］ 賀一，邱玉輝，劉光遠(yuǎn)，等.多維背包問(wèn)題的禁忌搜索求解［J］.計(jì)算機(jī)科學(xué)，2006，33（9）：169-172.

［5］ 劉勇，馬良.元胞微粒群算法及其在多維背包問(wèn)題中的應(yīng)用［J］.管理科學(xué)學(xué)報(bào)，2011，14（1）：86-96.

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

［7］ 杜巍，李樹(shù)茁，陳煜聰.一種求解多維背包問(wèn)題的小世界算法［J］.西安交通大學(xué)學(xué)報(bào)，2009，43（2）：10-14.

［8］ 楊廣益，歐陽(yáng)智敏，全惠云.松弛互補(bǔ)的分布估計(jì)算法求解多維背包問(wèn)題［J］.計(jì)算機(jī)工程與應(yīng)用，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］ 魏欣，馬良.多目標(biāo)旅行商問(wèn)題的大洪水算法求解［J］.系統(tǒng)工程，2009，27（7）：116-118.

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

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

［14］ 趙秋紅，肖依永，Mladenovic N.基于單點(diǎn)搜索的元啟發(fā)式算法［M］.北京：科學(xué)出版社，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

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

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