程春英

摘要：該文將螢火蟲(chóng)算法應(yīng)用于求解小規(guī)模0/1背包問(wèn)題，利用基本螢火蟲(chóng)算法的求解思想，對(duì)0/1背包問(wèn)題進(jìn)行分析，通過(guò)對(duì)物品數(shù)為10、25和50的背包問(wèn)題進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該算法在解決小規(guī)模0/1背包問(wèn)題是可行的。

關(guān)鍵詞：螢火蟲(chóng)算法；0/1背包問(wèn)題；感知范圍

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

2 螢火蟲(chóng)算法

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

螢火蟲(chóng)算法首先在問(wèn)題空間隨機(jī)分布[N]只螢火蟲(chóng)，這些螢火蟲(chóng)都帶有熒光，每個(gè)螢火蟲(chóng)都具有自己的感知范圍[Rid]（[0

2.1 螢火蟲(chóng)的熒光素

螢火蟲(chóng)算法中，螢火蟲(chóng)的熒光素值體現(xiàn)了螢火蟲(chóng)所處位置的優(yōu)劣并決定螢火蟲(chóng)的移動(dòng)方向。熒光素值越高對(duì)其感知范圍內(nèi)的其它螢火蟲(chóng)的吸引力就越強(qiáng)，朝這個(gè)方向聚集的可能性也就越大。

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4] 宋瀟瀟.求解大規(guī)模0-1背包問(wèn)題的改進(jìn)人工魚群算法[J].西華大學(xué)學(xué)報(bào)：自然科學(xué)版，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背包問(wèn)題的螢火蟲(chóng)群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（4）：993-994.