劉藝蘭，徐麗紅，吳豐彥，潘淑靜

(中國傳媒大學(xué)計算機學(xué)院，北京 100024)

0 引言

背包問題(Knapsack Problem，KP)是一種組合優(yōu)化的NP完全問題，也是運籌學(xué)中的一個典型的優(yōu)化難題，有非常廣泛的實際應(yīng)用背景，如運輸中的貨物裝載、人造衛(wèi)星的物品裝載、預(yù)算控制以及項目選擇等問題，很多整數(shù)規(guī)劃問題的解決理論上都依賴于高效的背包問題解法［1］。一般的背包問題在整數(shù)、有界的條件下可轉(zhuǎn)換成等價的0-1背包問題(0-1 Knapsack Problem)，0-1背包問題還可用于研究動態(tài)自適應(yīng)多媒體處理方法［2］、基于用戶遷徙網(wǎng)絡(luò)的廣告投放策略［3］等方面，因此研究0-1背包問題有非常重要的實際意義。

關(guān)于求解0-1背包問題的算法，很多學(xué)者都進行了研究，例如差異演化算法［4］、遺傳算法及其相關(guān)改進算法與混合算法［5-7］、改進人工魚群算法［8］、量子蟻群算法［9］、模糊粒子群算法［10］、細菌覓食算法［11］、煙花算法［12］等。本文則使用螢火蟲算法來研究0-1背包問題，螢火蟲算法有2種:GSO(Glowworm Swarm Optimisation)和FA(Firefly Algorithm)，文獻［13］經(jīng)過實驗對比說明了2種螢火蟲算法的可行性，并且尋優(yōu)精度整體上優(yōu)于粒子群優(yōu)化算法，而且螢火蟲算法參數(shù)少，實現(xiàn)簡單，因此可以使用螢火蟲算法來研究0-1背包問題。文獻［14］已設(shè)計并使用改進的GSO算法針對0-1背包問題進行了求解，并取得了較為滿意的效果，本文則使用另一種螢火蟲算法——FA來求解0-1背包問題。

下面對0-1背包問題進行描述:給定n個重量為{W1，W2，...，Wn}價值為{P1，P2，...，Pn}的物品和一個容量為V的背包，0-1背包問題是求這些物品中的一個最有價值的子集，并且要能夠裝到背包中。設(shè)變量xi表示第i種物品是否裝入背包，xi=1表示裝入背包，xi=0表示不裝入背包，則0-1背包問題的數(shù)學(xué)模型如下:

1 螢火蟲算法(FA)

1.1 簡介

螢火蟲算法是一種新型的仿生群智能優(yōu)化算法，是受自然界中的螢火蟲通過熒光進行信息交流這種群體行為的啟發(fā)演變而來的［13］。螢火蟲算法目前的2種版本，GSO是由印度學(xué)者Krishnanand等人［15］在2005年提出的，F(xiàn)A是由劍橋大學(xué)Xin-She Yang教授［16］在2008年提出的。本文使用FA來對0-1背包問題進行求解。

1.2 原理

自然界中的螢火蟲會發(fā)出熒光，以此來吸引異性、捕食或作為警戒信號等。螢火蟲優(yōu)化算法利用該原理，將搜索空間中的可行解模擬為螢火蟲個體的位置，將搜索和優(yōu)化過程模擬為螢火蟲個體通過吸引進行位置移動和更新的過程，每個螢火蟲位置的優(yōu)劣取決于其所代表的可行解對應(yīng)的目標函數(shù)值，將螢火蟲個體的優(yōu)勝劣汰過程模擬為搜索和優(yōu)化過程中用較好可行解取代較差可行解的迭代過程［17］。

1.3 流程

算法中使用到的字母符號及其所代表的意義如表1所示。

表1 字母符號說明表

(1)初始化基本參數(shù)(n，β0，γ，α，m)。

(2)隨機初始化螢火蟲的位置，計算目標函數(shù)值作為其最大螢光亮度I0。

(3)計算螢火蟲的I和β，確定移動方向。

(4)更新螢火蟲的空間位置。公式如下:

(5)重新計算螢火蟲的亮度。

(6)若達到最大迭代次數(shù)則轉(zhuǎn)下一步;否則，迭代次數(shù)增加1，轉(zhuǎn)(3)。

(7)輸出結(jié)果。

算法的時間復(fù)雜度為O(n2)，n為螢火蟲數(shù)目。

2 求解0-1背包問題的螢火蟲算法

將螢火蟲算法應(yīng)用到0-1背包問題時，每個螢火蟲個體的位置就是0-1背包問題的一個可行解向量，該向量的每個分量取0或1，第i個螢火蟲位置的第j個分量取0(或1)就代表該螢火蟲位置所代表的可行解是將第j個物品不裝入(或裝入)背包中。決定每個螢火蟲位置優(yōu)劣的目標函數(shù)值是其所代表可行解的物品總價值，總價值高的螢火蟲能夠吸引總價值低的螢火蟲向其移動，如此經(jīng)過多次迭代與移動就能夠優(yōu)勝劣汰。

將螢火蟲算法應(yīng)用到0-1背包問題的過程中，還需要考慮以下幾方面的內(nèi)容。

2.1 離散化

因為0-1背包問題的所有可行解都只包含0、1兩種狀態(tài)，因此本文參考文獻［14］以0.5為分界點，在初始化位置和每一次迭代更新位置后，對每個螢火蟲的位置進行離散化處理:

2.2 可行化

初始化位置和每一輪位置的更新、離散化后，得到的解未必可行，因為對于0-1背包問題，物品的總重量是有限制的，若某個解的總重量超過了限制，則為不可行解。對于每一輪可能存在的不可行解，本文參考文獻［14］，利用貪心策略將不可行解可行化，使搜索總是在可行解空間上進行，同時在保證解的可行性的前提下，盡量增加其適應(yīng)度值。不可行解xi可行化的過程如下:按物品的單位重量價值由小到大的方向?qū)ij=1變?yōu)閤ij=0，直至將不可行解變?yōu)榭尚薪狻?/p>

2.3 多樣化

為了增加螢火蟲種群的多樣性，本文借鑒遺傳算法的變異策略，對每一輪螢火蟲的位置在更新、離散化之后，對熒光亮度最低的螢火蟲進行變異處理，以增加螢火蟲種群的多樣性。變異的策略也是前面所述的貪心策略:對于熒光亮度最低的螢火蟲xi，按物品的單位重量價值由大到小的方向找到一個xij=0將其變?yōu)閤ij=1。

2.4 算法流程

綜上所述，求解0-1背包問題的螢火蟲算法的流程大致如下:

(1)初始化基本參數(shù)。設(shè)置螢火蟲數(shù)目n，最大吸引度β0，光強吸收系數(shù)γ，步長因子α，最大迭代次數(shù)m。

(2)隨機初始化螢火蟲位置。xij=rand。

(3)離散化。將(2)中隨機初始化的螢火蟲位置以0.5為分界點進行離散化。

(4)按照貪心算法機制將不可行解可行化。

(5)計算每個螢火蟲的目標函數(shù)值作為各自最大熒光亮度I0。

(6)計算螢火蟲之間的吸引度β。

(7)根據(jù)I0確定螢火蟲的移動方向，根據(jù)(6)中計算出的β更新螢火蟲的空間位置，對處在最佳位置的螢火蟲進行隨機擾動。

(8)對更新后的螢火蟲位置進行離散化。

(9)計算每個螢火蟲更新位置后的目標函數(shù)值作為各自最大熒光亮度I0。

(10)對熒光亮度I0最小的螢火蟲，按照貪心策略進行變異。

(11)將進行變異后的螢火蟲種群位置可行化。

(12)若滿足最大迭代次數(shù)，則跳出循環(huán)迭代，進行下一步;否則，迭代次數(shù)加1，轉(zhuǎn)至步驟(5)，進行下一次位置的更新。

(13)輸出結(jié)果。

求解0-1背包問題的螢火蟲算法的流程如圖1所示。

3 仿真實驗結(jié)果及分析

3.1 實驗內(nèi)容

本文運用Microsoft Visual Studio 2010軟件，將上述解決0-1背包問題的螢火蟲算法用C++語言編寫程序進行實現(xiàn)，進而驗證算法的運行效果。

根據(jù)以下問題的規(guī)模以及相關(guān)文獻的一般取值，算法的初始參數(shù)設(shè)置如下:螢火蟲數(shù)目n=6，最大吸引度 β0=1.0，光強吸收系數(shù) γ=1.0，步長因子 α =0.2。

測試數(shù)據(jù)有3組:

例1 20個物品，背包容量為 878，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}［14］。最優(yōu)解總價值為1024。

圖1 求解0-1背包問題的螢火蟲算法流程圖

例2 50個物品，背包容量為300，W={71，34，82，23，1，88，12，57，10，68，5，33，37，69，98，24，26，83，16，26，18，43，52，71，22，65，68，8，40，40，24，72，16，34，10，19，28，13，34，98，29，31，79，33，60，74，44，56，54，17}，P={26，59，30，19，66，85，94，8，3，44，5，1，41，82，76，1，12，81，73，32，74，54，62，41，19，10，65，53，56，53，70，66，58，22，72，33，96，88，68，45，44，61，78，78，6，66，11，59，83，48}。最優(yōu)解總價值為1063。

例3 80個物品，背包容量為 800，W={3，68，24，80，76，9，24，2，46，75，56，41，95，46，23，34，64，76，6，48，25，73，87，67，58，7，93，66，55，75，38，27，53，6，100，36，26，17，53，88，21，9，34，90，32，47，4，6，57，50，30，25，41，24，12，74，92，17，32，96，35，76，52，93，64，55，1，70，26，35，2，97，82，22，41，37，63，28，90，13}，P={38，16，29，47，22，25，17，49，15，15，75，11，56，99，51，92，59，37，13，98，61，50，32，17，44，79，41，53，45，29，62，64，2，23，31，45，57，68，57，26，51，26，86，83，94，20，98，24，91，89，1，63，21，46，74，56，64，72，58，8，74，24，27，35，94，49，65，21，16，25，1，45，63，4，37，25，39，68，49，11}。最優(yōu)解總價值為2085。

3.2 結(jié)果分析

3.2.1 實驗結(jié)果

例1 最大迭代次數(shù)m=40，程序運行結(jié)果為{1，1，1，1，1，1，1，0，1，1，1，1，1，0，1，0，1，1，1，1}，總重量為837(小于878)，總價值為1018，與真正的最優(yōu)解(1024)雖不一致，但比較接近。

例2 最大迭代次數(shù)m=40，程序運行結(jié)果為{0，1，0，0，1，0，1，0，0，0，0，0，0，0，0，0，0，0，1，0，1，0，0，0，0，0，0，1，0，0，1，0，1，0，1，0，1，1，1，0，0，1，0，1，0，0，0，0，0，1}，總重量為 295(小于 300)，總價值為1058，與真正的最優(yōu)解(1063)雖不一致，但比較接近。

例3 最大迭代次數(shù)m=90，程序運行結(jié)果為{1，0，1，0，0，1，0，1，0，0，0，0，0，1，1，1，0，0，1，1，1，0，0，0，0，1，0，0，0，0，1，1，0，1，0，0，1，1，0，0，1，1，1，0，1，0，1，1，1，1，0，1，0，1，1，0，0，1，1，0，1，0，0，0，1，0，1，0，0，0，0，0，0，0，0，0，0，1，0，0}，總重量為 792(小于800)，總價值為2081，與真正的最優(yōu)解(2085)雖不一致，但比較接近。

綜上所述，使用螢火蟲算法求解0-1背包問題是可行的，而且效果較為良好，故對于屬于組合優(yōu)化NP難題的0-1背包問題，又多了一種可行、有效的解決方法。

3.2.2 參數(shù)分析

螢火蟲算法中有幾個基本的參數(shù)，在上述仿真實驗中基本參數(shù)是在初始化時就給定的。下面參考文獻［18］對這幾個基本參數(shù)進行研究，主要有螢火蟲數(shù)目n、最大吸引度β0、光強吸收系數(shù)γ、步長因子α和最大迭代次數(shù)m，主要分析這幾個參數(shù)的變化對算法性能和最終解的影響。下面基于例1，依次改變這幾個參數(shù)的值來進行分析。

(1)螢火蟲數(shù)目n。

最大吸引度 β0=1.0，光強吸收系數(shù) γ =1.0，步長因子α=0.2，最大迭代次數(shù)m=40。

圖2 不同螢火蟲數(shù)目實驗結(jié)果對比

種群規(guī)模是影響螢火蟲算法優(yōu)化精度和收斂速度的重要參數(shù)之一，由圖2可以看出，在其他所有參數(shù)都相同的情況下，螢火蟲數(shù)目越多，則要聚集到一塊就需要較多的迭代次數(shù)，故算法的收斂速度越慢，但是數(shù)目多的話可以提高解的優(yōu)化程度;反之螢火蟲數(shù)目越少，聚集到一起所需的迭代次數(shù)就相對少，收斂速度較快，但解的質(zhì)量會相應(yīng)地降低。

(2)最大吸引度β0。

螢火蟲數(shù)目n=6，光強吸收系數(shù)γ=1.0，步長因子α=0.3，最大迭代次數(shù)m=40。

圖3 不同最大吸引度實驗結(jié)果對比

最大吸引度是每個螢火蟲自身所處位置(即光源處)的吸引度，它通過影響吸引度β來影響每輪螢火蟲移動的距離及算法的收斂速度等。由圖3可以看出，在其他所有參數(shù)都相同的情況下，最大吸引度越小，算法的收斂速度越慢;最大吸引度越大，算法的收斂速度越快。這是因為最大吸引度越小，每輪螢火蟲移動的距離就越小，要想聚集到一起就需要通過較多的迭代次數(shù)進行位置的移動和更新，收斂速度慢;相反最大吸引度越大，聚集到一起所需的迭代次數(shù)就越少，收斂速度快。

(3)光強吸收系數(shù)γ。

螢火蟲數(shù)目n=6，最大吸引度β0=1.0，步長因子α=0.7，最大迭代次數(shù)m=40。

圖4 不同光強吸收系數(shù)實驗結(jié)果對比

與最大吸引度相似，光強吸收系數(shù)γ對吸引度β影響較大，直接決定了螢火蟲個體的移動距離大小、收斂速度和算法的運行。由圖4可以看出，在其他所有參數(shù)都相同的情況下，光強吸收系數(shù)越小，算法的收斂速度越快;光強吸收系數(shù)越大，算法的收斂速度越慢。其原因也是光強吸收系數(shù)對每輪螢火蟲移動距離的影響，只不過計算公式中光強吸收系數(shù)之前添加了負號，因此光強吸收系數(shù)越小，每輪移動的距離反而越大，收斂速度快;而光強吸收系數(shù)越大，每輪移動的距離就越小，收斂速度慢。

(4)步長因子α。

螢火蟲數(shù)目n=6，最大吸引度β0=1.0，光強吸收系數(shù)γ=1.0，最大迭代次數(shù)m=40。

步長因子的引入是為了加大搜索區(qū)域，提高螢火蟲種群的多樣性，避免算法過早陷入局部最優(yōu)。步長因子的取值為［0，1］上的常數(shù)，應(yīng)與具體搜索區(qū)間范圍、位數(shù)相關(guān)，在較小搜索范圍內(nèi)，α取值過大，有可能導(dǎo)致算法無法收斂;取值過小，隨機移動距離極小，無法增加種群多樣性，不能起到擴大搜索范圍、避免算法過早收斂的作用。在本實驗中，取定其他參數(shù)后，由圖5可知，步長因子越大，收斂速度越慢;步長因子越小，收斂速度越快。由于本實驗增加了基于貪心策略的變異操作，因此當步長因子較小時，雖然隨機移動極小，但變異操作增加了種群的多樣性，擴大了搜索區(qū)域，在一定程度上避免了算法過早陷入局部最優(yōu)，故有較好的收斂效果;而當步長因子越大時，隨機移動的距離過大，要收斂就相對比較困難。

圖5 不同步長因子實驗結(jié)果對比

(5)迭代次數(shù)m。

螢火蟲數(shù)目n=6，最大吸引度β0=1.0，光強吸收系數(shù) γ =1.0，步長因子 α =0.2。

圖6 不同迭代次數(shù)實驗結(jié)果對比

迭代次數(shù)決定了螢火蟲種群要經(jīng)過多少輪的位置移動與更新才結(jié)束算法。由圖6可以看出，在其他所有參數(shù)都相同的情況下，迭代次數(shù)越多，解就越優(yōu);迭代次數(shù)越少，解就越差。因為螢火蟲種群的初始位置是隨機選取的，要最終都聚集到亮度高的螢火蟲周圍需要一定的迭代次數(shù)。因此經(jīng)過較少的迭代次數(shù)，螢火蟲還沒能夠從初始位置聚集到亮度高的螢火蟲周圍，而隨著迭代次數(shù)的增多，螢火蟲種群越來越向熒光高的螢火蟲附近聚集，最終就能夠聚集到較好的位置。

4 結(jié)束語

螢火蟲算法是一種新型的群智能優(yōu)化算法，具有捕捉極值域速度快、捕捉效率高等特點［14］，在生產(chǎn)調(diào)度、路徑規(guī)劃等方面具有良好的應(yīng)用前景。本文將螢火蟲算法應(yīng)用到屬于組合優(yōu)化和NP問題的0-1背包問題中，在Microsoft Visual Studio 2010環(huán)境下，使用C++語言編寫了算法的程序，并得到了較好的測試結(jié)果。不過螢火蟲算法還是有很大的改進空間，本文通過多次實驗對各個參數(shù)對算法性能的影響進行了分析，可以為參數(shù)的選取與優(yōu)化以及算法的改進提供一定的參考與幫助。

:

［1］拓守恒，周濤.一種用于求解0-1背包問題的動態(tài)伸縮算法［J］.計算機工程與應(yīng)用，2012，48(4):47-49.

［2］趙旭.0/1背包問題在動態(tài)自適應(yīng)多媒體處理方法中的應(yīng)用研究［J］.計算機工程與科學(xué)，2011，33(8):154-157.

［3］趙雪梅，周飛菲.基于用戶遷徙網(wǎng)絡(luò)的廣告投放策略研究［J］.電腦開發(fā)與應(yīng)用，2013，26(5):5-8.

［4］張欣，王志剛，夏慧明.差異演化算法求解多維0-1背包問題［J］.科學(xué)技術(shù)與工程，2012，12(6):1278-1280.

［5］吳迪，姜永增，宋廣軍.基于蜂群遺傳算法的0-1背包問題［J］.計算機工程與科學(xué)，2011，33(5):102-105.

［6］王娜，向鳳紅，毛劍琳.改進的自適應(yīng)遺傳算法求解0/1背包問題［J］.計算機應(yīng)用，2012，32(6):1682-1684.

［7］劉文濤，胡家寶.求解0-1背包問題的改進排擠遺傳算法［J］.計算機工程與設(shè)計，2011，32(6):2150-2153.

［8］宋瀟瀟.求解大規(guī)模0-1背包問題的改進人工魚群算法［J］.西華大學(xué)學(xué)報:自然科學(xué)版，2013，32(4):5-9.

［9］何小鋒，馬良.求解0-1背包問題的量子蟻群算法［J］.計算機工程與應(yīng)用，2011，47(16):29-31.

［10］柳寅，馬良.0-1背包問題的模糊粒子群算法求解［J］.計算機應(yīng)用研究，2011，28(11):4026-4027.

［11］戴秋萍，馬良，郗瑩.求解0-1背包問題的細菌覓食算法［J］.數(shù)學(xué)的實踐與認識，2013，43(3):178-183.

［12］張家琴.求解0/1背包問題的煙花算法研究［J］.武漢工程職業(yè)技術(shù)學(xué)院學(xué)報，2011，23(3):64-66.

［13］王皓.群智能優(yōu)化算法——螢火蟲算法［J］.科技致富向?qū)В?012(21):158-159.

［14］程魁，馬良.0-1背包問題的螢火蟲群優(yōu)化算法［J］.計算機應(yīng)用研究，2013，30(4):993-994.

［15］Krishnanand K N，Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics［C］//Proc.of IEEE Swarm Intelligence Symposium.Piscataway:IEEE Press，2005:84-91.

［16］Yang Xin-she.Nature-inspired Metaheuristic Algorithms［M］.Luniver Press，2008:83-96.

［17］劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法:螢火蟲算法［J］.計算機應(yīng)用研究，2011，28(9):3295-3297.

［18］高偉明.螢火蟲算法的研究與應(yīng)用［D］.蘭州:蘭州大學(xué)，2013.