改进的粒子群优化算法

闫文静, 邹书蓉, 张洪伟

（成都信息工程学院计算机学院,四川成都 610225）

0 引言

粒子群优化算法（Particle Swarm Optimization,PSO）是由Kennedy和Eberhart（1995年）首次提出的一种基于迭代的寻优算法[1],源于对生物界中鸟群觅食行为的研究,是一个基于群体智能（Swarm Intelligence,SI）的优化算法。PSO算法具有简洁性,易于实现,收敛速度快,需要调节的参数少等优点,一经提出便得到快速的发展。PSO算法已经在函数优化、神经网络训练、模式分类、模糊系统控制、求解大规模组合优化问题等各个领域的取得了大量的有效成果[2]。

在对PSO算法的研究过程中发现其存在易于陷入局部最优及早熟收敛等缺陷,针对这些问题许多学者提出了一些改进方案,例如w线性递减策略[3],通过反复试验,建议w=0.9线性递减到0.4的策略,这样使得粒子群算法早期具有良好的全局搜索能力,能快速定位到接近全局最优点的区域,后期则具有良好的局部搜索能力,能精确得到全局最优解。杂交PSO模型[4]将进化算法中的交叉操作引入PSO算法,使后代继承了双亲粒子的优点,加强了粒子间区域的搜索能力,有效摆脱局部最优。混沌粒子群优化模型[5],以目前整个粒子群所搜索到的最优位置为基础,利用混沌运动的遍历性去产生一个混沌序列,然后将产生序列中的最优位置的粒子随机地代替目前粒子群中的一个粒子,这样可以使粒子能有效地摆脱局部极值点,提高算法寻找全局最优点的能力。免疫粒子群优化算法[6]中机体能特异的识别“非己”和“自己”的刺激,保留记忆反应的能力,可以避免粒子群算法陷入局部最优的缺点。

针对PSO算法易于陷入局部最优的缺陷,提出了一种在引入自适应惯性权重基础上的新的进化模型的粒子群优化算法（New mode Particle Swarm Optimization,NPSO）。通过仿真实验与其他改进算法的比较表明,提出的新算法具有很好的收敛精度,能有效避免陷入局部最优及早熟收敛现象。

1 粒子群算法的基本原理

粒子群优化算法的基本概念源于鸟群捕食的过程,在PSO算法中,每个优化问题的解都看作是搜索空间中一个粒子,所有的粒子都有一个由被优化的函数决定的适应度值。PSO算法先初始化一群随机粒子,每个粒子的属性由速度vi（vi=（v1,v2,…,vD））,位置 xi（xi=（x1,x2,…,xD））来描述。在下一个时间点到来的时候,所有的粒子都是通过跟踪两个“极值”来更新其速度,这两个极值分别为个体局部极值（pbest）即粒子自身找到的最优解;全局极值（gbest）即整个群体找到的最优解。再通过优化问题所决定的适应度函数去评价新的粒子的优劣程度。粒子更新速度和位置公式如下:

2 粒子群算法的改进

2.1 PSO算法局部收敛性判断

全局最优值取决于个体最优值的变化,在迭代过程中,当前迭代的全局最优值总是要优于或至少等于上一次迭代所得的全局最优值。PSO算法在迭代过程中,粒子都是通过跟踪两个极值更新自己。即在找到这两个最优值后,粒子按照式（1）和（2）确定自己下一时刻的速度和位置。常规的粒子群算法中粒子都是向着一个方向在飞行,假如在飞行过程中遇到了局部极值点,全体粒子的速度将快速的下降为零从而聚集在局部最优停止飞行,这样粒子就陷入了局部极值点。为此改进PSO算法时,引入进化速度因子h,如果优化目标是寻极大值,F（gbestk）≥F（gbestk-1）,则定义h=F（gbestk-1）/F（gbestk）;反之,F（gbestk）≤F（gbestk-1）,则定义进化速度因子h=F（gbestk）/F（gbestk-1）;于是

根据上面的定义,进化速度因子0＜h≤1。在整个迭代过程中进化速度因子h的值与进化速度成反比,即h值越小,进化速度越快。一定迭代次数后,若h=1,代表算法找到了最优解或者停滞陷入了局部最优。此时将得到的最优解gbest与理论全局最优解（或期望最优解）做比较,可以判断出此时得到的最优解是否为陷入局部最优的解。大量的实验数据表明,h大于Δ（如0.2～0.5）时判断粒子陷入局部最优的可能性最大,在此应设法使粒子跳出局部最优的位置,使粒子能在搜索空间里继续搜索寻优。

2.2 粒子的聚集度

根据上面的定义粒子聚集度因子0＜s≤1,s值能有效反映当前所有粒子的聚集程度,同时也可反映出粒子的多样性。大量实验数据表明s的值与粒子的聚集程度成正比,即s值越大,粒子群的聚集度越大,这样表明粒子多样性越小。若s的值为1,则断定粒子群中的所有粒子具有同一性,如果验证此时的粒子为陷入局部最优,粒子将很难跳出该极值点。

2.3 自适应的惯性权值

惯性权重w是PSO算法中的一个重要参数,被用于调节粒子过去对现在的影响程度。Shi和Eberhart研究惯性权重w对优化性能的影响发现:较大的惯性权重能增强全局探索能力,较小的惯性权重能提高局部发掘能力有利于算法收敛。为此进行了大量的研究工作,先后提出了随机惯性权值（RIW）策略[7]、线性递减权值（LDW）策略[8]和模糊惯性权值（FIW）策略[9]。目前比较流行的做法是线性递减策略LDW,公式如下所示:

上式中,ws和we表示惯性因子的初始值和结束值,t表示当前次数,tmax表示迭代的最大次数。在优化方程性能上有明显效果,但是LDW中的w只与迭代的次数线性相关,因此不能适应算法运行中的非线性变化、复杂等特性。

研究w发现,惯性权重的值应该伴随着粒子群进化速度和粒子的聚集程度而变化[10],所以w可以表示为h和s的函数,即 w=f（h,s）。分析可知如果粒子群的进化速度降低时,此时减小 w的值,使算法在小空间范围内进行搜索,这样能较快地找到算法的最优解。如果粒子群的进化速度加快时,加大 w的值,使得粒子群在较大的空间内持续搜索寻优。若粒子在搜索空间里分布的比较分散,此时粒子群就不易陷入到局部最优,但是伴随着粒子群聚集度的逐渐升高,粒子将很容易陷入到局部最优,此时为提高粒子群的全局寻优能力应及时地加大粒子群搜索的空间。根据上面的分析可知,w值大小应该伴随着粒子的聚集度的加快而增大,相应的,也应伴随着粒子群进化速度的减慢而减小,w可以表示为:

wini为w 的初始值,通常 wini的值为1。由于0＜h≤1,0＜s≤1,wini-wh＜w ＜wini+ws。

2.4 改进的粒子群进化模型

为了使PSO算法避免“早熟”收敛现象[11],提出将陷入局部最优的粒子向群体最优的反方向飞行,这样便于粒子跳出局部最优并在解空间大范围飞行寻优。其速度迭代公式不变,位置迭代进化更新公式如下所示:

式（7）即是改变粒子寻优的飞行方向[12],使粒子能在大范围开拓搜索空间中寻优。提出的改进的粒子群优化算法的流程如下,粒子群迭代先是按照标准模型即式（1）、（2）进化,判断h值的大小,若发现粒子陷入局部收敛时,立即使用式（1）、（7）迭代进化,使粒子能及时跳出局部最优,在解空间里大范围搜索寻优。这样处理可以有效地防止“早熟”收敛,提高算法的全局收敛性能。

3 算法流程

综上所述,新算法流程如下:

（1）初始化。设定PSO算法的参数（N,c1,c2,ws和we等）,随机产生初始种群及每个粒子的速度和位置,计算每个粒子的适应值并排序。并初始化种群的全局最优值和个体最优值,并将粒子的pbest设置为当前位置,gbest设置为初始群体中最佳粒子的位置。

（2）根据式（1）、（2）更新每个粒子的速度和位置。

（3）重新计算粒子的适应度,按适应值排序,按照式（3）、（4）、（6）计算新的 h、s和w 。

（4）根据式（3）判断进化速度因子h值的大小,若大于Δ时,转向（4）,否则转向（5）

（5）按式（1）、（7）更新每个粒子的速度和位置。

（6）若算法未达到最大允许迭代次数,迭代次数I=I+1返回（2）,否则转到（6）。

（7）停止优化并输出结果。

4 算法仿真实验

表1给出了实验中运用4个经典测试函数,用这4个函数来仿真测试验证文中所提出算法的寻优能力,并将结果与标准PSO 、LDWPSO算法、NPSO算法进行对比分析。

表1 测试函数

f 1至 f4函数的最优值都是0,测试时4种算法的种群粒子数各取50,LDWPSO中惯性权重ws=0.8,we=0.1,c1=c2=2,h=0,s=0。测试函数维数为30,最大迭代次数500,测试3种算法所达到的精度。所有仿真实验都是通过Java语音编程,并对仿真结果作对比。对3种算法分别进行50次实验,表2给出了测试4个经典函数所达到精度的平均值。

表2 4个经典函数的测试结果

从表2可以看出,新算法相对于其他两个算法在平均最佳适应值上有明显提高,这说明新算法的优化能力得到了明显的提高。为了反映新算法性能的改善,对这4个经典的函数分别进行250次迭代,算法收敛图,如图1～4所示。

图1 Sphere函数收敛示意图

图3 Rastrigrin函数收敛示意图

图2 Griewank函数收敛示意图

图4 Rosenbrock函数收敛示意图

从图1～4经典函数的收敛图可以直接看出,NPSO算法明显优于基本粒子群算法和LDWPSO算法。算法的收敛性优于经典算法,充分体现了改进的优势。

5 结束语

为有效抑制和避免PSO算法早熟收敛,提出的新进化模式的粒子群优化算法原理为:在采用自适应惯性权重的基础上,通过判断粒子是否陷入局部最优,对陷入局部最优的粒子群采用新的进化模型,从而使粒子迅速跳出局部最优,在更大的空间里寻优,这样可以保证算法能够有效避免早熟收敛和陷入局部最优。通过对4个经典函数的测试,显示出改进的粒子群优化算法具有更好的收敛精度,能有效避免粒子陷入局部最优。若应用到实际优化问题上将起到很好的推动作用。

[1] KENNEDY J,EBERHART R C.Particle Swarm Optimization Proceedings of 1995[C].IEEE International Conference on Neural Networks,1995:1942-1948.

[2] Eberhar t RC,Shi Y H.Particle swarm optimization:developments,applications and resources[A].Proceedings of the IEEE Congress on Evolutionary Computation[C].Piscataway,USA:IEEE Service Center,2001.

[3] Shi Y,Eberhart RC.Empirical study of particle swarm optimization[C].Proceedingsof the IEEE Congresson Evolutionary Computation,2009.

[4] Wetter M.and Wright J.A comparison of deterministic and probabilistic optimization algorithms for nonsmoth simulation-based optimization[J].Building and Environment.2006.

[5] 李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,2007,14.

[6] 段富,苏同芬.免疫粒子群算法的改进及应用[J].计算机应用,2010,30:1883-1884.

[7] R Eberhart,Y Shi.Tracking and optimizing dynamic systems with particle swarms[A].The IEEE Congresson Evolutionary Computation[C].San Francisco,USA:IEEE,2001.

[8] Y Shi,R Eberhart.Empirical study of particle swarm optimization[A].International Conference on Evolutionary Computation[C].Washington,USA:IEEE,2002.

[9] Y Shi,R Eberhart.Fuzzy adaptive swarm optimization[A].The IEEE Congress on Evolutionary Computation[C].San Francisco,USA:IEEE,2001.

[10] 刘怀亮,高鹰,许若宁,等.一种新的改进粒子群优化方法[J].计算机工程与应用,2010,46.

[11] 李宁,邹彤,孙德宝,等.基于粒子群的多目标优化算法[J].计算机工程与应用,2005,41.

[12] 俞欢军.混合粒子群游湖算法研究[J].信息与控制,2005,34.