求解多維0/1背包問題的Memetic算法

劉夢佳+向鳳紅+郭寧

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

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

DOIDOI：10.11907/rjdk.172027

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號：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 引言

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

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

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

1 多維背包問題

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

2 Memetic算法求解多維0/1背包問題

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

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

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

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

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

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

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

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

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

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時，固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序。在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小[12]。基本流程如下：

Step1：初始化：設(shè)置初始溫度T（充分大）、退火終止溫度Tf（足夠小）以及退火系數(shù)k，選定一個初始解X，令當(dāng)前解為X，每個T值的迭代次數(shù)設(shè)為L。

Step2：從當(dāng)前解的鄰域中隨機選擇一個鄰居X′，計算Δ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：隨機生成初始種群P={X1，X2 Xpopsize}，迭代次數(shù)g=0。

Step2：進行模擬退火算法對種群進行局部優(yōu)化。

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

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

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

Step6：每條染色體的每個基因位都以概率Pm進行變異操作。

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

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

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

為檢驗算法的有效性，本文采用Matlab軟件編程，并將其與文獻[13]中改進的遺傳算法MGA、文獻[14]中的混合遺傳算法GGA進行對比。問題算例來源于文獻[14]。

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

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

4 結(jié)語

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

參考文獻：

[1] 李枝勇，馬良，張惠珍.求解多維背包問題的改進布谷鳥搜索算法[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背包問題的一種改進的遺傳算法[J].計算機科學(xué)，2006，33（7）：220-223.

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

[6] 任志剛，趙松云，黃姍姍，等.求解多維背包問題的蟻群—拉格朗日松弛混合優(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] 李藝貞.基于模因算法的動態(tài)多目標(biāo)優(yōu)化問題的研究[D].廈門：廈門大學(xué)，2012.

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

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

[12] 晏杰.模擬退火算法解決0-1背包問題的研究與實現(xiàn)[J].赤峰學(xué)院學(xué)報：自然科學(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背包問題的混合遺傳算法[J].武漢科技大學(xué)學(xué)報，2003，26（2）：214-216.

（責(zé)任編輯：黃 健）