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

• 计算机科学 • 上一篇    下一篇

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

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

  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   

  1. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China
  • Received:2019-12-06 Published:2020-12-01

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

中图分类号: