求解背包問題的布谷鳥搜索算法

許秋艷（鹽城工學院信息工程學院，鹽城　224051）

求解背包問題的布谷鳥搜索算法

許秋艷
（鹽城工學院信息工程學院，鹽城224051）

1　背包問題的數(shù)學模型

背包問題是計算機科學和管理科學中的一個典型優(yōu)化問題，有著極其重要的研究價值。就計算時間復雜程度而言，背包問題屬于經(jīng)典的組合優(yōu)化NP難問題。同時，背包問題在實際問題中有著廣泛的應用，如材料分割問題、投資選擇問題、項目組合問題等。

最經(jīng)典的背包問題是0-1背包問題，該問題可以表示為：給定1個背包和n個物品，其中第i個物品的價值為pi，重量為wi，背包能夠容納的物品重量為c?，F(xiàn)在要選擇部分物品放入背包中，在保證放入物品的總重量不超過c的條件下，使得物品的總價值達到最大。背包問題的數(shù)學模型可以描述為：令pi和wi分別表示第i個物品的價值和重量，c表示背包能夠容納的物品總重量，設決策變量：

則0-1背包問題可以表示成如下的0-1整數(shù)規(guī)劃模型

目前求解背包問題的算法可以分為傳統(tǒng)優(yōu)化算法和現(xiàn)代啟發(fā)式算法兩大類，例如分枝定界法、動態(tài)規(guī)劃法、降階法、遺傳算法、蟻群優(yōu)化算法、微粒群算法等等。這些方法為求解背包問題提供了思路，但都無法完全有效求解。如何設計背包問題的求解方法，仍然是一個開放性的問題。

2　背包問題的布谷鳥搜索算法

布谷鳥搜索算法是由Yang和Deb在2009年提出的一種現(xiàn)代啟發(fā)式算法，其優(yōu)化原理源于對布谷鳥寄生育雛行為和鳥類的萊維飛行行為的模擬。布谷鳥搜索算法已經(jīng)在神經(jīng)網(wǎng)絡訓練、工程設計優(yōu)化、交通流量預測和人臉識別等方面等到成功應用。基于該算法良好的優(yōu)化性能，本文將算法用于背包問題的求解。

布谷鳥搜索算法基本流程如下所示：

算法布谷鳥搜索算法

Begin

群體初始化，Xi表示第i個個體（i=1，2，…，n）

計算每個個體的適應度函數(shù)值Fi（i=1，2，…，n）While（未達到最大迭代次數(shù)）采用萊維飛行生成新解Xi

計算新解Xi的適應度函數(shù)值Fi

隨機選擇候選解Xj

If Fi＞Fj

采用新解替換候選解End

根據(jù)發(fā)現(xiàn)概率Pa舍棄差的解

保留每次迭代中產(chǎn)生的最好的解

End

End

上述布谷鳥搜索算法是為求解連續(xù)優(yōu)化問題而提出的，為充分發(fā)揮其在處理連續(xù)優(yōu)化問題的優(yōu)勢，仍限定算法的搜索空間為連續(xù)空間，且搜索范圍為［0，1］。為將算法搜索空間的解和背包問題離散的解相對應，采用如下方法：如果Xij＞rand，則其問題對應的分量取1；否則取0。其中，Xij表示第i個解的第j個分量；rand表示0到1之間的隨機數(shù)。

3　數(shù)值實驗

圖1　算例2的優(yōu)化示意圖

圖2　算例2的優(yōu)化示意圖

為驗證所提算法的優(yōu)化性能，采用背包問題的典型算例進行實驗。算法采用MATLAB（R2011a）軟件編程實現(xiàn)，在CPU為i7、內(nèi)存為4G的Dell臺式機上運行。大量的數(shù)值實驗表明，所提算法具有良好的優(yōu)化性能。限于篇幅，僅給出其中2個算例。

算例1物品件數(shù)n=10，各個物品重量w=［95，4，60，32，23，72，80，62，65，46］，各個物品價值p=［55，10，47，5，4，50，8，61，85，87］，背包最大重量c=269，最優(yōu)值為295。

算例2物品件數(shù)n=20，各個物品重量w= ［92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58］，各個物品價值 p=［44，46，90，72，91，40，75，35，8，54，78，40，77，15，61，17，75，29，75，63］，背包最大重量c=878，最優(yōu)值為1024。

采用本文提出的布谷鳥搜索算法，對這2個算例進行求解，均可以獲得最優(yōu)解。圖1-圖2給出了算法的優(yōu)化示意圖。

本文提出的布谷鳥搜索算法在求解背包問題時表現(xiàn)出良好的優(yōu)化性能，將算法用于其他類型的背包問題（如非線性背包問題、多維背包問題和多目標背包問題等）是進一步的研究方向。

［1］Yang X，Deb S.Cuckoo search via levy flights［C］.World Congress on Nature&Biologically Inspired Computing.Piscataway：IEEE Publications，2009：210-214.

［2］Yang X S，Deb S.Engineering optimization by cuckoo search［J］.International Journal of Mathematical Modeling and Numerical Optimization，2010，1（4）：330-343.

［3］樊小毛，馬良．0-1背包問題的蜂群優(yōu)化算法［J］.數(shù)學的實踐與認識，2010，40（6）：155-160．

Knapsack Problem；Cuckoo Search Algorithm；Combinatorial Optimization

Cuckoo Search Algorithm for Solving Knapsack Problem

XU Qiu-yan
（School of Information Engineering，Yancheng Institute of Technology，Yancheng 224051）

1007-1423（2015）23-0032-03

10.3969/j.issn.1007-1423.2015.23.007

許秋艷（1981-），女，江蘇東臺人，碩士，講師，研究方向為算法設計及其應用

2015-06-26

2015-08-05

背包問題是計算機科學一種典型的組合優(yōu)化難題。為處理背包問題，設計基于布谷鳥搜索算法的優(yōu)化方法。布谷鳥搜索算法是一種新型現(xiàn)代啟發(fā)式算法，在求解連續(xù)優(yōu)化問題時表現(xiàn)出良好的優(yōu)化性能。在求解背包問題時，算法的搜索空間限制在連續(xù)空間，并通過自定義的映射，將背包問題的解空間和算法的搜索空間相對應。數(shù)值試驗驗證該算法的可行性和有效性。

背包問題；布谷鳥搜索算法；組合優(yōu)化

Knapsack problem （KP）is a typical NP-hard problem in combinatorial optimization in computer science.To deal with KP，proposes a method based on cuckoo search algorithm（CSA）.CSA is a novel metaheuristic and shows good performance in solving continuous optimization problems.For solving KP，the search space of CSA is restricted in continuous space.The solution space of KP is corresponded to the search space of CSA by the self-defined map.The experimental results show that the proposed algorithm is feasible and effective.