粒子群算法中惯性权重研究及实验分析

摘要：惯性权重是粒子群算法的一项重要参数，其值变化形式直接影响粒子群算法的性能。在介绍粒子群基本算法的基础上，分析已有固定惯性权重、时变惯性权重和动态自适应惯性权重粒子群算法的基本原理。通过4个典型测试函数的仿真实验，证明不同算法的收敛速度和全局寻优能力。

关键词关键词：粒子群算法；惯性权重；优化算法

中图分类号：TP312文献标识码：A文章编号文章编号：16727800（2013）0010005704

作者简介：徐宏英（1980-），女，重庆电子工程职业学院计算机学院讲师，研究方向为计算智能、嵌入式技术。

式（1）为粒子速度迭代公式，由3部分组成，第1部分为粒子的先前速度，第2部分为“认知（cognition）”部分，表示粒子本身的思考，第3部分为“社会（social）” 部分，表示粒子之间的信息共享与相互合作。其中c1和c2是加速常数，分别调节粒子飞向自身最好位置方向和全局最好位置方向的步长，通常取值2。r1和r2是均匀分布于[0，1]之间的随机数。式（2）为粒子的位置迭代公式，粒子当前位置与前一次位置和当前粒子速度相关。式（3）为粒子最大速度和最小速度限制，防止粒子远离搜索空间。

1.2算法流程

标准PSO算法流程如下： Step1：设置种群规模m，搜索空间的维数D，随机产生m个粒子的初始位置和速度，计算个体极值pi和群体全局极值pg；Step2：根据方程（1）和（2），更新每个粒子的速度和位置，并根据方程（3）将粒子的速度限制在一定的范围内； Step3：计算每个粒子的适应度值； Step4：将当前计算的粒子适应度值与粒子个体极值pi比较，如优于粒子个体极值，则设置当前粒子的适应值为粒子个体极值pi，用当前位置更新个体历史最好位置； Step5：将当前计算的粒子适应度值与群体全局极值pg比较，如优于全体全局极值，则设置当前粒子的适应值为群体全局极值pg；Step6：如果达到最大迭代次数或者最小准则，终止程序；否则，返回步骤2。

1.3测试函数

本文实验中采用的4个非线性标准测试函数如下：

（1）f1（x）：Sphere函数。

f1（x）=∑ni=1x2i-100≤xi≤100（4）

Sphere函数为非线性的对称单峰函数，函数比较简单，主要用于测试算法的寻优精度，其全局最小值f（x）=0；x（i）=0，i=1，2…，n。

（2）f2（x）：Rosenbrock函数。

f2（x）=∑n-1i=1（100（x2i-xi+1）2+（xi-1）2）-2.048≤xi≤2.048（5）

Rosenbrock函数为非凸、病态单峰函数，用来评价优化函数的执行能力，其全局最小值f（x）=0；x（i）=1，i=1，2，…，n。

（3）f3（x）：Rastrigin函数。

f3（x）=10·n+∑ni=1（x2i-10cos（2πxi））-5.12≤xi≤5.12（6）

Rastrigin函数复杂多峰函数，容易陷入局部最优。其全局最小值f（x）=0；x（i）=0，i=1，2…，n。

（4）f4（x）：Griewank函数。

f4（x）=14000∑ni=1x2i-∏ni=1cos（xii）+1-600≤xi≤600（7）

Griewank函数为不可分离的、可变维数的多峰函数。随着维数增加，寻找全局最优变得相对容易，其全局最小值f（x）=0；x（i）=0，i=1，2…，n。

2惯性权重调整方法及实验分析

2.1固定惯性权重

文献[2]引入惯性权重概念，并对Schaffer’s f6 函数进行测试。结果表明，当惯性权重取值区间在[0.9，1.2]之间，粒子群算法在合理的迭代次数里，寻找函数全局最优值能力较好，特别是当w=0.9时，粒子群算法寻找最优值所需的平均迭代次数最小。文献[3]提出了PSO压缩因子模型，其速度更新公式为：

vid（t+1）=K{vid（t）+c1r1（pid（t）-xid（t））+c2r2（pgd（t）-xid（t））}（8）

其中： K=22-C-C2-4C，φ=c1+c2Clerc从数学上证明了采用该迭代公式可以获得比基本PSO算法更好的收敛性。 Eberhart在文献[4]里对惯性权重的PSO算法和收缩因子的PSO算法进行了实验对比，当压缩因子PSO算法中K=0.729，φ=4.1，Vmax=Xmax时，算法收敛效果要好于线性递减的惯性权重的PSO算法，在形式上等效于基本PSO算法中w=0.729，c1=c2=1.494 45。

2.2时变惯性权重Shi在文献[5]中提出线性递减惯性权重粒子群算法（LDIW），即惯性权重随着迭代次数的增加，其值从0.9线性递减到0.4，这样粒子群算法在早期具有更好的全局搜索能力，后期具有更好的局部搜索能力。其惯性权重w按照下式变化：

w（k）=wini-（wini-wend）Kmax×k（9）

文献[6]认为很小的惯性权重就能保证粒子群算法的全局搜索和局部搜索，大的惯性权重可以使算法更趋于稳定。作者借鉴模拟退火算法思想：在搜索过程中不仅接受好的解，也在一定程度上接受差的邻近解，这种方法可以使算法跳出局部最优点。文中提出一种线性递增惯性权重粒子群算法（LIIW），其惯性权重w按照下式变化：

w（k）=wend+（wini-wend）Kmax×k（10）

文献[7]根据递减惯性权重和递增惯性权重粒子群算法的特点，提出一种具有先增后减惯性权重的粒子群算法（BLIW），其惯性权重w按照下式变化：

w（k）=2·（wini-wend）Kmax×k+wend，0≤k/Kmax≤0.5w（k）=-2·（wini-wend）Kmax×k+（2wini-wend），0.5

文献[8]提出一种非线性递减惯性权重粒子群算法（NLDIW）。惯性权重是关于迭代次数的函数，当n为1时，即Shi提出的线性递减惯性权重策略，其惯性权重w按照下式变化：

w（k）=wend+（（Kmax-k）Kmax）n×（wini-wend）（12）

文献[9]和[10]指出线性递减惯性权重策略中全局搜索和局部搜索的比例没有变化，对于复杂高维函数，全局搜索和精细局部搜索时间不够，因此提出惯性权重指数递减（IDIW）和余弦递减（CDIW）的粒子群算法，增加迭代初期的全局搜索时间和迭代后期的局部搜索时间，其惯性权重w按照下式变化：

w（k）=wend+（wini-wend）·exp（-m·（kKmax）n）（13）

w（k）=wend+（wini-wend）·（1+cos（（k-1）π/（Kmax-1））2）（14）

上述6种粒子群算法中的惯性权重只随着迭代次数线性、非线性变化，算法简单、容易实现。下面通过4个典型函数的测试，分析比较这6种时变惯性权重粒子群算法的性能。实验参数设置如下：粒子规模为200，粒子维数30维，最大迭代次数500，加速常数c1=c2=2.05，最大惯性权重wini=0.9，最小惯性权重wend=0.4，vmax=xmax，算法在相同情况下运行20次。非线性递减惯性权重粒子群算法（NLDIW）中指数n=1.2，指数递减惯性权重粒子群算法（IDIW）中m=20，n=6。采用两种方案进行实验：一是计算500次迭代下的每种算法运行结果的平均适应值；二是确定每个函数的优化目标值，设定函数f2的优化目标值为0.001，函数f1、f4的优化目标值为0.01，f3的优化目标值为100，计算平均迭代数。取20次实验中各个函数适应值的最优值、最差值、平均值以及达优率和平均迭代次数作为评价各算法性能的标准。实验结果如表1-表4所示，上述6种简单的线性、非线性时变惯性权重粒子群算法，在特定的参数设置下，线性递减（LDIW）、非线性递减（NLDIW）、指数递减（IDIW）和正弦递减（CDIW）这4种惯性权重粒子群算法寻优能力强，20次运算粒子最优适应平均值较低，并具有较高的达优率。而线性递增（LIIW）和先增后减（BLIW）这两种算法的寻优效果差。

表1Sphere函数实验结果

算法算法性能评价标准最优值迭代次数 最差值平均值达优率平均

LDIW4.127 0e-112.429 0e-62.274 6e-70.95 357.02

LIIW0.684 85.614 22.775 80无穷大

BLIW1.0e+46.0e+43.7e+40无穷大

NLDIW5.7185e-7 1.6e-32.932 1e-41181，40

IDIW8.323 0e-85.250 1e-45.741 3e-51231.10

CDIW5.682 9e-7 2.782 6e-46.834 6e-51205.45

表2Rosenbrock函数实验结果

算法算法性能评价标准最优值迭代次数 最差值平均值达优率平均

LDIW5.218e-104.194 3 0.209 70.9548.550

LIIW3.937 8e-4 0.003 2 0.001 50.3079

BLIW4.194 325.165 813.841 2 0 无穷大

NLDIW7.054 6e-115.272 9e-71.064 4e-7 1 25.35

IDIW2.136e-12 1.777 9e-71.371 9e-8 1 27.60

CDIW7.85 3e-14 1.305 6e-72.231 7e-8 1 29.45

表3Rastrigin函数实验结果

算法算法性能评价标准最优值迭代次数 最差值平均值达优率平均

LDIW0.003 3 202.514 80.711 0.7032.21

LIIW0.214 9 29.124 2 6.679 9 1 2

BLIW144.62 376.021 293.6140 无穷大

NLDIW1.196 2e-5215.226 91.756 20.6046.66

IDIW3.119 2e-7169.497 75.119 50.6556.38

CDIW0.002 8 260.032 104.5550.5061.2

表4Griewank函数实验结果

算法算法性能评价标准最优值迭代次数 最差值平均值达优率平均

LDIW1.879e-100.291 80.059 00.55 162.36

LIIW0.713 6 1.079 20.962 40无穷大

BLIW90.301 540.65297.760无穷大

NLDIW2.492e-6 0.117 80.019 30.75 178.26

IDIW6.137e-8 0.108 50.009 70.90 244.72

CDIW2.559e-1190.6764.542 20.80 188.31

2.3动态自适应惯性权重

上述惯性权重策略简单且收敛速度快，被广泛使用。但这些方法存在算法早熟收敛问题，后期粒子多样性变差，收敛速度变慢，算法极易陷入局部最优。惯性权重只是按迭代改进，不同粒子在同代惯性权重值相同，忽略了迭代过程中粒子适应度、粒子规模和搜索空间与惯性权重的关系。因此人们在上述惯性权重策略的基础上，充分考虑粒子之间的进化差异，自适应动态地根据不同粒子的搜索状态赋予不同的惯性权重。现有的动态自适应惯性权重策略概括为4种：（1）基于目标函数。这种方法的基本思路为：计算粒子在每次迭代时对应的函数值和最优粒子对应的函数值，定义关于目标函数值变化、描述算法收敛性的功能函数，惯性权重根据收敛性函数自适应动态变化。文献[11]提出一种惯性权重值随着粒子的位置和目标函数的性质而变化的动态改变惯性权重的粒子群算法（MPSO），其惯性权重w按照下式变化：

wn=e-an/an-1an=1m∑mi=1f（Xni）-f（Xnmin）n=0，1，2，…f（Xni）=f（xni，1，xni，2，…，xni，D）f（Xnmin）=mini=1，2，，，mf（Xni）（15）

（2）基于聚焦距离变化。这种方法首先计算所有粒子到历史最佳位置的欧几里得空间距离（平均聚焦距离和最大聚焦距离），并定义聚焦距离变化率k，将惯性权重表示为聚焦距离变化率的函数[12]，其惯性权重w按照下式变化：

MeanDist=（∑mi=1∑Dd=1（ptd-xid）2mMaxDist=maxi=1，2，...m（∑Dd=1（ptd-xid）2）k=MaxDist-MeanDistMaxDistw=（a1+r/2.0）lnk，k>1a1a2+r/2.0，0.05≤k≤1（a2+r/2.0）1lnk，k

（3）粒子进化度和聚合度。粒子进化度定义为当前全局最优值与前一次全局最优值的比值，其值越大，表明粒子进化速度越快，当粒子进化度为1时，表明算法停滞或找到最优值。粒子聚合度定义为当前全局最优值与当前粒子适应值总和的比值，其值越大，表明粒子分布越分散，当聚合度为1时，表明粒子聚合到全局最优点。文献[1314]提出惯性权重应随着粒子群进化度和聚合度变化而变化，惯性权重w按照下式变化：

e=Pgbest（T）Pgbest（T-1）a=PsizePgbest（T）∑Psizei=1Pibest（T）w=f（e，a）=w0-0.5e+0.1a （17）

（4）基于粒子维信息。这种方法充分考虑粒子之间的进化差异，对不同粒子赋予不同的惯性权重。文献[1516]提出基于不同粒子不同维的动态自适应惯性权重粒子群算法（AWPSO），其惯性权重w按照下式变化：

ij = （C1 *R1 *（pbestij -xkij） + C2 *R2 *（gbestij -xkij））/vkijwkij = （wmax -（（wmax -wmin /itmax ）*k）*（1/（1 + e-kk*zij ））（18）

测试函数同上，粒子群算法其它参数分别设置为：粒子数200，维数10、30、50，迭代数500、1000、1500，适应度函数最优值作为算法评价标准。算法运行结果如表5所示。

表5不同动态自适应惯性权重粒子群算法运行结果

函数粒子数维数迭代数MPSODCWPSO1DCWPSO2AWPSO

10500 3.623e-31 5.392 4e-87.673e-423.753e-69

f1（x）200301 0002.050e-41.3412 2.6957 1.000e+4

501 5001.435e-15 57.384 7158.57 2.000e+4

10500 1.977e-24 1.066e-6 2.827e-133.695 4

f2（x）200301 0005.881e-428.667 0.008 8 1.012e+4

501 50048.5167 639.19 2.880 3e+51.977e+10

10500 8.968 20.1397 0.995 0 1.776e-15

f3（x）200301 00028.90197.112 256.04 26.866

501 50048.835623.38 763.40 3.009e+4

10500 6.217e-15 6.041e-6 1.110e-160.022 1

f4（x）200301 0000.02610.007 1 0.481 3 5.994 9

501 5000.008 20.798 9 0.0354 3.499 1

从表5结果可知，4种不同的自适应动态惯性权重粒子群算法，在不同维数和不同迭代数条件下，其寻优效果不同。f1（x）和f2（x）测试函数为单峰函数，粒子维数越小，四种算法寻优能力越强，随着粒子维数的增加，4种算法中基于粒子维信息的算法寻优能力越差，而基于目标函数的粒子群算法寻优能力最好。对于复杂多峰函数f3（x）和f4（x）四种算法寻优能力相差不大。

3结语

惯性权重是粒子群算法的一个重要参数，可以控制算法的开发和探索能力。目前，关于粒子群惯性权重的研究文章种类繁多，大多数都是在特定的参数设置下，新算法与线性递减粒子群算法的性能比较。本文对粒子群算法惯性权重研究进行分类，并将现有算法在相同的参数设置下，进行仿真实验并对比分析各算法的性能。从实验结果来看，惯性权重是影响粒子群算法的重要因素，但与粒子数目、粒子维数、迭代次数等其它因素也密切相关，粒子群算法本身具有很大的随机性，如何正确选取这些参数缺乏理论指导，这是以后继续研究的方向。

参考文献参考文献：

[1]KENNEDY J，EBERHART R C.Particle swarm optimization[C].Perth：IEEE International Conference on Neural Networks，19421948.[2]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]. Proc the IEEE Int’1 Conf on Evolutionary Computation，1998：6973.[3]CLERC，M.The swarm and the queen： towards a deterministic and adaptive particle swarm optimization[C].Porc. 1999 ICEC，1999.[4]EBERHART R，SHI paring inertia weights and constriction factors in particle swarm optimization[C].IEEE Congress on Evolutionary Computation，2000.[5]SHI Y，EBERHART R C.Empirical study of particle swarm optimization[C]. Proc of Congress on Computational Intelligence，1999.[6]ZHENG YONGLING，MA LONGHUA，ZHANG LIYAN，et al.on the convergence analysis and parameter selection in particle swarm Optimization[C].Proceedings of the Second International Conference on Machine Learning and Cybernetics，2003.[7]崔红梅，朱庆保.微粒群算法的参数选择及收敛性分析[J].计算机工程与应用，2007，43（23）：8991.[8]CHATTERJEE A，SIARRY P.Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J].Computers and Operations Research，2006， 33（3）：859871.[9]刘伟，周育人.一种改进惯性权重的PSO算法[J].计算机工程与应用，2009，45（7）：4648.[10]陈国初，俞金寿.增强型微粒群优化算法及其在软测量中的应用[J]. 控制与决策，2005，20（4）：377381.[11]王启付，王战江，王书亭.一种动态改变惯性权重的粒子群优化算法[J].中国机械工程，2005，16（11）：945948.[12]任子晖，王坚.一种动态改变惯性权重的自适应粒子群算法[J].计算机科学，2009，36（2）：227229.[13]朱小六，熊伟丽，徐保国.基于动态惯性因子的PSO算法的研究[J].计算机仿真，2007，24（5）： 154157.[14]黄泽霞，俞攸红，黄德才.惯性权自适应调整的量子粒子群优化算法[J].上海交通大学学报，2012，46（2）：228232.[15]李军民，王洪涛.一种改进惯性权重策略的粒子群优化算法[J].西安科技大学学报，2010，30（5）： 604608.[16]王洪涛，任燕.基于改进惯性权重的粒子群优化算法[J].计算机应用与软件，2011，28（10）：271：274.