基于混合編碼的差異演化算法解0-1背包問題

摘 要:針對典型的一類NP完全問題——背包問題，提出一種混合編碼的差異演化求解方法。該方法基于差異演化算法框架，采用混合編碼機制，每個決策變量均由一個實數和一個二進制數的組合表示。利用新定義的映射算子，構建混合編碼的種群;增加邊界約束處理算子，確保變異算子計算結果滿足邊界約束條件;利用新定義的丟棄算子對于不可行的裝包策略進行修正。通過數值仿真實驗，將該方法與遺傳算法、二進制差異算法的計算結果比較分析，表明該算法求解背包問題的有效性與適用性。

關鍵詞:0-1背包問題; 混合編碼; 差異演化算法; 丟棄算子

中圖分類號:TP18文獻標志碼:A

文章編號:1001-3695(2010)06-2031-03

doi:10.3969/j.issn.1001-3695.2010.06.009

Mixed-coding-based differential evolution algorithm for 0-1 knapsack problem

DENG Chang-shou1，2， ZHAO Bing-yan1， LIANG Chang-yong2

(1. School of Information Science Technology， Jiujiang University， Jiujiang Jiangxi 332005， China; 2. Institute of Computer Network System， Hefei University of Technology， Hefei 230009， China)

Abstract:This paper proposed mixed-coding-based differential evolution algorithm for 0-1 knapsack problem which was NP complete. This algorithm was based on the original differential evolution using mix-coding mechanism in which each decision variable was represented by the combination of one float number and a binary number. Firstly， proposed a new mapping operator to construct mixed-coding population， and then defined a new operator which dealt with the boundary constraint. Lastly used a discarding operator to adapt the infeasible solution. Simulation numerical results compared with that of genetic algorithm and binary differential evolution show that this algorithm is efficient and practical for 0-1 knapsack problem.

Key words:0-1 knapsack problem; mix coding; differential evolution; discarding operator

0 引言

背包問題(knapsack problem，KP)有著廣泛的應用背景，如貨物裝載、選址、材料切割等問題。理論上盡管背包問題的結構簡單，但它卻具有組合爆炸的性質。由于背包問題的NP完全性質，使得許多傳統的精確算法，如貪心算法、動態規劃算法、回溯法、分支限界法等盡管可以得到準確解，但是其時間復雜性與物品數目呈指數關系，因而時間復雜度高。進化算法盡管不一定得到準確解，但可以得到比較有效解，而且時間復雜度比較低，在求解背包問題中得到了廣泛使用。例如文獻[1]采用一種基于模式替代的遺傳算法(GASR)求解背包問題，獲得比標準遺傳算法更好的計算結果。文獻[2]提出一種二進制差異演化算法(BDE)求解背包問題，實驗證明其求解效率高于文獻[3]的改進郭濤算法。文獻[4~6]分別用不同的智能方法求解背包問題。盡管這些方法的穩定性和求解速度較快，但是求解精度仍然有待進一步提高。本文在以前提出的混合編碼差異演化算法[7]基礎上，利用新定義的算子引導種群搜索方向，提出一種基于混合編碼差異演化(MCDE)算法求解背包問題的新方法。

1 背包問題數學模型

0-1背包問題是指給定n種物品和一個背包，wi與pi(i=1，2，…，n)分別為物品i的重量和價值，V為背包總重量限制。如何選擇物品，使得裝入背包中的物品總價值最大?其數學模型可以表示為下述0-1整數規劃模型:

maxf=∑ni=1piwi

s.t. ∑ni=1wixi≤V

xi∈{0，1} (i=1，2，…，n)(1)

其中:變量xi(i=1，2，…，n)為1時，物品i裝入背包;而xi(i=1，2，…，n)為0時，物品i不裝入背包。

2 差異演化算法

差異演化(differential evolution，DE)算法是一種實數編碼的基于種群演化的全局優化算法[8]。DE算法原理簡單、控制參數少，實施隨機、并行、直接的全局搜索，易于理解和實現。DE算法在連續問題的優化中獲得了廣泛的應用。在演化求解過程中，DE算法隨機產生初始群體，然后將群體中兩個成員間的差向量適當加權后，增加至第三個成員。DE算法利用此方法生產新個體，如果新個體的適應值更好，那么新個體將代替原個體。

DE演化算法根據變異算子和交叉算子的不同，形成了不同的模式，其中常見的是DE/rand/1/bin和DE/best/1/bin[9]。DE/rand/1/bin的具體內容有四種。

1)生成初始種群

在n維空間中，隨機生成滿足上下界約束的m個體的種群POP=(popij)m×n。方法如下:

popij=xlj+rand(0，1)(xuj-xlj)(2)

其中:i=1，2，…，m，j=1，2，…，n;xlj和xuj分別表示第j個變量的下界和上界。

2)變異算子

對種群中的每個向量popi(i=1，2，…，m)實施變異時，從種群中另外隨機選擇三個向量popp1、popp2、popp3，要求彼此互不相同，即i≠p1≠p2≠p3。設本次種群處于第t代，則變異操作如式(3)所示:

hi(t+1)=popp1(t)+F(popp2(t)-popp3(t))(3)

其中:F為縮放因子，(popp2(t)-popp3(t))為差異向量;i=1，2，…，m。

3)交叉算子

對種群中的每個向量，利用交叉算子增加群體的多樣性，具體操作如下:

ui(t+1)=hi(t+1) if (rand≤CR or j=R(i))

popi(t) otherwise(4)

其中:i=1，2，…，m，rand∈[0，1]的隨機小數，CR∈[0，1]為交叉概率，R(i)∈[1，n]的隨機整數。采用這種交叉策略可以保證ui(t+1)至少有一個分量由hi(t+1)的相應分量貢獻。

4)選擇算子

為了確定ui(t+1)能否成為下一代種群中的成員，DE算法基于優勝劣汰的原則，利用式(5)所示的選擇操作進行選擇。

popi(t+1)=ui(t+1) if (f(ui(t+1))≤f(popi(t)))popi(t) otherwise(5)

由以上描述可以看出，DE算法涉及的數據結構和運算簡單，易于編程語言實現。

3 解0-1背包問題的混合編碼差異演化算法

3.1 MCDE算法原理

盡管DE算法在連續領域獲得了廣泛成功的應用[10]，然而從上文關于DE算法的描述可以發現，DE算法中如式(3)所示的變異算子對于實數域是封閉，對于0-1整數規劃問題，其計算結果不封閉。為了求解0-1背包問題，MCDE算法中利用混合編碼的方式，種群中的每個個體的分量均為兩個部分構成，記為Y=(X，B)。其中X是實數，其初始值屬于區間[0，1];B是二進制數，其值屬于離散集合{0，1}。在MCDE算法中，利用映射算子，產生混合編碼種群并在演化過程中維持種群的混合編碼;利用邊界約束處理算子確保變異算子的結果一直屬于區間[0，1];利用丟棄算子修正非法的裝包策略，引導種群向最優解方向進化。

3.2 映射算子

為了有效求解0-1背包問題，MCDE算法利用映射算子產生混合編碼的種群。對種群中每個個體的向量，利用式(6)定義的一個新映射算子構建混合編碼的個體。

f(x)=0 x∈[0，0.5)1 x∈[0.5，1](6)

即當x∈[0，0.5)時，將其映射為二進制數0;當x∈[0.5，1]時，將其映射為二進制數1。例如某個個體分量的編碼可能為(0.8，1)或(0.2，0)。

3.3 邊界約束處理算子

即使將混合編碼的某個分量的值限制在區間[0，1]，式(3)所定義的變異算子計算結果也往往在區間[0，1]之外。為了確保式(6)所示的映射算子的有效性，MCDE算法利用新定義的邊界約束處理算子對此進行處理。

hij(t+1)=hij(t+1) if hij(t+1)∈[0，1]rand(0，1) otherwise(7)

3.4 丟棄算子

在利用演化算法求解0-1背包問題時，迭代過程中常常會出現解違反背包問題的重量約束條件。本文在MCDE算法中利用丟棄算子對違反重量約束的解進行修正。丟棄算子首先對所有待裝包的物品按照價值密度(即物品價值/物品重量)升序排序，然后按照物品的價值密度依次從低到高進行丟棄，直到符合重量約束條件為止。

3.5 MCDE算法流程圖

綜上所述，MCDE算法的流程如圖1所示。

4 數值實驗

為了檢驗MCDE算法的性能，文中選擇了四個常用于測試演化算法性能的背包問題進行實驗，其物品規模分別為20、50、100和100。分別記為KP1、KP2、KP3和KP4。其中KP1、KP2和KP3選自文獻[1]，文獻[2]利用KP2和KP4測試BDE算法的性能。為了分別比較本文提出的MCDE與GASR[1]和BDE[2]的性能，分兩組進行實驗。第一組采用KP1，KP2和KP3;第二組采用KP2和KP4。四個背包問題的具體數據如下:

a)KP1。物品的價值集P={92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58};物品的重量集W={44，46，90，72，91， 40，75，35，8，54，78，40，77，15，61，17，75，29，75，63};背包的最大容量為878，規模為20。

b)KP2。物品的價值集P={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，規模為50。

c)KP3。物品的價值集P={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};背包的最大容量為671 8，規模為100。

d)KP4。 物品的價值集P={72，490，651，833，833，489，359，337，267，441，70，934，467，661，220，329，440，774，595，98，424，37，807， 320，501，309，834，851，34，459，111，253，159，858，793，145，651，856，400，285，405，95，391，19，96，273，152，473，448，231};物品的重量集W={438，754，699，587，789， 912，819，347，511，287，541，784，676，198，572，914，988，4，355，569，144，272，531， 556，741，489，321，205，607，399，747，118，651，806，9，607，121，370，999，494，743，967，718，397，589，193，369};背包的最大容量為為11 258，規模為100。

第一組實驗MCDE算法和文獻[1]GASR參數設置如表1所示。

表1 MCDE與GASR參數設置對比

算法種群規模變異概率交叉概率最大迭代次數

MCDE500.50.5150

GASR[1]2000.060.6181 000

實驗時，對于三個不同的背包問題，各種最大迭代次數分別運行10次。MCDE算法所求出的最好結果(記為總價值/總重量)以及所用最少迭代次數與文獻[1]求解的最好結果(總價值/重量)對比如表2所示。其中GA與GASR的結果直接引自文獻[1]。

表2 第一組實驗結果對比

實例

GAGASRMCDE

最好結果(迭代次數)最好結果(迭代次數)最好結果(迭代次數)

KP11 042/878(29)1 042/878(12)1 042/878(5)

KP23 077/1 000(192)3 103/1 000(50)3 105/997(46)

KP325 848/6 716(319)26 559/6 717(147)26 559/6 717(137)

表2的實驗結果表明，對于三個背包問題，MCDE算法均取得了良好的結果。與GA算法相比，MCDE算法僅用四分之一的種群，而且在較少的迭代次數內求出了更好的解。與GASR算法相比，MCDE算法同樣可以在較少的迭代次數內找到最好結果。其中KP2的最優結果優于RSGA算法求解結果。MCDE算法求解上述三個背包問題的最優結果的進化曲線如圖2所示。

第二組實驗，MCDE的參數設置與第一組相同。文獻[3]改進的郭濤算法，種群大小為50，最大迭代次數為10 000。文獻[2]的BDE算法的種群大小均為50，交叉概率為0.1，最大進化代數均為200。所有的方法均獨立進行100 次。計算結果對比如表3所示。其中BDE和改進郭濤算法的結果直接引自文獻[2]。

從實驗結果可以看出，對于KP2，MCDE算法的尋優能力超過BDE算法和改進的郭濤算法。對于KP4，MCDE算法的穩定性優于改進的郭濤算法，其求解能力與BDE算法相同。

表3 第二組實驗結果對比

問題已知最優解

達到(超過)已知最優解的次數

改進郭濤算法[3]BDE[2]MCDE

KP23 10397100100

KP416 10294100100

對于KP2，MCDE算法求得的最優解為3 119，優于已知的最優解(3 103)。對于KP4，MCDE算法每次都能夠求解出最優解16 102。對于KP2的100次求解結果分布情況如圖3所示。

5 結束語

0-1背包問題是離散域上有約束的NP完全問題。本文提出一種MCDE算法成功求解0-1背包問題。MCDE算法基于DE算法框架，利用混合編碼機制，同時新增的算子成功解決DE算法求解離散優化問題時的計算不封閉問題。此外，MCDE算法利用丟棄算子引導種群快速尋優。四個不同的0-1背包問題實驗結果表明，MCDE算法求解0-1問題精度高、收斂速度快、穩定性較好，是求解背包問題的有效方法。此外，MCDE算法同樣適用于求解與0-1背包問題類似的帶約束條件的NP離散優化問題，具有廣闊的應用前景。

參考文獻:

[1]李康順， 賈玉珍， 張文生. 一種基于模式替代的遺傳算法解0/1背包問題[J].計算機應用研究，2009，26(2):470-417.

[2]蔡鴻英，郝志峰，王志剛，等.解0-1背包問題的二進制差異演化算法[J].計算機工程與設計，2009，30(7):1716-1718，1721.

[3]龔文引，蔡之華，詹煒蔡. 一種新的求解0-1 背包問題的自適應算法[J].微型機與應用，2005，24(12):63-66.

[4]秦玲，白云，章春芳，等.解0-1背包問題的蟻群算法[J].計算機工程，2006，32(6): 212-215.

[5]寧愛兵，馬良.0/1背包問題競爭決策算法[J]，計算機工程與應用，2008，44(3):14-16，38.

[6]劉建芹，賀毅朝，顧茜茜.基于離散微粒群算法求解背包問題研究[J].計算機工程與設計，2007，28(13):3189-3191，3204.

[7]鄧長壽，梁昌勇.求解武器—目標分配問題的混合編碼差異演化算法[J].計算機應用研究，2009，26(1):74-76.

[8]STORN R. Differential evolution design of an IIR-filter with requirements for mafnitude and group delay[C]//Proc of IEEE International Conference on Evolutionary Computation.[S.l.]: IEEE Press，1996:268-273.

[9]STORN R， PRICE K. Differential evolution:a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of Global Optimization，1997，11(4):341-359.

[10]VERSTERSTROM J， THOMSEN R. A comparative study of differential evolution， particle swarm optimization， and evolutionary algorithm on numerical benchmark problems[C]//Proc of Congress on Evolutionary Computation.[S.l.]:IEEE Press，2004:1980-1987.