吳聰聰，賀毅朝，陳嶷瑛，劉雪靜，才秀鳳

WU Congcong,HE Yichao,CHEN Yiying,LIU Xuejing,CAI Xiufeng

石家莊經(jīng)濟學(xué)院 信息工程學(xué)院，石家莊050031

School of Information Engineering,Shijiazhuang University of Economics,Shijiazhuang 050031,China

1 引言

背包問題（Knapsack Problem，KP）[1]是典型的組合優(yōu)化難題，具有較高的理論研究與實際應(yīng)用價值，在投資決策、預(yù)算控制、項目選擇、資源分配和貨物裝載等方面都有著非常重要的應(yīng)用?？焖俑咝У厍蠼釱P 問題一直是演化計算領(lǐng)域中的一個研究熱點，人們已相繼研究了如何利用遺傳算法、蟻群算法和微粒群算法，和聲算法等求解0-1 背包問題，取得了許多有益的結(jié)果[2-7]。本文提出了一種二進制蝙蝠算法，在求解KP 問題上取得了很好的效果，有很高的實用價值。

0-1KP 的一般描述：假設(shè)有d個物品，它們重量集W={w1,w2,…,wd}，物品價值集為V={v1,v2,…,vd}，背包的最大載重為C。找出一種裝包方法，使得裝入物品重量在不超過背包載重的前提下總價值最高。

0-1KP 的數(shù)學(xué)模型表示如下：

蝙蝠算法（Bat Algorithm，BA）[8]是Yang 于2010 年提出的一種新型啟發(fā)式算法，與其他算法相比，BA 在準(zhǔn)確性和有效性方面遠(yuǎn)優(yōu)于其他算法，且沒有許多參數(shù)要進行調(diào)整[9]。雖然蝙蝠算法提出時間不長，但已經(jīng)受到許多國內(nèi)外學(xué)者的關(guān)注，不但對算法的性能進行各種改進[9-12]，并將其成功的應(yīng)用到工程設(shè)計[13-16]、分類[17]、神經(jīng)網(wǎng)絡(luò)[18]、模糊聚類[19]等領(lǐng)域。本文在原算法基礎(chǔ)上提出了一種二進制蝙蝠算法BBA（Binary Bat Algorithm），使其能夠求解離散最優(yōu)化問題；為提高算法的收斂速度，加入了時變慣性因子w；求解0-1 背包問題中，將貪心策略引入BBA 得到貪心二進制蝙蝠算法GBBA（Greedy Binary Bat Algorithm），在求解精度和收斂性上都有很大改進，仿真實驗結(jié)果顯示算法精度和收斂性能都優(yōu)于文獻[15]的遺傳變異蝙蝠算法。

2 蝙蝠算法

蝙蝠是一種神奇的動物，它靠一種回聲定位器來探測獵物，避免障礙物。2010 年Yang 根據(jù)微型蝙蝠的回聲定位原理，并在以下面規(guī)則為前提的基礎(chǔ)上提出了一種蝙蝠算法。

（1）所有蝙蝠粒子利用自身回聲定位感知與目標(biāo)之間的距離，同時以一種特別的方式辨別目標(biāo)和背景障礙物的不同。

（2）蝙蝠i在位置Xi以速度Vi飛行，以變化頻率Fi∈[Fmin,Fmax]（或波長）和響度Ai搜尋目標(biāo)。它們可以判斷自己與獵物之間的距離并自動調(diào)整脈沖波長（或頻率）同時根據(jù)接近目標(biāo)的程度調(diào)整脈沖發(fā)射速率Ri∈[0，1]。

（3）假定響度是從最大值（正值）A0變化到固定最小值A(chǔ)min。

算法1蝙蝠算法的實現(xiàn)

步驟1確定目標(biāo)函數(shù)。

步驟2初始化每只蝙蝠位置Xi(i=1,2,…,n)，速度Vi，脈沖發(fā)射速率Ri，脈沖響度Ai，脈沖頻率Fi。

步驟3while（未到達(dá)預(yù)定的迭代次數(shù)）。

（1）利用公式（3）～（5）更新蝙蝠的速度Vi和位置Xi而產(chǎn)生后代：

（2）if（隨機數(shù)rand1 ＞Ri）：

從當(dāng)前最優(yōu)個體中選擇一個個體，利用公式（6）隨機產(chǎn)生一個局部個體，并計算這個局部個體的適應(yīng)度值；

（3）讓該蝙蝠隨機飛行。

（4）if（隨機數(shù)rand2 ＜Ai&&局部個體的適應(yīng)度值較全局最優(yōu)個體好）。

接受該新解為當(dāng)前最優(yōu)個體，用公式（7）和（8）增大Ri和減小Ai：

（5）對各個蝙蝠最優(yōu)解排序，選出當(dāng)前全局最優(yōu)解X*。

end while

步驟4輸出最終結(jié)果X*。

上面算法中公式（3）中Fmin和Fmax限制脈沖頻率的變化范圍，在Yang 的論文[8]中設(shè)置為0 和100，β為[0，1]上服從均勻分布的隨機因子。公式（7）中的α是脈沖響度衰減系數(shù)，為[0，1]上的常數(shù)，公式（8）中的γ是脈沖頻度增加系數(shù)，為大于零的常數(shù)。

3 二進制蝙蝠算法

蝙蝠算法主要應(yīng)用于解決連續(xù)函數(shù)的求解問題，為了拓展它的應(yīng)用范圍提出了一種簡捷高效的蝙蝠算法二進制化的方法。針對每只蝙蝠位置Xi引入一個新的二進制向量Bi，向量Bi在每一維上的值對應(yīng)于該蝙蝠的位置向量每一維上的數(shù)據(jù)，這里采用微粒群二進制算法[20-22]中使用的模糊函數(shù)作為轉(zhuǎn)化橋梁，映射關(guān)系如公式（9）：

其中Xij是第i只蝙蝠在第j維的位置值，它的取值是[-1,1]之間的實數(shù)。蝙蝠的實數(shù)位置Xi和速度Vi的變化仍然按照公式（3）～（5）進行計算。只是在設(shè)計目標(biāo)函數(shù)的時候要使用新的二進制位置向量Bi來計算。這里用0-1 背包問題作為實例。

第i只蝙蝠的二進制位置向量Bi的每一維上的值對應(yīng)背包物品的裝入與否，1 表示對應(yīng)物品裝入，0 表示不裝入。目標(biāo)函數(shù)計算公式如下：

當(dāng)該蝙蝠對應(yīng)二進制向量Bi確定的裝包方法使得裝入物品總重量不超過背包容量C時，裝入物品總價值為目標(biāo)函數(shù)值，否則目標(biāo)函數(shù)值為0；整個背包問題，相當(dāng)于找f(X)的最大值。另外第i只蝙蝠的局部最好位置也應(yīng)該有兩個，一個是實數(shù)向量，一個是二進制向量；蝙蝠群的全局最好位置也同樣的對應(yīng)兩個。

從公式（3）～（5）可以看出，在計算下一代蝙蝠時，算法在這里僅考慮了蝙蝠自身特征Vi，Xi和群體的社會因素X*，沒有考慮蝙蝠的局部特征，為提高蝙蝠局部搜索能力，從而提高算法的收斂性能，這里引入時變慣性因子[23]w到公式（4），生成新的速度變化公式如下：

w的變化公式如下：

其中t為迭代的代數(shù)，sumt為預(yù)定的總代數(shù)。

通過上面的分析，給出二進制蝙蝠算法BBA 的實現(xiàn)過程：

算法2二進制蝙蝠算法BBA

步驟1確定目標(biāo)函數(shù)。

步驟2初始化每只蝙蝠實數(shù)位置Xi(i=1,2,…,n)和二進制位置Bi，速度Vi，脈沖發(fā)射速率Ri，脈沖響度Ai，脈沖頻率Fi。

步驟3用公式（9）計算每只蝙蝠的適應(yīng)值，并將它設(shè)置成每只蝙蝠局部的最好適應(yīng)值，設(shè)每只蝙蝠局部最好實數(shù)位置Pi=Xi，局部最好二進制位置Pbi=Bi；從各個蝙蝠的局部最好適應(yīng)值中找出適應(yīng)值最好的蝙蝠k，設(shè)蝙蝠全局最好實數(shù)位置X*=Xk，蝙蝠全局最好二進制位置Pb*=Bk。

步驟4while（未到達(dá)預(yù)定的迭代次數(shù)）。

（1）利用公式（3）、（11）、（5）、（9）更新蝙蝠的速度Vi和實數(shù)位置Xi和二進制位置Bi產(chǎn)生后代。

（2）if（隨機數(shù)rand1 ＞Ri）：

從當(dāng)前最優(yōu)個體中選擇一個個體，利用公式（6）隨機產(chǎn)生一個局部實數(shù)個體，同時用公式（9）相應(yīng)產(chǎn)生局部二進制個體，并用公式（10）計算這個局部個體的適應(yīng)度值。

endif

（3）讓該蝙蝠隨機飛行。

（4）if（隨機數(shù)rand2 ＜Ai&&局部個體的適應(yīng)度值較全局最優(yōu)個體好）：

接受該新解（實數(shù)和二進制）為當(dāng)前最優(yōu)個體，用公式（7）和（8）增大Ri和減小Ai。

endif

（5）對各個蝙蝠最優(yōu)解排序，選出當(dāng)前全局最優(yōu)解（X*，Pb*）。

end while

步驟5輸出最終結(jié)果Pb*。

4 二進制蝙蝠算法求解0-1 背包問題

使用BBA 直接求解背包問題，找到最優(yōu)解的機率偏低，原因是當(dāng)出現(xiàn)無效蝙蝠（裝入總物品超重）時，只粗暴的將目標(biāo)函數(shù)值設(shè)為0，相當(dāng)于直接舍去了該蝙蝠的原有的飛行信息，這樣對集體尋優(yōu)是一個損失，從而減慢了找到最優(yōu)解的速度和機會。如果不直接舍去無效蝙蝠，而是對該蝙蝠加以修正，在最小改變其原有飛行信息的基礎(chǔ)上，把它拉到在靠近最優(yōu)值附近的合法的軌道上來，對整個蝙蝠群體找到最優(yōu)將是大貢獻。很明顯這樣會大大提高算法的收斂效率，仿真實驗證明確實如此。這里把貪心策略引入到修正無效蝙蝠中，當(dāng)無效蝙蝠出現(xiàn)的時候，使用優(yōu)化函數(shù)對蝙蝠位置（Xi和Bi）進行優(yōu)化，使其成為有效的蝙蝠，并且在有效蝙蝠的基礎(chǔ)上調(diào)整到的最佳。該優(yōu)化函數(shù)的設(shè)計參考了文獻[4]的優(yōu)化策略并做了改進。具體優(yōu)化函數(shù)實現(xiàn)如下：

算法3優(yōu)化函數(shù)（為方便描述用數(shù)組形式表示各個相關(guān)向量）

輸入：無效蝙蝠u的位置向量Xu[1…d]，以及它所對應(yīng)的二進制向量Bu[1…d]和該蝙蝠的裝入物品總重sumw；

輸出：蝙蝠u的合法位置向量，合法的二進制向量。

步驟1將所有物品按價值和重量的比vi/wi從小到大排序，構(gòu)成單位重量的價值由低到高的一組數(shù)sortnum[1…d]（序號為sortnum[j]的物品單位重量的價值高于序號為sortnum[j+1]物品）。

步驟2將單位價值量低的并在背包中的物品依次取出，當(dāng)背包中物品總重量小于或等于背包載重C時停止。

（1）j=1；

（2）if(Bu[sortnum[j]]==1)

{sumw=sumw-W[sortnum[j]]；

Bu[sortnum[j]]=0；

Xu[sortnum[j]]=-Xu[sortnum[j]]；}

if(sumw＜=C)結(jié)束整個步驟2，else 轉(zhuǎn)到（3）

}

（3）j=j+1；

（4）if（j>物品個數(shù)d）轉(zhuǎn)到步驟3，else 轉(zhuǎn)到（2）。

步驟3將單位價值量高并且還沒有裝入背包的物品測試是否還能裝入，如果裝入后沒有超重，則裝入。

（1）令j=d；

（2）if(Bu[sortnum[j]]==0)

{sumw=sumw+W[sortnum[j]]；

if(sumw＜=C)

{Bu[sortnum[j]]==1；

Xu[sortnum[j]]=-Xu[sortnum[j]]；}

elsesumw-=W[sortnum[j]]；}

（3）j=j-1；

（4）if(j＞0)轉(zhuǎn)到（2），else 轉(zhuǎn)到（5）；

（5）輸出Xu[1…d]和Bu[1…d]。

在二進制蝙蝠算法中，當(dāng)無效蝙蝠出現(xiàn)時即調(diào)用上面的優(yōu)化函數(shù)修正蝙蝠，由此即得貪心二進制蝙蝠算法GBBA。

5 仿真實驗

仿真計算所使用微機的硬件環(huán)境為Intel?CoreTMDuo CPU T2400 1.83 GHz，1 GB RAM，操作系統(tǒng)Windows XP2002，編程環(huán)境VC++6.0。GBBA 算法中各個參數(shù)的設(shè)置：Vmax=6.0 ；Xmax=-1.0 ；Xmax=1.0 ；Fmin=0.01；Fmax=0.071；R0=0.75；A0=0.005；脈沖頻度增強系數(shù)β=0.7；脈沖音強衰減系數(shù)α=0.95；三個實例的數(shù)據(jù)均來自文獻[15]中。

表1 GBBA 與GMBA 算法求解實例1～3 的結(jié)果比較

表2 GBBA 與GMBA 算法求解實例1～3 的收斂性比較

實例1物品個數(shù)d=10，背包載重限制C=269，物件重量集W={95,4,60,32,23,72,80,62,65,46}，物件價值集V=[55,10,47,5,4,50,8,61,85,87]，問題的最優(yōu)值為295。

實例2物件個數(shù)d=20，背包載重限制C=878，物件重量集W=[92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,7048,14,58]，物件價值集V=[44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63]，問題的最優(yōu)值為1 024。

實例3物件個數(shù)d=50，背包載重限制C=11 258，物件重量集W= [438，754，699，587，789，912，819，347，511，287，541，784，676，198，572，914，988，4，355，569，144，272，531，556，741，489，321，84，194，483，205，607，399，747，118，651，806，9，607，121，370，999，494，743，967，718，397，589，193，369]，物件價值集V= [72，490，651，833，883，489，359，337，267，441，70，934，467，661，220，329，440，774，595，98，424，37，807，320，501，309，834，851，34，459，111，253，159，858，793，145，651，856，400，285，405，95，391，19，96，273，152，473，448，231]，問題的最優(yōu)值為16 102。

為了驗證算法的尋優(yōu)能力和收斂性能，對上述三個實例分別計算50 次，結(jié)果與文獻[15]中實驗結(jié)果進行比對如表1 和表2 所示。

在表1 中，“最差值”是指運行50 次中最差的結(jié)果，“最優(yōu)值”是50 次中最優(yōu)的結(jié)果，“平均值”是50 個結(jié)果的平均數(shù)。此表數(shù)據(jù)證明，本文提出的貪心蝙蝠算法在求解精度和穩(wěn)定性方面均優(yōu)于文獻[15]改進的蝙蝠算法，能夠更有效地找到最優(yōu)解。尤其是數(shù)據(jù)量大的背包問題（如實例3），更加凸顯本算法的優(yōu)勢。

為了更好地和GMBA 算法做比較，本文使用了同樣的收斂性比較方案：在最大迭代次數(shù)范圍內(nèi)，如果找到最優(yōu)值則立即結(jié)束該次迭代，且認(rèn)為尋優(yōu)成功，如果找不到則認(rèn)為尋優(yōu)失敗，結(jié)果如表2 所示。在表2 中，“最小數(shù)”指尋優(yōu)成功代數(shù)中最小數(shù)，“平均數(shù)”指各個尋優(yōu)成功代數(shù)的平均數(shù)，“成功率”指尋優(yōu)成功的概率。表2 實驗數(shù)據(jù)顯示，GBBA 算法的收斂速度高于GMBA 算法，尤其對于數(shù)據(jù)量大的背包問題，成功率遠(yuǎn)高于GMBA 算法。

6 結(jié)束語

本文以簡捷的方式給出了一種二進制蝙蝠算法，并且為了提高算法的收斂性能引入時變慣性因子；在利用二進制蝙蝠算法求解背包問題時針對無效蝙蝠進行修正，修正中采用了貪心策略，不僅把無效蝙蝠拉到有效的線路上，并且加以優(yōu)化，使它更有利于快速地找到最優(yōu)解，進而提出了GBBA 算法。仿真計算結(jié)果表明GBBA 的收斂速度快，找到最優(yōu)解的成功率高，是一種非常適于求解背包問題的算法?；贕BBA 算法的高效性，今后將進一步研究如何利用蝙蝠算法求解動態(tài)背包問題以及其他組合最優(yōu)化問題。

[1] 康立山，謝云，尤矢勇，等.非數(shù)值并行算法—模擬退火算法[M].北京：科學(xué)出版社，1998：5-7.

[2] Yuen S Y.A genetic algorithm that adaptively mutates and never revisits[J].IEEE Transactions on Evolutionary Computation，2009，13（2）：454-472.

[3] Changdar C，Mahapatra G S，Pal R K.An ant colony optimization approach for binary knapsack problem under fuzziness[J].Applied Mathematics and Computation，2013，223：243-253.

[4] 賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計算機工程與設(shè)計，2007，28（11）：2655-2658.

[5] 何小鋒，馬良.求解0-1 背包問題的量子蟻群算法[J].計算機工程與應(yīng)用，2011，47（16）：29-31.

[6] 李寧，劉建芹，賀毅朝.基于和聲搜索算法求解組合優(yōu)化問題[J].計算機應(yīng)用，2012，32（4）：1041-1044.

[7] 沈顯君，王偉武，鄭波盡，等.基于改進的微粒群優(yōu)化算法的0-1 背包問題求解[J].計算機工程，2006，32（18）：23-25.

[8] Yang Xinshe.A new metaheuristic bat-inspired algorithm[C]//Proceedings of Nature Inspired Cooperative Strategies for Optimization，2010：65-74.

[9] 賀興時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優(yōu)化算法[J].計算機應(yīng)用研究，2013，9（31）：392-397.

[10] 謝健，周永權(quán)，陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模擬識別與人工智能，2013，26（9）：829-837.

[11] 劉長平，葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真[J].系統(tǒng)仿真學(xué)報，2013，25（6）：1183-1188.

[12] Yang Xinshe.Bat algorithm for multiobjective optimization[J].International Journal Bio-Inspired Computation，2011，3（5）：267-274.

[13] Yang Xinshe.GANDOMI A H.Bat algorithm：A novel approach for global engineering optimization[J].Engineering Computations，2012，29（5）：464-483.

[14] Lemma T A，Bin M H F.Use of fuzzy systems and bat algorithm for energy modeling in a gas turbine generator[C]//Proc of IEEE Colloquium on Humanities，Science and Engineering，2011：305-310.

[15] 李枝勇，馬良，張惠珍.遺傳變異蝙蝠算法在0-1 背包問題上的應(yīng)用[J].計算機工程與應(yīng)用，2014，50（11）：49-52.

[16] 盛曉華，葉春明.基于蝙蝠算法的PFSP 調(diào)度干擾管理研究[J].計算機工程與應(yīng)用，2014，50（8）：241-246.

[17] Mish R A S，Shaw K，Mish R A D.A new metaheuristic classification approach for microarray data[J].Procedia Technology，2012，4（1）：802-806.

[18] Khan K，Sahai A.A comparison of BA，GA，PSO，BP and LM for training feed forward neural networks in e-learning context[J].International Journal of Intelligent Systems and Applications，2012，4（7）：23-29.

[19] Khan K，Nikov A，Sahai A.A fuzzy bat clustering method for ergonomic screening of office workplaces，S3T 2011[C]//Advances in Intelligent and Soft Computing，2011：59-66.

[20] Kennedy J，Spears W M.Matching algorithms to problems：An experimental test of the particle swarm and some genetic algorithms on the multimode problem generator[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC），1998：78-83.

[21] Kennedy J，Eberhartr C.A discrete binary particle swarm optimization[C]//Proceedings of 1997 Conference on System，Man，and Cybernetices.Piscataway，NJ：IEEE Service Center，1997：4104-4109.

[22] 賀毅朝，王彥祺，劉建芹.一種適于求解離散問題的二進制粒子群優(yōu)化算法[J].計算機應(yīng)用與軟件，2007，24（1）：157-159.

[23] 崔志華，曾建潮.微粒群優(yōu)化算法[M].北京：科學(xué)出版社，2011：33-35.