一种惯性权重自适应的粒子群优化算法

罗 华

(上海理工大学 光电信息与计算机学院，上海 200093)

一种惯性权重自适应的粒子群优化算法

罗 华

(上海理工大学 光电信息与计算机学院，上海 200093)

针对基本粒子群算法的早熟收敛性，在寻优过程中易陷入局部极值。提出一种自适应惯性权重的粒子群优化算法，该算法利用了粒子聚集度、迭代次数来动态的改变惯性权重，以此来平衡局部寻优能力和全局寻优能力，使达到自适应，并使用典型测试函数Griewank和Sphere进行了仿真测试，以此验证改进策略的效果。实验表明，对于多峰函数，与基本粒子群相比较，改进的粒子群优化算法在收敛速度和收敛精度上均高于基本粒子群算法以及一些常见的改进算法。

粒子群优化；自适应；惯性权重；聚集度

粒子群算法的思想源于对鸟类觅食运动行为的模拟，对鸟群简化社会模型的研究。1987年，Reynolds 根据鸟类群体飞行的特点，提出用于模拟鸟类聚集飞行的行为，Reynolds提出了3个规则来作为鸟群个体的简单行为：(1)避免碰撞。避免和临近的个体相碰撞；(2)速度一致。尽量和临近个体在速度上保持协调一致；(3)向中心聚集。尽量试图向自己所认为的群体中心靠近。1995年，Eberhart和Kennedy受到Biod模型的启发，对模型进行深入研究，提出了粒子群优化算法[1]，粒子群算法是典型的智能优化算法，自从提出以来，易实现和可调参数较少等优点吸引了大批学者进行研究，已经逐渐应用到很多行业当中，但是粒子群算法本身也存在容易陷入局部极值、进化后期的收敛速度慢、精度低、易早熟收敛等缺点，目前主要集中在算法的改进和算法研究上[1-6]，所以出现了诸多改进的粒子群算法，有线性递减惯性权重策略(LDIW)[7]、非线性惯性权重策略(NLIW)[8]、模糊惯性权重策略(FIW)[9]、随机惯性权重策略(RIW)[10]等，不同策略在实现起来都在一定程度上使粒子群收敛速度加快，但还是避免不了陷入局部极值中。

本文在非线性惯性权重策略基础下，基于基本粒子群算法引入了惯性权重自适应、聚集距离、迭代次数相结合的概念。并且通过经典测试函数仿真验证，在迭代过程中动态改变惯性权重，使其能够摆脱局部极值的干扰，在加快了算法收敛的速度的同时，跟其他优化算法比起来还保持了精度。

1 基本粒子群算法和惯性权重的分析

Eberhart和Kennedy提出基本的粒子群算法如下v(t+1)v(t)+c1r1(pbestij-xij)+c2r2(gbestij-xij)

(1)

xij(t+1)=xij(t)+vij(t+1)

(2)

Shi等人在Eberhart和Kennedy提出的粒子群算法的基础上在速度项中增加了惯性权重系数来平衡全局搜索和局部搜索能力，修改后的新的粒子群算法如[6]

v(t+1)=ωv(t)+c1r1(pbestij(t)-xij(t))+

c2r2(gbestij-x(t))

(3)

位置更新公式如下

xij(t+1)=xij(t)+vij(t+1)

(4)式中，ω是惯性权重，惯性权重是最重要的进化参数，其决定了粒子先前飞行速度对当前飞行速度的影响程度，当惯性权重较大时，整体的全局搜索能力加强，局部搜索能力减弱；当惯性权重较小时，整体的局部搜索能力加强。因此可通过调整惯性权重的值来实现粒子全局搜索和局部搜索，恰当的调整惯性权重可以调高算法性能，提高寻优能力，同时还能减少迭代次数[11]。vij(t+1)代表当前迭代的速度，pbestij(t)和gbestij(t)分别代表个体当前找到的最有位置和整体粒子目前找到的最优位置；c1、c2是非负的学习因子；r1、r2是[0，1]区间的随机数。因此，如何寻找合适的惯性权重值，使之在搜索精度和搜索速度方面起到恰当的协调作用，成为业界学者的一个焦点，主要分为线性策略和非线性策略两种[12]。

已有线性调整和非线性惯性权重策略。即随进化过程，线性的减少ω的值。这样可使算法在进化初期探索能力较强，能在较大范围的解空间内搜索，并不断搜索新的区域，然后到后期逐渐收敛到较好的区域并进行更精细地搜索，以加快收敛速度[13]

ω=(ω1-ω2)×(T-t)/T+ω2

(5)

其中，ω1和ω2分别是惯性权重的初始值和终端值；T和t分别是当前进化代数和最大进化代数。Shi等人的研究表明，当ω从0.9线性减小到0.4时粒子群算法可以获得满意的优化结果[14]。

为了改善递减策略中存在的缺陷，提出了先增后减的策略[15]

(6)

经过实验分析，像这样的先增后减的策略，前期有较快的收敛性，后期的局部搜索能力也不错。

2 本文提出的惯性权重调整策略

本文提出的调整策略利用到了已有的平均聚集距离和最大聚集距离[8]

(8)

(9)

其中，Mean代表平均聚集距离；Max代表最大聚集距离；m代表粒子群的粒子个数；D代表每个粒子的维数；pid代表粒子群目前搜索到的最优位置；xid代表每个粒子目前搜索到的最优位置。

在整个粒子群寻优过程中迭代次数也在影响着最后寻优的结果，所以本文在改进的时候就利用了迭代次数对寻优过程的影响，将迭代的影响与聚集度结合起来，来实现惯性权重的动态调整。由于传统的非线性策略要么只是考虑到迭代对算法的影响，要么就利用迭代次数再给定一个控制因子来动态的调整惯性权重，这样虽然能优化算法，但没有真正的智能化，利用聚集距离来及时的判断与全局最优的距离，如果最大聚集距离Mean过大，说明整个粒子群是分散的，就需要增大ω，增强粒子群的全局搜索能力，相反，若Mean在减小，说明粒子群整体在收敛，这时就要减小ω，增强它的局部搜索能力。在此，提出一个定理

(10)

(11)

步骤 1 随机初始化每个粒子的位置和速度;

步骤 2 先计算每个粒子的适应值，然后初始化个体极值和全局极值;

步骤 3 根据式(8)，式(9)计算平均聚集距离和最大聚集距离，根据式(10)计算出聚集距离变化率，再根据式(11)计算惯性权重ω;

步骤 4 根据式(3)，式(4)来更新粒子的速度与位置，迭代次数加1;

步骤 5 若未满足循环结束的条件，则继续步骤2，若满足，则退出循环，并输出全局最优值。

3 实验与分析

为了验证改进的可行性，使用了两个最典型的测试函数进行实例计算并且与基本粒子群算法作比较，来证明改进的效果。在实验中，取粒子数m=30，学习因子c1=c2=1.496 2，D=50，改进的粒子群算法和基本粒子群算法参数一样，分别迭代500次，测试函数如下。

表1 实验所用测试函数和相关参数

(1)Griewank函数

(12)

Griewank 函数仿真结果如下。

与基本粒子群相比，改进的粒子群算法收敛速度更快了，在迭代约为10次时便可达到收敛，找到最优解，算法寻优效果大幅加强。

图2 改进的粒子群算法寻优过程

(2)Sphere函数

(13)

图3 基本粒子群算法寻优过程

图4 改进的粒子群算法寻优过程

图3与图4是有Sphere函数仿真测试而得，两图相比较可以看出，改进的粒子群算法与基本粒子群收敛精度在后期基本一致，但收敛的速度远高于基本粒子群算法的收敛速度，改进粒子群算法在迭代约为3次便已寻找到最优值0，而基本粒子群在将近30次在寻找到。

4 结束语

从仿真结果来看，改进的粒子群算法不论在收敛速度还是精度上均远高于基本粒子群算法，所以可证明本文所提出的利用聚集距离的变化和迭代次数对寻优的影响来实现改进粒子群算法的方法是可行的。将惯性权重用非线性的方式表示同时利用聚集距离的变化，通过自适应的调整，来使整个粒子群寻优时可不断的修正目标值，防止陷入局部收敛，使整个群体更具有了目的性。同时本文提出的改进算法在精度上比起基本粒子群算法也有所提升，实验证明改进的算法在高纬时寻优效果也比较稳定，优化效果明显。

[1] Kennedy J,Eberhart R.Particle swarm optimization[C].IEEE lnt Conf on Neural Networks.Piscataway:IEEE Service Center，1995:1942-1948.

[2] 李丽,牛奔.粒子群优化算法[M].北京:冶金工业出版社,2009.

[3] 潘峰,李位星,高琪,等.粒子群优化算法与多目标优化[M].北京:北京理工大学出版社,2013.

[4] Salomon R.Reevaluating genetic algorithm performance under coordinate ro- tation of benchmark functions[J].Bio Systems,1996(39):263-278.

[5] Frans V D B. An analysis of particle swarm optimizers[J]. Particle Swarm Optimization,2002(5)：442-447.

[6] By Y, Eberhart R. Parameter selection in particle swarm optimization[C].Proceedings of the 7th Annual Conference on Evolutionary Programming,2010.

[7] 任子晖,王坚.一种动态改变惯性权重的自适应粒子群算法[J].计算机科学,2009,36(2):227-229.

[8] 李宁,孙德宝,岑翼刚.带变异算子的粒子群优化算法[J].计算机工程与应用,2004,40(17):12-14.

[9] 徐志烽.一种多粒子群的协同优化算法[J].现代电子技术,2007,30(1):131-133.

[10] 陈红州,顾国昌,康望星.一种具有感觉的微粒群算法[J].计算机研究与发展,2005,42(8):1299-1305.

[11] 窦全胜,周春光,徐中宇,等.动态优化环境下的群核进化粒子群优化方法[J].计算机研究与发展,2006,43(1):89-95.

[12] 姚耀中,徐玉如.粒子群优化算法分析[J].哈尔滨工程大学学报,2007,28(11):1242-1246.

[13] 邢万波,杨圣奇,王树平,等.一种改进的自适应邻域粒子群优化算法[J].计算机应用,2008,28(12):3055-3057,3088.

[14] Mendes R,Kenedy J.The full informed particle swarm: simpler maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[15] Bask S,Suganthan P N.A novel concurrent particle swarm optimization[C].Piscataway,NJ:Proceedings of the Congress on Evolutionary Computation,IEEE Press,2004.

A Inertia Weight Adaptive Particle Swarm Optimization Algorithm

LUO Hua

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093, China)

Mainly for the basic particle swarm algorithm of premature convergence, Easy to fall into local minima in the optimization process. In this paper, a particle swarm optimization algorithm of adaptive inertia weight, The algorithm use the particle concentration, The number of iterations to dynamically changing inertia weight, In order to balance the local optimization and global optimization ability, Make to achieve adaptive, And use the typical test functions Griewank and Sphere has carried on the simulation test, To verify the improvement strategy. simulation results show, For multimodal function, Compared with the basic particle swarm, The improved particle swarm optimization algorithm in convergence speed and higher than the basic particle swarm algorithm convergence precision and some of the common algorithm.

particle swarm optimization; adaptive; inertia weight; degree of aggregation

2016- 04- 16

罗华(1992-)，男，硕士研究生。研究方向：群智能等。

10.16180/j.cnki.issn1007-7820.2017.03.009

TP301.6

A

1007-7820(2017)03-030-04