带权重的贪心萤火虫算法求解0-1背包问题

doi:10.3969/j.issn.1006-2475.2019.05.016

计算机与现代化

带权重的贪心萤火虫算法求解0-1背包问题

(西华师范大学数学与信息学院，四川南充637000)

收稿日期:2018-10-19 出版日期:2019-05-14 发布日期:2019-05-14
作者简介:任静敏（1993-），女，四川南充人，硕士研究生，研究方向：智能算法，E-mail: stopbao@qq.com；通信作者：潘大志（1974-），男，四川三台人，教授，硕士生导师，中国计算机学会(CCF)会员，博士，研究方向：智能计算与算法设计，E-mail: pdzzj@126.com。
基金资助:
国家自然科学基金资助项目（11371015）；四川省教育厅自然科学基金资助项目(18ZA0469)；西华师范大学校级科研团队项目（CXTD2015-4）；西华师范大学英才基金资助项目（17YC385）

Solving 0-1 Knapsack Problem Based on Weighted Greedy Firefly Algorithm

(College of Mathematics and Information, China West Normal University, Nanchong 637000, China)

Received:2018-10-19 Online:2019-05-14 Published:2019-05-14

摘要/Abstract

摘要： 根据萤火虫算法的自身特点，将自适应权重、改进贪心算法、变异算子与基本萤火虫算法相结合，提出一种带权重的贪心萤火虫算法。通过加入自适应权重与变异算子，可以提高算法全局搜索能力，加入贪心算法在一定程度上可提高算法收敛速度，整体看，改进萤火虫算法提高了算法性能。通过仿真实验将改进后的算法与一些基本算法进行比较，实验结果表明，该算法在求解0-1背包问题时，无论在运算速度还是求解精度上都有明显改进。

关键词: 萤火虫算法, 背包问题, 贪心算法, 变异算子, 自适应权重

Abstract: According to the characteristics of firefly algorithm, a weighted greedy firefly algorithm is proposed by combining adaptive weight, improved greedy algorithm, mutation operator with basic firefly algorithm. By adding adaptive weight and mutation operator, the global searching ability of the algorithm could be improved. The addition of greedy algorithm can improve the convergence speed of the algorithm to a certain extent. On the whole, the improved firefly algorithm improves the algorithm performance. Through the simulation experiment, the improved algorithm was compared with some basic algorithms. The experimental results show that the algorithm has obvious improvement in the speed and precision of solving 0-1 knapsack problem.

Key words: firefly algorithm, knapsack problem, greedy algorithm, mutation operator, adaptive weight

中图分类号:

TP18

任静敏，潘大志. 带权重的贪心萤火虫算法求解0-1背包问题[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.05.016.

REN Jing-min， PAN Da-zhi. Solving 0-1 Knapsack Problem Based on Weighted Greedy Firefly Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.05.016.

参考文献

［1］贺毅朝,刘坤起,张翠军,等. 求解背包问题的贪心遗传算法及其应用［J］. 计算机工程与设计, 2007,28(11):2655-2657.
［2］樊小毛,马良. 0-1背包问题的蜂群优化算法［J］. 数学的实践与认识, 2010,40(6):155-160.
［3］马良,王龙德. 背包问题的蚂蚁优化算法［J］. 计算机应用, 2001,21(8):4-5.
［4］王会颖,贾瑞玉,章义刚，等. 一种求解0-1背包问题的快速蚁群算法［J］. 计算机技术与发展, 2007,17(1):104-107.
［5］〖KG-*4〗CHIL M C. Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem［J］. Applied Soft Computing, 2015,26:378-389.
［6］王莉,绍定宏,陆金桂. 基于遗传算法的0/1背包问题求解［J］. 计算机仿真, 2006,23(3):154-156.
［7］厍向阳,朱命昊,赵亚敏. 求解0/1背包问题的改进人工鱼群算法研究［J］. 计算机工程与应用, 2011,47(21):43-46.
［8］ BUAYEN P， WERAPUN J. Parallel time-space reduction by unbiased filtering for solving the 0/1-Knapsack problem［J］. Journal of Parallel and Distributed Computing, 2018,122:195-208.
［9］ ZHOU Y Q, CHEN X, ZHOU G. An improved monkey algorithm for a 0-1 knapsack problem［J］. Applied Soft Computing, 2016,38:817-830.
［10］TING Y L, MOHAMMED A B, AHAMAD T K. Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm［J］. Expert Systems with Applications, 2016,54(C):241-250.
［11］ZHANG X G, HUANG S Y, HU Y,et al. Solving 0-1 knapsack problems based on amoeboid organism algorithm［J］. Applied Mathematics and Computation, 2013,219(19):9959-9970.
［12］ARCHETTI C, BERTAZZI L, SPERANZA M G. Reoptimizing the 0-1 knapsack problem［J］. Discrete Applied Mathematics, 2010,158(17):1879-1887.
［13］TRUONG T K, LI K L, XU Y M.Chemical reaction optimization with greedy strategy for the 0-1 knapsack problem［J］. Applied Soft Computing, 2013,13(4):1774-1780.
［14］程美英,倪志伟,朱旭辉. 萤火虫优化算法理论研究综述［J］. 计算机科学, 2015,42(4):19-24.
［15］欧阳喆,周永权. 自适应步长萤火虫优化算法［J］. 计算机应用, 2011,31(7):1804-1807.
［16］顾明亮,李旻. 基于动态调整惯性权重的混合粒子群算法［J］. 计算机与现代化, 2018(6):25-29.
［17］敖永才,师奕兵,张伟,等. 自适应惯性权重的改进粒子群算法［J］. 电子科技大学学报, 2014,43(6):874-880.
［18］常友渠,肖贵元,曾敏. 贪心算法的探讨与研究［J］. 重庆电力高等专科学校学报, 2008,13(3):40-42.
［19］邝航宇,金晶,苏勇. 自适应遗传算法交叉变异算子的改进［J］. 计算机工程与应用, 2006,42(12):93-96.
［20］程魁,马良. 0-1背包问题的萤火虫群优化算法［J］. 计算机应用研究, 2013,30(4):993-994.
［21］刘建芹,贺毅朝,顾茜茜. 基于离散微粒群算法求解背包问题研究［J］. 计算机工程与设计, 2007,28(13):3189-3191.
［22］莫愿斌,马彦追,郑巧燕. 求解0-1背包问题的萤火虫算法［J］. 计算机工程与设计, 2014,35(8):2778-2784.
［23］王秋芬,梁道雷. 一种求解0-1背包问题的启发式遗传算法［J］. 计算机应用与软件, 2013,30(2):33-57.

[1]	卢磊, 贺智明, 黄志成. 基于多策略改进的麻雀搜索算法[J]. 计算机与现代化, 2023, 0(10): 23-31.
[2]	韩沐枫. 计及需求响应的微电网多时间尺度调度仿真[J]. 计算机与现代化, 2023, 0(03): 102-106.
[3]	刘雅文, 蒋妍, 潘大志. 改进二进制和声搜索算法求解多维背包问题[J]. 计算机与现代化, 2022, 0(08): 13-19.
[4]	李茹, 范冰冰. 基于混合策略改进的鲸鱼优化算法[J]. 计算机与现代化, 2022, 0(06): 13-20.
[5]	郑捷, 潘大志, . 改进的离散型萤火虫优化算法求解柔性作业车间调度问题 [J]. 计算机与现代化, 2021, 0(08): 11-15.
[6]	万科. 社交网络中正影响支配集问题的轮转贪心算法[J]. 计算机与现代化, 2020, 0(09): 49-53.
[7]	王岗，汪志成. 基于中长期交易电量校核的输电通道选择方法[J]. 计算机与现代化, 2019, 0(04): 38-.
[8]	陈宏伟，王万成，王继拓 . 混合自适应粒子群算法在电力经济调度中的应用[J]. 计算机与现代化, 2019, 0(03): 45-.
[9]	刘永洛1，王文强2，马立武2. 自适应权重CV模型在超声相控阵图像分割中的应用[J]. 计算机与现代化, 2019, 0(02): 37-.
[10]	孙源,刘汉强. 基于萤火虫算法的无监督最小视觉差彩色图像分割[J]. 计算机与现代化, 2018, 0(12): 85-.
[11]	曹雪雪. 基于贪心算法的智能宿舍分配方法[J]. 计算机与现代化, 2018, 0(01): 23-26.
[12]	王茵梦1，王松青2，杜庆伟1. 基于NSGA-II算法的认知无线电频谱分配[J]. 计算机与现代化, 2015, 0(10): 77-82.
[13]	刘艺兰，徐丽红，吴丰彦，潘淑静. 求解01背包问题的萤火虫算法[J]. 计算机与现代化, 2014, 0(4): 113-117.
[14]	欧微;易朝晖;焦丽萍. 基于混沌优化搜索的智能组卷算法[J]. 计算机与现代化, 2013, 218(10): 6-9.
[15]	吕聪颖;胡平;刘炯. 求解多约束0-1背包问题的遗传算法的改进[J]. 计算机与现代化, 2012, 1(9): 140-142.

带权重的贪心萤火虫算法求解0-1背包问题

Solving 0-1 Knapsack Problem Based on Weighted Greedy Firefly Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价