求解0-1背包问题的萤火虫算法
2014-08-23刘艺兰徐丽红吴丰彦潘淑静
刘艺兰,徐丽红,吴丰彦,潘淑静
(中国传媒大学计算机学院,北京 100024)
0 引言
背包问题(Knapsack Problem,KP)是一种组合优化的NP完全问题,也是运筹学中的一个典型的优化难题,有非常广泛的实际应用背景,如运输中的货物装载、人造卫星的物品装载、预算控制以及项目选择等问题,很多整数规划问题的解决理论上都依赖于高效的背包问题解法[1]。一般的背包问题在整数、有界的条件下可转换成等价的0-1背包问题(0-1 Knapsack Problem),0-1背包问题还可用于研究动态自适应多媒体处理方法[2]、基于用户迁徙网络的广告投放策略[3]等方面,因此研究0-1背包问题有非常重要的实际意义。
关于求解0-1背包问题的算法,很多学者都进行了研究,例如差异演化算法[4]、遗传算法及其相关改进算法与混合算法[5-7]、改进人工鱼群算法[8]、量子蚁群算法[9]、模糊粒子群算法[10]、细菌觅食算法[11]、烟花算法[12]等。本文则使用萤火虫算法来研究0-1背包问题,萤火虫算法有2种:GSO(Glowworm Swarm Optimisation)和FA(Firefly Algorithm),文献[13]经过实验对比说明了2种萤火虫算法的可行性,并且寻优精度整体上优于粒子群优化算法,而且萤火虫算法参数少,实现简单,因此可以使用萤火虫算法来研究0-1背包问题。文献[14]已设计并使用改进的GSO算法针对0-1背包问题进行了求解,并取得了较为满意的效果,本文则使用另一种萤火虫算法——FA来求解0-1背包问题。
下面对0-1背包问题进行描述:给定n个重量为{W1,W2,...,Wn}价值为{P1,P2,...,Pn}的物品和一个容量为V的背包,0-1背包问题是求这些物品中的一个最有价值的子集,并且要能够装到背包中。……
