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

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

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

石家莊經濟學院 信息工程學院，石家莊050031

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

1 引言

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

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

0-1KP 的數學模型表示如下：

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

2 蝙蝠算法

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

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

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

（3）假定響度是從最大值（正值）A0變化到固定最小值Amin。

算法1蝙蝠算法的實現

步驟1確定目標函數。

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

步驟3while（未到達預定的迭代次數）。

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

（2）if（隨機數rand1 ＞Ri）：

從當前最優個體中選擇一個個體，利用公式（6）隨機產生一個局部個體，并計算這個局部個體的適應度值；

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

（4）if（隨機數rand2 ＜Ai&&局部個體的適應度值較全局最優個體好）。

接受該新解為當前最優個體，用公式（7）和（8）增大Ri和減小Ai：

（5）對各個蝙蝠最優解排序，選出當前全局最優解X*。

end while

步驟4輸出最終結果X*。

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

3 二進制蝙蝠算法

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

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

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

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

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

w的變化公式如下：

其中t為迭代的代數，sumt為預定的總代數。

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

算法2二進制蝙蝠算法BBA

步驟1確定目標函數。

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

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

步驟4while（未到達預定的迭代次數）。

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

（2）if（隨機數rand1 ＞Ri）：

從當前最優個體中選擇一個個體，利用公式（6）隨機產生一個局部實數個體，同時用公式（9）相應產生局部二進制個體，并用公式（10）計算這個局部個體的適應度值。

endif

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

（4）if（隨機數rand2 ＜Ai&&局部個體的適應度值較全局最優個體好）：

接受該新解（實數和二進制）為當前最優個體，用公式（7）和（8）增大Ri和減小Ai。

endif

（5）對各個蝙蝠最優解排序，選出當前全局最優解（X*，Pb*）。

end while

步驟5輸出最終結果Pb*。

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

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

算法3優化函數（為方便描述用數組形式表示各個相關向量）

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

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

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

步驟2將單位價值量低的并在背包中的物品依次取出，當背包中物品總重量小于或等于背包載重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)結束整個步驟2，else 轉到（3）

}

（3）j=j+1；

（4）if（j>物品個數d）轉到步驟3，else 轉到（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)轉到（2），else 轉到（5）；

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

在二進制蝙蝠算法中，當無效蝙蝠出現時即調用上面的優化函數修正蝙蝠，由此即得貪心二進制蝙蝠算法GBBA。

5 仿真實驗

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

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

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

實例1物品個數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]，問題的最優值為295。

實例2物件個數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]，問題的最優值為1 024。

實例3物件個數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]，問題的最優值為16 102。

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

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

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

6 結束語

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

[1] 康立山，謝云，尤矢勇，等.非數值并行算法—模擬退火算法[M].北京：科學出版社，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] 賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應用[J].計算機工程與設計，2007，28（11）：2655-2658.

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

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

[7] 沈顯君，王偉武，鄭波盡，等.基于改進的微粒群優化算法的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] 賀興時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優化算法[J].計算機應用研究，2013，9（31）：392-397.

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

[11] 劉長平，葉春明.具有混沌搜索策略的蝙蝠優化算法及性能仿真[J].系統仿真學報，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 背包問題上的應用[J].計算機工程與應用，2014，50（11）：49-52.

[16] 盛曉華，葉春明.基于蝙蝠算法的PFSP 調度干擾管理研究[J].計算機工程與應用，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] 賀毅朝，王彥祺，劉建芹.一種適于求解離散問題的二進制粒子群優化算法[J].計算機應用與軟件，2007，24（1）：157-159.

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