改進(jìn)二進(jìn)制人工蜂群算法求解多維背包問題

王志剛，夏慧明

（南京師范大學(xué)泰州學(xué)院數(shù)學(xué)科學(xué)與應(yīng)用學(xué)院，江蘇泰州 225300）

改進(jìn)二進(jìn)制人工蜂群算法求解多維背包問題

王志剛，夏慧明

（南京師范大學(xué)泰州學(xué)院數(shù)學(xué)科學(xué)與應(yīng)用學(xué)院，江蘇泰州 225300）

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

人工蜂群算法；多維背包問題；貪婪算法；組合優(yōu)化

1 前言

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

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

2 人工蜂群算法

2.1 傳統(tǒng)人工蜂群算法

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

引領(lǐng)蜂和跟隨蜂根據(jù)式（1）在食物源的鄰域生成一個(gè)候選食物源

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

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

式（2）中，fiti為第i個(gè)食物源的適應(yīng)值，即食物源的適應(yīng)值越優(yōu)，其被選擇的概率就越大。在最大化問題中，fiti與優(yōu)化問題目標(biāo)函數(shù)值 fi的對應(yīng)關(guān)系為

在ABC算法中，某個(gè)蜜蜂個(gè)體如果連續(xù)經(jīng)過limit次循環(huán)之后食物源仍然沒有得到更新，個(gè)體就要放棄食物源，轉(zhuǎn)變?yōu)閭刹旆洹刹旆渫ㄟ^式（4）產(chǎn)生一個(gè)新的食物源

2.2 二進(jìn)制人工蜂群算法

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

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

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

3 改進(jìn)二進(jìn)制人工蜂群算法

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

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

2）在尋找最優(yōu)值的過程中，假定xij和xkj對最優(yōu)值的判定是相互獨(dú)立的。

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

式（10）中，p1、p2為xij發(fā)現(xiàn)最優(yōu)值的概率的終值和初始值；iter為當(dāng)前迭代次數(shù)；MCN為最大迭代次數(shù)。

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

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

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

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

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

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

1）設(shè)置迭代次數(shù)iter，群體規(guī)模SN，限定的循環(huán)次數(shù)limit，最大迭代次數(shù)MCN，xij發(fā)現(xiàn)最優(yōu)值的概率的終值p1和初始值p2。

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

3）引領(lǐng)蜂按式(9)產(chǎn)生候選食物源，用貪婪算法修正并計(jì)算其適應(yīng)值，如果候選食物源vi的函數(shù)值優(yōu)于原有食物源xi的函數(shù)值，則用其替換xi，否則保留xi不變。

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

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

續(xù)表

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

6 結(jié)語

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

[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ī)器人路徑規(guī)劃[J].電焊機(jī)，2009，39(4)：93-96.

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

[9]孫曉雅，林 焰.改進(jìn)的人工蜂群算法求解任務(wù)指派問題[J].微電子學(xué)與計(jì)算機(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，F(xiàn)rance：[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，F(xiàn)ranken N.Binary differential evolution[C]//IEEE Congress on Evolutionary Computation.Vancouver：IEEE，2006：1873-1879.

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

[15]喻學(xué)才，張?zhí)镂?多維背包問題的一個(gè)蟻群優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào)，2008，31(5)：810-819.

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

[17]冀俊忠，黃 振，劉椿年.基于變異和信息素?cái)U(kuò)散的多維背包問題的蟻群算法[J].計(jì)算機(jī)研究與發(fā)展，2009，46(4)：644-654.

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

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

[20]劉 毅，宋玉階.多維背包問題的DNA計(jì)算[J].生物數(shù)學(xué)學(xué)報(bào)，2008，23(1)：180-186.

[21]李春梅，馬 良.求解多維0-1背包問題的人工魚群算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，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

南京師范大學(xué)泰州學(xué)院資助項(xiàng)目(Q201232)

王志剛，1978年出生，男，山東濰坊市人，講師，主要研究方向?yàn)榻M合優(yōu)化與算法研究；E-mail：wzg19.scut@163.com