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

摘要：

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

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

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;陕西省重点研究;发展项目

在线出版日期：2020-12-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：90-98