双尺度变异离散粒子群算法求解背包问题

Discrete Particle Swarm Optimization Algorithm Based on Double-scale Mutation for Knapsack Problems

针对传统离散粒子群算法求解背包问题早熟收敛、精度低等缺点提出一种解决背包问题的双尺度变异离散粒子群算法。利用对当前最优解进行双尺度速度变异,可以实现提高算法局部最优解搜索能力的同时,保持算法的全局搜索能力和逃出局部极值的能力。在算法初期利用粗尺度速度变异可使粒子快速定位到最优解区域,算法后期则通过逐渐减小的细尺度变异可提高算法最优解的精度。粒子位置初始化过程中,把采用贪心策略所得的结果作为一个粒子的初始位置。将改进算法与其他算法比较证明该算法不仅能够有效解决其他算法搜索能力差的问题,同时还提高了最优解的精度和收敛速度。

To deal with the problem of premature convergence and low precision of the traditional discrete particle swarm optimization algorithm for knapsack problems, a discrete particle swarm optimization algorithm based on double-scale velocity mutation for knapsack problems was proposed. The double- scale velocity mutation operator was introduced on the current optimal solution, which could not only improve the ability of local search, but also keep the abilities of global space search and escaping from local optimum. The coarse-scale mutation operators could be utilized to quickly localize the global optimal space at the early evolution. The fine multi-scale mutation operators which gradually reduced could improve the precision of optimal solution at the later evolution. In the course of initialization, the results were used that obtained from greedy strategy as the initial position of a particle. Comparison of the performance of the proposed approach with the other DPSO algorithms was experimented. The experimental results show that the proposed approach can not only effectively solve the problem of lack of local search ability, but also significantly improve the accuracy of the solution and speed up the convergence.