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

开篇：润墨网以专业的文秘视角，为您筛选了一篇求解0/1背包问题的萤火虫算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：该文将萤火虫算法应用于求解小规模0/1背包问题，利用基本萤火虫算法的求解思想，对0/1背包问题进行分析，通过对物品数为10、25和50的背包问题进行了仿真实验，实验结果表明该算法在解决小规模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）是运筹学中一类经典的优化问题，是一个经典的N-P问题[1]。背包问题在现实生活中具有广泛的应用背景，如物流公司货物的发配、控制预算以及工厂的下料等都可以用背包问题进行求解。在设计解决复杂组合优化问题时，背包问题往往作为其子问题出现。

对于0/1背包问题人们提出了很多好的改进的算法，例如蚁群算法[2]、粒子群算法[3]、人工鱼群算法[4]等等。萤火虫算法（Glowworm Swarm Optimization， GSO）[5-6]是2005年由印度学者Krishnanand和Ghose提出的一种基于生物群体智能的随机优化算法，它是继粒子群优化算法、细菌觅食算法、人工鱼群算法之后的又一种新型的仿生智能优化算法。萤火虫算法是通过模拟萤火虫在觅食、警戒和求偶等生活习性中产生的因光而吸引移动的行为来解决最优问题的。该算法具有实现简单，计算效率高、适用能力强等特点，已经成为了计算智能领域的研究热点。

0/1背包问题是典型的背包问题，0/1背包问题是指：给定[n]种物品和一个背包，第[i]个物品的重量为[wi]，第[i]个物品的价值为[v i]，背包的限制容量为[c]。求应怎样装入背包中的物品，使得装入背包中物品的总价值最大。

2 萤火虫算法

自然界中的萤火虫都会发出特有的闪光信号来吸引其它萤火虫，这种闪光信号就是短促并有节奏的荧光，萤火虫借助荧光来完成觅食、求偶和警戒等行为。萤火虫算法就是模拟自然界中萤火虫发光行为来构造的一种随机优化算法，算法中利用萤火虫的发光特性在其感知范围内寻找其它同伴，并向感知范围内位置较好的萤火虫方向移动，从而实现位置更新和移动过程。

萤火虫算法首先在问题空间随机分布[N]只萤火虫，这些萤火虫都带有荧光，每个萤火虫都具有自己的感知范围[Rid]（[0

2.1 萤火虫的荧光素

萤火虫算法中，萤火虫的荧光素值体现了萤火虫所处位置的优劣并决定萤火虫的移动方向。荧光素值越高对其感知范围内的其它萤火虫的吸引力就越强，朝这个方向聚集的可能性也就越大。

4 结论

本文根据基本萤火虫算法的基本思路，分析了萤火虫算法在解决小规模背包问题上的可行性。通过仿真实验对物品数为10、25和50的问题进行了求解，实验结果表明，对于基本萤火虫算法，当问题规模较小时可以找到目前已知最优解，但随着问题规模的增大寻优效果不是很理想，需要对基本萤火虫算法加以改进来适应求解大规模的背包问题。

参考文献：

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

[2] 马良，王龙德. 背包问题的蚂蚁优化算法[J]. 计算机应用.2001，21（8）：4-5.

[3] 沈显君，王伟武，郑波尽，等. 基于改进的微粒群优化算法的0-1背包问题求解[J]. 计算机工程，2008，32（18）：23-25.

[4] 宋潇潇.求解大规模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背包问题的萤火虫群优化算法[J].计算机应用研究，2013，30（4）：993-994.