APP下载

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

2014-08-23刘艺兰徐丽红吴丰彦潘淑静

计算机与现代化 2014年4期
关键词:优化

刘艺兰,徐丽红,吴丰彦,潘淑静

(中国传媒大学计算机学院,北京 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背包问题是求这些物品中的一个最有价值的子集,并且要能够装到背包中。……

登录APP查看全文

猜你喜欢

优化
超限高层建筑结构设计与优化思考
PEMFC流道的多目标优化
民用建筑防烟排烟设计优化探讨
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
由“形”启“数”优化运算——以2021年解析几何高考题为例
围绕“地、业、人”优化产业扶贫
事业单位中固定资产会计处理的优化
4K HDR性能大幅度优化 JVC DLA-X8 18 BC
几种常见的负载均衡算法的优化