好位置 p g 作比较 , 如果较好 , 则重新设置 p g ; Step5 : 根据公式 ( 1) 和 ( 2 ) 进行速度和位置 ( 解 ) 的迭代 ;
Step6 : 重复 Step2 ～ Step5 , 直到满足算法停止
上式中 r3 t 0 > T 0 和 r4 t g > T g 为极值扰动算子 。 其 中 : t 0 , t g 分别表示个体极值和全局极值进化停滞步 数 ; T 0 , T g 表示个体极值和全局极值需要扰动的停 滞步数阈值 ; 1 , t0 ≤ T0 r3 t 0 > T 0 = 和 r4 t g > T g = U ( 0 , 1) , t 0 > T 0 1 , tg ≤ Tg 表示带条件的均匀随机函数 。 U ( 0 , 1) , t g > T g 这个粒子运动公式避免了由粒子速度项引起的 粒子发散而导致后期收敛变慢和精度低的问题 。 极 值扰动算子可以加快粒子跳出局部极值点而继续优 化。 文献 [ 7 ] 提出的改进算法中粒子速度更新公式 为: x i d = w 3 x i d + c1 3 r 1 3 ( p i d - x i d ) +
其中 , Hi 为信息扩散函数 , t 为当前进化代数 ( 当前 迭代代数) , T 是设定的进化总代数 。 信息扩散函数 由 3 部分组成 , 即 1) 1 - ( d i + 1) / ( max d j + 1) 将移动尺度与粒子 1 ≤j ≤n 隶属于 P“ 的程度联系起来 。 越靠近 Pg 的粒 g 周围” 子 , 受其影响越大 , 移动尺度相对越大 ; 反之 , 移动尺 度越小 。 同一代粒子群变尺度向 Pg 靠拢 , 有利于提 高群体多样性 。 其中 , d i 是第 i 个粒子与 Pg 的距离 , 距离是用两个粒子的位置差异来衡量的 ; 1 是为了 避免分母为 0 。 2) ( n + 1) / ( n + n′ + 1 ) 将移动尺度与粒子的 分布联系起来 。 搜索时 , 判断粒子进入 Pg 周围的情 况 , 分布于内围的粒子数目多 , 则移动尺度逐渐变 小 , 有利于后期进化群体多样性的保持 。 3) 1 - t/ T 将移动尺度与进化代数联系起来 , 在算法进化初期 , 粒子以较大的速度向 Pg 移动 , 有 利于加快搜索 ; 随着进化代数的增加 , 移动尺度逐渐 变小 , 有利于进化后期群体多样性的保持 。 根据公式 ( 5) , ( 6) 得知 ,粒子速度更新公式增加 一个信息扩散函数 , 利用粒子的分布和迭代代数自 适应控制” 社会认知” 学习的移动尺度 , 从而能够充 分利用先验知识来指导粒子移动 , 增强了局部搜索 能力 ,提高群体多样性 , 有效增强避免早熟收敛能 力。 2. 2 与各种原理 、 算法等的融合使用 PSO 作为一种随机搜索的优化算法 , 要优化不
作者简介 : 陈永刚 ( 1978 - ) ,男 ,河南修武人 ,河南科技大学电子信息工程学院助教 。 魏汪洋 ( 1978 - ) ,男 ,河南周口人 ,河南科技大学电子信息工程学院讲师 。 肖春宝 ( 1976 - ) ,男 ,河北保定人 ,河南科技大学电子信息工程学院讲师 。
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.
2009 年 5 月 西 安 邮 电 学 院 学 报 第 14 卷 第 3 期 J OU RNAL OF XI’ AN UN IV ERSIT Y OF POST AND TEL ECOMMUN ICA TIONS
May 2009 Vol114 No 13
粒子群优化算法在函数优化上的研究与发展
陈永刚 ,魏汪洋 ,肖春宝
( 河南科技大学 电子信息工程学 PSO) 与其他演化算法相似 ,也是基于群体的 。每个粒子被随机初始化以表示一个可能的 解 ,并在解空间通过更新迭代搜索最优解 。该算法的特点是简单容易实现而又功能强大 。该算法最初被提出来主 要应用于函数优化 。经过几年的发展 ,已经出现了大量的改进算法 。本文总结了这些改进算法的基本主要形式 , 并给出了未来可能的研究方向 。 关键词 : 粒子群算法 ; 函数优化 ; 群智能 中图分类号 : TP18 文献标识码 :A 文章编号 :1007 - 3264 ( 2009) 03 - 0113 - 04
PSO 算法模型 , 认为粒子具有量子行为 , 此模型称
平均结果总是好于标准 PSO 的结果 。 文献 [ 8 ] 还提出了有分工策略的 PSO 算法 。在 此方法中 ,粒子群被分为 3 个子群体 : POP Core , P
Near 和 P Far 。其中 POP Core 不断在群体最
有附近探索新的群体最优 , 而从保证了群体最优解 附近的充分搜索 ; P
( 2 ) 中令惯性因子 w = 0 。 其粒子进化方程描述为 : x id = x id + c1 3 r 1 3 ( p i d x i d) + ( 3) c2 3 r2 3 ( p gd - x i d )
与基本 PSO 算法相比 , 上式描述的进化方程使 得全局搜索能力减弱 , 但是局部搜索能力得到了加 强。 文献 [ 6 ] 提出了一个更简化而高效的 PSO 算法 。 其中粒子的运动公式为 :

2 , 为收敛因 Φ Φ2 - 4Φ | | 2 子 , Φ = c1 + c2 > 4 。 通常取 Φ 为 4 . 1 , 则 χ = 0 .
其中 χ =
729 。 实验结果表明 , 与使用惯性权重的粒子群算法
相比 , 使用收敛因子的粒子群算法有更快的收敛速 度。 文献 [ 5 ] 提出的一种随机 PSO 算法 。 在式 ( 1) ,
1 粒子群算法介绍
1. 1 PSO 算法基本原理 PSO 初始化为一群随机粒子 ( 随机解 ) , 然后通
过迭代找到最优解 。在每一次迭代中 , 粒子通过跟 踪两个 “极值” 来更新自己 。第一个就是粒子本身所
收稿日期 :2008 - 10 - 21 基金项目 : 河南省基础与前沿技术研究项目 ( 编号 :072300410210)
引言
粒子群优化算法 ( PSO ) 是由 Kennedy 和 Eber2
hart 等于 1995 年发明的一种基于群智能的进化计
算技术 [ 1 - 2 ] ,来源于对鸟群捕食的行为研究 。后来
shi 等人 [ 3 ] 引入惯性权重 w , 形成了当前的标准版
本 。PSO 的优势在于概念简单 , 容易实现并且没有 许多参数需要调整 。因此 , 该算法很快应用于神经 网络 , 多目标优化 , 组合优化 , 函数优化等问题 。作 为一种高效的全局优化算法 , PSO 可用于求解大量 非线性 、 不可微和多峰值的复杂函数优化问题 。为 了提高算法的优化效率 , 近几年出现了很多改进的
0 Gn / Gmax 。 如果 f rac < 0. 9 ,且 f rac > dist [ l ]/ max inst , 则针对 l best 进行搜索 ; 否则使用 g best 。 对函数 Rosenbrock 和 Rast rigrin 等进行测试显示 ,本方法的
文 献[8 ] 提 出 了 有 模 拟 退 火 的 粒 子 群 算 法 ( PSOwSA) 。PSOwSA 方法是在 PSO 方法的基础 上引入模拟退火思想 。当温度变化相对缓慢时 , 能 够搜索到较好的结果 。 文献 [ 9 ] 从 量 子 力 学 的 角 度 提 出 了 一 种 新 的
c2 3 r2 3 ( p gd - x i d ) x id = x id + v id ( 1) ( 2)
其中 c1 和 c2 是非负常数 , 称为学习因子 。 r1 和 r2 是介于 [ 0 , 1 ] 之间的随机数 。 每一维粒子的速度 都会被限制在一个最大速度 V max , 如果某一维更新 后的速度超过用户设定的 V max , 那么这一维的速度 就被设定为 V max , 即 V i d ∈ [ - V max , V max ] 。 1. 2 算法流程 标准 PSO 的算法流程如下 : Step1 : 初始化所有粒子 ,包括随机位置和速度 ; Step2 : 评价每个粒子的适应值 ;
PSO 算法 ,并且已经应用于许多科学和工程领域 。
找到的最优解 。 这个叫做个体极值 , 记为 Pi 。 另一个 极值是整个种群目前找到的最优解 。 这个极值是全 局极值 , 记为 Pg 。 设搜索空间为 D 维 , 总粒子数为 n , 第 i 个粒子 表示为 X i = ( x i 1 , x i2 , …, x iD ) ; 第 i 个粒子的历史 最优位置记为 Pi = ( p i1 , p i 2 , …, p iD ) ; 整个群体经 历过的最好位置记为 Pg = ( p g1 , p g2 , …, p gD ) ; 粒子 速度记为 V i = ( v i1 , v i 2 , …, v iD ) 。 则对于每一代 , 每 个粒子的位置根据如下方程变化 。 v i d = w 3 v i d + c1 3 r 1 3 ( p i d - x i d ) +
2. 1 从两个核心运动公式入手进行分析和改动
( 5)
H i = [ 1 - ( d i + 1 ) / ( max d j + 1) ] 3 [ ( n +
1) / ( n + n + 1) ] 3 [ 1 - t/ T ]
( 6)
由于算法的优化效果取决于粒子运动的两个公 式 ,所以改动公式 ,就相当于是粒子的运动发生了变 化 ,进而产生不同的优化效果 。 文献 [ 4 ] 描述了一种带收敛因子的粒子群优化 算法 ,其位置和速度更新公式如下所示 : v i d = χ( v i d + c1 3 r1 3 ( p i d c2 3 r2 3 ( p gd - x i d ) ) x id) +