程春英

摘要：該文將螢火蟲算法應用于求解小規(guī)模0/1背包問題，利用基本螢火蟲算法的求解思想，對0/1背包問題進行分析，通過對物品數為10、25和50的背包問題進行了仿真實驗，實驗結果表明該算法在解決小規(guī)模0/1背包問題是可行的。

關鍵詞：螢火蟲算法；0/1背包問題；感知范圍

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）02-0166-03

Abstract：In this paper， the glowworm dwarm optimization was applied to solve the small-scale 0/1 knapsack problem， using basic idea of glowworm swarm optimization ， analyze the 0/1 knapsack problem， Through the items for 10、20 and 50 knapsack problem to carry on the simulation experiment， The experimental results show that the algorithm in solving the small-scale 0/1 knapsack problem is feasible.

Key words： glowworm swarm optimization； 0/1Knapsack problem ； feeling range

1 引言

背包問題（Knapsack Problem）是運籌學中一類經典的優(yōu)化問題，是一個經典的N-P問題[1]。背包問題在現實生活中具有廣泛的應用背景，如物流公司貨物的發(fā)配、控制預算以及工廠的下料等都可以用背包問題進行求解。在設計解決復雜組合優(yōu)化問題時，背包問題往往作為其子問題出現。

對于0/1背包問題人們提出了很多好的改進的算法，例如蟻群算法[2]、粒子群算法[3]、人工魚群算法[4]等等。螢火蟲算法（Glowworm Swarm Optimization， GSO）[5-6]是2005年由印度學者Krishnanand和Ghose提出的一種基于生物群體智能的隨機優(yōu)化算法，它是繼粒子群優(yōu)化算法、細菌覓食算法、人工魚群算法之后的又一種新型的仿生智能優(yōu)化算法。螢火蟲算法是通過模擬螢火蟲在覓食、警戒和求偶等生活習性中產生的因光而吸引移動的行為來解決最優(yōu)問題的。該算法具有實現簡單，計算效率高、適用能力強等特點，已經成為了計算智能領域的研究熱點。

0/1背包問題是典型的背包問題，0/1背包問題是指：給定[n]種物品和一個背包，第[i]個物品的重量為[wi]，第[i]個物品的價值為[v i]，背包的限制容量為[c]。求應怎樣裝入背包中的物品，使得裝入背包中物品的總價值最大。

2 螢火蟲算法

自然界中的螢火蟲都會發(fā)出特有的閃光信號來吸引其它螢火蟲，這種閃光信號就是短促并有節(jié)奏的熒光，螢火蟲借助熒光來完成覓食、求偶和警戒等行為。螢火蟲算法就是模擬自然界中螢火蟲發(fā)光行為來構造的一種隨機優(yōu)化算法，算法中利用螢火蟲的發(fā)光特性在其感知范圍內尋找其它同伴，并向感知范圍內位置較好的螢火蟲方向移動，從而實現位置更新和移動過程。

螢火蟲算法首先在問題空間隨機分布[N]只螢火蟲，這些螢火蟲都帶有熒光，每個螢火蟲都具有自己的感知范圍[Rid]（[0

2.1 螢火蟲的熒光素

螢火蟲算法中，螢火蟲的熒光素值體現了螢火蟲所處位置的優(yōu)劣并決定螢火蟲的移動方向。熒光素值越高對其感知范圍內的其它螢火蟲的吸引力就越強，朝這個方向聚集的可能性也就越大。

4 結論

本文根據基本螢火蟲算法的基本思路，分析了螢火蟲算法在解決小規(guī)模背包問題上的可行性。通過仿真實驗對物品數為10、25和50的問題進行了求解，實驗結果表明，對于基本螢火蟲算法，當問題規(guī)模較小時可以找到目前已知最優(yōu)解，但隨著問題規(guī)模的增大尋優(yōu)效果不是很理想，需要對基本螢火蟲算法加以改進來適應求解大規(guī)模的背包問題。

參考文獻：

[1] Tian Feng-nan， Wang Yu. Summary algorithm for solving 0-1 knapsack Problem [J].Soft ware Guide.2009，8（1）：59-61.

[2] 馬良，王龍德. 背包問題的螞蟻優(yōu)化算法[J]. 計算機應用.2001，21（8）：4-5.

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

[4] 宋瀟瀟.求解大規(guī)模0-1背包問題的改進人工魚群算法[J].西華大學學報：自然科學版，2013，32（4）：5-9.

[5] Krishnanand K N，Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics[C]//Swarm Intelligence symposium，2005. SIS 2005. Proceedings 2005 IEEE. IEEE，2005：84-91.

[6] Krishnanand K N，Ghose D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications [J]. Multivalent and Grid Systems，2006：209-222.

[7] 程魁，馬良.0-1背包問題的螢火蟲群優(yōu)化算法[J].計算機應用研究，2013，30（4）：993-994.