计算机工程Issue(10)：198-203,6.DOI:10.3969/j.issn.1000-3428.2014.10.037
求解0/1背包问题的自适应元胞粒子群算法
Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem
摘要
Abstract
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难题Key words
Particle Swarm Optimization(PSO)/0/1 knapsack problem/adaptive factor/cellular automata/combinatorial constrained optimization/NP hard problem分类
信息技术与安全科学引用本文复制引用
李枝勇,马良,张惠珍..求解0/1背包问题的自适应元胞粒子群算法[J].计算机工程,2014,(10):198-203,6.基金项目
高等学校博士学科点专项科研联合基金资助项目(20123120120005) （20123120120005）
上海市一流学科建设基金资助项目(S1201YLXK) （S1201YLXK）
上海高校青年教师培养计划基金资助项目(slg12010) （slg12010）
上海市教育委员会科研创新基金资助项目(14YZ090) （14YZ090）
上海市研究生创新基金资助项目(JWCXSL1202) （JWCXSL1202）
上海理工大学博士科研启动基金资助项目(1D-10-303-002)。 （1D-10-303-002）
