基于控制理论的微粒群算法分析和改进

郝武伟

摘要：该文主要是参照控制理论，对基本微粒群算法、标准微粒群算法和带有收缩因子的微粒群算法做了充分细致的解析，通过分析发现它们或者一个积分环节与两个惯性环节构成的系统；或者是三个惯性环节构成的体系，为了使算法的效率更快，创建由积分环节与震荡环节构成的系统所对应的改进微粒群算法，深入研讨参数的选择方法，论证这种算法的可行性和有效性，对相应算法性能分析，并提出相应的改进方法。

关键词：控制；微粒群算法；惯性环节；震荡环节

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）32-0235-04

1 引言

众所周知，微粒群算法（particle swarm optimization， PSO）被Kennedy和Eberhart创造性的提出来以后，因为这种算法不仅计算的速度很快，而且这种算法本身具有正确性和易实现性。在当今国际的相关的领域引起了很多学者的关注和深入探索，并运用于实际应用中。

目前一些前沿的科學家已经把微粒群算法有效的应用在人工神经网络的训练方法、分选XOR问题的神经网络训练、极小极大的相关问题、众多的目标的优先改进等方面。而且，对于微粒群算法的修改完善方面，最早是由Kennedy和Eberhart率先提出的二进制的PSO算法。在1998年的时候，Shi和Eberhart率先的提出了带惯性系数的PSO算法，并且Clerc为了充分的保证这种微粒群算法的收敛性，就采取把收缩因子加入到进化方程中的方法。Angeline在学习借用进化计算的选择理论概念，并且把这种理论概念用在PSO算法里面。并且，Lovbjerg等人就更加深入的把进化计算的方法运在PSO算法里面。考虑到群体里面微粒的多种多样特性，为了保证这种特性，Suganthan在算法里面加入空间领域的理论概念，并且不断地完善这种方法，提升算法的相应的性能。

在算法收敛方面，F.van den Bergh借鉴Solis和Wets关于随机性的计算方法的收敛法则，通过结果表明了标准PSO算法不能收敛于全局的最佳解，甚至于局部最优解。在这个准则的基础上，作者提出随机PSO法，这种算法很好的保证以概率1收敛于全局最佳解。

这篇文章主要是运用控制理论对三个常见的微粒群算法进行深入分析研究，并且通过计算发现它们的速度进化方程大致都可以分解成许多个惯性环节、积分环节等特点的环节组合，而且这些组合都能借用一阶微分方程进行有力的叙述，为了这样，我们还要加入以二阶微分方程的震荡环节，高效的提升微粒群算法的全局收敛性能，进而很大程度提升微粒群算法的计算效率。作为一种随机的优化算法，PSO算法在相应的应用领域具有很大的用，所以，深入研究各种算法的有效性，对于提升微粒群算法具有很大的帮助，更好地为运用到实际中创造价值。

2 以控制理论为基础的微粒群算法分析

这篇文章主要是分析研讨下面的问题：

[maxf（x），][x∈D?Rn] （1）

一般标准微粒群算法大体可以作如下描述：

[vjk（t+1）=wvjk（t）+c1r1（pjk-xjk（t））+c2r2（pgk-xjk（t））xjk（t+1）=xjk（t）+vjk（t+1）] （2）

这里[vjk（t）]表示t时刻微粒j的速度向量的第k维分量，[xjk（t）]t时刻微粒j位置向量的第k维分量，[pjk]表示t时刻微粒j的历史最佳位置向量的第k维分量，[pgk]表示t时刻种群历史最佳位置向量的第k维分量。r1，r2是0到1之间的随机的两个数，w，c1，c2是常数。

众所周知，自打J.Kennedy率先提出了基本微粒群算法之后，在经过很多学者的不断的改进完善，最常使用的就是增加惯性系数w的标准微粒群算法和带收缩因子的改进微粒群算法。接下来，我们运用控制理论对这三种微粒群算法进行分析。

2.1 基本微粒群算法的分析

我们针对速度的进化的方程进行深入的研究分析。可以把方程式（2）的速度化方程改写为：

[vjk（t+1）=T1（t）+T2（t）+T3（t）] （3）

这里面的其他关系：

[T1（t）=vjk（t）T2（t）=c1r1（pjk-xjk（t））T3（t）=c2r2（pgk-xjk（t））]

可是为了深入明白[T1（t）]，[T2（t）]，[T3（t）]起到的作用，我们需要分别思考，下面三个特殊的进化方程式：

[vjk（t+1）=vjk（t）xjk（t+1）=xjk（t）+vjk（t+1）] （4）

[vjk（t+1）=c1r1（pjk-xjk（t））xjk（t+1）=xjk（t）+vjk（t+1）] （5）

[vjk（t+1）=c2r2（pgk-xjk（t））xjk（t+1）=xjk（t）+vjk（t+1）] （6）

针对上面的三个特殊进化方程进行深入分析论证，主要是为了更好地搞清楚[T1（t）]，[T2（t）]，[T3（t）]的具体作用。接下来，还要分别研究这三个进化方程式：

（1）先假设速度的进化方程式（4）式，就会得出下面结论：

[vjk（0）=vjk（1）=...=vjk（t）]

进而就能得出：

[xjk（t）=vjk（0）t+xjk（0）]

如果假设[xjk（0）=0]，然后就能推出：[xjk（t）=vjk（0）t]，很明显这个时候是积分的环节过程。

（2）假设速度的进化方程式是（5）式，h1=c1r1，[h1]，[pjk]作为常数，[rt=1t]作为单位的阶跃函数，经过化简计算，能得出：

[xjk（t+1）=xjk（t）+h1pjk-h1xjk（t）]

由于积分的差分形式，有[dxjk（t）dt=xjk（t+1）-xjk（t）]，进而上面的方程式转换成：

[dxjk（t）dt=-h1xjk（t）+h1pjkr（t）]

然后针对上述的方程应用拉普拉斯变换，得到下面的方程式：

[sXjk（s）=-h1Xjk（s）+h1pjks]

分析整理得：[Xjk（s）=h1pjks（s+h1）]

运用拉普拉斯反变换之后，得到：[xjk（t）=pjk（1-e-h1t）]

进而，发现T2（t）实际上相当一个惯性环节，并且极限位置是[pjk]。

（3）假设速度的进化方程式为（6）式，运用同样的方法，得到下面的方程式：

[xjk（t）=pgk（1-e-h2t）]

h2=c2r2，得出结论，T3（t）相当一个惯性环节，相应的极限位置是[pgk]。

2.2 标准微粒群算法的分析

针对标准的微粒群算法来说，因为导入了惯性因子w，所以只有T1（t）不一样，如下面的计算公式：

[vjk（t+1）=wvjk（t）xjk（t+1）=xjk（t）+vjk（t+1）] （7）

如果w=1，就会变成基本微粒群算法，因此可以假设w≠1.

又因为[vjk（t+1）=wvjk（t）]，进而推导出：[vjk（t+1）=wt+1vjk（0）]

把方程式代到位置进化方程式里面，能到下面的方程式：

[xjk（t+1）=xjk（t）+wt+1vjk（0）]

进而推导出： [dxjk（t）dt=wt+1vjk（0）]

通过求解，得出：[xjk（t）=wvjk（0）lnwetlnw-1+xjk（0）]

如果假设[Xj（0）]=0，得到下面方程式：

[xjk（t）=-wvjk（0）lnw1-e-tln1w]

所以，当[ln1w]>0，也就是w<1的时候，得出一个惯性环节，其极限位置是[-wvjk（0）lnw]。发现对于标准微粒群算法能够看成三个惯性环节组成的。

2.3 带有收缩因子的微粒群算法的分析

为了有利于分析，把带有收缩因子的微粒群算法的进化方程式重新改写为下面方程式：

[vjk（t+1）=vjk（t）+c1r1（pjk-xjk（t））+c2r2（pgk-xjk（t））xjk（t+1）=xjk（t）+kvjk（t+1）] （8）

同理，针对速度进化的方程进行相应分解，能得到相应的三个特殊进化方程式：

[vjk（t+1）=vjk（t）xjk（t+1）=xjk（t）+kvjk（t+1）] （9）

[vjk（t+1）=c1r1（pjk-xjk（t））xjk（t+1）=xjk（t）+kvjk（t+1）] （10）

[vjk（t+1）=c2r2（pgk-xjk（t））xjk（t+1）=xjk（t）+kvjk（t+1）] （11）

接下来，针对（9）、（10）和（11）方程式进行深入分析。

针对（9）方程式来说，如果假设X（0）=0，会得出下面方程式：

[xjk（t）=kvjk（0）t]

显而易见，这个时候是积分环节，只是轨迹的斜率相对发生了改变。

针对（10）方程式来说，假设h1=c1r1，[h1]，[pjk]作为常数，[rt=1t]作为单位的阶跃函数，通过简化，得出下面的方程式：

[xjk（t+1）=xjk（t）+kh1pjk-kh1xjk（t）]

因为[dxjk（t）dt=xjk（t+1）-xjk（t）]，所以上面的方程式可以简化成：

[dxjk（t）dt=-kh1xjk（t）+kh1pjk（t）?r（t）]

对上面的方程式运用拉普拉斯转变，得出：[sXjk（s）=-kh1Xjk（s）+kh1pjks]

整理得出：[Xjk（s）=kh1pjks（s+kh1）]

运用拉普拉斯转换，得出：[xjk（t）=pjk（1-e-kh1t）]

进而，会得出结论T2（t）实际上相当于是一个惯性环节，而且他的极限位置就是[pjk]。

针对（11）方程式来说，[xjk（t）=pgk（1-e-kh1t）]

会发现T3（t）相当于一个惯性环节，并且他的极限位置就是[pgk]。

通过上面的深入推论研究，很容易发现，针对基本微粒群算法、标准微粒群算法以及带有惯性因子的微粒群算法来说，他们其实都可以被看成一个积分环节与两个惯性环节组成的或者三个惯性环节组成的。并且惯性环节（图1）和積分环节（图2）都是能用一阶积分方程来论述，为了更好地提升微粒群算法的效率，导入二阶积分方程论述的震荡环节（图3）。并且从图3能看出，惯性环节只能在它的极限位置下面进行搜查，积分环节只能在他的直线四周来搜查，会很大程度限制微粒群算法的搜索性能。但是，震荡环节就可以在他的极限位置四周开展幅度从大到小的有效搜索，进而更好的提升算法的全面搜索性能。

3 控制理论的改进微粒群算法

为了更好提升微粒群算法的搜索性能，提出了一种改进的微粒群算法，这里T2（t）、T3（t）都是作为震动环节，因此进化方程是：

[xjk（t+1）=xjk（t）+kvjk（t+1）] （12）

[vjk（t+1）=wvjk（t）+c1r1（pjk-f（xjk（t-1），xjk（t）））+c2r2（pgk-f（xjk（t-1），xjk（t）））] （13）

可以在速度進化方程式里面运用[xjk（t）]和[xjk（t-1）]的某一函数f来代替[xjk（t）]。比如下面的线性组合方程式：

[f（xjk（t），xjk（t-1））=Txjk（t）+（1-T）xjk（t-1）] （14）

这里面α是在0到1之间的随机的数字，参数k是步长，用来调整位置[xjk（t+1）]里面的[xjk（t）]的利用率。接下来，进行更深入的推论，针对速度的进化方程进行深入分析解答，得出下面的方程式：

[T1（t）=wvjk（t）T2（t）=c1r1pjk-Txjk（t）-（1-T）xjk（t-1）T3（t）=c2r2pgk-Txjk（t）-（1-T）xjk（t-1）]

率先分析相应单独的进化方程式：

（1）针对T1来说，进化方程式是：

[vjk（t+1）=wvjk（t）xjk（t+1）=xjk（t）+kvjk（t+1）]

当w=1的时候，方程式就和带惯性因子的微粒群算法T1一样，成为积分环节。不然，和基本的微粒群算法T1相似；当w<1的时候，得到一个惯性环节，极限位置是[-kwvjk（0）lnw]。

（2）针对T2来说，进化方程式是：

[vjk（t+1）=h1（pjk-Txjk（t）-（1-T）xjk（t-1））xjk（t+1）=xjk（t）+kvjk（t+1）]

假设α是常数，得出下面的方程式：

[xjk（t+2）=xjk（t+1）+khipjk-kTh1xjk（t+1）-k（1-T）h1xjk（t）]

运用[x''jk（t）=xjk（t+2）-2xjk（t+1）+xjk（t）]，[rt=1t]作为单位的阶跃函数，推导出：

[1kh1x''jk（t）+1+h1kTkh1x'jk（t）+xjk（t）=p?jk1（t）]

进而他的传递函数就是：

[xjk（s）=pjkf2s2+2afs+1]

这里，[f=1kh1]，[a=1+Th1k2kh1]，运用拉普拉斯原理反变换，出：

[xjk（t）=pjk（1-e-awnt1-a2sin（wdt+arctg1-aa）]

这里，[wn=1f]表示无阻尼自然震荡环节；[wd=wn1-a2]表示阻尼自然震荡频率。依照控制理论，震荡环节的单位阶跃是有阻尼的正弦震荡曲线。震荡程度和阻尼比是有关系的，a值越小，震荡就会越强。当a≥1的时候，[Xj（t）]作为单调上升曲线，不再是震荡环节。因此，需要思考ξ<1的条件。

又因为[a=1+Th1k2kh1<1]，且h1>0，推出T<[2kh1-1kh1]

依照随机数选择范围，得出：0<[2kh1-1kh1]<1又或者1<[2kh1-1kh1]

通过推导，得出φ1的选取范围区间是：[h1]>[14k]

因此，推导出震荡环节的参数选择区间范围是[h1]>[14k]

利用标准算法（PSO）、结合震荡环节的改进微粒群算法（MPSO），对函数f1和f2分析。对于函数f1来说，不管是平均收敛代数还是平均收敛率，改进微粒群算法都比标准微粒群算法，尤其是平均收敛率得到很大提升。针对函数f2来说，得到的效果更好，平均收敛率到巨大提升，主要是因为震荡环节的导入。正因为算法的全局搜索性能全面提升，在计算量都一样的情况下，局部搜索性能就一定会降低，所以平均收敛代数会有适量提升，总体来说，微粒群里面加入震荡环节，很好地提升了算法的全局搜索性能。

（3）按照相同的原理分析T3（t），结果作为震荡环节的参数范围[h2<14k]，得出相应的微粒群算法的框架论述：

Step1.初始化种群和队形参数；

Step2.依据计划的方程式（12）、（13）、（14）计算微粒速度和位置；

Step3.评价每一个微粒的适应度；

Step4.对于每一个微粒，把他的使用值和他经历的最优位置作比较，并保留最佳；

Step5.对于每一个微粒，把他的使用值和群体所经历的最佳位置对比，保留最佳；

Step6.最后论证是否满足结束条件。如果满足条件，算法结束；不满足条件，转到Step2。

4 结论

这篇文章主要是运用控制理论，通过分析比较三种微粒群算法，推导出速度进化方程式仅仅用到了可以用一阶微分方程式表示的积分环节和惯性环节。为了更好地提升全局搜索性能，进而提出了可以运用二阶微分方程表示的震荡环节。发现，提升速度的利用率，全局收敛性能也得到巨大提升。

参考文献：

[1] Kennedy J， Eberhart R C. Particle swarm optimization[C].In：Proceedings of IEEE International Conference on NeuralNetworks， IEEE Service Center， Piscataway， NJ， 1995：1942-1948.

[2] Engelbrecht A P， Ismail A. Training product unit neuralnetworks， stability and control[J]. Theory and Applications，1999，2（1-2）： 59-74.

[3] Kennedy J. The particle swarm： social adaption of knowledge[C]. In： Proceedings of the International Conference onEvolutionary Computation， USA， 1997：303-308.

[4] Parsopoulos K E， Plagianakos V P， Magoulas G D. Improvingthe particle swarm optimizer by function "stretching"[A]. In：Hadjisavvas N， Pardalos P M eds.， Advances in ConvexAnalysis and Global Optimization [M]. Kluwer AcademicPublishers， 2001：445-457.

[5] Coello Coello C A， Lechuga M S. MOPSO： a proposal formultiple objective particle swarm optimization[C].Honolulu，Hawaii USA.IEEE Congress on Evolutionary Computation，2002：1135-1138.

[6] Kennedy J， Eberhart R C. A discrete binary version of theparticle swarm algorithm [C]. In： Proceedings of theConference on System， Man and Cybernetics， 1997：4104-4109.

[7] Shi Y， Eberhart R C. A modified particle swarm optimizer[C].In： Proceedings of IEEE International Conference onEvolutionary Computation， Anchorage， Alaska， 1998： 125-128.

[8] Clerc M. The swarm and the queen： towards a deterministic andadaptive particle swarm optimization[C].In： Proceedings of theCongress on Evolutionary Computation， Washington D. C，USA， 1999， IEEE Service Center， Piscataway， NJ， 1951-1957.

[9] Angeline P J. Using selection to improve particle swarmoptimization [C]. In： Proceedings of International JointConference on Neural Networks'99， Washington DC， USA，1999：84-89.

[10] Lovbjerg M， Rasmussen T K， Krink T. Hybrid particle swarmoptimiser with breeding and subpopulations[C].In： Proceedingsof the Genetic and Evolutionary Computation Conference， SanFrancisco， USA， 2001：135-138.

[11] Suganthan P N. Particle swarm optimizer with neighbourhoodoperator [C]. In： Proceedings of the Congress on EvolutionaryComputation， Washington DC， USA， 1999：1958-1961.

[12] F.van den Bergh. An analysis of particle swarm optimizers[C].University of Pretoria， 2001.

[13] Zeng Jian-chao， Cui Zhi-hua. A guaranteed global convergenceparticle swarm optimizer [J]. Computer Research andDevelopment， 2004，41（8）： 1333-1338.

[14]曾建潮，崔志華.一种保证全局收敛的PSO算法[J].计算机研究与发展，2004，41（8）： 1333-1338.