针对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算法均能以较高概率命中最优解, 提高了高维度背包问题求解的稳定性和可靠性.
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] 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
中国综合性科技类核心期刊(北大核心)