元胞微粒群算法及其在多维背包问题中的应用  

Cellular particle swarm optimization algorithm and its application to multi-dimensional knapsack problem

作　　者：刘勇[1,2] 马良[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]盐城工学院基础教学部,盐城224051

出　　处：《管理科学学报》2011年第1期86-96,共11页Journal of Management Sciences in China

基　　金：国家自然科学基金资助项目(70871081);上海市重点学科建设项目资助(S30504)

摘　　要：针对离散微粒群算法早熟收敛问题,基于元胞自动机的原理和离散微粒群算法,提出一种元胞微粒群算法.将元胞及其邻居引入到算法中来保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值.通过对典型多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的全局优化能力.Aiming at the premature convergence problem in discrete particle swarm optimization algorithm, a novel cellular particle swarm optimization algorithm is proposed, which is based on the principles of cellular automata and discrete particle swarm optimization algorithm. 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. Simulated tests of multi-dimensional knapsack problem and comparisons with other algorithms show the algorithm is feasible and effective and the algorithm has strong global optimization ability.

关 键 词：元胞自动机 离散微粒群算法 多维背包问题 优化 

分 类 号：O22[理学—运筹学与控制论]