基于Inver-Over算子的改进离散粒子群优化算法  

Modified Discrete Particle Swarm Optimization Algorithm Based on Inver-Over Operator

作　　者：郑东亮[1] 薛云灿[1] 杨启文[1] 李斐[1] 

机构地区：[1]河海大学计算机与信息学院,常州213022

出　　处：《模式识别与人工智能》2010年第1期97-102,共6页Pattern Recognition and Artificial Intelligence

基　　金：国家863计划资助项目(No.2006AA050104)

摘　　要：离散粒子群算法能充分利用粒子的局部极值和全局极值信息,但收敛速度慢、精度低;Inver-Over算子收敛速度快、精度高,但学习具有盲目性.结合二者优点,文中提出一种基于Inver-Over算子的改进离散粒子群优化算法.为防止早熟收敛,引入局部最优子群的概念,使粒子向局部最优子群中粒子学习而不是向个体局部最优学习.引入3个参数:学习选择概率用以确定粒子的学习对象,代数阈值确定何时向全局最优粒子学习,局部最优子群比决定最优子群的规模.讨论这些参数的选择原则,并给出相应参考选择范围.研究表明,文中算法与普通离散粒子群优化算法和郭涛算法相比,收敛速度和求解精度都有较大提高.Though the discrete particle swarm optimization （DPSO） can make the best of the local and global optima of particles, it converges slowly with low precision. The Guo Tao algorithm converges with fast high precision, but it is blindfold to learn from the other particles. A modified discrete particle swarm optimization algorithm is presented based on the inver-over operator （IDPSO）. To prevent premature convergence, the local sub-optimum particle swarm is introduced into IDPSO. Particles learn from the particles in the local sub-optimum particle swarm instead of their local optima. Three new parameters are introduced into IDPSO. Learning selection probability is introduced to select the particle to be learned. A generation threshold is introduced to define when to learn from the global particle. Local sub-optimum particle swarm ratio is introduced to define the size of the sub-optimum particle swarm. Selecting principles of these parameters is detailed discussed and the general reference scopes are given. Experiments are carried out on the traveling salesman problem and the results show that the modified IDPSO achieves good results compared with the Guo Tao algorithm and the general DPSO. The proposed algorithm improves both the convergence speed and solution precision.

关 键 词：离散粒子群优化(DPSO) Inver—Over算子 郭涛算法 旅行商问题 

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