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

摘要：该文主要是参照控制理论，对基本微粒群算法、标准微粒群算法和带有收缩因子的微粒群算法做了充分细致的解析，通过分析发现它们或者一个积分环节与两个惯性环节构成的系统；或者是三个惯性环节构成的体系，为了使算法的效率更快，创建由积分环节与震荡环节构成的系统所对应的改进微粒群算法，深入研讨参数的选择方法，论证这种算法的可行性和有效性，对相应算法性能分析，并提出相应的改进方法。关键词：控制；微粒群算法；惯性环节；震荡环节中图分类号：TP301文献标识码：A文章编号：1009-3044(2016)32-0235-04DOI:10.14004/j.cnki.ckt.2016.4526

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

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

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

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

价值。

2以控制理论为基础的微粒群算法分析这篇文章主要是分析研讨下面的问题：

maxf(x),x∈D⊆Rn

(1)（2）

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

ìvjk(t+1)=wvjk(t)+c1r1(pjk-xjk(t))+c2r2(pgk-xjk(t))íx(t+1)=x(t)+v(t+1)

jkjkîjk

t时刻微粒j位置向量的第k维分量，pjk表示t时刻微粒j的历史

xjk(t)这里vjk(t)表示t时刻微粒j的速度向量的第k维分量，

最佳位置向量的第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))

分别思考，下面三个特殊的进化方程式：

ìvjk(t+1)=vjk(t)

íx(t+1)=x(t)+v(t+1)

jkjkîjk

ìvjk(t+1)=c1r1(pjk-xjk(t))

íx(t+1)=x(t)+v(t+1)

jkjkîjk

T2(t),T3(t)起到的作用，可是为了深入明白T1(t)，我们需要

T3(t)=c2r2(pgk-xjk(t))

（4）（5）

收稿日期：2016-10-25作者简介：郝武伟（1983—），男，山西闻喜人，讲师，硕士研究生，主要研究方向为计算智能。本栏目责任编辑：梁

书

计算机工程应用技术235

ComputerKnowledgeandTechnology电脑知识与技术ìívjkîx(针对上面的三个特殊进化方程进行深入分析论证，(tt++1)1)==cx2r(2t()p+gkv-(xjk(t))（6）

jk

jkjkt+1)

为了更好地搞清楚T分别研究这三个进化方程式：

1(t)，Tt)的具体作用。接下来，主要是

2(t),T3(还要（1）先假设速度的进化方程式（进而就能得出：

v4）式，就会得出下面结论：

vjk(0)=jk(1)=...=vjk(t)

xjk如果假设x(t)=vjk(0)t+xjk(0)

jk个时候是积分的环节过程。

(0)=0，然后就能推出：xjk(t)=vjk(0)t，很明显这

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

xjk(t+1)jk由于积分的差分形式，有dx(t)+h1pjk-h1xjk(dt(t)t)

jk=xjk(t+1)-xjk(t)，进而上面的方程式转换成：

dxjkdt(t)=-h1xjk(t)+h1pjkr(t)然后针对上述的方程应用拉普拉斯变换，得到下面的方程

式：

sXjk(hs)=-h1Xjk(s)+

h1pjk

s分析整理得：Xjk(s)=

1pjk

s(s+h运用拉普拉斯反变换之后，1)得到：xjk-h1t进而，发现T(t)=pjk(1-e)

2是p。

(t)实际上相当一个惯性环节，并且极限位置jk（3）假设速度的进化方程式为（6）式，运用同样的方法，得到下面的方程式：

xjk(t)=pgk(1-e-h2t是ph=c，得出结论，T)22r23(t)相当一个惯性环节，相应的极限位置gk。

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

ìívjk(t+1)=wvîjk

+1)=xjkx(t(t()t+)

vjk如果w=1，就会变成基本微粒群算法，因此可以假设(t+1)（7）

jkw≠1.

又因为vjk把方程式代到位置进化方程式里面，(t+1)=wvjk(t)，进而推导出：vjk(t+1)=wt+1vjk(0)dxx能到下面的方程式：

x(t+1)=t+1

jkjk(t)+wvjk(0)进而推导出：

jkdt(t)=wt+1vjk(0)通过求解，得出：xwvjkjk(t)=(0)[etlnw

-1]+xjk如果假设Xlnw(0)

j(0)=0，得到下面方程式：

xwvjk(t)=-

lnjkw(0)éê-tln1wùë1-eúû

所以，当ln1w>0，也就是w<1的时候，得出一个惯性环节，

236

计算机工程应用技术第12卷第32期(2016年11月)

其极限位置是-

wv三个惯性环节组成的。

lnjkw(0)。发现对于标准微粒群算法能够看成2.3带有收缩因子的微粒群算法的分析为了有利于分析，把带有收缩因子的微粒群算法的进化方程式重新改写为下面方程式：

ìívjk(t+1)=vjk(t)+c1r1(pjk-xjk(t))+c2r2(pgk-xjk(t))

îx（jk(t+1)=xjk(t)+kvjk同理，针对速度进化的方程进行相应分解，(t+1)

8）能得到相应的

三个特殊进化方程式：

ìívjk(t+îx(t+1)1)==vxjk((tt)

)+kv(t+1)（9）

jk

jkjkìívjkîx(jk

(tt++1)1)==cx1r1((t)p+jkkv-xjk(t(t+))

1)（10）

jkjkìívjk(t+1)=c2r2(pgkîx接下来，针对（9）、（10）和（11）方程式进行深入分析。(t+1)=x(t)+kv-x(tjk+(t))

1)（11）

jk

jkjk针对（9）方程式来说，如果假设显而易见，这个时候是积分环节，)=X(0)=0,kv会得出下面方程式：

xjk(tjk只是轨迹的斜率相对发(0)t

生了改变。

针对（10）方程式来说，假设h1r(t)=1(t)作为单位的阶跃函数，=c1r1，h1，pjk作为常数，

t+1)=x通过简化，得出下面的方程式：

xjk(jk(t)+kh1pjk-kh1xjk(t)

因为dxjkdt(t)=xjk(t+1)-xjk(t)，所以上面的方程式可以简化成：

dxjkdt(t)=-kh1xjk(t)+kh1pjk(t)∘r(t)对上面的方程式运用拉普拉斯转变，得出：

sXs)=-khkh1X1pjk

jk(jk(s)+

s整理得出：X(s)=

khs(s+1pjk

jkkh1运用拉普拉斯转换，得出：)xjk进而，会得出结论T(t)=pjk(1-e

-kh1t

)

2且他的极限位置就是p。

(t)实际上相当于是一个惯性环节，而

jk针对（11）方程式来说，xjk会发现T(t)=pgk(1-e

-kh1t

)

3p(t)相当于一个惯性环节，并且他的极限位置就是gk。

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

本栏目责任编辑：梁

书

（第12卷第32期(2016年11月)

ComputerKnowledgeandTechnology电脑知识与技术

这里，f=出：

1+Th1k1，a=，运用拉普拉斯原理反变换，2kh1kh1-awn1-axjk(t)=pjk(1-etsin(wdt+arctg)a1-a2wd=wn1-a2表这里，wn=1表示无阻尼自然震荡环节；

f示阻尼自然震荡频率。依照控制理论，震荡环节的单位阶跃是有阻尼的正弦震荡曲线。震荡程度和阻尼比是有关系的，a值

Xj(t)作为单调上升曲线，越小，震荡就会越强。当a≥1的时候，不再是震荡环节。因此，需要思考ξ<1的条件。

又因为a=1+Th1k2kh1<1,且h1>0，推出T<

2kh1-1kh1

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

xjk(t+1)=xjk(t)+kvjk(t+1)（12）

依照随机数选择范围，得出：0<2kh1-1kh1

2kh1-1<1又或者1vjk(t+1)=wvjk(t)+c1r1(pjk-f(xjk(t-1),xjk(t)))+c2r2(pgk-f(xjk(t-1),xjk(t)))因此，推导出震荡环节的参数选择区间范围是h1>14k（13）

利用标准算法（PSO）、结合震荡环节的改进微粒群算法

可以在速度进化方程式里面运用xjk(t)和xjk(t-1)的某一函

（MPSO）,对函数f1和f2分析。对于函数f1来说，不管是平均收敛

数f来代替xjk(t)。比如下面的线性组合方程式：代数还是平均收敛率，改进微粒群算法都比标准微粒群算法，

f(xjk(t),xjk(t-1))=Tx(t)+(1-T)xjk(t-1)（14）尤其是平均收敛率得到很大提升。针对函数f2来说，得到的效

果更好，平均收敛率到巨大提升，主要是因为震荡环节的导这里面α是在0到1之间的随机的数字，参数k是步长，用

入。正因为算法的全局搜索性能全面提升，在计算量都一样的来调整位置xjk(t+1)里面的xjk(t)的利用率。接下来，进行更深

情况下，局部搜索性能就一定会降低，所以平均收敛代数会有入的推论，针对速度的进化方程进行深入分析解答，得出下面

适量提升，总体来说，微粒群里面加入震荡环节，很好地提升了的方程式：

算法的全局搜索性能。T1(t)=wvjk(t)

（3）按照相同的原理分析T3(t)，结果作为震荡环节的参数

T2(t)=c1r1pjk-Tx(t)-(1-T)xjk(t-1)

范围h2<1，得出相应的微粒群算法的框架论述：

4kT3(t)=c2r2pgk-Tx(t)-(1-T)xjk(t-1)

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

率先分析相应单独的进化方程式：Step2.依据计划的方程式（12）、（13）、（14）计算微粒速度和（1）针对T1来说，进化方程式是：位置；

ìvjk(t+1)=wvjk(t)Step3.评价每一个微粒的适应度；íx(t+1)=x(t)+kv(t+1)

jkjkStep4.对于每一个微粒，把他的使用值和他经历的最优位îjk

当w=1的时候，方程式就和带惯性因子的微粒群算法T1一置作比较，并保留最佳；样，成为积分环节。不然，和基本的微粒群算法T1相似；当w<1Step5.对于每一个微粒，把他的使用值和群体所经历的最

kwvjk(0)佳位置对比，保留最佳；

的时候，得到一个惯性环节，极限位置是-。

lnwStep6.最后论证是否满足结束条件。如果满足条件，算法

（2）针对T2来说，进化方程式是：结束；不满足条件，转到Step2。

v(t+1)=h(p-T(t)-(1-T)x(t-1))ìjkjkxjk1

4结论íx(t+1)=x(t)+kv(t+1)

jkjkjkî

这篇文章主要是运用控制理论,通过分析比较三种微粒群假设α是常数，得出下面的方程式：

算法，推导出速度进化方程式仅仅用到了可以用一阶微分方程xjk(t+2)=xjk(t+1)+khipjk-kTh1xjk(t+1)-k(1-T)h1xjk(t)

式表示的积分环节和惯性环节。为了更好地提升全局搜索性

r(t)=1(t)作为单位运用x''jk(t)=xjk(t+2)-2xjk(t+1)+xjk(t)，

能，进而提出了可以运用二阶微分方程表示的震荡环节。发

的阶跃函数，推导出：

现，提升速度的利用率，全局收敛性能也得到巨大提升。

1x''(t)+1+h1kTx'(t)+x(t)=p∘1(t)

jkjkjk

参考文献:kh1jkkh1

jk

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

4k[[jk

jk

]]jk

进而他的传递函数就是：

pjk

xjk(s)=22af

fs+2s+1

书

[1]KennedyJ,EberhartRC.Particleswarmoptimization[C].In:ProceedingsofIEEEInternationalConferenceonNeuralNet⁃计算机工程应用技术本栏目责任编辑：梁

237

ComputerKnowledgeandTechnology电脑知识与技术works,IEEEServiceCenter,Piscataway,NJ,1995：1942-[2]1948.works,EngelbrechtstabilityAandP,Ismailcontrol[J].A.TrainingTheoryandproductApplications,1999,2unitneuralnet⁃[3](1-2):[C].Kennedy59-74.In:ProceedingsJ.Theparticleoftheswarm:InternationalsocialadaptionConferenceofknowledge[4]tionaryingtheParsopoulosComputation,KE,USA,1997：303-308.onEvolu⁃HadjisavvasparticlesisN,swarmPlagianakosPardalosoptimizerVP,MagoulasGD.Improv⁃PMeds.,byfunctionAdvances\"stretching\"[A].In:[5]2001andGlobalOptimization[M].KluwerAcademicPublishers,inConvexAnaly⁃Coello：445-457.pleCoelloCA,LechugaMS.MOPSO:USA.IEEEobjectiveaproposalformulti⁃CongressparticleonswarmEvolutionaryoptimization[C].Honolulu,HawaiiComputation,2002：1135-[6]1138.ticleKennedyJ,EberhartR[7]System,swarmManalgorithmC.Adiscretebinaryversionofthepar⁃andCybernetics,[C].In:Proceedings1997oftheConferenceonIn:ShiProceedingsY,EberhartofRIEEEC.AInternationalmodifiedparticle：4104-4109.Conferenceswarmoptimizer[C].onEvolution⁃238

计算机工程应用技术第12卷第32期(2016年11月)

[8]aryandadaptiveClercComputation,M.TheswarmAnchorage,Alaska,1998：125-128.theCongressparticleswarmandtheoptimization[C].In:queen:towardsaProceedingsdeterministic[9]USA,Angeline1999,IEEEonEvolutionaryServiceComputation,WashingtonD.C,ofzation[C].PIn:J.UsingProceedingsselectionCenter,oftoPiscataway,NJ,1951-1957.InternationalimproveparticleJointConferenceswarmoptimi⁃on[10]NeuralmoptimiserLovbjergNetworks'99,M,ingsofwithRasmussenWashingtonDC,USA,1999：84-.breedingTandK,Krinksubpopulations[C].In:T.Hybridparticleswar⁃[11]SanFrancisco,theGeneticoperatorSuganthanPUSA,andProceed⁃N.Particle2001Evolutionary：ComputationConference,swarm135-138.optimizerwithneighbourhood⁃[12]Computation,[C].In:F.vandenBergh.WashingtonProceedingsoftheCongressonEvolutionary⁃AnanalysisDC,USA,of1999：1958-1961.[13]UniversitygenceparticleZengJian-ofparticleswarmoptimizers[C].chao,Pretoria,2001.swarmCuioptimizerZhi-hua.[J].Aguaranteedglobalconver⁃[14]Development,究与发展曾建潮,崔志华2004,41(8):ComputerResearchand⁃,2004,41(8):.一种保证全局收敛的1333-1338.1333-1338.PSO算法[J].计算机研本栏目责任编辑：梁书