求解0-1背包问题的混合粒子群改进算法研究

doi:10.3969/j.issn.1000-5641.201921025

华东师范大学学报（自然科学版） ›› 2020, Vol. 2020 ›› Issue (6): 90-98.doi: 10.3969/j.issn.1000-5641.201921025

求解0-1背包问题的混合粒子群改进算法研究

姚若侠, 薛丹, 谢娟英, 范虹

陕西师范大学计算机科学学院, 西安 710119

收稿日期:2019-12-06 发布日期:2020-12-01
通讯作者: 姚若侠, 女, 教授, 博士生导师, 研究方向为符号计算、智能计算、模式识别. E-mail: rxyao@snnu.edu.cn E-mail:rxyao@snnu.edu.cn
基金资助:
国家自然科学基金(11471004, 61673251); 陕西省重点研究和发展项目(2018SF-251)

Study of an improved hybrid particle swarm optimization algorithm for solving 0-1 knapsack problems

YAO Ruoxia, XUE Dan, XIE Juanying, FAN Hong

School of Computer Science, Shaanxi Normal University, Xi’an 710119, China

Received:2019-12-06 Published:2020-12-01

摘要/Abstract

摘要： 针对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.

Key words: knapsack problem, particle swarm optimization algorithm, greedy optimization strategy, simulated annealing algorithm

中图分类号:

TP301

姚若侠, 薛丹, 谢娟英, 范虹. 求解0-1背包问题的混合粒子群改进算法研究[J]. 华东师范大学学报（自然科学版）, 2020, 2020(6): 90-98.

YAO Ruoxia, XUE Dan, XIE Juanying, FAN Hong. Study of an improved hybrid particle swarm optimization algorithm for solving 0-1 knapsack problems[J]. Journal of East China Normal University(Natural Science), 2020, 2020(6): 90-98.

参考文献

[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

求解0-1背包问题的混合粒子群改进算法研究

Study of an improved hybrid particle swarm optimization algorithm for solving 0-1 knapsack problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	张昆;许世远;王军. 模拟退火算法在生态保护区空间选址中的应用：以澳大利亚蓝山保护区为例[J]. 华东师范大学学报(自然科学版), 2010, 2010(2): 1-8.
[2]	宋娟;全惠云. 图像增强技术中的智能算法[J]. 华东师范大学学报(自然科学版), 2007, 2007(3): 93-99.