求解多維0/1背包問(wèn)題的Memetic算法

劉夢(mèng)佳+向鳳紅+郭寧

摘要：根據(jù)多維0/1背包問(wèn)題的特點(diǎn)，結(jié)合遺傳算法和模擬退火算法的優(yōu)點(diǎn)，設(shè)計(jì)了一種Memetic算法。該算法以基于模式替換的改進(jìn)遺傳算法作為全局搜素算法，采用模擬退火算法進(jìn)行局部搜索。全局搜索算法引入了模式替換，使每代種群中的最好基因個(gè)體保存下來(lái)形成模式，引導(dǎo)種群搜索方向，提高搜索性能，然后進(jìn)行選擇、均勻交叉和變異操作，最后采用最大化修復(fù)策略，對(duì)不可行解進(jìn)行修復(fù)，并對(duì)可行解進(jìn)行修正。模擬退火算法以一定概率接受較差的解，從而避免陷入局部最優(yōu)解。通過(guò)實(shí)驗(yàn)仿真和算法比較驗(yàn)證了Memetic算法的優(yōu)越性和有效性。

關(guān)鍵詞：多維0/1背包；Memetic算法；遺傳算法；模擬退火算法

DOIDOI：10.11907/rjdk.172027

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）012-0070-04

Abstract：According to the characteristics of multidimensional 0/1 knapsack problem and the advantages of genetic algorithm and simulated annealing algorithm，a Memetic algorithm is designed. The Memetic algorithm uses the improved genetic algorithm introduced model of replacementas the global search algorithm， and uses the simulated annealing algorithm to perform local search. The global search algorithm introduced the pattern substitution， so excellent genes from each generation population are preserved to form mode and guide the search direction of the population，which improve the search performance. After that，through selection， uniform crossover and mutation operation， the solutions are obtained. Finally the infeasible solution and the feasible solution are repaired by introduced maximum repair strategy.The simulated annealing algorithm accepted poor solutions with a certain probability， thus avoiding trapping in local optimal solutions.The superiority and effectiveness of the Memetic algorithm are verified by experimental simulation and algorithm comparison.

Key Words：the multidimensional 0/1 knapsack； Memetic algorithm； genetic algorithm； simulated annealing algorithm

0 引言

多維背包問(wèn)題（Multidimensional Knapsack Problem，MKP）是著名的整數(shù)規(guī)劃問(wèn)題，有著許多重要的實(shí)際應(yīng)用背景，如貨物裝載、材料切割、資源分配、投資決策等問(wèn)題[1]?，F(xiàn)有3種求解方法：精確方法（中間匹配法、動(dòng)態(tài)規(guī)劃等[2]）、啟發(fā)式方法（粒子群算法[3]、遺傳算法[4]、布谷鳥(niǎo)算法[5]、混合算法[6]等）以及上述方法的混合算法。其中，精確方法只適用于較小規(guī)模的問(wèn)題且計(jì)算過(guò)程非常復(fù)雜，故啟發(fā)式方法及其混合算法得到了廣泛應(yīng)用。進(jìn)化算法多采用精英策略，在具有高進(jìn)化效率的同時(shí)，存在易陷入局部最優(yōu)解等局限性[7]。

Memetic算法是一種基于種群的全局搜索與基于個(gè)體的局部啟發(fā)式搜索的結(jié)合體，由Moscato和Norman等[8]在1992年正式提出。Memetic算法提出的是一種框架及一個(gè)概念，在該框架下，可以采用不同的搜索策略構(gòu)成不同的Memetic算法，如全局搜索策略可以采用遺傳算法、進(jìn)化策略、進(jìn)化規(guī)劃等，局部搜索策略可以采用爬山搜索、模擬退火、貪婪算法、禁忌搜索、導(dǎo)引式局部搜索等。正是這種全局搜索和局部搜索的結(jié)合機(jī)制使模因算法的搜索效率在某些問(wèn)題領(lǐng)域比傳統(tǒng)進(jìn)化算法快幾個(gè)數(shù)量級(jí)，因而可被廣泛地應(yīng)用于問(wèn)題求解領(lǐng)域[9]。

遺傳算法具有較強(qiáng)的全局搜索性能，但是遺傳算法在搜索過(guò)程中容易出現(xiàn)早熟現(xiàn)象。模擬退火算法模擬固體退火過(guò)程，不僅能夠向目標(biāo)函數(shù)優(yōu)化的方向迭代，而且通過(guò)引入接受準(zhǔn)則，能夠以一定概率接受較差的解，從而避免陷入局部最優(yōu)解。但當(dāng)問(wèn)題規(guī)模較大時(shí)，其收斂速度較慢。本文根據(jù)多維背包問(wèn)題的特點(diǎn)，結(jié)合遺傳算法和模擬退火算法，設(shè)計(jì)了基于模式替換的改進(jìn)遺傳算法作為全局搜索算法，局部搜索部分采用模擬退火算法的Memetic算法。其中，基于模式替換的改進(jìn)遺傳算法是在貪婪遺傳算法的基礎(chǔ)上引入模式替換，使每代種群中的最好基因個(gè)體保存下來(lái)形成模式，引導(dǎo)種群的搜索方向，提高搜索性能，接著進(jìn)行選擇、均勻交叉、變異操作；最后引入最大化修復(fù)策略，對(duì)不可行解進(jìn)行修復(fù)，同時(shí)對(duì)可行解進(jìn)行修正。實(shí)驗(yàn)結(jié)果表明，該Memetic算法比傳統(tǒng)的貪婪遺傳算法和基于模式替換的改進(jìn)遺傳算法具有更強(qiáng)的尋優(yōu)能力。

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

背包問(wèn)題（Knapsack Problem，KP）有多種形式，普通背包問(wèn)題僅考慮物品的某一約束，但實(shí)際中的背包問(wèn)題常常受到多類(lèi)資源限制，如投資決策問(wèn)題中資金、人力、原材料等多維約束的限制，這一類(lèi)在多種資源約束條件下的背包問(wèn)題即多維背包問(wèn)題（MKP）[10]。MKP可描述為：給定n個(gè)價(jià)值為Pj （j=1，2，…，n）的物品， m種有限數(shù)量的資源約束ci （i=1，2，…，m），物品j對(duì)資源i的消耗為wij （i=1，2，…，m；j=1，2，…，n），從n個(gè)物品中選擇出一組滿(mǎn)足所有資源約束的物品組合，使所選物品價(jià)值總和最大。數(shù)學(xué)模型為：

2 Memetic算法求解多維0/1背包問(wèn)題

2.1 基于模式替換的全局搜索算法

（1）編碼及初始種群生成。本文采用二進(jìn)制矩形編碼，隨機(jī)生成PopSize個(gè)個(gè)體，每個(gè)個(gè)體是長(zhǎng)度為n的字符串，相當(dāng)于一條染色體，字符串中的每一位相當(dāng)于一個(gè)基因位，PopSize行n列的矩陣即為初始群體。

（2）適應(yīng)度函數(shù)計(jì)算。根據(jù)遺傳算法定義適應(yīng)度函數(shù)f=∑nj=1Pj *xj，計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值，判斷其是否符合優(yōu)化準(zhǔn)則，若符合，輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)向選擇操作。

（3）模式替換操作。為增強(qiáng)搜索導(dǎo)向和搜索能力，本文在選擇操作之前引入模式替換操作。模式替換[11]即是利用種群中“*”這一不確定字符產(chǎn)生新個(gè)體，用產(chǎn)生的新個(gè)體替換原種群中質(zhì)量不好的個(gè)體，使替換后的個(gè)體在經(jīng)過(guò)交叉和變異之后仍能較大概率地存活下來(lái)，保證好的基因不丟失。

傳統(tǒng)的遺傳算法只在最優(yōu)個(gè)體中尋找最優(yōu)解，起初能找到比較滿(mǎn)意的最優(yōu)解，但隨著迭代次數(shù)增加，最優(yōu)解變得越來(lái)越少，導(dǎo)致交叉和變異操作往往只能在最優(yōu)解內(nèi)部發(fā)生，極大地降低了遺傳速度，使收斂過(guò)程放慢。為了提高遺傳算法的搜索速度、尋優(yōu)能力，防止早熟現(xiàn)象出現(xiàn)，本文根據(jù)文獻(xiàn)[11]的模式替換思想進(jìn)行了改進(jìn)。具體操作如下：①每隔20代進(jìn)行一次模式生成、模式替換；②將種群適應(yīng)值按降序排列的個(gè)體集中前ML個(gè)個(gè)體記錄下來(lái)，并進(jìn)行統(tǒng)計(jì)；③將質(zhì)量?jī)?yōu)良的ML個(gè)個(gè)體生成模式采樣空間。設(shè)定一個(gè)模式固定率，Ra=0.5。計(jì)算被記錄個(gè)體每一基因位上0（或1）的個(gè)數(shù)占當(dāng)前種群此基因位總字符數(shù)的比例，若比例超過(guò)Ra，則該基因位值為0（或1），否則為*，由此得到采樣空間模式。被確定為0或1的基因稱(chēng)為個(gè)體的優(yōu)良基因；④將具有優(yōu)良基因的新個(gè)體加入原種群中，計(jì)算所有個(gè)體的適應(yīng)度，并按適應(yīng)度降序排列。然后取前PopSize個(gè)個(gè)體作為當(dāng)前種群，由此替代原種群中質(zhì)量較差的個(gè)體。

（4） 選擇操作。保留父代和子代的最優(yōu)個(gè)體，染色體在種群中被選擇的可能性與個(gè)體的適應(yīng)度大小成正比。

（6）變異操作。定義參數(shù)Pm=0.1作為變異操作的概率，由交叉操作得到的每條染色體的每個(gè)基因位都以概率Pm進(jìn)行變異。

（7）最大化利率修復(fù)策略。為修復(fù)遺傳過(guò)程中不滿(mǎn)足約束條件的不可行解，Zitzler等提出了最大化利率修復(fù)策略，即將物品的價(jià)值密度ρij=Pj/wij按升序排列，搜索出不滿(mǎn)足約束條件的情況，然后從包中逐一拿出價(jià)值密度小的物品，直到每一維資源都滿(mǎn)足約束條件。該修復(fù)策略簡(jiǎn)單易行，是目前求解背包問(wèn)題中最常用的修復(fù)策略。但該策略存在一個(gè)缺陷，即它只考慮了物品的價(jià)值重量比，沒(méi)有兼顧各維資源的利用率，不利于算法的快速收斂。針對(duì)以上缺陷，本文作了以下改進(jìn)：在對(duì)不可行解進(jìn)行修復(fù)的同時(shí)，對(duì)可行解進(jìn)行修正。具體操作如下：①搜索出不滿(mǎn)足資源約束條件的物品選擇策略，對(duì)于在該選擇策略下被放入的物品，按價(jià)值密度升序排列的先后次序依次減掉物體（即令相應(yīng)物體對(duì)應(yīng)的xj=0）；②對(duì)xj=0的物體按價(jià)值密度降序排列的先后次序依次選擇具有最大剩余的資源，直到消耗的資源達(dá)到約束上限為止。

2.2 基于模擬退火的局部搜索算法

模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫度升高變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序。在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小[12]?；玖鞒倘缦拢?/p>

Step1：初始化：設(shè)置初始溫度T（充分大）、退火終止溫度Tf（足夠?。┮约巴嘶鹣禂?shù)k，選定一個(gè)初始解X，令當(dāng)前解為X，每個(gè)T值的迭代次數(shù)設(shè)為L(zhǎng)。

Step2：從當(dāng)前解的鄰域中隨機(jī)選擇一個(gè)鄰居X(jué)′，計(jì)算Δf=f（X′ ）-f（X）。

Step3：若Δf>0，則令X=X′，否則若exp（-Δf/T）>random（0，1），則令X=X′。令L=L-1，若L>0，執(zhí)行Step2、Step3，否則執(zhí)行Step4。

Step4：T=k*T，若T>Tf，轉(zhuǎn)Step2，否則輸出當(dāng)前解作為最優(yōu)解，程序結(jié)束。

2.3 Memetic算法具體流程

Step1：隨機(jī)生成初始種群P={X1，X2 Xpopsize}，迭代次數(shù)g=0。

Step2：進(jìn)行模擬退火算法對(duì)種群進(jìn)行局部?jī)?yōu)化。

Step3：計(jì)算適應(yīng)度函數(shù)并進(jìn)行排序。

Step4：若Mod（g，20）=1，則按2.1節(jié)中的步驟（3）進(jìn)行模式替換，否則轉(zhuǎn)Step4。

Step5： 按個(gè)體適應(yīng)度選擇兩個(gè)解，通過(guò)均勻交叉產(chǎn)生新的解，應(yīng)用模擬退火算法進(jìn)行局部搜索并保留最優(yōu)個(gè)體。

Step6：每條染色體的每個(gè)基因位都以概率Pm進(jìn)行變異操作。

Step7： 對(duì)種群采取最大化利率修復(fù)策略，通過(guò)模擬退火算法進(jìn)行個(gè)體的深度搜索，記錄迄今為止最好的解。

Step8：g=g+1，若g達(dá)到最大迭代步數(shù)，則輸出最優(yōu)結(jié)果，否則轉(zhuǎn)Step3。

3 算例及結(jié)果分析

為檢驗(yàn)算法的有效性，本文采用Matlab軟件編程，并將其與文獻(xiàn)[13]中改進(jìn)的遺傳算法MGA、文獻(xiàn)[14]中的混合遺傳算法GGA進(jìn)行對(duì)比。問(wèn)題算例來(lái)源于文獻(xiàn)[14]。

資源數(shù)和物品數(shù)分別為m=2，n=28；資源約束為C1=C2=600；項(xiàng)目j對(duì)應(yīng)的效益為Pj，對(duì)第i維資源的消耗為wij；實(shí)例的最佳效益為141 278（此時(shí)，第3，5，6，7，8，10，12，13，14，19，21，23，24，26號(hào)項(xiàng)目被執(zhí)行）。實(shí)例數(shù)據(jù)如表1所示。

由表2可知，3種算法都可以在有限的迭代次數(shù)中達(dá)到最優(yōu)，但Memetic算法求得的平均最優(yōu)值比MGA和GGA算法更接近最優(yōu)值，說(shuō)明Memetic算法在解決多維背包問(wèn)題時(shí)求解精度更高；從平均迭代次數(shù)看，Memetic算法達(dá)到最優(yōu)值時(shí)代數(shù)最小，說(shuō)明該算法的收斂速度比MGA和GGA算法快；3種算法中，Memetic算法求得的平均最差值最大，表明該算法的求解能力高于其它兩種算法。從圖1三種算法的迭代圖看，Memetic算法迭代到15代左右已經(jīng)接近最優(yōu)解，而MGA和GGA算法分別在接近35代和70代時(shí)才趨于收斂，本文算法的全局搜索導(dǎo)向和尋優(yōu)能力明顯較強(qiáng)。

4 結(jié)語(yǔ)

本文設(shè)計(jì)了一種基于模式替換的改進(jìn)遺傳算法作為全局搜索算法，局部搜索部分采用模擬退火算法的Memetic算法。其中基于模式替換的改進(jìn)遺傳算法引入了模式替換操作，并使用了最大化修復(fù)策略，引導(dǎo)種群的搜索方向，提高了搜索性能，避免了早熟現(xiàn)象出現(xiàn)。同時(shí)，以模擬退火算法作為局部搜索，提高了求解精度。仿真結(jié)果表明，Memetic算法在求解多維0/1背包問(wèn)題時(shí)具有良好的收斂性和較強(qiáng)的尋優(yōu)能力。目前，本文只研究了待選物品數(shù)量多的情況，今后將對(duì)大規(guī)模資源約束的多維背包問(wèn)題進(jìn)行深入研究。

參考文獻(xiàn)：

[1] 李枝勇，馬良，張惠珍.求解多維背包問(wèn)題的改進(jìn)布谷鳥(niǎo)搜索算法[J].控制工程，2016，23（7）：1069-1075.

[2] Y CUI.A new dynamic programming procedure for three-staged cutting patterns[J]. Journal of Global Optimization， 2013，5（2）：349-357.

[3] CHIL M C.Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem[J].Applied Soft Computing， 2015，26（1）：378-389.

[4] 曾智，楊小帆，陳靜，等.求解多維0-1背包問(wèn)題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)科學(xué)，2006，33（7）：220-223.

[5] 張晶，吳虎勝.改進(jìn)二進(jìn)制布谷鳥(niǎo)搜索算法求解多維背包問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2015，35（1）：183-188.

[6] 任志剛，趙松云，黃姍姍，等.求解多維背包問(wèn)題的蟻群—拉格朗日松弛混合優(yōu)化算法[J].控制與決策，2016，31（7）：1178-1184.

[7] SC CHU， HC HUANG， JF RODDICK.Overview of algorithms for swarm intelligence[C].Proc.of the International Conference on Computational Collective Intelligence，2011：8-41.

[8] MOSCATO P，NORMAN M G.A memetic approach for the travelling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems[C].Proceedings of the International Conference on Parallel Computing and Transport Applications，Amsterdam：IOS press，1992：177-186.

[9] 李藝貞.基于模因算法的動(dòng)態(tài)多目標(biāo)優(yōu)化問(wèn)題的研究[D].廈門(mén)：廈門(mén)大學(xué)，2012.

[10] 薛俊杰，王瑛，孟祥飛，等.二進(jìn)制反向?qū)W習(xí)煙花算法求解多維背包問(wèn)題[J].系統(tǒng)工程與電子技術(shù)，2017，39（2）：451-458.

[11] 李康順，賈玉珍，張文生.一種基于模式替代的遺傳算法解0/1背包問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，2009，26（2）：470-471.

[12] 晏杰.模擬退火算法解決0-1背包問(wèn)題的研究與實(shí)現(xiàn)[J].赤峰學(xué)院學(xué)報(bào)：自然科學(xué)版， 2013 （8）：9-10.

[13] X LIU，F(xiàn) XIANG，J MAO.An improved method for solving the large-scale multidimensional 0-1 knapsack problem[C].International Conference on Electronics & Communication Systems. Coimbatore， INDIA，2014.

[14] 姚瑞楓，宋玉階.多維0-1背包問(wèn)題的混合遺傳算法[J].武漢科技大學(xué)學(xué)報(bào)，2003，26（2）：214-216.

（責(zé)任編輯：黃 ?。?