改進二進制人工蜂群算法求解多維背包問題

王志剛，夏慧明

（南京師范大學泰州學院數學科學與應用學院，江蘇泰州 225300）

改進二進制人工蜂群算法求解多維背包問題

王志剛，夏慧明

（南京師范大學泰州學院數學科學與應用學院，江蘇泰州 225300）

針對二進制人工蜂群算法收斂速度慢、易陷入局部最優的缺點，提出一種改進的二進制人工蜂群算法。新算法對人工蜂群算法中的鄰域搜索公式進行了重新設計，并通過Bayes公式來決定食物源的取值概率。將改進后的算法應用于求解多維背包問題，在求解過程中利用貪婪算法對進化過程中的不可行解進行修復，對背包資源利用不足的可行解進行修正。通過對典型多維背包問題的仿真實驗，表明了本文算法在解決多維背包問題上的可行性和有效性。

人工蜂群算法；多維背包問題；貪婪算法；組合優化

1 前言

人工蜂群[1～4](artificial bee colony，ABC)算法是由Karaboga于2005年提出的一種基于群體智能的仿生優化算法。實驗表明，ABC算法比遺傳算法(GA)、差分進化算法(DE)、粒子群優化算法(PSO)具有更好的優化性能。由于其具有收斂速度快、控制參數少、易于實現等優點，已引起越來越多的學者關注，并在很多優化問題中取得了成功的應用[5～9]。傳統的ABC算法主要用于求解連續空間的優化問題，對于一些采用二進制編碼的0～1整數規劃問題卻難以處理，這已成為限制其發展的一個瓶頸。為此，Marinakis等在2009年提出了一種二進制人工蜂群(binary artificial bee colony，BABC)算法[10]，然而其鄰域搜索方式存在一些不足：a.鄰域搜索方式是隨機的，導致算法的開采能力較弱，收斂速度較慢；b.鄰域搜索公式是單維的，使得候選食物源與原食物源極易相同，導致鄰域搜索失敗，影響算法性能。Pampará等[11]又提出了3種BABC算法，重點在于連續域到離散域的映射，但未研究新的鄰域搜索方式。

在前人研究的基礎上，本文提出一種改進的二進制人工蜂群(modified binary artificial bee colony，MBABC)算法，并將其應用于多維背包問題的求解。MBABC算法對ABC算法中引領蜂和跟隨蜂的鄰域搜索公式進行重新定義，并利用Bayes公式決定蜜蜂食物源的取值概率。在求解多維背包問題時，加入了貪婪算法這個有效的局部搜索方法，利用啟發式信息，加快算法的收斂速度。通過對多維背包問題標準測試庫的仿真實驗和與其他算法的比較，表明了本文算法在迭代相同次數的情況下更容易找到最優解，體現了算法的可行性和高效性，為多維背包問題的求解提供了一種新的解決辦法，拓展了ABC算法的應用領域。

2 人工蜂群算法

2.1 傳統人工蜂群算法

ABC算法主要模擬蜜蜂種群的智能采蜜行為。蜂群主要由引領蜂(employed bees)、跟隨蜂(onlookers)和偵察蜂(scouts)三個部分組成。人工蜂群算法在求解優化問題時，食物源代表優化問題的一個可能解，蜂群采蜜(食物源)的過程也就是搜尋優化問題最優解的過程。食物源的優劣取決于優化問題的適應值(函數值)，適應值高的食物源較優。人工蜂群算法中解的個數(SN)等于引領蜂或跟隨蜂的個數。用xi=(xi1，xi2，…，xiD)表示第i個食物源(i=1，2，…，SN，D為搜索空間的維數)。首先，人工蜂群算法隨機產生SN個解(食物源)，然后蜂群對所有的食物源進行循環搜索，循環次數為MCN。引領蜂首先在食物源的鄰域生成一個候選食物源，并比較候選食物源與先前食物源的優劣，如果候選食物源的適應值優于先前食物源的適應值，則用候選食物源代替先前的食物源，否則保持先前的食物源不變。結束之后，引領蜂回到舞蹈區把食物源優劣的信息通過跳搖擺舞傳達給跟隨蜂，跟隨蜂根據所得到的信息按照一定概率選擇食物源，適應值越高的食物源被選擇的概率越大。跟隨蜂選中食物源后，也在食物源的鄰域生成一個候選食物源，并比較候選食物源與選中食物源的優劣，保留較優的食物源。人工蜂群算法就是通過上述反復循環來最終找到最優解的。當某個蜜蜂個體經過limit次循環食物源沒有更新時，個體放棄該食物源變成偵察蜂，尋找新的食物源。

引領蜂和跟隨蜂根據式（1）在食物源的鄰域生成一個候選食物源

式（1）中，vij是生成的候選食物源；k∈{1，2，…，SN}，j∈{1，2，…，D}，這兩個數都是隨機選取的，但k≠i；rij是[-1，1]上均勻分布的隨機數，它控制xij鄰域的生成范圍。隨著迭代次數的增加，(xij-xkj)之間的距離縮小，搜索的空間也縮小，即搜索的步長縮小，動態地調整步長，有助于算法提高精度，并最終獲得最優解。式(1)稱為ABC算法的鄰域搜索公式。

跟隨蜂通過如下概率來選擇食物源

式（2）中，fiti為第i個食物源的適應值，即食物源的適應值越優，其被選擇的概率就越大。在最大化問題中，fiti與優化問題目標函數值 fi的對應關系為

在ABC算法中，某個蜜蜂個體如果連續經過limit次循環之后食物源仍然沒有得到更新，個體就要放棄食物源，轉變為偵察蜂。偵察蜂通過式（4）產生一個新的食物源

2.2 二進制人工蜂群算法

Marinakis等人提出的BABC算法仿照二進制粒子群優化(BPSO)算法[12]和二進制差分進化(BDE)算法[13]的思想，將初始化得到的xi和鄰域搜索公式(1)得到的vi通過logistic函數轉換為二進制的和，轉換公式為

式（6）、式（8）中，rand2和 rand3均為(0，1)之間均勻分布的隨機數。

算法的其他流程與傳統的ABC算法相同，在此不再贅述。

3 改進二進制人工蜂群算法

BABC算法繼續沿用傳統ABC算法中的鄰域搜索公式(1)得到的vi轉換成二進制的的必要性并不是很強，而且采用的logistic函數的主要功能是限界，并沒用充分的理由。此外，在BABC算法中采用單維更新，這使得候選食物源與原食物源極易相同，導致鄰域搜索失敗。為此，本文對鄰域搜索公式進行重新定義。首先，在生成候選食物源vij時，不采取隨機選取一個 j∈{1，2，…，D}，而是使j取遍1，2，…，D，這樣可以避免候選食物源與原食物源極易相同的缺陷；其次，從式(1)可以看出，vij的取值主要由 xij和 xkj決定，當xij和 xkj取0或1后，可以通過設定xij和xkj判斷取0和1的可信度，然后借助Bayes公式來決定vij到底取0還是取1。因此，先作如下兩個假定。

1）由于優化過程中vij的真值是未知的，故假定先驗概率P(vij=0)=P(vij=1)=0.5。

2）在尋找最優值的過程中，假定xij和xkj對最優值的判定是相互獨立的。

記xij作出正確判定的概率為P1，xkj作出正確判定的概率為P2，由Bayes公式可得

式（10）中，p1、p2為xij發現最優值的概率的終值和初始值；iter為當前迭代次數；MCN為最大迭代次數。

4 求解多維背包問題的改進二進制人工蜂群算法

多維背包問題是組合優化領域中一個經典的NP難題，在很多實際工程問題中有著廣泛的應用。因而，尋找可以有效解決該問題的算法具有重要的研究意義。目前，許多學者利用不同的思想提出了各種各樣的算法來對其進行求解。賀一等[14]借鑒認知心理學有關記憶系統的表述，在禁忌搜索算法中引入長時記憶，構造了基于雙禁忌表的禁忌搜索算法，在求解多維背包問題的仿真實驗中取得了不錯的效果。俞學才等[15]通過定義新的選擇概率的規則和基于背包項的一種序的啟發式信息，提出了求解多維背包問題的蟻群優化算法。孔民等[16]在蟻群優化系統高維立方體結構的基礎上，提出一種二進制螞蟻算法來求解多維背包問題。冀俊忠等[17]提出基于變異和信息素擴散的多維背包問題的蟻群算法。劉勇等[18]基于元胞自動機的原理和離散粒子群算法，提出一種元胞粒子群算法，該算法具有較好的全局優化能力。除了上述算法外，還有小世界算法[19]、DNA計算[20]、人工魚群算法[21]等。

多維背包問題可描述為：有n個價值為wj(j=1，2，…，n)的 物 品 ，m 個 容 積 為ci(i=1，2，…，m)的背包，第 j個物品占用第i個背包的體積大小為aij。如何選擇物品使其既可以裝入這m個背包，又能使裝入物品的總價值最大。其數學模型為

式(11)中，f(x1，x2，…xn)為目標函數；n為物品數量；m為背包數量；wj為第 j個物品的價值；ci為第i個背包的體積；aij為第 j個物品占用第i個背包的體積大小；xj為0～1變量，xj=1表示第 j件物品被裝入背包，xj=0表示第j件物品沒有被裝入背包。

采用MBABC算法在求解多維背包問題時通過鄰域搜索得到的解不一定可行，為此，引入貪婪算法來修正不可行解，同時在保證解可行的前提下，盡量增加其適應值。若解不可行，則按物品 j的價值密度ρj=cjwj(j=1，2，…，n)由小到大的方向將xj=1變為xj=0，直到將不可行的解變成可行解；若解可行，則在保證解可行的前提下，按ρj由大到小的方向將xj=0變成xj=1，盡量增加其適應值。

求解多維背包問題的MBABC算法步驟如下。

1）設置迭代次數iter，群體規模SN，限定的循環次數limit，最大迭代次數MCN，xij發現最優值的概率的終值p1和初始值p2。

2）初始化種群X(SN×n)，對X中的每個向量xi（i=1，2，…，SN）用貪婪算法修正并計算適應值。

3）引領蜂按式(9)產生候選食物源，用貪婪算法修正并計算其適應值，如果候選食物源vi的函數值優于原有食物源xi的函數值，則用其替換xi，否則保留xi不變。

4）利用式(2)計算與xi有關的概率值qi。

5）跟隨蜂根據qi選擇食物源，并按式(9)產生候選食物源，用貪婪算法修正計算其適應值，如果候選食物源vi的函數值優于原有食物源xi的函數值，則用其替換xi，否則保留xi不變。

6）判斷是否有要放棄的解，如果存在，則按照式(4)隨機產生一個滿足約束條件的新解來代替它。

7）記錄迄今為止最好的解。

8）判斷算法是否滿足停止條件，如滿足則輸出最優結果，否則返回步驟3。

5 仿真實驗

為了驗證本文算法的性能，采用VC++編程，對文獻[18]中的55個標準測試算例進行了仿真實驗。限于篇幅，本文僅列出文獻[18]和其他算法共同采用的較大規模背包問題的實驗結果。表1為本文算法與文獻[12]的BPSO算法和文獻[18]的元胞粒子群算法（CPSO）以及文獻[10]提出的BABC算法的實驗結果對比，BPSO和CPSO的參數設置見文獻[18]，BABC算法和本文算法中群體規模均為100(與BPSO和CPSO的群體規模一致)，limit=50，在本文算法中的另外兩個參數 p1和 p2分別取值為p1=0.9，p2=0.1。仿真實驗時，對每個算例獨立運行20次，記錄20次實驗中獲優次數、最優解、最劣解和平均解。

表1 BPSO、CPSO、BABC和MBABC的性能比較Table 1 Comparison results of BPSO，CPSO，BABC and MBABC

續表

從表1的對比數據可以看出，BPSO在很多情況下沒有搜索到最優解或者獲優次數很少，極易陷入局部最優而停滯不前；BABC憑借人工蜂群算法良好的優化性能，在最終優化結果上相比于BPSO有顯著的改善。但由于BABC采用單維更新，這使得候選食物源與原食物源極易相同，容易導致鄰域搜索失敗，因而其求解效率不是很高。而MBABC克服了BABC容易陷入局部極值的缺陷，能以較快的速度達到全局最優，有較高的全局尋優性能。在對測試算例進行的仿真實驗中要優于BABC以及BPSO和CPSO兩種優化算法，表明了本文算法在解決多維背包問題上的可行性和有效性。

6 結語

二進制人工蜂群算法具有收斂速度慢、容易陷入局部最優等問題，針對這一不足，本文提出一種改進的二進制人工蜂群算法，并將其與貪婪算法相結合，應用于多維背包問題的求解。仿真實驗結果表明，改進后算法的優化性能明顯優于二進制人工蜂群算法和其他一些進化算法，為多維背包問題的求解提供了一個新的思路，并拓展了人工蜂群算法的應用范圍。

[1]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06，Kayseri：Erciyes University，Engineering Faculty，Computer Engineering Department，2005.

[2]Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony(ABC)algorithm[J].Journal of Global Optimization，2007，39(3)：459-471.

[3]Karaboga D，Basturk B.Artificial bee colony(ABC)optimization algorithm for solving constrained optimization[J].Foundations of Fuzzy Logic and Soft Computing，2007，4529：789-798.

[4]Karaboga D，Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing，2008，8(1)：687-697.

[5]Karaboga D.A new design method based on artificial bee colony algorithm for digital IIR filters[J].Journal of the Franklin Institute，2009，346(4)：328-348.

[6]Singh A.An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem[J].Applied Soft Computing，2009，9(2)：625-631.

[7]胡中華，趙 敏.基于人工蜂群算法的機器人路徑規劃[J].電焊機，2009，39(4)：93-96.

[8]胡中華，趙 敏.基于人工蜂群算法的TSP仿真[J].北京理工大學學報，2009，29(11)：978-982.

[9]孫曉雅，林 焰.改進的人工蜂群算法求解任務指派問題[J].微電子學與計算機，2012，29(1)：23-26.

[10]Marinakis Y，Marinaki M，Matsatsinis N.A hybrid discrete artificial bee colony-GRASP algorithm for clustering[C]//International Conference on Computers Industrial Engineering.Troyes，France：[s.n.]，2009：548-553.

[11]Pampará G，Engelbrecht A P.Binary artificial bee colony optimization[C]//IEEE Symposium on Swarm Intelligence.Paris：IEEE，2011：1-8.

[12]Kennedy J，Eberhart R C.A discrete binary version of the particle swarm algorithm[C]//Proceedings of IEEE Conference on Systems，Man，and Cybernetics.Orlando，1997，5：4104-4108.

[13]Pampará G，Engelbrecht A P，Franken N.Binary differential evolution[C]//IEEE Congress on Evolutionary Computation.Vancouver：IEEE，2006：1873-1879.

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

[15]喻學才，張田文.多維背包問題的一個蟻群優化算法[J].計算機學報，2008，31(5)：810-819.

[16]孔 民，田 澎，李相勇.多維背包問題的二進制螞蟻算法[J].管理科學學報，2009，12(2)：44-53.

[17]冀俊忠，黃 振，劉椿年.基于變異和信息素擴散的多維背包問題的蟻群算法[J].計算機研究與發展，2009，46(4)：644-654.

[18]劉 勇，馬 良.元胞微粒群算法及其在多維背包問題中的應用[J].管理科學學報，2011，14(1)：86-96.

[19]杜 巍，李樹茁，陳煜聰.一種求解多維背包問題的小世界算法[J].西安交通大學學報，2009，43(2)：10-14.

[20]劉 毅，宋玉階.多維背包問題的DNA計算[J].生物數學學報，2008，23(1)：180-186.

[21]李春梅，馬 良.求解多維0-1背包問題的人工魚群算法[J].數學的實踐與認識，2010，40(17)：195-199.

Modified binary artificial bee colony algorithm for multidimensional knapsack problem

Wang Zhigang，Xia Huiming
（School of Mathematics，Nanjing Normal University Taizhou College，Taizhou，Jiangsu 225300，China）

The binary artificial bee colony algorithm has the shortcomings of slower convergence speed and falling into local optimum easily.According to the defects，a modified binary artificial bee colony algorithm is proposed.The algorithm redesign neighborhood search formula in artificial bee colony algorithm，the probability of the food position depends on the Bayes formula.The modified algorithm was used for solving multidimensional knapsack problem.During the evolution process，it used the greedy algorithm to repair the infeasible solution and rectify feasible solution with insufficient use.The simulation results showed the feasibility and effectiveness of the proposed algorithm.

artificial bee colony algorithm；multidimensional knapsack problem；greedy algorithm；combinatorial optimization

TP301.6

A

1009-1742（2014）08-0106-07

2013-11-11

南京師范大學泰州學院資助項目(Q201232)

王志剛，1978年出生，男，山東濰坊市人，講師，主要研究方向為組合優化與算法研究；E-mail：wzg19.scut@163.com