求解0/1背包问题的自适应元胞粒子群算法  

Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem

作　　者：李枝勇[1] 马良[1] 张惠珍[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程》2014年第10期198-203,共6页Computer Engineering

基　　金：高等学校博士学科点专项科研联合基金资助项目(20123120120005);上海市一流学科建设基金资助项目(S1201YLXK);上海高校青年教师培养计划基金资助项目(slg12010);上海市教育委员会科研创新基金资助项目(14YZ090);上海市研究生创新基金资助项目(JWCXSL1202);上海理工大学博士科研启动基金资助项目(1D-10-303-002)

摘　　要：对0/1背包问题进行研究,提出一种自适应元胞粒子群算法。在算法设计过程中,重新定义粒子位置和速度的更新方程,引入自适应因子,为有效粒子的主动进化和无效粒子的主动退化提供依据,新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子,将元胞及其邻居引入到算法中保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验,结果表明,该算法不仅可以有效求解0/1背包问题,而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性。0/1 knapsack problem is studied,and adaptive cellular particle swarm optimization algorithm is presented. In the design of the algorithm,the rules about updating the particle’ s velocity and position are redefined,an adaptive factor is introduced to provide a basis for the active evolution of the valid particle and the active degradation of the invalid particle,a new coding mode is given to make new particles be valid with great probability and fast speed,cellular and its neighbor are introduced into the algorithm to maintain the swarm’ s diversity and the algorithm uses evolutionary rule of cellular in local optimization to avoid local optima. Simulation experimental results of different scale 0/1 knapsack problem and comparisons with other algorithms show that the algorithm not only can solve the 0/1 knapsack problem effectively,but also can get the good second-best solution even for the global optimal solution with a faster rate,and has a certain degree of stability.

关 键 词：粒子群优化 0/1背包问题 自适应因子 元胞自动机 组合约束优化 NP难题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]