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

許秋艷（鹽城工學(xué)院信息工程學(xué)院，鹽城　224051）

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

許秋艷
（鹽城工學(xué)院信息工程學(xué)院，鹽城224051）

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

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

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

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

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

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

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

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

算法布谷鳥搜索算法

Begin

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

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

計(jì)算新解Xi的適應(yīng)度函數(shù)值Fi

隨機(jī)選擇候選解Xj

If Fi＞Fj

采用新解替換候選解End

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

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

End

End

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

3　數(shù)值實(shí)驗(yàn)

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

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

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

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

算例2物品件數(shù)n=20，各個(gè)物品重量w= ［92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58］，各個(gè)物品價(jià)值 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。

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

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

［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ù)學(xué)的實(shí)踐與認(rèn)識(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-），女，江蘇東臺(tái)人，碩士，講師，研究方向?yàn)樗惴ㄔO(shè)計(jì)及其應(yīng)用

2015-06-26

2015-08-05

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

背包問題；布谷鳥搜索算法；組合優(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.