在 1995 年提出的一种基于群体智能的随机优化算法， 是在鸟群、 鱼群和人类社会行为规律的启发下提出 来的. 由于算法收敛的速度快、 设置参数少、 实现简 单， 近年来受到学术界的广泛重视. 现在， 粒子群算 法已广泛应用在函数优化、 神经网络训练、 模式分 类、 模糊系统控制以及其他工程领域 . 尽管传统的粒子群算法在低维空间的函数优
Abstract：Particle swarm optimization is a new computational method for tackling optimization functions. However，it is easily trapped into the local optimization when solving highdimension functions. To overcome this shorts velocity and position update rule to adjust its coming ，a new particle swarm optimization which improves particle’ movement based on the individual best position is proposed in the paper. The modified algorithm can enhance capability of optimization. Five benchmark functions are tested， and the results indicate that the modified particle swarm optimization is effective to find the global optimal solution. Key words：particle swarm optimization； swarm intelligence； evolutionary computation
要：粒子群算法是求解函数优化问题的一种新的进化算法 ， 然而它在求解高维函数时容易 陷入局部最优. 为了克服这个缺点， 提出了一种新的粒子群算法， 算法对粒子的速度和位置更新公 摘 式进行了改进， 使粒子在其最优位置的基础上进行位置更新 ， 增强了算法的寻优能力. 通过对 5 个 ， . 基准函数的仿真实验 表明了改进算法的有效性 关键词：粒子群算法； 群体智能； 进化计算 中图分类号： TP301. 6 文献标志码： A 文章编号： 1007－ 2683 （ 2010 ） 02－ 0031－ 04
收稿日期： 2009 － 05 － 23 Email： sdggh@ 163. com； 作者简介： 郭广寒（ 1980 —） ， 男， 助教， 王志刚（ 1978 —） ， 男， 讲师.
粒 子 群 算 法 是 由 Kennedy 和 Eberhart
32
哈
尔
滨
理
工
大
学
学
报
第 15 卷
操作的粒子群算法 . 在前人研究的基础上 ， 提出了 ， 一种改进的 粒 子 群 算 法 算 法 对 粒 子 的 更 新 方 式 使粒子在其最优位置的基础上产生下 进行调整 ， 一时刻的位 置 ， 这样使得粒子的新位置可以在一 增加了粒子获得较好解的几 个较优起点 上 产 生 ， 率 . 5 个基准测试函数的实验结果说明了新方案在 防止算法陷入局部最优的能力和解的稳定性方面 都有了明显提高 .
1
传统的粒子群算法
粒子群算法是一种基于种群的优化算法， 种群
称为粒子群， 粒子群中的个体称为粒子. 设有 N 个 其中第 i 个粒子表示为一个 D 粒子组成一个群体， x i2 ， …， x iD ） ， i = 1， 2， …， N， 维的向量 x i = （ x i1 ， 即第 i 个粒子在 D 维的搜索空间中的位置是 x i . 第 i 个粒 记为 v i = （ v i1 ， 子的飞行速度也是一个 D 维的向量， v i2 ， …， v iD ） ， 记第 i 个粒子迄今为止搜索到的最优位 p i2 ， …， p iD ） . 整个种群迄今为止搜索 置为 p i = （ p i1 ， p g2 ， …， p gD ） ，Kennedy 和 到的最优位置为 p g = （ p g1 ， Eberhart 最早提出的 PSO 算法采用下面的公式对粒 子进行操作， 即 v id = c1 r1 （ p id － x id ） + c2 r2 （ p gd － x id ） x id = x id + v id （1） （2）
第 15 卷
第2 期
哈 尔 滨 理 工 大 学 学 报
JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY
Vol. 15 No. 2 Apr. 2010
2010 年 4 月
一种改进的粒子群算法
1 2 郭广寒 ， 王志刚
（ 1. 哈尔滨理工大学 荣成学院， 山东 威海 264300 ；2. 南京师范大学 泰州学院 数学系， 江苏 泰州 225300 ）
0
引
言
［ 1 － 2］
质量高的特点 ， 但是一 化问题上具有求解速度快 、 旦函数的维度增加 ， 其优化性能便急剧下降 ， 易陷 入局部最优解 . 为了克服这一不足 ， 研究者提出了 3］ 很多 PSO 的改进方法 ， 如文［ 引入了压缩因子来 4］ 改进算法 ； 文［ 引入了自适应调整惯性权重因子 w 的方法来改进算法 ； 文［ 5］ 提出了具有高斯变异 6］ 的粒子群优化算法 ； 文［ 提出了协同粒子群优化 ； ［ 7 ］ ， Lovbjerg 算法 文 中 等人将遗传算法中的群体 概念引入 PSO 算法中 ， 同时引入 繁 殖 算 子 以 进 行 8］ 子群体间的信息交流 ； 文［ 提出了带新颖学习策 9］ 略的粒子群算法 ； 文［ 提出了一种引入随机摄动
A Modified Particle Swarm Optimization
GUO Guanghan1 ， WANG Zhigang2
（ 1. School of Rongcheng，Harbin University of Science and Technology，Weihai 264300 ，China； 2. Department of Mathematics， Taizhou College， Nanjing Normal University， Taizhou 225300 ， China）
i = 1， 2， …， N， d = 1， 2， …， D，c1 和 c2 表示学习 其中， 0， 1］ 因子，r1 和 r2 是［ 上均匀分布的随机数， 每一维 粒子的速度都被限制在一个最大速度 vmax （ vmax > 0 ） vi = vmax ； 若 vi < － vmax 时， vi = 之间， 若 vi > vmax 时， － vmax . 3］ 文［ 在粒子群算法中引入压缩因子， 将式 （ 1 ） 变换为 v id = χ （ v id + c1 r1 （ p id － x id ） + c2 r2 （ p gd － x id ） ） （ 3 ） 在式 （ 3 ） 中，χ = 为 压 缩 因 子， 2 |2 － － 槡 － 4 | = c1 + c2 > 4 ， 通常取 χ = 0. 729 ，c1 = c2 = 2. 05 ， 把 这种改进算法记为 PSO1 . 4］ 文［ 在粒子群算法中引入了线性减小的惯性 权重，将式（ 1 ） 变换为 v id = wv id + c1 r1 （ p id － x id ） + c2 r2 （ p gd － x id ） （ 4 ） N MAXITER － N iter + w2 ， w1 、 w2 式（ 4 ） 中，w = （ w1 － w2 ） N MAXITER N iter 为当前迭代次数， 为惯性权重的初始值和终值， N MAXITER 为最大迭代次数， 把这种改进算法记 PSO2 . 2
第2 期
郭广寒， 等：一种改进的粒子群算法
33
行对比. 6 ） 若未达到结束条件 （ 通常设为足够好的适应 度或达到一个预设最大代数 G max ） ， 则返回步骤 2 ） .
下对 5 个测试函数分别独立运行 30 次得到平均最 优适应值和标准差.
表2
函数 f1 f2 f3 f4 f5
PSO1 、 PSO2 、 MSPO 对函数的测试结果
PSO1 2.623%8E-43 7.914%1E-43 37.645%0 40.685%7 95.548%5 34.164%3 0.018%9 0.024%7 -9%368.811 703.108%8 PSO2 1.205%8E-16 3.245%4E-16 77.808%2 69.392%6 47.758%1 12.180%2 0.012%9 0.016%1 -10%639.56 518.933%7 MPSO 1.159%3E-112 2.523%9E-112 15.452%9 21.040%7 31.334%9 18.579%5 0.007%1 0.007%3 -12%305.63 211.839%1
2
改进的粒子群算法
在粒子群算法的迭代公式中， 把式（ 1 ） 和式 （ 2 ） 结合起来可以得到如下公式： x id （ t + 1 ） = x id （ t） + w （ x id （ t） － x id （ t － 1 ） ） + c1 r1 （ p id （ t） － x id （ t） ） + c2 r2 （ p gd （ t） － x id （ t） ） （5） 即粒子在 t + 1 时刻的位置是粒子在 t 时刻的位置上 c1 r1 （ p id （ t ） － x id （ t ） ） 和 沿着 w （ x id （ t） － x id （ t － 1 ） ） 、 c2 r2 （ p gd （ t） － x id （ t ） ） 的矢量和的方向前进， 而不考 虑粒子在 t 时刻位置上的好坏. 此外在传统的粒子 群算法中， 每个粒子获得的信息只有自身最优位置 那么其他粒子的最优信 信息和群体最优位置信息， 息是否对粒子的运动有参考作用呢 ？ 正如社会学家 E. O. Wilson［10］所说 ：“至少在理论上， 在群体搜索食 物的过程中， 群体中的每个个体可以从群体的新发 . 因此在 现和群体中所有其他个体的经验中受益 ” 这里可把公式（ 5 ） 改为 x id （ t + 1 ） = p id （ t） + w （ x id （ t） － p id （ t － 1 ） ） + c1 r1 （ q d （ t） － p id （ t） ） + c2 r2 （ p gd （ t） － p id （ t） ） （6） 即把传统粒子群算法中的速度和位置更新公式变为 v id = wv id + c1 r1 （ q d － p id ） + c2 r2 （ p gd － p id ） （ 7 ） x id = p id + v id （8） 其中 q 是种群中通过赌轮方式选出的粒子最优位 置. 更新后的速度和位置更新公式表示粒子每次都 在其最优位置上往下一个方向飞行， 当其无法获得 ， 更新时 粒子依旧停留在原来的最优位置处 ， 直到粒 子最优位置的适应值更新. 这样可以使粒子在一个 比较好的起点上产生下一时刻的位置， 增加了粒子 产生一个新的较好位置的几率， 使算法的寻优能力 得到提高. 算法步骤如下： 1 ） 在初 始 化 范 围 内， 对粒子群进行随机初始 化， 包括初始位置和速度. 2 ） 计算每个粒子的适应度. 3 ） 对于每个粒子， 将其适应度与所经历过的最 好位置的适应度进行比较， 如果更好， 则将其作为粒 用当前位置更新个体历史最 子的个体历史最优值， 好位置. 4 ） 对每个粒子， 将其历史最优适应度与群体内 或邻域内所经历的最好位置的适应度进行比较 ， 若 ， . 更好 则将其作为当前的全局最好位置 5 ） 根据式（ 7 ） 和式 （ 8 ） 对粒子的速度和位置进