基于改进鸡群优化算法的0-1背包问题研究

Research on 0-1 knapsack problem based on improved chicken swarm optimization algorithm

目的针对多种算法在求解0-1背包问题时存在的不足,采用改进鸡群算法优化背包问题。方法为避免优化过程中雄鸡粒子易出现早熟收敛、陷入局部最优而无法取得全局最优的情况,在母鸡和小鸡的位置更新公式中引入惯性权重因子ω,提高算法的全局和局部搜索能力。结果与结论选取不同的种群规模和惯性权重,对ICSO(Improved Chicken Swarm Optimization)算法优化0-1背包问题进行仿真,验证了改进算法的有效性;通过BA(Bat Algorithm),PSO(Particle Swarm Optimization),CSO(Chicken Swarm Optimization)和ICSO算法测试标准Sphere函数,证明了ICSO算法比其他算法有更好的全局搜索能力,收敛速度更快,稳定性更好。

Purposes—To optimize the knapsack problem with an improved chicken swarm algorithm in allusion to the shortcomings of many algorithms in solving 0-1 knapsack problem.Methods—In the process of optimization,the rooster particles are prone to premature convergence and can not get globally optimized.In order to avoid this situation,inertia weight factorωis introduced into the location update formula of hens and chickens to improve the global and local search ability of the algorithm.Result and Conclusion—With different population size and inertia weight,the ICSO(Improved Chicken Swarm Optimization)is simulated to optimize the 0-1 knapsack problem,thus verifying the effectiveness of the improved algorithm.With the standard sphere function tested by BA(Bat Algorithm),PSO(Particle Swarm Optimization),CSO(Chicken Swarm Optimization)and ICSO algorithm,it is proved that the ICSO algorithm has better global search ability,faster convergence speed and better stability than other algorithms.