跟随变异立子扰动变化的惯性权重PSO算法

【信息科学与控制工程】

跟随变异粒子扰动变化的惯性权重PSO算法

邢焕革1，卫一熳1,2

(1.海军工程大学，武汉430033； 2. 68215部队,青海 民和810800)

摘要：针对困扰粒子群算法“早熟”和收敛慢的2大难题，提出了一种跟随变异粒子扰动变化的惯性权重策略，将粒子群体一致性变化趋势与粒子变异操作相关联，以此来增加粒子的多样性；根据粒子变异程度的大小对惯性权重作出相应调整，使粒子在提高全局寻优能力的同时，又很好地改善了收敛精度和收敛速度，避免因惯性权重单边非线性变化而导致粒子群全局寻优能力稳定性不佳的问题。仿真对比表明，改进的算法较好地避开了局部最优解的干扰问题，具有收敛速度快、寻优精度高等优势。

关键词：变异粒子；惯性权重；粒子群算法

收稿日期：2014-09-22

基金项目：军队研究生课题(2011JY002-422)的资助

作者简介：邢焕革(1967—)，男，副教授，主要从事装备保障指挥、军事复杂网络系统研究;卫一熳(1986—)，女，研究生，主要从事装备保障指挥研究。

doi:10.11809/scbgxb2015.01.030

中图分类号：TP18

文章编号：1006-0707(2015)01-0106-05

本文引用格式：邢焕革，卫一熳.跟随变异粒子扰动变化的惯性权重PSO算法[J].四川兵工学报，2015(1):106-110.

Citation format:XING Huan-ge, WEI Yi-man.Inertia Weight Particle Swarm Optimization Algorithm with Mutation Particle Disturbance Changes[J].Journal of Sichuan Ordnance,2015(1):106-110.

Inertia Weight Particle Swarm Optimization Algorithm with

Mutation Particle Disturbance Changes

XING Huan-ge1, WEI Yi-man1,2

(1.Navy University of Engineering, PLA, Wuhan 430033, China;

2.The 68215thTroop of PLA, Minhe 810800, China)

Abstract:Aiming at the problems of the particle swarm algorithm “premature” and slow convergence, the inertia weight adjustment strategy with the mutation particles disturbance change was presented. In order to increase the diversity of the particles, the consistent of the particles group changing tendency was related with the particle mutation. The inertia of the weight of the particles was put forward with a corresponding adjustment according to the degree of variation the mutation particles, and the global searching ability of the particles is not only improved, but also that the convergence precision and speed of the particles are advanced, the poor stability problem of the particles swarm optimization ability, which is generated due to the inertia weight unilateral nonlinear change, is avoided. Simulation results show that the improved algorithm has the advantages of fast convergence speed, high precision optimization and so on.

Key words: mutation particle; inertia weight; particle swarm optimization

粒子群算法(particle swarm optimization,PSO)是一种群体智能优化算法[1]。该算法以其简单、调整参数少、容易实现等优势已被广泛运用于函数优化、模式识别、系统控制等领域。然而，该算法在实现过程中常会陷入局部寻优，容易出现“早熟”现象，同时还会产生收敛速度较慢等问题[2,3]。针对这些不足，许多学者提出了很多改进方案，归纳起来有：惯性权重改进算法[4]、学习因子改进算法[5]、拓扑结构改进算法[6]、混合算法[7]、小生境PSO改进算法[8]、离散型PSO改进算法等[9]。以上算法仅在某一方面改善了粒子群算法的不足，但是要想到达全局寻优，又不出现“早熟”现象，而且收敛速度还要快，需要通过与其他算法或技术融合在一起才能实现整体寻优效果。

为了进一步改善粒子群算法的不足，近年来，进化算法中的变异操作也引入到粒子群算法之中。该方法通过保持种群的多样性来避免算法陷入局部寻优，在一定程度上增强了算法的全局寻优能力。例如文献[10]中在改善算法早熟收敛的问题上，对群体粒子的最优解采取随机扰动策略，使其变异，从而提高了全局寻优能力，避免算法陷入局部寻优。但该方法在进行变异操作时采用的是单一均匀变异方式，减弱了粒子的逃逸能力，导致粒子的多样性变化不足，致使全局寻优能力不强。

针对以上不足，本文提出一种跟随变异粒子扰动变化的惯性权重PSO算法。该算法引入了粒子的变异操作，将粒子群体一致性变化趋势与粒子变异操作相关联。在整个寻优迭代过程中，一旦粒子趋于一致，则对整个粒子群产生变异操作，从而增加了粒子的多样性。同时，根据粒子变异程度的大小对惯性权重作出相应调整，使粒子在提高全局寻优能力的同时，又很好地改善了收敛精度和收敛速度，避免因惯性权重单边非线性变化而导致粒子群全局寻优能力稳定性不佳的问题。

1标准粒子群算法[11]

在N维的搜索空间里，有M个粒子组成的群体，其中第i个粒子表示为一个N维的向量xi=(xi1,xi2,…,xiN)，i=1,2,…,M。即第i个粒子在N维搜素空间里的位置是xi，每个粒子的位置都是一个潜在的解。将这个潜在的解代入目标函数，就可计算出其对应的适应度值，根据适应度值的大小来衡量解的优劣。设第i个粒子的“飞行”速度用一个N维的向量表示为vi=(vi1,vi2,…,viN)，i=1,2,…,M。在迭代过程中，第i个粒子搜索到的当前个体粒子最优位置为pi=(pi1,pi2,…,piN)，i=1,2,…,M，粒子群搜索到的当前整体最优位置为pq=(pq1,pq2,…,pqN)。粒子通过追踪个体和整体粒子当前的最优位置来更新自己的位置和速度。

vij=wvij+c1r1(pij-xij)+c2r2(pqj-xij)

(1)

xij=xij+viji=1,2,…,M；j=1,2,…,N

(2)

式中：w称为惯性权重，影响着粒子的收敛速度，大量研究表明，较大的w全局寻优能力较强，较小的w局部寻优能力较强；c1和c2是学习因子，可以调整个体最优和群体最优的比例大小，使粒子具有向群体最优个体学习的能力，通常c1和c2均取2；r1和r2是0～1的随机数。

2跟随变异粒子扰动变化的惯性权重PSO算法

2.1算法思想

通过对标准PSO算法的研究发现，众多学者认为惯性权重w的确定对算法性能和效率的提高起着至关重要的作用。较大的w全局寻优最好，搜索速度快，但收敛精度较低；较小的w局部搜索能力强，收敛精度较高。经过实验证明，无论是标准PSO算法中w线性递减策略，还是文献[10]中算法中w的非线性单边变化惯性权重策略，其简单、直观的特点，在寻优过程中有较好的表现，但没能充分协调好PSO算法的全局和局部搜索能力。随着w的减小，粒子在趋于一致的同时，很容易陷入局部寻优无法跳出。为克服以上不足，充分运用w的特性，引入进化算法中的粒子变异思想，采取跟随变异粒子扰动变化的惯性权重策略来改善PSO算法。其基本思想是：在寻优过程中，一旦粒子趋于一致时，对粒子就进行扰动操作，使粒子发生变异，以便粒子在搜索空间内保持多样性特点，从而避免了粒子陷入局部寻优，消除算法“早熟”现象；同时，根据粒子变异程度的大小对惯性权重作出相应调整，使改进后的算法在全局寻优能力上更加稳定。

2.2体方法

根据以上算法的基本思想，本文将针对PSO算法中粒子容易陷入局部寻优、出现“早熟”现象，以及收敛速度慢等问题提出的具体方法是：在寻优过程中首先判断粒子是否趋于一致，如果趋于一致，则在搜索范围内对粒子进行随机扰动操作，以增加粒子的多样性，使其跳出局部寻优；然后根据变异粒子扰动的程度大小改变算法的惯性权重，这样不仅提高了算法寻优搜索能力，而且使算法在全局寻优能力上更加稳定，同时还加快了单次迭代寻优算法的收敛速度；最后，通过寻优结果收敛性判断，即可得到最优解。

1) 粒子趋于一致性判定方法

在PSO算法中，粒子一致的判定直接影响着最优解的确定。如何判定粒子趋于一致是关系到算法搜寻到目标函数最优解的关键，本文将根据粒子散布位置的相似度来判断粒子是否趋于一致。具体方法是通过粒子xi散布的均方差来判断粒子是否趋于一致，其公式表示为

(3)

式中：k是表示粒子数量；d表示粒子散布的均方差。当d小于一定阈值时，粒子趋于一致。

2) 粒子变异操作处理方法

随着PSO算法迭代次数的增加，粒子趋于一致，出现“早熟”现象，此时算法很可能陷入局部寻优状态。对此，本文引入变异操作思想，即对当前粒子状态施加扰动，并确保变异后的粒子状态处在搜索范围内。其扰动操作可用下式表示

xinew=xiold+δ

(4)

式中：δ是随机扰动量；xinew表示变异操作后的粒子状态。

3) 惯性权重的变化处理方法

在惯性权重的改进方案研究上，大多数文献是通过迭代次数的增加对惯性权重采用线性或非线性单边变化策略，虽然在一定程度上平衡了粒子局部和全局寻优能力，但全局寻优能力的稳定性不佳。本文将采用跟随变异粒子扰动程度来调整惯性权重的大小，使算法在全局寻优能力上更加稳定，同时还加快了单次迭代寻优算法的收敛速度。其公式表示为

(5)

惯性权重函数w的变化曲线如图1所示。

图1　惯性权重w的变化曲线

从图1可以看出，w值是在0～1的范围内变化。在单次寻优过程中，随着迭代次数的增加，粒子趋于一致，粒子相似度增加，粒子散布减小。当小于给定的阈值时，就可认为粒子趋于一致，w随之减小，此时对粒子进行变异操作，使粒子在搜索范围内随机散布，以此增加粒子的多样性，同时调整w的大小，使之跟随变异粒子进行操作，再一次进入全局寻优状态。经过多次这样的循环，直到满足最优收敛条件，得到最优解，寻优过程结束。

4)寻优结果收敛性判断方法

判断算法是否收敛，是确定目标函数最优值的关键步骤。本文设定在有限次迭代寻优过程中有l次最优结果是相似的，且最优结果是连续出现的，对l次最优结果求均方差，其均方差小于设定的阈值σ1，同时l次寻优过程中保存的粒子最优解与其平均最优解也小于设定的阈值σ2，说明算法收敛，得到目标函数的最优解。该方法确保了算法在全局寻优时的稳定性能。其公式表示为

(6)

2.3现步骤

步骤1初始化粒子的位置和速度，本文取c1、c2=2，w=0.7，迭代次数、搜索空间可以根据函数的不同进行调整；

步骤2计算当前粒子位置；

步骤3计算每个粒子的适应值；

步骤4保存单个粒子适应值的最优解，将保存的单个粒子位置的最优解pi设为当前位置；

步骤5寻找粒子群体的最优值pq设为初始种群的最优位置；

步骤6利用式(3)判断粒子是否趋于一致；

步骤7当d≤0.1时，利用式(4)，更新xi，按照式(5)调整惯性权重w，按照式(1)和式(2)更新粒子的速度和位置，更新pi和pq。

步骤8利用式(6)判断粒子是否搜索到最优值，若满足，输出结果pq，算法结束；否则返回步骤2。

3仿真与结果分析

为了测试分析跟随变异粒子扰动变化的惯性权重PSO算法的性能，文中选用了3种经典测试函数作为目标函数，并且将改进的算法与标准PSO算法和文献[10]中所用到的算法(以下简称文献算法)进行对比。

3.1测试函数 [12]

1)Sphere函数

(7)

2)Rastrigrin函数

(8)

3)Rosenbrock函数

(9)

3.2实验参数设置 [10]

在进行3种算法测试时，取20个数作为种群粒子数；对3个典型测试函数分别从10、20、30维，对应的最大迭代次数分别为500、1 000、1 500次进行测试。对标准PSO算法，设置初始惯性权重w=0.9，随着迭代次数的增加，w线性递减至0.4，学习因子c1和c2设为2；文献算法初始惯性权重w从1.2非线性递减到0.4，学习因子c1和c2设为2.05；改进算法设置初始惯性权重w=0.7，随着迭代次数的增加，粒子在寻优过程中的变异扰动使w在0～1之间波动变化，学习因子c1和c2设为2。实验在Matlab7.11.0(R2010b)的运行环境中进行，3个典型的测试函数用上述3种算法在10、20、30维的情况下分部运行50次，以其平均值作为优化结果。其中，最优值是整个寻优过程中所搜索到的最优值；均值是指50次运行求得的最优值的平均值。

3.3实验结果与分析

通过3个典型的测试函数对3种算法进行测试，对表1、表2和表3的数据进行比较，可以看出无论是在最优值，还是均值方面文献算法比标准PSO算法都更具有优越性，但改进算法相比较前2种算法的精度都要高，其探索解的能力更强，获得解的总体质量较好。

表1　3种算法对 Sphere函数的仿真结果

表2　3种算法对 Rastrigrin函数的仿真结果

表3　3种算法对 Rosenbrock函数的仿真结果

图2、图3和图4指标准PSO算法、文献算法和改进算法对3种测试函数在粒子数为20、维数为20、迭代次数为1 000的情况下，随迭代次数的增加，相应函数适应值的变化曲线图。可以看出，在迭代次数相同的情况下，改进算法的收敛速度要明显快于标准PSO算法和文献算法的收敛速度。

图2　 Sphere函数测试结果

图3　 Rastrigrin函数测试结果

图4　 Rosenbrock函数测试结果

总之，通过3种算法对上述3种典型测试函数的测试结果进行对比表明，改进算法在收敛精度和收敛速度方面比文献算法和标准PSO算法都要高。

4结论

本文针对困扰粒子群算法“早熟”和收敛慢的2大难题，提出一种跟随变异粒子扰动变化的惯性权重PSO算法，使惯性权重随变异粒子的扰动变化而变化，提高了算法的全局搜索能力，稳定性更强。通过跟标准PSO算法和文献算法对3个典型测试函数进行测试分析，结果表明改进算法能够避开局部最优解的干扰，收敛速度快，寻优精度高。

参考文献：

[1]KennedyJ,EberhartR.ParticleSwarmOptimization[C]//ProceedingoftheIEEEInternationalConferenceonNetworks．[S.l.]:[s.n.],1995：1942-1948.

[2]ParsopoulosKE,VrahatisMN.Onthecomputationofallglobalminimizersthroughparticleswarmoptimization[J].IEEETrans.onEvolutionaryComputation,2004,8(3):211-224.

[3]MendesR,KennedyJ,NevesJ.Thefullyinformedparticleswarm:Simpler,mayberbetter[J].IEEETrans.OnEvolutionaryComputation,2004,8(3):204-210.

[4]周俊，陈璟华，刘国祥，等．粒子群优化算法中惯性权重综述[J]．广东电力，2013,26(7)：6-12.

[5]王克华，牛慧，张亚南，等．一种参数自适应调整和边界约束的粒子群算法[J]．电子设计工程，2011,19(21)：46-50.

[6]KennedyJ.Stereotyping.ImprovingParticleSwarmPerformancewithClusteranalysis[C]//ProceedingsoftheCongressonEvolutionaryComputing.Piscatawat,2000,NJ:1507-1512.

[7]张捍东，方玲，岑豫皖，等．三种混合粒子群算法比较[J]．自动化与仪表，2011(7)：10-13.

[8]史哲文，白雪石，郭禾，等．基于改进小生境粒子群算法的多模函数优化[J]．计算机应用研究，2012,29(2)：465-468.

[9]李志，陈年生，郭小珊，等．粒子群算法及其改进技术研究[J]．湖北师范学院学报:自然科学版，2011，31(2)：104-108.

[10]邵洪涛，秦亮曦，何莹．带变异算子的非线性惯性权重PSO算法[J]．计算机技术与发展，2012,22(8)：30-34.

[11]姜长元，赵曙光，沈士根，等．惯性权重正弦调整的粒子群算法[J]．计算机工程与应用，2012,48(8)：40-42.

[12]刘志雄，梁华．粒子群算法中随机数参数的设置于实验分析[J]．控制理论与应用，2010，27(11)：1489-1496．

(责任编辑杨继森)