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

来源：华东师范大学学报·哲学社会科学版杂志2020年第6期北京时间：

作者：姚若侠, 薛丹, 谢娟英, 范虹

摘要：针对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算法均能以较高概率命中最优解, 提高了高维度背包问题求解的稳定性和可靠性.

关键词：背包问题,粒子群优化算法,贪心优化策略,模拟退火算法,

基金资助：国家自然科学基金(11471004, 61673251); 陕西省重点研究和发展项目(2018SF-251)