何 玲，林 耿

(閩江學(xué)院 數(shù)學(xué)系，福建 福州 350108)

Memetic算法求解多維背包問題

何 玲，林 耿

(閩江學(xué)院 數(shù)學(xué)系，福建 福州 350108)

針對多維背包問題較難找到全局最優(yōu)解的情況，提出了一種求解多維背包問題的Memetic算法，該算法主要由帶反饋機制的禁忌局部搜索算法、交叉算子和種群更新策略組成.其中，種群更新策略需要同時考慮種群中解的質(zhì)量與種群的多樣性，以提高算法搜索的多樣性.測試表明，該算法能夠有效避免陷入局部最優(yōu)解并找到比現(xiàn)有算法更好的結(jié)果.

多維背包問題；啟發(fā)式算法；禁忌搜索

多維背包問題(MKP)是一個經(jīng)典的NP困難的組合優(yōu)化問題，具有廣泛的應(yīng)用背景，如計算機系統(tǒng)設(shè)計、集合劃分、組合拍賣、材料切割、存儲分配等[1].給定n個物品的集合I={1,…,n},多維背包問題考慮的是從集合I中選出一組滿足所有問題約束的物品，使得這些物品的價值之和最大.引入n維0-1向量x，其中xj為對應(yīng)第j個物品的變量.當(dāng)?shù)趈個物品被選中放入背包時，xj=1；否則，xj=0.多維背包問題可以描述為如下的整數(shù)規(guī)劃：

其中，pj，wij，ci為正實數(shù).

由于多維背包問題在理論上的重要性及應(yīng)用的廣泛性，近些年來備受關(guān)注.目前，求解多維背包問題的算法大致可分為精確算法和啟發(fā)式算法.精確算法包括隱枚舉法、分支定界[2]、動態(tài)規(guī)劃[3]等，這些精確算法能夠有效地找到較小規(guī)模多維背包問題的精確解，但對于較大規(guī)模的多維背包問題則難以在可接受的時間內(nèi)找到高質(zhì)量的解.近年來，學(xué)者們根據(jù)不同的思想提出了許多啟發(fā)式算法，如遺傳算法[4-5]、蟻群算法[6-7]、分布估計算法[8]、禁忌搜索[9]、演化算法[10-12]、粒子群算法[13]、分散搜索算法[14]、競爭決策算法[15]和免疫算法[16]等.

Memetic算法是遺傳算法和局部搜索算法的結(jié)合體，它有效地結(jié)合了基于種群的全局搜索和基于個體的局部搜索.目前，Memetic算法已經(jīng)成功地應(yīng)用于解決許多NP困難的組合優(yōu)化問題，如排序問題[17]、車輛路徑問題、圖的頂點著色[18]、最大二等分問題等.根據(jù)多維背包問題的特點構(gòu)造了求解多維背包問題的Memetic算法，設(shè)計了帶反饋機制的禁忌搜索作為局部搜索算法，能夠快速地搜索到較好的局部最優(yōu)解.采用同時考慮解的質(zhì)量和種群多樣性的多目標(biāo)函數(shù)作為種群更新準(zhǔn)則，更好地保持了種群中解的質(zhì)量和解的多樣性，有效地避免了過早收斂.通過標(biāo)準(zhǔn)測試實例分析，與現(xiàn)存的算法進(jìn)行比較，該方法能夠在可接受的時間內(nèi)找到高質(zhì)量的解.

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

1.1算法框架

精確罰函數(shù)法形式簡單、計算量低，已經(jīng)成功地解決了許多約束優(yōu)化問題.為了降低局部搜索階段的計算量，采用精確罰函數(shù)法定義適應(yīng)度函數(shù)為

(1)隨機構(gòu)造初始種群P={x1,…,xp}.

(2)對種群P中的每個解xj，j=1,…,p,分別采用帶反饋機制的禁忌搜索算法進(jìn)行局部搜索，所得的局部最優(yōu)解仍記為xj.令x*=Argmax{g(x),x∈P∩S}.

(3)從種群P中任意選擇兩個解，通過交叉算子產(chǎn)生一個新的解z，以z為初始點，應(yīng)用帶反饋機制的禁忌搜索算法進(jìn)行局部搜索，所得的局部最優(yōu)解仍記為z.如果z∈S且f(z)>f(x*)，則令x*=z.

(4)利用同時考慮種群中解的質(zhì)量和種群多樣性的種群更新策略更新種群.

(5)如果算法的停止準(zhǔn)則滿足，則停止，輸出x*；否則，轉(zhuǎn)步驟(3).

下面分別對算法框架中的帶反饋機制的禁忌搜索算法、交叉算子、種群更新策略和算法停止準(zhǔn)則進(jìn)行詳細(xì)介紹.

1.2帶反饋機制的禁忌搜索算法

禁忌搜索于1986年由Glover提出后，已經(jīng)成功地被應(yīng)用于解決各種優(yōu)化問題.本研究采用帶有反饋機制的禁忌搜索算法作為Memetic算法的局部搜索算法.下面首先給出鄰域的概念.

給定兩個解x和y，它們之間的距離為

(1)

采用(1)變換鄰域，鄰域內(nèi)的解與當(dāng)前解最多只有一個變量的取值不同，即

N(x)={y∶d(x,y)≤1}.

(2)

變量xj的增益gain(xj)為翻轉(zhuǎn)xj后的適應(yīng)度函數(shù)值與當(dāng)前解的適應(yīng)度函數(shù)值的差，即

gain(xj)=g(x′)-g(x)，

(3)

其中，x′=(x1,…,xj-1,1-xj,xj+1,…,xn).在鄰域搜索時，該禁忌搜索算法從自由的變量(不在禁忌列表)中選擇增益最大的變量翻轉(zhuǎn).當(dāng)某個變量xj被翻轉(zhuǎn)后，更新所有自由變量的增益并禁止變量xj在后面的tj次迭代中再次翻轉(zhuǎn).若翻轉(zhuǎn)在禁忌列表中的某個變量能夠產(chǎn)生比當(dāng)前最優(yōu)解更好的解，則允許翻轉(zhuǎn)禁忌列表中的變量.經(jīng)過一定數(shù)量(maxcount)的迭代后，該禁忌搜索停止，返回整個禁忌搜索過程中找到的最好的解.

禁忌長度是所有禁忌算法中一個重要的參數(shù)，本研究通過種群中的信息來動態(tài)更新禁忌的長度.用一個整數(shù)變量tj來表示變量xj的禁忌長度，tj=0表示變量xj可以自由翻轉(zhuǎn).設(shè)種群P={x1,…,xp}，當(dāng)變量xj翻轉(zhuǎn)后，tj由以下公式確定：

(4)

其中，t0為參數(shù)，表示初始的禁忌長度.

1.3交叉算子

交叉算子是Memetic算法中一個重要的算子，用于產(chǎn)生新的解.新產(chǎn)生的解應(yīng)該繼承種群P中解的優(yōu)良結(jié)構(gòu)，同時應(yīng)該還具有一些新的結(jié)構(gòu)，擴展新的搜索空間.

交叉算子可以通過以下兩個階段產(chǎn)生新的解：第一階段，通過種群中解的相似性確定部分解；第二階段，將未確定的物品按照一定的規(guī)則排序并依次將一些物品添加入背包，構(gòu)成一個解.

第二階段是添加物品的過程，首先通過式(5)確定還可以裝入背包的物品集合

(5)

對集合T中的物品按照將其放入背包后背包中物品的總價值與使用的總資源及剩下資源的比值大小來排序，即T中物品按照下式函數(shù)值從大到小進(jìn)行排列：

(6)

設(shè)物品f為排序中的第一個物品，將物品f放入背包，令zf=1.然后，根據(jù)式(5)更新集合T，并按照式(6)對T種物品重新排序并選擇第一個物品放入背包.重復(fù)以上步驟，直到?jīng)]有物品可以裝入背包，即T=?為止.

1.4種群更新策略

利用帶反饋機制的禁忌搜索算法對交叉算子產(chǎn)生的新解z進(jìn)行局部搜索，所得的局部最優(yōu)解仍記為z.用新得到的解z來更新種群P，本研究采用文獻(xiàn)[17]中的種群更新策略來更新種群.該策略同時考慮種群中解的質(zhì)量和多樣性.一個新的解如果能夠插入種群，要么是提高了種群中解的質(zhì)量，要么是提高了種群的多樣性.種群中解的多樣性可以通過解與集合間的距離來衡量.給定一個解x與一個集合A(x?A)，它們間的距離d(x,A)定義為

d(x,A)=min{d(x,y),y∈A}.

(7)

按照下面的多目標(biāo)函數(shù)從大到小對解進(jìn)行排序：

(8)

其中，α>0為參數(shù)，用于平衡解的質(zhì)量和解的多樣性.

首先根據(jù)式(7)算出d(z,P)，d(xi,P∪{z}/{xi})，其中i=1,…,p.并根據(jù)式(8)，計算出λ(z,P)，λ(xi,P∪{z}/{xi})，其中i=1,…,p，并將它們從大到小進(jìn)行排序.設(shè)xf,xs為排序中的最后兩位，如果xf≠z，則將z插入種群P，并將xf從種群中刪除；否則，以20%的概率將z插入種群P，將xs從種群中刪除.

在搜索的初級階段，種群中解的質(zhì)量相對較差，多樣性較好，此時，多目標(biāo)函數(shù)λ(x,A)中的前一部分g(x)起主要作用.隨著搜索的深入，種群中解的差距越來越小，λ(x,A)中的后一部分起主要作用，從而增加了種群的多樣性，使得算法不會過早收斂.

1.5算法停止準(zhǔn)則

可以通過算法的運行時間或算法的運行代數(shù)來作為算法的停止準(zhǔn)則，本研究采用算法的運行代數(shù)作為停止準(zhǔn)則.當(dāng)算法運行的代數(shù)超過maxgeneration時，算法停止，并將整個過程中找到的最好的解輸出.

2 仿真實驗

為了檢驗Memetic算法的性能，用C語言在電腦上進(jìn)行了仿真實驗.

2.1標(biāo)準(zhǔn)測試?yán)雍退惴▍?shù)設(shè)置

采用來自O(shè)RLIBRY的標(biāo)準(zhǔn)測試?yán)訙y試算法的性能.

設(shè)置懲罰參數(shù)k=10 000，種群數(shù)量p=20，初始禁忌長度t0=20，禁忌搜索中的最大迭代次數(shù)maxcount=2n，種群更新策略中的平衡參數(shù)α=0.001，Memetic算法的最大迭代次數(shù)maxgeneration=80.

2.2實驗結(jié)果

表1列出了Memetic算法在10個標(biāo)準(zhǔn)測試?yán)由线\行50次得到的最好解、平均解和平均運行時間.為了與現(xiàn)存的適應(yīng)度平均選擇的離散差分演化算法(BDE-FUSS)比較，表1同時列出了BDE-FUSS在這些標(biāo)準(zhǔn)測試?yán)由系臏y試結(jié)果，這些測試結(jié)果是在筆記本電腦(Core2 T6600 2.2 GHz, RAM 2 G)上進(jìn)行仿真實驗得到的.

表1 Memetic算法與BDE-FUSS算法運行結(jié)果的比較Tab.1 Comparison results between the proposed algorithm and BDE-FUSS

從表1可以看出，Memetic算法對10個標(biāo)準(zhǔn)測試?yán)佣寄軌蛘业阶顑?yōu)解；BDE-FUSS能夠找到4個標(biāo)準(zhǔn)測試?yán)拥淖顑?yōu)解.從算法運行得到的平均解進(jìn)行比較，除了WEING5外，Memetic算法能夠找到比BDE-FUSS質(zhì)量更高的平均解.特別是對于WEISH類的5個測試?yán)?，Memetic算法每次都能夠找到問題的最優(yōu)解.由于本研究采用同時考慮解的質(zhì)量和多樣性的種群更新策略，能有效地防止過早收斂.Memetic算法的平均運行時間比BDE-FUSS運行的時間要長.

為了進(jìn)一步與差異演化算法(CYYH)、二進(jìn)制粒子群優(yōu)化算法(BPSO)[19]和免疫克隆算法(IDCA)[20]進(jìn)行對比，選取標(biāo)準(zhǔn)測試數(shù)據(jù)中的實例HP2，PB2，PB5，PB7，WEING7，WEISH06，WEISH23，WEISH25來驗證.針對每個測試?yán)樱\行Memetic算法20次，表2列出了4種算法求解以上幾個實例所得到的平均解.表2中BPSO，IDCA，CYYH算法的數(shù)據(jù)均來自文獻(xiàn)[11].

表2 Memetic算法與其他算法的比較結(jié)果Tab.2 Comparison results between the proposed algorithm and other algorithm

從表2可以看出，除了HP2和PB2這兩個實例外，Memetic算法每次都能找到最優(yōu)解.在所有的8個測試實例中，Memetic算法獲得的平均解質(zhì)量都優(yōu)于IDCA，有5個實例采用Memetic算法獲得的平均解質(zhì)量優(yōu)于BPSO，有1個實例采用Memetic算法獲得的平均解質(zhì)量優(yōu)于CYYH.以上實驗結(jié)果表明，本研究提出的Memetic算法能夠有效求解多維背包問題.

3 結(jié)語

本研究以帶反饋機制的禁忌搜索作為局部搜索算法，構(gòu)造了既能繼承種群優(yōu)良結(jié)構(gòu)又能有效開拓新搜索空間的交叉算子，采用了同時考慮種群解的質(zhì)量和多樣性的種群更新策略，有效避免了算法的早熟現(xiàn)象.提出了求解多維背包問題的Memetic算法，實驗結(jié)果表明該算法是求解多維背包問題的有效算法.

[1] Hill R R, Cho Y K, Moore J T.Problem reduction heuristic for the 0-1 multidimensional knapsack problem[J].Computers & Operations Research, 2012,39(1):19-26.

[2] Shih W. A branch and bound method for the multiconstraint zero-one knapsack problem[J]. Journal of the Operational Research Society, 1979, 30(4): 369-378.

[3] Toth P. Dynamic programming algorithms for the zero-one knapsack problem[J]. Computing, 1980, 25(1): 29-45.

[4] Chu P C, Beasley J E. A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics, 1998, 4(1): 63-86.

[5] Alves M J, Almeida M. MOTGA: a multiobjective tchebycheff based genetic algorithm for the multidimensional knapsack problem[J]. Computers & Operations Research, 2007, 34(11): 3458-3470.

[6] Kong M, Tian P, Kao Y C. A new ant colony optimization algorithm for the multidimensional knapsack problem[J]. Computers & Operations Research, 2008, 35(8): 2672-2683.

[7] Ke L J, Feng Z R, Ren Z G, et al. An ant colony optimization approach for the multidimensional knapsack problem[J]. Journal of Heuristics, 2010, 16(1): 65-83.

[8] Wang L, Wang S Y, Xu Y. An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem[J]. Expert Systems with Applications, 2012, 39(5): 5593-5599.

[9] 賀一，邱玉輝，劉光遠(yuǎn)，等.多維背包問題的禁忌搜索求解[J].計算機科學(xué),2006,33(9):169-172.

[10]周雅蘭，朱耀輝，張軍.具有學(xué)習(xí)機制的離散差分演化算法[J].計算機科學(xué),2011,38(7):225-227.

[11]張欣，王志剛，夏慧明.差異演化算法求解多維0-1背包問題[J].科學(xué)技術(shù)與工程,2012,12(6):1278-1280.

[12]周雅蘭，朱耀輝.適應(yīng)度平均選擇的離散差分演化算法[J].小型微型計算機系統(tǒng),2012,33(1):151-154.

[13]鐘培華，吳志遠(yuǎn)，繆建群.區(qū)域分割粒子群算法及多維背包問題求解[J].計算機工程與應(yīng)用,2011,47(36):73-75.

[14]張曉霞，劉哲.一種新的求解多維背包問題的分散算法[J].計算機應(yīng)用研究,2012,29(5):1716-1719.

[15]熊小華，寧愛兵，馬良.基于多交換鄰域搜索的多維0/1背包問題競爭決策算法[J].系統(tǒng)工程理論與實踐,2010,30(8):1448-1456.

[16]錢淑渠，武慧虹.約束動態(tài)免疫算法及對背包問題性能測試研究[J].計算機應(yīng)用與軟件,2012,29(5):155-158.

[17]Gao L,Zhang G H,Zhang L P,et al.An efficient memetic algorithm for solving the job shop scheduling problem[J].Computers & Industrial Engineering,2011,60(4):699-705.

[18]Lu Z P,Hao J K.A memetic algorithm for graph coloring[J].European Journal of Operational Research,2010,203(1):241-250.[19]Kennedy J,Eberhart R C.A discrete binary version of the particle swarm algorithm[C]∥Proceedings of the World Multi-conference on Systemics,Cybernetics and Informatics.Piscataway:Nagoya Japan,1997:4101-4109.

[20]杜海峰，焦李成，劉若辰.免疫優(yōu)勢克隆算法[J].電子與信息學(xué)報,2004,26(12):1918-1924.

Amemeticalgorithmforsolvingthemultidimensionalknapsackproblem

HE Ling, LIN Geng

(DepartmentofMathematics,MinjiangUniversity,Fuzhou350108,China)

For the difficulty of finding the global optimal solutions for multidimensional knapsack problem, this paper proposed a memetic algorithm for solving the multidimensional knapsack problem. The memetic algorithm integrated a tabu local search method with a feedback mechanism, a crossover operator, a population updating method. The population updating method took both the solution quality and the diversity of the population into account and enhanced the diversity of the search. The proposed algorithm was tested by some benchmarks. The results show that the proposed algorithm can avoid trapping in local optimal solutions and performs better than existed algorithm in terms of average solution quality.

multidimensional knapsack problem; heuristic; tabu search

2014-03-21

國家自然科學(xué)基金(11226236,11301255);大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項目(201310395014);福建省中青年教師教育科研項目(JA13246)

何玲(1993-)，女，四川成都人，本科，主要從事人工智能方面的研究.

林耿(1981-)，男，福建莆田人，副教授，博士，主要從事人工智能與組合優(yōu)化研究.

O221.4

A

1674-330X(2014)02-0067-05