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