Study of an improved hybrid particle swarm optimization algorithm for solving 0-1 knapsack problems
-
摘要: 针对0-1背包问题求解, 将离散二进制粒子群优化 (Binary Particle Swarm Optimization, BPSO) 算法、贪心优化策略和模拟退火算法有机结合, 提出了一种改进算法: 带贪心优化的混合粒子群和模拟退火(Hybrid optimization algorithm based on the BPSO, the Simulated Annealing (SA) Algorithm and the Combined Greedy Optimization Operator (CGOO), BPSOSA-CGOO) 算法. 基于新算法, 完成了9组不同维度数据的仿真实验. 实验结果表明, BPSOSA-CGOO算法能够以较小的种群规模及迭代次数实现0-1背包问题的有效求解, 并在问题维度为20维的测试数据中找到优于已知最优解的解; 独立重复实验验证了, 无论对于低维度还是高维度背包问题, BPSOSA-CGOO算法均能以较高概率命中最优解, 提高了高维度背包问题求解的稳定性和可靠性.Abstract: In order to solve 0-1 knapsack problems with greater stability and efficiency, we propose a BPSOSA-CGOO (Hybrid optimization algorithm based on the BPSO (binary particle swarm optimization), the simulated annealing (SA) algorithm and the combined greedy optimization operator (CGOO)) algorithm which is composed of the BPSO, the greedy optimization strategy, and the simulated annealing algorithm. Simulation experiments of 9 groups of different dimensions show that the BPSOSA-CGOO algorithm can solve 0-1 knapsack problems efficiently for small population sizes and iteration times. Meanwhile, it was observed that experiments performed with the algorithm can also find a better solution for 20-dimensional test data. In independent and repeated experiments, the BPSOSA-CGOO algorithm can achieve the optimal solution with high probability for both low-dimensional and high-dimensional knapsack problems; hence, stability and reliability is significantly improved when using the BPSOSA-CGOO algorithm to solve high-dimensional knapsack problems.
-
图 1 模拟退火操作产生新解示意图
Fig. 1 Schematic diagram of a simulated annealing operation generating new solutions
图 3 不同测试数据命中次数对比柱状图
Fig. 3 Comparison bar graph of the hit times with different test data
图 4 20次独立重复执行测试数据8的结果图
Fig. 4 Result chart of test data 8 in 20 independent experiments
表 1 BPSOSA-CGOO算法对不同测试数据的执行结果
Tab. 1 Results from the BPSOSA-CGOO algorithm with different test data
编号 维数 已知解 实验最优解 实验解 进化
次数价值 重量 价值 重量 1 10 295 269 (0111000111) 295 269 1 2 15 481.07 354.96 (001010110111011) 481.07 354.96 1 3 20 1024 871 (10111111010111111101) 1042 878 3 4 23 9767 9768 (11111111010000011000000) 9767 9768 12 5 50 3103 1000 (11010101111011011011011111110100001010011000001000) 3103 1000 63 6 50 16102 11231 (01111001010111000110101010110100011011011010000110) 16102 11231 14 7 60 8362 2393 (111111111111111111111111111111111111111111110100110110111000) 8362 2393 10 8 80 5183 1170 (1111111111111111111111111111011101010010001011000100000000000
1000010000000000000)5183 1170 103 9 100 15170 3818 (1111111111111111111111111111111111111111111111111111111111111
111111111010101111000011010001100011010)15170 3818 10 
下载: 导出CSV
表 2 BPSOSA-CGOO算法20次独立重复实验执行结果
Tab. 2 Results from the BPSOSA-CGOO algorithm with different test data after 20 repeat runs
编号 维数 已知解 最优解 最差解 平均值 标准差 SSN AVIN 价值 重量 价值 重量 价值 重量 价值 重量 1 10 295.00 269.00 295.00 269.00 295.00 269.00 295.00 269.00 0.00 20 0.8 2 15 481.07 354.96 481.07 354.96 481.07 354.96 481.07 354.96 0.00 20 1.7 3 20 1024.00 871.00 1042.00 878.00 1042.00 878.00 1042.00 878.00 0.00 20 14.7 4 23 9767.00 9768.00 9767.00 9768.00 9767.00 9768.00 9767.00 9768.00 0.00 20 12.0 5 50 3103.00 1000.00 3103.00 1000.00 3093.00 1000.00 3102.20 1000.00 2.48 18 100.0 6 50 16102.00 11231.00 16102.00 11231.00 16102.00 11231.00 16102.00 11231.00 0.00 20 51.0 7 60 8362.00 2393.00 8362.00 2393.00 8362.00 2393.00 8362.00 2393.00 0.00 20 11.3 8 80 5183.00 1170.00 5183.00 1170.00 5135.00 1172.00 5170.50 1169.90 13.82 1 103.0 9 100 15170.00 3818.00 15170.00 3818.00 15170.00 3818.00 15170.00 3818.00 0.00 20 14.4
下载: 导出CSV
表 3 修改参数后测试数据8的20次独立重复实验执行结果
Tab. 3 Results from 20 independent experiments of test data 8 after parameter modification
算法 已知解 最优解 最差解 平均值 标准差 SSN GOPSO 5183 5183 5168 5180.7 3.86 8 BPSOSA-CGOO 5183 5183 5178 5182.2 1.32 13
下载: 导出CSV
表 4 10次独立重复实验执行结果
Tab. 4 Results from 10 independent experiments
用例维数 实验参数 已知解 最优解 最差解 平均值 标准差 种群 迭代 100 100 200 8254 8003 7925 7957.5 21 1000 500 8254 8016 7997 8010.7 6
下载: 导出CSV
-
[1] MATHEWS G B. On the partition of numbers [J]. Proceedings of the London Mathematical Society, 1896, s1-28(1): 486-490. [2] 邹恒明. 算法之道 [M]. 北京: 机械工业出版社, 2010: 67-72. [3] KELLERER H, PFERSCHY U, PISINGER D. Knapsack Problems [M]. Berlin: Springer-Verlag, 2004. [4] KARP R M, MILLER R E, THATCHER J W. Reducibility among combinatorial problems [J]. Journal of Symbolic Logic, 1975, 40(4): 618-619. [5] MARTELLO S, TOTH P. Knapsack Problems: Algorithms and Computer Implementations [M]. New York: John Wiley & Sons, Inc., 1990. [6] 王熙照, 贺毅朝. 求解背包问题的演化算法 [J]. 软件学报, 2017, 28(1): 1-16. [7] BANSAL J C, DEEP K. A modified binary particle swarm optimization for knapsack problems [J]. Applied Mathematics and Computation, 2012, 218(22): 11042-11061. [8] EZUGWU A E, PILLAY V, HIRASEN D, et al. A comparative study of meta-heuristic optimization algorithms for 0-1 knapsack problem: Some initial results [J]. IEEE Access, 2019(7): 43979-44001. [9] HU J S, CHEN G L, GUO G C. Solving the 0-1 knapsack problem on quantum computer [J]. Chinese Journal of Computers, 1999, 22(12): 1314-1316. [10] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to Algorithms [M]. 2nd ed. Cambridge: MIT Press, 2001: 323-399. [11] PUSHPA S K, MRUNAl T V, SUHAS C. A study of performance analysis on knapsack problem [J]. International Journal of Computer Applications, 2016(2): 5-10. [12] GOLDBERG D E. Genetic Algorithms in Search, Optimization and Machine Learning [M]. Boston: Addison-Wesley Longman Publishing Co., Inc., 1989. [13] 霍红卫, 许进, 保铮. 基于遗传算法的0-1背包问题求解 [J]. 西安电子科技大学学报, 1999, 26(4): 101-105. [14] 陈国良, 王熙法, 庄镇泉. 遗传算法及其应用 [M]. 北京: 人民邮电出版社, 1999: 1-195. [15] 贺毅朝, 王熙照, 李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究 [J]. 计算机学报, 2016, 39(12): 2614-2630. [16] 徐小平, 庞润娟, 王峰, 等. 求解0-1背包问题的烟花算法 [J]. 计算机系统应用, 2019, 28(2): 164-170. [17] KENNEDY J, EBERHART R. Particle swarm optimization [C] // Proceedings of ICNN’95 - International Conference on Neural Networks. IEEE, 1995: 1942-1948. [18] EBERHART R C, SHI Y H. Particle swarm optimization: developments, applications and resources [C]// Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546). IEEE, 2001: 81-86. [19] 赵传信, 季一木. 粒子群优化算法在0/1背包问题的应用 [J]. 微机发展, 2005, 15(10): 23-25. [20] 贺毅朝, 王熙照, 李文斌, 等. 求解随机时变背包问题的精确算法与进化算法 [J]. 软件学报, 2017, 28(2): 185-202. [21] 贺毅朝, 刘坤起, 张翠军, 等. 求解背包问题的贪心遗传算法及其应用 [J]. 计算机工程与设计, 2007, 28(11): 2655-2657, 2681. [22] 贺毅朝, 宋建民, 张敬敏, 等. 利用遗传算法求解静态与动态背包问题的研究 [J]. 计算机应用研究, 2015, 32(4): 1011-1015. [23] 任静敏, 潘大志. 带权重的贪心萤火虫算法求解0-1背包问题 [J]. 计算机与现代化, 2019(5): 86-91. [24] 耿亚, 吴访升. 基于粒子群-模拟退火算法的背包问题研究 [J]. 控制工程, 2019, 26(5): 991-996. [25] 周洋, 潘大志. 求解0-1背包问题的贪心优化粒子群算法 [J]. 西华师范大学学报(自然科学版), 2018, 39(3): 319-324. [26] KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm [C]// 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation. IEEE, 1997: 4104-4108. [27] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671-680. [28] 卢宇婷, 林禹攸, 彭乔姿, 等. 模拟退火算法改进综述及参数探究 [J]. 大学数学, 2015, 31(06): 96-103. [29] 庞峰. 模拟退火算法的原理及算法在优化问题上的应用 [D]. 长春: 吉林大学, 2006: 1-5 [30] 谷鹏, 王大龙, 张世仓. 基于粒子群优化的扩展卡尔曼滤波方法研究 [J]. 工业控制计算机, 2019, 32(11): 80-82. [31] 李鹏, 李兵舰, 亓亮, 等. 一种改进的粒子群优化算法及其在无人机航路规划中的应用 [J]. 舰船电子对抗, 2019, 42(5): 59-64. [32] 郭玉洁, 张强, 袁和平. 一种双种群协同多目标粒子群优化算法及应用 [J]. 吉林大学学报(理学版), 2019, 57(5): 1155-1162. -
点击查看大图
图(5) / 表(4)
计量
- 文章访问数: 200
- HTML全文浏览量: 91
- PDF下载量: 18
- 被引次数: 0