摘要： 对0/ 1 背包问题进行研究,提出一种自适应元胞粒子群算法。在算法设计过程中,重新定义粒子位置和速度的更新方程,引入自适应因子,为有效粒子的主动进化和无效粒子的主动退化提供依据,新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子,将元胞及其邻居引入到算法中保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验,结果表明,该算法不仅可以有效求解0/ 1 背包问题,而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性。
关键词:
粒子群优化,
0/ 1 背包问题,
自适应因子,
元胞自动机,
组合约束优化,
NP 难题
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
Key words:
Particle Swarm Optimization ( PSO ),
0/ 1 knapsack problem,
adaptive factor,
cellular automata,
combinatorial constrained optimization,
NP hard problem
中图分类号: