一种求解0-1背包问题的整数混沌粒子群优化算法

An Integer Chaos-Particle-Swarm-Optimization Algorithm for 0-1Knapsack Problem

针对0-1背包问题(0-1KP)的特点,以经典的速度-位移模型为基础整数编码各粒子,以混沌序列指导全局搜索,以排列的改变描述粒子的飞行.更新粒子的位置,进而提出用于求解0-1KP的整数混沌粒子群优化(ICPSO)算法.该算法由于背包容量的限制,融入到编码和粒子飞行中,因而不会在进化中产生无效的粒子,从而提高了算法的求解效率.实验结果表明:ICPSO算法简明、有效,较典型遗传算法,及粒子群算法具有更好的收敛性能和求解速度.

For solving 0-1 knapsack problem （KP）, an integer chaos-particle-swarm-optimization （ICPSO） algorithm is presented. In the algorithm, according to the characteristic of 0-1 KP, the classical velocity-position model is inherited; each particle is encoded with integers; a chaos sequence is employed to direct global search and the permutation change is used to depict the flying behavior of each particle, （i. e. , the update of position）. Further, because the limit of pack ca- pacity is taken into consideration in the coding and particle flying process, no invalid particles are produced in the evolu- tionary process, which thereby enhances the algorithm efficiency. Experimental results demonstrate that ICPSO is simple but effective, and better than genetic algorithm and particle swarm optimization at constringency and convergence speed.