计 算 机 工 程 第 34 卷 第12期
Vol.34 No. 12 Computer Engineering ·博士论文·
文章编号：1000—3428(2008)12—0031—03
文献标识码：A
2008年6月
June 2008
中图分类号：TP301.6
惯性权值对粒子群算法收敛性的影响及改进
黄翀鹏，熊伟丽，徐保国
(江南大学通信与控制工程学院，无锡 214122)
摘 要：研究惯性权值对粒子群算法(PSO)收敛性的影响，在分析线性权值递减策略基础上，提出一种基于各粒子适应值的递减策略——FDIW 。标准测试函数对比实验表明，该策略可以使粒子在搜索初期获得更好的多样性，从而使粒子具有更强的摆脱局部极值的能力，在搜索末期可以加快粒子收敛速度以提高PSO 算法的性能。 关键词：粒子群优化算法；惯性权值；递减策略；适应值
Influnce of Inertia Weight on Astringency of Particle Swarm
Algorithm and Its Improvement
HUANG Chong-peng, XIONG Wei-li, XU Bao-guo
(School of Communication and Control Engineering, Jiangnan University, Wuxi 214122)
【Abstract 】Inspired by studying the effect of inertia weight in convergence of Particle Swarm Optimization(PSO) and analyzing advantages anddisadvantages of the existing Linear Decreasing Inertia Weight(LDIW), a new modified strategy for inertia weight is proposed based on fitness——FDIW. Comparative experiments of benchmark functions indicate that for most continuous optimization problems, FDIW has more varieties of theswarm at the early stages so that it can escape from local minimum more easily. FDIW can speed up the convergence of particles at the later stages toimprove the performance of PSO.
【Key words】Particle Swarm Optimization(PSO) algorithm; inertia weight; decreasing strategy; fitness
文献[1]提出粒子群算法(Particle Swarm Optimization, PSO) ，具有计算简洁、易于实现、需调整参数少等特点。惯性权值w 的选取影响该算法性能和效率，先后出现了线性递减w (LDIW)[2]、模糊w (FIW)[3]和随机w (RIW)[4]等改进策略。其中，FIW 需要专家知识建立模糊规则，实现难度较大；RIW 用于求解动态系统；而LDIW 相对简单且收敛快，采用最为广泛。本文在LDIW 基础上，从理论和实验两方面分析了w 对PSO 收敛性的影响，提出基于各粒子适应值的w 改进策略。该策略通过区别对待同次迭代中适应值好和适应值差的粒子，以充分发挥其自身优势。实验证明：该策略在加大粒子收敛性的同时，有效地减少早熟现象的发生，并取得了满意的结果。
2 惯性权值对粒子群算法性能的影响分析
2.1 理论分析
为便于分析，笔者将PSO 简化为一维、单个粒子的运动。同时可以令ϕ1=c 1rand (),ϕ2=c 2Rand (),ϕ=ϕ1+ϕ2, = 1-ϕ, ϕp =ϕ1pbest +ϕ2gbest 。为加强针对性，令ϕ, , ϕp 为固定常数，使得w 作为式(1)、式(2)中的唯一变量，利用状态空间将其描述为
Y (t +1) =AY (t ) +B (3) 其中，Y (t ) =⎢
⎡ϕp ⎤⎡w ⎤⎡x (t ) ⎤
; A =⎢; B =⎢⎥。 ⎥⎥⎣v (t ) ⎦⎢ϕp ⎦⎥⎣−ϕw ⎦⎣
矩阵A 的特征方程为
λ2−(w +)
λ+w =0 (4)
1 标准粒子群算法
标准PSO 算法描述为
(t +1) (t ) (t ) (t ) (t ) t
v id =w v id +c 1rand ()(pbest id -x id ) +c 2Rand ()(gbest id -x id ) (1)
矩阵A 的两个特征值为
e 1,2 (t +1) (t ) (t +1)
(2) x id =x id +v id
其中，
∆=(w +2−4w (5)
(t ) (t )
其中，v id 和x id 表示t 时刻微粒i 速度向量和位置向量的第(t ) (t ) d 维分量；pbest id 和gbest id 表示微粒i 和种群历史最优位置
向量的第d 维分量；c 1,2是统计加速度权重，通常取2；rand ()和Rand ()是介于(0,1)间的随机数。
(t ) (t +1)
w 惯性权值决定着v id 对v id 的影响程度。经验认为，w
基金项目：国家“863”计划基金资助项目“基于智能无线传感器网络的温室环境监控系统平台及其关键技术研究”(10Z22006AA10Z
335) ；国家“863”计划基金资助重大项目“车载农田土壤信息快速采集关键技术与产品研发”(10A32006AA10A31)；江苏省自然科学基金资助项目“多肽分离纯化粒子群算法优化的研究”(BK2005012) 作者简介：黄翀鹏(1982－) ，男，博士研究生，主研方向：智能控制与优化；熊伟丽，博士；徐保国，教授、博士生导师 收稿日期：2008-01-02 E-mail ：[email protected]
较大有利于粒子群的全局搜索；w 较小有利于粒子群的局部搜索。本文将从理论角度出发，辅以微观层面对单个粒子在搜索空间运动过程进行分析，来对该经验加以验证，并从中得到启发。
—31—
式(3)的显式表示为
t t ⎧ϕp −[k 1e 1(e 1−w ) +k 2e 2(e 2−w )]
⎪⎪x (t ) =
(6) ϕ⎨
⎪t t ⎪⎩v (t ) =k 1e 1+k 2e 2
其中，t max 为最大允许迭代次数；t 为当前的迭代次数；w start
和w end 是初始惯性权值和进化到最大允许迭代次数的取值。
从e 1,2角度看，该策略在迭代初期，由于w 较大，e 1,2也较大，有利于全局寻优；在迭代末期，由于w 较小，e 1,2也较小，有利于局部寻优。从对Rose 函数寻优看，见图3。
806040
由式(6)知，x (t ) 和v (t ) 的收敛速率完全取决于e 1,2，值越小，收敛越快。显然1,2的大小与w 的取值成正比，w 对收敛性的影响与经验结论相一致。
2.2 实验分析
虽然上述理论分析与经验相一致，但PSO 中
(t ) gbest id
(t ) pbest id
和
y
是不断寻优的变量。同时，正因为ϕ1,2所具有的不确
200-20-40-60
定性才给整个算法带来了多样性和创新。因此，将它们视为常量的理论具有一定局限性。一旦加入如此多的不确定因素，基于理论上的分析必将变得格外复杂，很难用常规手段处理。为能直观了解动态系统中w 对粒子运动轨迹的影响，现对Rose 函数最小寻优。Rose 函数为
f (x ) =100(x 2−x ) 2+(1−x ) 2 (7)
t
图1、图2分别给出了w ＝0.4和w ＝0.9时，粒子在搜索空间的运动过程。可见，当w ＝0.4，所有粒子收敛，且收敛速率较快，但粒子振荡幅值小，一旦搜索维数较大，或遇到具有大量局部最优的多峰函数时，往往易陷入局部最优。当w ＝0.9，少部分粒子收敛，且收敛速率较慢；大量粒子始终处于运动状态，这是由于ϕ1,2随机变化的缘故；同时粒子振荡幅值大，几乎遍及整个搜索空间。因此，以上微观层面的分析，亦与前文的经验结论相一致。
图3 LDIW策略
算法存在两个缺陷：
(1)迭代初期局部搜索能力较弱，即使初始粒子已接近全局最优点，也往往会被错过，而在迭代后期，则因全局搜索能力变弱，而易陷入局部最优。
(2)式(8)的最大迭代次数t max 较难预测，从而影响算法的性能。
3.2 基于各粒子适应值权值改进策略
综上所述，为进一步提高PSO 算法性能，本文提出一种新的w 的改进策略——基于各粒子适应值的权值改进策略(Fitness Decreasing Inertia Weight, FDIW)。
由文献[1]可知，PSO 算法源自鸟群群体运动行为模拟。正如鸟的觅食，每只鸟都作为独立的个体而存在，它们有的距食物较近，放慢速度以确定食物的具体方位；有的距食物较远，因此，提高速度以尽快找出食物的大致方向。同样在PSO 算法的迭代过程中，各粒子间亦存在着这种差异。综合对鸟群的分析，以及“比较优势”可知：当粒子位置较优，w 应取值较小，使该粒子以局部搜索为主；当粒子位置较差，w 应取值较大，使该粒子以全局搜索为主。
FDIW 策略描述为
⎧w =w +(w −w )(1−q ) (9)end start end ⎪⎪
&randsome 1=1||randsome 2=0 (10) ⎨q =t /t max if(f g /f i )
⎪
&randsome 2=1||randsome 1=0 (11)⎪⎩q =f g /f i if(f g /f i ) ≥(t /t max ）
y
0t
图1 w ＝0.4时粒子的运动过程
其中，t max , t , w start 和w end 的定义如前所述；randsome 1,2为随机判断值，取0或1；w 为当前第i 个粒子的惯性权值；q 为第
(t ) (t )
i 个粒子递减斜率；f g , f i 分别对应于gbest id 和pbest id 。式(9)
y
-100
t
图2 w ＝0.9时粒子的运动过程
3 惯性权值取值的改进策略
3.1 线性递减策略
目前，对w 的改进策略使用最为广泛的是：文献[2]提出LDIW 策略，表示为
w =w end +(w start −w end )(1−t /t max ) (8) —32—
反映了迭代过程中种群w 变化的大势，与LDIW 策略类同；
式(10)、式(11)反映了种群中各粒子w 的变化，将其嵌入到 式(9)中，是群体学中个体服从群体的诠释。
在FDIW 策略中w 的大小由粒子适应值和迭代次数共同决定，是对缺陷(2)的克服。在迭代初期，如果某粒子适应值较好，则w 由适应值决定，其值较小，因此，在大部分粒子进行全局寻优时，该粒子可以先行进行局部寻优；同时，本文在大部分粒子w 值参照式(10)、式(11)，随机选取少量粒子，通过令randsome 1＝0或randsome 2＝0，使得它的w 值逆向变化，以加入扰动，使迭代后期仍有不少粒子具有一定的速度，
在相对范围较大的空间进行搜索，是对缺陷(1)进行的策略。
该策略基于多种群、多迭代的PSO 算法。因此，仅对单一维度的Rose 函数寻优，很难反映出其优越性。本文将在下面仿真实验中，通过标准函数的来测试这一策略。
4 仿真实验
本文通过两个经典的函数优化问题来测试FDIW 改进策略对PSO 性能上的改善。测试函数的具体数学描述如下：
Sphere 函数为
f (x ) =∑x i 2 (12)
i =1
n
n
Rosenbrock 函数为
f (x ) =∑[100×(x i +1−x i 2) 2+(x i −1) 2]
i =1
少部分进行全局搜索，因此，其可以在比LPSO 迭代次数少的情况下取得高精度的解。但稍显不足的，在部分函数中FPSO 和LPSO 的最终收敛精度趋同，这一方面可能是由于算法本身在多次迭代后具有一定收敛性，另一方面可能是w start 和w end 的取值并非FPSO 的最佳架构，因为作为FPSO 算法其在迭代过程中均有反向粒子存在，所以在FPSO 中w start ~w end 可取更大范围的值。现取w start ＝1.0和w end ＝0.3。表2、表3是SPSO, LPSO, FPSO 3种算法对于上述基本函数不同种群、不同维数、不同迭代次数的寻优精度及收敛率。从表2、表3中数据可见，当FPSO 中w 具有更大范围时，在迭代次数相同的情况下，往往可以获得更好的取值精度。
表2 Sphere中3种算法的比较
M D Gmax
10 1 00020 1 50030 2 00010 1 00020 1 50030 2 00010 1 00020 1 50030 2 000
寻优 收敛 寻优 收敛 寻优 收敛 精度 率/(%) 精度 率/(%) 精度 率/(%)1e-0884 1e-21 90 1e-2488 1e-0128 1e-10 24 1e-1430
1e-0714 — — — —
1e-10100 1e-25 100 1e-29100 1e-0262 1e-15 52 1e-2258
1e-10 12 1e-1614 — —
1e-12100 1e-29 100 1e-36100 1e-0390 1e-18 78 1e-2776 1e-0116 1e-13 28 1e-2228
(13)
其中，算法的其他参数设置如表1所示。第1代种群采用随
机初始化的方法，各函数直接将函数表达式作为适应度函数，结束条件为最大迭代次数。
表1 函数搜索范围
max 函数 范围 初始边界 达标值
Sphere [-100,100] [50,100] 100 1.00E-01 Rosenbrock [-100,100] [15,30] 100 1.00E+03
20
40
每个基准函数分别设置维度为10, 20, 30；相应的迭代次数为1 000, 1 500, 2 000；相应的粒子数为20, 40, 80。分别运用w ＝0.7时的SPSO 、w start ＝0.9, w end ＝0.4的LPSO 和FPSO 对其进行测试。图4、图5显示了对最后一种情况的对比。
1080
表3 Rosenbrock中3种算法的比较
M D Gmax
20 1 50030 2 00020 1 50030 2 00020 1 50030 2 000
SPSO LPSO FPSO
寻优 收敛 寻优 收敛 寻优 收敛 精度 率/(%) 精度 率/(%) 精度 率/(%)414.7750 53.68 72 36.5680
257.75 60 137.2376 — —
217.4366 42.43 74 25.2384
144.96 60 86.9478 — —
208.2572 32.73 84 17.8990
37.80 80 54.4386 — —
20
100f i t n e s s
40
80
105 结束语
笔者目前在PSO 算法方面做了较多改进[5]。本文研究了惯性权值因子大小对粒子群优化算法(PSO)收敛性所带来的影响，分析线性权值递减策略(LDIW)，提出一种基于各粒子适应值的递减策略——FDIW ，使得PSO 算法在寻优能力和精度要求上都有不同程度的提高。但w start 和w end 取何值时，PSO 算法的性能会最优，及其在全局和局部间达到最佳平衡，还需要大量实验来验证。同时PSO 算法本身缺乏理论依据，具有一定的盲动性和随机性，如何解决这一缺陷也是需要着重研究的问题。
参考文献
[1] Eberhart R C. A New Optimizer Using Particle Swarm Theory[C]//
Proceedings of the 6th International Symposium on Micro and
10t
图4 Sphere中的对比情况
1010810f i t n e s s
104
10210
Human Science. Nagoya, Japan: [s. n.], 1995: 39-43.
t
[2] Eberhart R C. Empirical Study of Particle Swarm Optimizatio[C]//
Proc. of International Conference on Evolutionary Computation. Washington D. C., USA: IEEE Press, 1999: 1945-1950.
[3] Eberhart R C. Fuzzy Adaptive Particle Swarm Optimization[C]//
Proc. of the IEEE Congress on Evolutionary Computation. San Francisco, USA: IEEE Press, 2001: 101-106.
[4] Shi Y. Tracking and Optimizing Dynamic Systems with Particle
Swarms[C]//Proc. of the IEEE Congress on Evolutionary Computation. San Francisco, USA: IEEE Press, 2001: 94-100. [5] 熊伟丽, 徐保国, 周其明. 基于改进粒子群算法的PID 参数优化
方法研究[J]. 计算机工程, 2005, 31(24): 41-43.
图5 Rosenbrock中的对比情况
在运行初始阶段，FPSO 和SPSO 的收敛速度要优于LPSO ，主要是因为在SPSO 中w 较小，而在FPSO 中由适应值决定的较优粒子w 亦较小，所以这两种方案初始时寻优能力要强于LPSO ；同时，SPSO 到达一定代数后趋于稳定，可能是因为搜索前期w 相对较小缺乏一定的全局搜索，而后期w 又相对较大难以收敛的缘故。而FPSO 由于其在迭代初期大部分粒子w 较大仍以全局搜索，且w 基本递减；在后期又对部分粒子加入扰动，使得在整体以局部搜索为主时，仍有
—33—