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

关键词

背包问题 / 粒子群优化算法 / 贪心优化策略 / 模拟退火算法