求解0－1背包问题的萤火虫算法

莫愿斌，马彦追，郑巧燕

（1.广西民族大学 理学院，广西 南宁530006；2.广西民族大学 广西混杂计算与集成电路设计分析重点实验室，广西 南宁530006）

0 引 言

目前对于背包问题 （knapsack problem，KP）的求解有多种方法，例如回溯法、动态规划法、分支限界法、递归法等精确方法以及如贪心算法、Lagrange法的近似算法。精确算法虽然可以得到准确解，但是时间复杂度对于物品的数量是指数级的，在现实中很难推行，近似算法不一定能求得准确解，但可得到比较有效的解［1］。近年来，仿生智能优化算法得到了快速的发展，在许多传统方法难以解决的大规模复杂问题中体现出了优异的寻优性能。国内外许多学者将智能算法应用于求解背包问题中，贺毅朝等［1］提出了求解背包问题的贪心遗传算法；Dexuan Zou等［2］提出了一种新的全局和声搜索算法并应用于0－1背包问题的求解；李若平等［3］引入学习机制提出一种学习型和声搜索算法求解0－1背包问题；王秋芬等［4］提出了一种求解0－1背包问题的启发式遗传算法；刘建芹等［5］提出了基于贪心变换策略的离散微粒群算法；武慧虹等［6］提出了一种克隆选择免疫遗传算法并应用于高维0－1背包问题的求解中；宋晓萍等［7］提出了求解背包问题的离散杂草优化算法。这些算法在有限的时间内虽不能保证得到最优解，但选择充分多个解验证后，错误概率能降到可接受的程度。

以上的这些方法在一定程度都有各自的优缺点，因此，对该问题的求解研究还在一直进行，寻求快速、简洁、性能优的算法始终是研究的目标。萤火虫算法 （firefly algorithm，FA）是在2008年由英国剑桥学者Yang提出的一种启发式智能优化方法［8，9］，该算法一经提出，受到国内外许多学者的关注和研究，并且已经成功应用于组合优化［10，11］、路径规划［12］、图像处理［13］、经济调度［14］等领域。本文将贪心策略和变异策略融入到萤火虫算法中，提出了一种贪心萤火虫算法 （GDFA）。该算法提高了基本萤火虫算法的求解精度和全局收敛能力，并将改进的算法应用到求解0－1背包问题中。多个实例仿真实验结果表明，该算法对0－1背包问题的求解是可行的，并取得了良好的效果。

1 0－1背包问题的数学描述

2 算法思想

2.1 基本萤火虫算法 （FA）

在自然界中，大约存在2000多种萤火虫，大多数种类都会发出其独特的荧光，目前对萤火虫发光的真实目的还不清楚，一般认为萤火虫利用闪光信号来吸引异性或者是吸引潜在的猎物，实现求偶或觅食的目的。萤火虫算法就是模拟这种发光的生物学特性而表现出来的社会性行为而设计的随机优化算法。在萤火虫算法中存在2个关键的要素：自身亮度和吸引度。自身亮度反映了萤火虫位置的优劣，亮度小的萤火虫会被亮度大的吸引，并向亮度大的萤火虫方向移动，吸引度影响着萤火虫所要移动的距离，通过萤火虫的移动，每个个体自身亮度和吸引度得到不断更新，最终实现目标优化的目的［9］。

在萤火虫算法中［8］，萤火虫的吸引度的大小和亮度的大小是成正比的，亮度由目标函数决定。一个萤火虫处在坐标为X 的位置，它的亮度I 可以取为I（X）＝f（X），X的位置越好，它的亮度就越大，它对其它个体的吸引度随着它们之间距离的增加而变小，另外在荧光传输的过程中，会被传播介质吸收一部分，所以吸引度的大小还和介质吸收因子有关。因此，一个萤火虫对距离其r处的亮度I 可以表示为式 （2）所示，称为相对亮度

式中：I0——萤火虫对距离其r＝0处的荧光亮度，γ——介质吸收因子，rij——萤火虫i到萤火虫j 的欧式距离。萤火虫的吸引度β被定义为

式中：β0 ——萤火虫对距离其r＝0处的吸引度，βmin ——最小吸引度，βmin ＝0.2。萤火虫i被萤火虫j 吸引的移动公式为

式中：xi，xj——萤火虫i和j的位置，α——步长因子，rand——区间［0，1］上服从均匀分布的随机因子。

2.2 贪心策略

为提高算法的搜索性能以及保证解的可行性，本文引入了贪心算法修正可行解，它是一种局部搜索机制，使得算法的搜索总是在可行解空间上进行，同时在保证解的可行性的前提下，尽量增加其适应度值［15］。对于一个解来说，如果它所对应装入物品的总质量大于背包可以承受的重量，说明此解是不可行解，找出此解装入背包的物品，并把这些物品按单位质量价值按升序排列，由从小到大的方向将xi＝1变为xi＝0，直至将不可行解变为可行解。如果一个解所对应装入物品的总质量小于背包所能承受的重量，说明此解为可行解，为了尽可能增加解的适应度，找出此解没有装入背包的物品，并把这些物品按单位质量价值按降序排列，由从大到小的方向将xi＝0变为xi＝1，直至使总重量超过背包所能承受的重量的物品为xi＝0。

2.3 变异策略

为了增加种群中个体的多样性，使萤火虫不易陷入局部极值，本文加入了变异策略。经过贪心策略产生的所有新个体在一定概率下发生变异，形成新一代种群，本文对表现型编码中的每一位编码以大小为0.05的概率变异，即将0变为1，或1变为0。

2.4 求解0－1背包问题的萤火虫算法实施步骤

步骤1 初始化算法的参数，萤火虫数目m，步长因子α0，最大吸引度β0 ，最小吸引度βmin ，介质吸收因子γ，最大迭代次数maxT。

步骤2 随机产生一个m×N 的0／1矩阵作为m 个萤火虫的初始位置，N 为要装入背包物品的数量。利用式 （1）计算各自的目标值作为自己的最大亮度I0，记录最优位置gbest。

步骤3 根据式 （2）、式 （3）计算各个萤火虫之间的相对亮度I和吸引度β，依照I的大小确定萤火虫的移动方向。

步骤4 利用式 （4）对萤火虫的位置进行更新，随机扰动处在最好位置的萤火虫。由于萤火虫的位置编码只有（0，1）2种状态，这里以0.5为界点，如果xij≤0.5，则令xij＝0，否则，令xij＝1。

步骤5 进行贪心策略搜索。使不可行解通过减少背包的物品变为可行解，同时在保证解的可行性的前提下，尽量增加其适应度值。

步骤6 对新种群实施变异策略操作，以增加种群多样性。

步骤7 重新计算更新后萤火虫的亮度，判断是否满足结束条件，若是，转到步骤8，否则转步骤3，进入下一次搜索。

步骤8 输出最优位置和最优解。

3 仿真实验与分析

为了验证GDFA 求解背包问题的性能，选取了5个常用的实例，物品数分别为20、50、50、80和100。对这些实例进行仿真实验，由于算法的随机性，通过各自独立运行多次与文献 ［5］的GDPSO 算法和文献 ［1］的GGA 算法进行比较。实验环境为处理器：AMD Phenom （tm）8400，主频：1.05 GHz，内存：1.75 GB，操作系统：Windows XP，集成开发环境：Matlab2012a。在GDFA 中，设定步长因子α＝0.5，最大吸引度β0 ＝1，最小吸引度βmin＝0.2，介质吸收因子γ＝1。

例1：企业投资问题实例。投资问题指的是某企业将总投资金额C 元将投入到n 种项目中，对于项目i需要投资ci元，最终可获益pi元。此问题可以归结为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。设置GDFA算法种群为20，独立运行100次，与文献 ［16］的结果比较见表1。由表1可见，GDFA 算法的求解效率最高。

表1 4种算法的计算结果对比

例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，回溯法解得最优值1024，设置FDFA 算法的种群为20，运行10次迭代后可得到最好解1024，表2列出了5种算法对此实例的计算结果。表3列出了3种算法的最优解以及成功率，成功率是算法求得最优解次数与运行总次数的比值，每个算法独立运行100次来比较算法的性能。由表2和表3可以看出GDFA 算法的求解结果优于其它算法。

表2 5种算法的计算结果对比

表3 3种算法的计算结果对比

例3：物品个数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］。该问题的最优目标值为3103，对应的总重量为1000，最优解为［11010101111011011011011111110100001010011000001000］。贪婪算法求解此例得到的最优值为3036，设置算法种群规模为30，通过设置不同的迭代次数，每个算法独立运行100次，实验结果比较见表4。从表4可以看出，3种算法在一定的迭代次数内都可以找到目标最优值，随着迭代次数的增加，各算法的找到最优值的次数也在增加。GDFA算法在10代以内就可以找到最优值，而GDPSO 算法在迭代次数设置成50时才能找到最优值，并且成功率较低。虽然GGA 在迭代次数为10时的成功率高于GDFA，但迭代次数大于20 时，GDFA 算法的成功率要高于GGA 算法，并且在150 代时GDFA 算法的成功率达到了100%，而GGA 算法和GDPSO 算法还不能每次都找出最优值。GDFA 算法保持较高的成功率，GDPSO 算法的成功率最低，GDFA 算法的平均值最优。其目标函数值随着迭代次数的变化曲线效果如图1所示。

表4 2种算法的计算结果对比

图1 例3的收敛效果

例4：物品个数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］；该问题的最优目标值为4882，对应的总重量为959，最优解为 ［111110111110011001010110001000 00111000011111111111］。设置种群规模为30，随机实验结果比较见表5。从表5可以看出，GDFA 算法在较少的迭代次数内就能够找到最优值，而GDPSO 算法和GGA 算法则要用相对比较多的迭代次数才能找到最优值，每个迭代次数GDFA 算法的最差值都比GDPSO 算法和GGA 算法要接近最优值，并且成功率明显比后2种算法高很多。当迭代次数增大时，GDFA 的成功率增长速度很快，而后2 种算法不太明显。设置迭代次数大于100 时，GDFA 算法求解此问题的成功率可以达到100%，远高于后2种算法，GDFA 算法的平均值最接近目标最优值。其目标函数值随着迭代次数的变化曲线效果如图2所示。

表5 3种算法的计算结果对比

图2 例4的收敛效果

例5：物品个数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］；该问题的最优目标值为5183，对应的总重量为1170，最优解为 ［111111111111 11111111111111110111010100100010 110001000000000001000010000000000000］。设置算法的种群为50，实验结果比较见表6。从表6中可以看出，GDFA算法的最差值都明显优于另外2 种算法，在200 代以内GDPSO 算法和GGA 算法没有找到最优值，而GDFA 在20代就可以找到最优值，在设置为500代时，GDPSO 能够找到最优值，但成功率只有3%，GGA 算法在500代以内没有找到最优值，GDFA 算法的成功率更高，其搜索性能明显优于其它2种算法。其目标函数值随着迭代次数的变化曲线效果如图3所示。

例6：物品个数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］；该问题的最优目标值为26559，对应的总重量为6717，最优解为 ［11111111111111 1111111111111111111111111111111101111111101000101101 1 011111110001110111000000000000001］。设置种群规模为50，实验结果比较见表7。从表7中可以看出，GDFA 算法在50代内可以找到最优值，而另外2种算法的成功率都为0。对于每个迭代次数，GDFA 算法的平均值比其它2种算法的平均值更接近最优值，其成功率也是最高的，GGA 算法在200代以内无法找到最优值。其目标函数值随着迭代次数的变化曲线效果如图4所示。

表6 3种算法的计算结果对比

图3 例5的收敛效果

表7 3种算法的计算结果对比

图4 例6的收敛效果

4 结束语

0－1背包问题属于组合优化问题，且是NP难题，本文用萤火虫算法的思想来求解经典的0－1背包问题。将贪心策略和变异策略融入到萤火虫算法中，提出了一种贪心萤火虫算法 （GDFA），该算法提高了基本萤火虫算法的求解精度和全局收敛能力，在求解0－1背包问题的实例中，表现出良好的搜索性能。将本文提出的算法与其它算法如贪心遗传算法、贪心微粒群算法的比较结果表明，本文算法在求解0－1 背包问题时收敛速度更快，求解成功率更高，性能占优，为求解此类问题提供了一种新的可行方法，同时，萤火虫算法的应用领域也得到扩展。

［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）. ［贺毅朝，刘坤起，张翠军，等.求解背包问题的贪心遗传算法及其应用 ［J］.计算机工程与设计，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）.［李若平，欧阳海滨，高立群，等.学习型和声搜索算法及其在0－1 背包问题中的应用 ［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背包问题的启发式遗传算法 ［J］.计算机应用与软件，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］.计算机工程与设计，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背包问题应用 ［J］.计算机应用，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）.［宋晓萍，胡常安.离散杂草优化算法在0／1背包问题中的应用 ［J］.计算机工程与应用，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－heuristic 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）.［刘长平，叶春明.一种新颖的仿生群智能优化算法：萤火虫算法［J］.计算机应用研究，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］.智能系统学报，

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 背包问题的萤火虫群优化算法［J］.计算机应用研究，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）. ［高尚，杨静宇.背包问题的混合粒子群优化算法 ［J］.中国工程科学，2006，8 （11）：94－98.］