莫愿斌，馬彥追，鄭巧燕

（1.廣西民族大學(xué) 理學(xué)院，廣西 南寧530006；2.廣西民族大學(xué) 廣西混雜計算與集成電路設(shè)計分析重點實驗室，廣西 南寧530006）

0 引 言

目前對于背包問題 （knapsack problem，KP）的求解有多種方法，例如回溯法、動態(tài)規(guī)劃法、分支限界法、遞歸法等精確方法以及如貪心算法、Lagrange法的近似算法。精確算法雖然可以得到準(zhǔn)確解，但是時間復(fù)雜度對于物品的數(shù)量是指數(shù)級的，在現(xiàn)實中很難推行，近似算法不一定能求得準(zhǔn)確解，但可得到比較有效的解［1］。近年來，仿生智能優(yōu)化算法得到了快速的發(fā)展，在許多傳統(tǒng)方法難以解決的大規(guī)模復(fù)雜問題中體現(xiàn)出了優(yōu)異的尋優(yōu)性能。國內(nèi)外許多學(xué)者將智能算法應(yīng)用于求解背包問題中，賀毅朝等［1］提出了求解背包問題的貪心遺傳算法；Dexuan Zou等［2］提出了一種新的全局和聲搜索算法并應(yīng)用于0－1背包問題的求解；李若平等［3］引入學(xué)習(xí)機制提出一種學(xué)習(xí)型和聲搜索算法求解0－1背包問題；王秋芬等［4］提出了一種求解0－1背包問題的啟發(fā)式遺傳算法；劉建芹等［5］提出了基于貪心變換策略的離散微粒群算法；武慧虹等［6］提出了一種克隆選擇免疫遺傳算法并應(yīng)用于高維0－1背包問題的求解中；宋曉萍等［7］提出了求解背包問題的離散雜草優(yōu)化算法。這些算法在有限的時間內(nèi)雖不能保證得到最優(yōu)解，但選擇充分多個解驗證后，錯誤概率能降到可接受的程度。

以上的這些方法在一定程度都有各自的優(yōu)缺點，因此，對該問題的求解研究還在一直進(jìn)行，尋求快速、簡潔、性能優(yōu)的算法始終是研究的目標(biāo)。螢火蟲算法 （firefly algorithm，F(xiàn)A）是在2008年由英國劍橋?qū)W者Yang提出的一種啟發(fā)式智能優(yōu)化方法［8，9］，該算法一經(jīng)提出，受到國內(nèi)外許多學(xué)者的關(guān)注和研究，并且已經(jīng)成功應(yīng)用于組合優(yōu)化［10，11］、路徑規(guī)劃［12］、圖像處理［13］、經(jīng)濟調(diào)度［14］等領(lǐng)域。本文將貪心策略和變異策略融入到螢火蟲算法中，提出了一種貪心螢火蟲算法 （GDFA）。該算法提高了基本螢火蟲算法的求解精度和全局收斂能力，并將改進(jìn)的算法應(yīng)用到求解0－1背包問題中。多個實例仿真實驗結(jié)果表明，該算法對0－1背包問題的求解是可行的，并取得了良好的效果。

1 0－1背包問題的數(shù)學(xué)描述

2 算法思想

2.1 基本螢火蟲算法 （FA）

在自然界中，大約存在2000多種螢火蟲，大多數(shù)種類都會發(fā)出其獨特的熒光，目前對螢火蟲發(fā)光的真實目的還不清楚，一般認(rèn)為螢火蟲利用閃光信號來吸引異性或者是吸引潛在的獵物，實現(xiàn)求偶或覓食的目的。螢火蟲算法就是模擬這種發(fā)光的生物學(xué)特性而表現(xiàn)出來的社會性行為而設(shè)計的隨機優(yōu)化算法。在螢火蟲算法中存在2個關(guān)鍵的要素：自身亮度和吸引度。自身亮度反映了螢火蟲位置的優(yōu)劣，亮度小的螢火蟲會被亮度大的吸引，并向亮度大的螢火蟲方向移動，吸引度影響著螢火蟲所要移動的距離，通過螢火蟲的移動，每個個體自身亮度和吸引度得到不斷更新，最終實現(xiàn)目標(biāo)優(yōu)化的目的［9］。

在螢火蟲算法中［8］，螢火蟲的吸引度的大小和亮度的大小是成正比的，亮度由目標(biāo)函數(shù)決定。一個螢火蟲處在坐標(biāo)為X 的位置，它的亮度I 可以取為I（X）＝f（X），X的位置越好，它的亮度就越大，它對其它個體的吸引度隨著它們之間距離的增加而變小，另外在熒光傳輸?shù)倪^程中，會被傳播介質(zhì)吸收一部分，所以吸引度的大小還和介質(zhì)吸收因子有關(guān)。因此，一個螢火蟲對距離其r處的亮度I 可以表示為式 （2）所示，稱為相對亮度

式中：I0——螢火蟲對距離其r＝0處的熒光亮度，γ——介質(zhì)吸收因子，rij——螢火蟲i到螢火蟲j 的歐式距離。螢火蟲的吸引度β被定義為

式中：β0 ——螢火蟲對距離其r＝0處的吸引度，βmin ——最小吸引度，βmin ＝0.2。螢火蟲i被螢火蟲j 吸引的移動公式為

式中：xi，xj——螢火蟲i和j的位置，α——步長因子，rand——區(qū)間［0，1］上服從均勻分布的隨機因子。

2.2 貪心策略

為提高算法的搜索性能以及保證解的可行性，本文引入了貪心算法修正可行解，它是一種局部搜索機制，使得算法的搜索總是在可行解空間上進(jìn)行，同時在保證解的可行性的前提下，盡量增加其適應(yīng)度值［15］。對于一個解來說，如果它所對應(yīng)裝入物品的總質(zhì)量大于背包可以承受的重量，說明此解是不可行解，找出此解裝入背包的物品，并把這些物品按單位質(zhì)量價值按升序排列，由從小到大的方向?qū)i＝1變?yōu)閤i＝0，直至將不可行解變?yōu)榭尚薪?。如果一個解所對應(yīng)裝入物品的總質(zhì)量小于背包所能承受的重量，說明此解為可行解，為了盡可能增加解的適應(yīng)度，找出此解沒有裝入背包的物品，并把這些物品按單位質(zhì)量價值按降序排列，由從大到小的方向?qū)i＝0變?yōu)閤i＝1，直至使總重量超過背包所能承受的重量的物品為xi＝0。

2.3 變異策略

為了增加種群中個體的多樣性，使螢火蟲不易陷入局部極值，本文加入了變異策略。經(jīng)過貪心策略產(chǎn)生的所有新個體在一定概率下發(fā)生變異，形成新一代種群，本文對表現(xiàn)型編碼中的每一位編碼以大小為0.05的概率變異，即將0變?yōu)?，或1變?yōu)?。

2.4 求解0－1背包問題的螢火蟲算法實施步驟

步驟1 初始化算法的參數(shù)，螢火蟲數(shù)目m，步長因子α0，最大吸引度β0 ，最小吸引度βmin ，介質(zhì)吸收因子γ，最大迭代次數(shù)maxT。

步驟2 隨機產(chǎn)生一個m×N 的0／1矩陣作為m 個螢火蟲的初始位置，N 為要裝入背包物品的數(shù)量。利用式 （1）計算各自的目標(biāo)值作為自己的最大亮度I0，記錄最優(yōu)位置gbest。

步驟3 根據(jù)式 （2）、式 （3）計算各個螢火蟲之間的相對亮度I和吸引度β，依照I的大小確定螢火蟲的移動方向。

步驟4 利用式 （4）對螢火蟲的位置進(jìn)行更新，隨機擾動處在最好位置的螢火蟲。由于螢火蟲的位置編碼只有（0，1）2種狀態(tài)，這里以0.5為界點，如果xij≤0.5，則令xij＝0，否則，令xij＝1。

步驟5 進(jìn)行貪心策略搜索。使不可行解通過減少背包的物品變?yōu)榭尚薪?，同時在保證解的可行性的前提下，盡量增加其適應(yīng)度值。

步驟6 對新種群實施變異策略操作，以增加種群多樣性。

步驟7 重新計算更新后螢火蟲的亮度，判斷是否滿足結(jié)束條件，若是，轉(zhuǎn)到步驟8，否則轉(zhuǎn)步驟3，進(jìn)入下一次搜索。

步驟8 輸出最優(yōu)位置和最優(yōu)解。

3 仿真實驗與分析

為了驗證GDFA 求解背包問題的性能，選取了5個常用的實例，物品數(shù)分別為20、50、50、80和100。對這些實例進(jìn)行仿真實驗，由于算法的隨機性，通過各自獨立運行多次與文獻(xiàn) ［5］的GDPSO 算法和文獻(xiàn) ［1］的GGA 算法進(jìn)行比較。實驗環(huán)境為處理器：AMD Phenom （tm）8400，主頻：1.05 GHz，內(nèi)存：1.75 GB，操作系統(tǒng)：Windows XP，集成開發(fā)環(huán)境：Matlab2012a。在GDFA 中，設(shè)定步長因子α＝0.5，最大吸引度β0 ＝1，最小吸引度βmin＝0.2，介質(zhì)吸收因子γ＝1。

例1：企業(yè)投資問題實例。投資問題指的是某企業(yè)將總投資金額C 元將投入到n 種項目中，對于項目i需要投資ci元，最終可獲益pi元。此問題可以歸結(jié)為0－1 背包問題，即選擇一種組合，在不超過總投資的情況下，使得收益最大。n＝7，［c1，c2，…，c7］＝［3，4，3，3，15，13，16］，［p1，p2，…，p7］＝［12，12，9，15，90，26，12］，C ＝35。設(shè)置GDFA算法種群為20，獨立運行100次，與文獻(xiàn) ［16］的結(jié)果比較見表1。由表1可見，GDFA 算法的求解效率最高。

表1 4種算法的計算結(jié)果對比

例2：N＝20；V＝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］；e－近似法解得近似值1018，回溯法解得最優(yōu)值1024，設(shè)置FDFA 算法的種群為20，運行10次迭代后可得到最好解1024，表2列出了5種算法對此實例的計算結(jié)果。表3列出了3種算法的最優(yōu)解以及成功率，成功率是算法求得最優(yōu)解次數(shù)與運行總次數(shù)的比值，每個算法獨立運行100次來比較算法的性能。由表2和表3可以看出GDFA 算法的求解結(jié)果優(yōu)于其它算法。

表2 5種算法的計算結(jié)果對比

表3 3種算法的計算結(jié)果對比

例3：物品個數(shù)N＝50；背包限重V＝1000；物品重量集合W＝ ［80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50 20 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1］；物品價值集合P＝［220 208 198 192 180 180 165 162 160 158 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 56 50 30 20 15 10 8 5 3 1］。該問題的最優(yōu)目標(biāo)值為3103，對應(yīng)的總重量為1000，最優(yōu)解為［11010101111011011011011111110100001010011000001000］。貪婪算法求解此例得到的最優(yōu)值為3036，設(shè)置算法種群規(guī)模為30，通過設(shè)置不同的迭代次數(shù)，每個算法獨立運行100次，實驗結(jié)果比較見表4。從表4可以看出，3種算法在一定的迭代次數(shù)內(nèi)都可以找到目標(biāo)最優(yōu)值，隨著迭代次數(shù)的增加，各算法的找到最優(yōu)值的次數(shù)也在增加。GDFA算法在10代以內(nèi)就可以找到最優(yōu)值，而GDPSO 算法在迭代次數(shù)設(shè)置成50時才能找到最優(yōu)值，并且成功率較低。雖然GGA 在迭代次數(shù)為10時的成功率高于GDFA，但迭代次數(shù)大于20 時，GDFA 算法的成功率要高于GGA 算法，并且在150 代時GDFA 算法的成功率達(dá)到了100%，而GGA 算法和GDPSO 算法還不能每次都找出最優(yōu)值。GDFA 算法保持較高的成功率，GDPSO 算法的成功率最低，GDFA 算法的平均值最優(yōu)。其目標(biāo)函數(shù)值隨著迭代次數(shù)的變化曲線效果如圖1所示。

表4 2種算法的計算結(jié)果對比

圖1 例3的收斂效果

例4：物品個數(shù)N＝50；背包限重V＝959；物品價值集合P＝ ［293 291 290 280 278 274 269 265 248 247 245 245 241 234 229 228 222 216 214 191 191 187 171 170 164 152 142 132 131 126 122 116 112 111 110 106 77 76 74 73 69 67 42 41 35 33 30 29 28 26］；物品重量集合W＝ ［95 39 69 63 49 104 56 58 47 23 17 129 91 28 77 125 73 5 103 63 76 23 47 79 119 125 26 119 79 56 50 75 12 26 31 43 41 38 29 21 14 9 3 17 8 8 9 7 4 5］；該問題的最優(yōu)目標(biāo)值為4882，對應(yīng)的總重量為959，最優(yōu)解為 ［111110111110011001010110001000 00111000011111111111］。設(shè)置種群規(guī)模為30，隨機實驗結(jié)果比較見表5。從表5可以看出，GDFA 算法在較少的迭代次數(shù)內(nèi)就能夠找到最優(yōu)值，而GDPSO 算法和GGA 算法則要用相對比較多的迭代次數(shù)才能找到最優(yōu)值，每個迭代次數(shù)GDFA 算法的最差值都比GDPSO 算法和GGA 算法要接近最優(yōu)值，并且成功率明顯比后2種算法高很多。當(dāng)?shù)螖?shù)增大時，GDFA 的成功率增長速度很快，而后2 種算法不太明顯。設(shè)置迭代次數(shù)大于100 時，GDFA 算法求解此問題的成功率可以達(dá)到100%，遠(yuǎn)高于后2種算法，GDFA 算法的平均值最接近目標(biāo)最優(yōu)值。其目標(biāo)函數(shù)值隨著迭代次數(shù)的變化曲線效果如圖2所示。

表5 3種算法的計算結(jié)果對比

圖2 例4的收斂效果

例5：物品個數(shù)N＝80；背包限重V＝1173；物品價值集合P＝ ［199 194 193 191 189 178 174 169 164 164 161 158 157 154 152 152 149 142 131 125 124 124 124 122 119 116 114 113 111 110 109 100 97 94 91 82 82 81 80 80 80 79 77 76 74 72 71 70 69 68 65 65 61 56 55 54 53 47 47 46 41 36 34 32 32 30 29 29 26 25 23 22 20 11 10 9 5 4 3 1］；物品重量集合W＝ ［40 27 5 21 51 16 42 18 52 28 57 34 44 43 52 55 53 42 47 56 57 44 16 2 12 9 40 23 56 3 39 16 54 36 52 5 53 48 23 47 41 49 22 42 10 16 53 58 40 1 43 56 40 32 44 35 37 45 52 56 40 2 23 49 50 26 11 35 32 34 58 6 52 26 31 23 4 52 53 19］；該問題的最優(yōu)目標(biāo)值為5183，對應(yīng)的總重量為1170，最優(yōu)解為 ［111111111111 11111111111111110111010100100010 110001000000000001000010000000000000］。設(shè)置算法的種群為50，實驗結(jié)果比較見表6。從表6中可以看出，GDFA算法的最差值都明顯優(yōu)于另外2 種算法，在200 代以內(nèi)GDPSO 算法和GGA 算法沒有找到最優(yōu)值，而GDFA 在20代就可以找到最優(yōu)值，在設(shè)置為500代時，GDPSO 能夠找到最優(yōu)值，但成功率只有3%，GGA 算法在500代以內(nèi)沒有找到最優(yōu)值，GDFA 算法的成功率更高，其搜索性能明顯優(yōu)于其它2種算法。其目標(biāo)函數(shù)值隨著迭代次數(shù)的變化曲線效果如圖3所示。

例6：物品個數(shù)N＝100；背包限重V＝6718；物品價值集合P＝ ［597 596 593 586 581 568 567 560 549 548 547 529 529 527 520 491 482 478 475 475 466 462 459 458 454 451 449 443 442 421 410 409 395 394 390 377 375 366 361 347 334 322 315 313 311 309 296 295 294 289 285 279 277 276 272 248 246 245 238 237 232 231 230 225 192 184 183 176 174 171 169 165 165 154 153 150 149 147 143 140 138 134 132 127 124 123 114 111 104 89 74 63 62 58 55 48 27 22 12 6］；物品重量集合W＝ ［54 183 106 82 30 58 71 166 117 190 90 191 205 128 110 89 63 6 140 86 30 91 156 31 70 199 142 98 178 16 140 31 24 197 101 73 169 73 92 159 71 102 144 151 27 131 209 164 177 177 129 146 17 53 164 146 43 170 180 171 130 183 5 113 207 57 13 163 20 63 12 24 9 42 6 109 170 108 46 69 43 175 81 5 34 146 148 114 160 174 156 82 47 126 102 83 58 34 21 14］；該問題的最優(yōu)目標(biāo)值為26559，對應(yīng)的總重量為6717，最優(yōu)解為 ［11111111111111 1111111111111111111111111111111101111111101000101101 1 011111110001110111000000000000001］。設(shè)置種群規(guī)模為50，實驗結(jié)果比較見表7。從表7中可以看出，GDFA 算法在50代內(nèi)可以找到最優(yōu)值，而另外2種算法的成功率都為0。對于每個迭代次數(shù)，GDFA 算法的平均值比其它2種算法的平均值更接近最優(yōu)值，其成功率也是最高的，GGA 算法在200代以內(nèi)無法找到最優(yōu)值。其目標(biāo)函數(shù)值隨著迭代次數(shù)的變化曲線效果如圖4所示。

表6 3種算法的計算結(jié)果對比

圖3 例5的收斂效果

表7 3種算法的計算結(jié)果對比

圖4 例6的收斂效果

4 結(jié)束語

0－1背包問題屬于組合優(yōu)化問題，且是NP難題，本文用螢火蟲算法的思想來求解經(jīng)典的0－1背包問題。將貪心策略和變異策略融入到螢火蟲算法中，提出了一種貪心螢火蟲算法 （GDFA），該算法提高了基本螢火蟲算法的求解精度和全局收斂能力，在求解0－1背包問題的實例中，表現(xiàn)出良好的搜索性能。將本文提出的算法與其它算法如貪心遺傳算法、貪心微粒群算法的比較結(jié)果表明，本文算法在求解0－1 背包問題時收斂速度更快，求解成功率更高，性能占優(yōu)，為求解此類問題提供了一種新的可行方法，同時，螢火蟲算法的應(yīng)用領(lǐng)域也得到擴展。

［1］HE Yichao，LIU Kunqi，ZHANG Cuijun，et al.Greedy genetic algorithm for solving knapsack problems and its applications ［J］.Computer Engineering and Design，2007，28（11）：2655－2657 （in Chinese）. ［賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應(yīng)用 ［J］.計算機工程與設(shè)計，2007，28 （11）：2655－2657.］

［2］Zou Dexuan，Gao Liqun，Li Steven，et al.Solving 0－1knapsack problem by a novel global harmony search algorithm ［J］.Applied Soft Computing，2011，11 （2）：1556－1564.

［3］LI Ruoping，OUYANG Haibin，GAO Liqun，et al.Learned harmony search algorithm and its application to 0－1knapsack problems［J］.Control and Decision，2013，28 （2）：205－210（in Chinese）.［李若平，歐陽海濱，高立群，等.學(xué)習(xí)型和聲搜索算法及其在0－1 背包問題中的應(yīng)用 ［J］.控制與決策，2013，28 （2）：205－210.］

［4］WANG Qiufen，LIANG Daolei.A heuristic genetic algorithm for solving 0－1knapsack problem ［J］.Computer Applications and Software，2013，30 （2）：33－37 （in Chinese）.［王秋芬，梁道雷.一種求解0－1背包問題的啟發(fā)式遺傳算法 ［J］.計算機應(yīng)用與軟件，2013，30 （2）：33－37.］

［5］LIU Jianqin，HE Yichao，GU Qianqian.Solving knapsack problem based on discrete particle swarm optimization ［J］.Computer Engineering and Design，2007，28 （13）：3189－3191（in Chinese）.［劉建芹，賀毅朝，顧茜茜.基于離散微粒群算法求解背包問題研究 ［J］.計算機工程與設(shè)計，2007，28（13）：3189－3191.］

［6］WU Huihong，QIAN Shuqu，XU Zhidan.Immune genetic algorithm based on clonal selection and its application to 0／1 knapsack problem ［J］.Journal of Computer Application，2013，33 （3）：845－848 （in Chinese）.［武慧虹，錢淑渠，徐志丹.克隆選擇免疫遺傳算法對高維0／1背包問題應(yīng)用 ［J］.計算機應(yīng)用，2013，33 （3）：845－848.］

［7］SONG Xiaoping，HU Chang’an.Discrete invasive weed optimization algorithm for 0／1knapsack problem ［J］.Computer Engineering and Applications，2012，48 （30）：239－242 （in Chinese）.［宋曉萍，胡常安.離散雜草優(yōu)化算法在0／1背包問題中的應(yīng)用 ［J］.計算機工程與應(yīng)用，2012，48 （30）：239－242.］

［8］Yang XS.Nature－inspired metaheuristic algorithms ［M］.Luniver Press，2008.

［9］Yang XS.Firefly algorithms for multimodal optimization ［G］.LNCS 5792：Stochastic Algorithms：Foundations and Applications，2009：169－178.

［10］Sayadi MK，Ramezanian R，Ghaffari－Nasab N.A discrete firefly meta－h(huán)euristic with local search for make span minimization in permutation flow shop scheduling problems［J］.Inter－national Journal of Industrial Engineering Computations，2010，1 （1）：1－10.

［11］LIU Changping，YE Chunming.Novel bioinspired swarm intelligence optimization algorithm：firefly algorithm ［J］.Application Research of Computers，2011，28 （9）：3295－3297 （in Chinese）.［劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法［J］.計算機應(yīng)用研究，2011，28（9）：3295－3297.］

［12］Srivatsava PR.Optimal test sequence generation using firefly algorithm ［J］.Swarm and Evolutionary Computation，2012，8：44－53.http：／／dx.doi.org／10.1016／j.swevo.2012.08.003.

［13］Horng Ming－Huwi，Liou Ren－Jean. Multilevel minimum cross entropy threshold selection based on the firefly algorithm［J］.Expert Systems with Applications，2011，38 （12）：14805－14811.

［14］GUO Liping，LI Xiangtao，GU Wenxiang.An improved fire－fly algorithm for the blocking flow shop scheduling problem［J］.CAAI Transactions on Intelligent Systems，2013，8（1）：33－38 （in Chinese）.［郭麗萍，李向濤，谷文祥.改進(jìn)的螢火蟲算法求解阻塞流水線調(diào)度問題 ［J］.智能系統(tǒng)學(xué)報，

2013，8 （1）：33－38.］

［15］CHENG Kui，MA Liang.Artificial glowworm swarm optimization algorithm for 0－1knapsack problem ［J］.Application Research of Computers，2013，30 （4）：993－998 （in Chinese）. ［程魁，馬良.0－1 背包問題的螢火蟲群優(yōu)化算法［J］.計算機應(yīng)用研究，2013，30 （4）：993－998.］

［16］GAO Shang，YANG Jingyu.Solving knapsack problem by hybrid particle swarm optimization algorithm ［J］.Engineering Science，2006，8 （11）：94－98 （in Chinese）. ［高尚，楊靜宇.背包問題的混合粒子群優(yōu)化算法 ［J］.中國工程科學(xué)，2006，8 （11）：94－98.］