基于控制理論的微粒群算法分析和改進(jìn)

郝武偉

摘要：該文主要是參照控制理論，對基本微粒群算法、標(biāo)準(zhǔn)微粒群算法和帶有收縮因子的微粒群算法做了充分細(xì)致的解析，通過分析發(fā)現(xiàn)它們或者一個積分環(huán)節(jié)與兩個慣性環(huán)節(jié)構(gòu)成的系統(tǒng)；或者是三個慣性環(huán)節(jié)構(gòu)成的體系，為了使算法的效率更快，創(chuàng)建由積分環(huán)節(jié)與震蕩環(huán)節(jié)構(gòu)成的系統(tǒng)所對應(yīng)的改進(jìn)微粒群算法，深入研討參數(shù)的選擇方法，論證這種算法的可行性和有效性，對相應(yīng)算法性能分析，并提出相應(yīng)的改進(jìn)方法。

關(guān)鍵詞：控制；微粒群算法；慣性環(huán)節(jié)；震蕩環(huán)節(jié)

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）32-0235-04

1 引言

眾所周知，微粒群算法（particle swarm optimization， PSO）被Kennedy和Eberhart創(chuàng)造性的提出來以后，因為這種算法不僅計算的速度很快，而且這種算法本身具有正確性和易實現(xiàn)性。在當(dāng)今國際的相關(guān)的領(lǐng)域引起了很多學(xué)者的關(guān)注和深入探索，并運(yùn)用于實際應(yīng)用中。

目前一些前沿的科學(xué)家已經(jīng)把微粒群算法有效的應(yīng)用在人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練方法、分選XOR問題的神經(jīng)網(wǎng)絡(luò)訓(xùn)練、極小極大的相關(guān)問題、眾多的目標(biāo)的優(yōu)先改進(jìn)等方面。而且，對于微粒群算法的修改完善方面，最早是由Kennedy和Eberhart率先提出的二進(jìn)制的PSO算法。在1998年的時候，Shi和Eberhart率先的提出了帶慣性系數(shù)的PSO算法，并且Clerc為了充分的保證這種微粒群算法的收斂性，就采取把收縮因子加入到進(jìn)化方程中的方法。Angeline在學(xué)習(xí)借用進(jìn)化計算的選擇理論概念，并且把這種理論概念用在PSO算法里面。并且，Lovbjerg等人就更加深入的把進(jìn)化計算的方法運(yùn)在PSO算法里面。考慮到群體里面微粒的多種多樣特性，為了保證這種特性，Suganthan在算法里面加入空間領(lǐng)域的理論概念，并且不斷地完善這種方法，提升算法的相應(yīng)的性能。

在算法收斂方面，F(xiàn).van den Bergh借鑒Solis和Wets關(guān)于隨機(jī)性的計算方法的收斂法則，通過結(jié)果表明了標(biāo)準(zhǔn)PSO算法不能收斂于全局的最佳解，甚至于局部最優(yōu)解。在這個準(zhǔn)則的基礎(chǔ)上，作者提出隨機(jī)PSO法，這種算法很好的保證以概率1收斂于全局最佳解。

這篇文章主要是運(yùn)用控制理論對三個常見的微粒群算法進(jìn)行深入分析研究，并且通過計算發(fā)現(xiàn)它們的速度進(jìn)化方程大致都可以分解成許多個慣性環(huán)節(jié)、積分環(huán)節(jié)等特點的環(huán)節(jié)組合，而且這些組合都能借用一階微分方程進(jìn)行有力的敘述，為了這樣，我們還要加入以二階微分方程的震蕩環(huán)節(jié)，高效的提升微粒群算法的全局收斂性能，進(jìn)而很大程度提升微粒群算法的計算效率。作為一種隨機(jī)的優(yōu)化算法，PSO算法在相應(yīng)的應(yīng)用領(lǐng)域具有很大的用，所以，深入研究各種算法的有效性，對于提升微粒群算法具有很大的幫助，更好地為運(yùn)用到實際中創(chuàng)造價值。

2 以控制理論為基礎(chǔ)的微粒群算法分析

這篇文章主要是分析研討下面的問題：

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

一般標(biāo)準(zhǔn)微粒群算法大體可以作如下描述：

[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之間的隨機(jī)的兩個數(shù)，w，c1，c2是常數(shù)。

眾所周知，自打J.Kennedy率先提出了基本微粒群算法之后，在經(jīng)過很多學(xué)者的不斷的改進(jìn)完善，最常使用的就是增加慣性系數(shù)w的標(biāo)準(zhǔn)微粒群算法和帶收縮因子的改進(jìn)微粒群算法。接下來，我們運(yùn)用控制理論對這三種微粒群算法進(jìn)行分析。

2.1 基本微粒群算法的分析

我們針對速度的進(jìn)化的方程進(jìn)行深入的研究分析。可以把方程式（2）的速度化方程改寫為：

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

這里面的其他關(guān)系：

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

可是為了深入明白[T1（t）]，[T2（t）]，[T3（t）]起到的作用，我們需要分別思考，下面三個特殊的進(jìn)化方程式：

[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）

針對上面的三個特殊進(jìn)化方程進(jìn)行深入分析論證，主要是為了更好地搞清楚[T1（t）]，[T2（t）]，[T3（t）]的具體作用。接下來，還要分別研究這三個進(jìn)化方程式：

（1）先假設(shè)速度的進(jìn)化方程式（4）式，就會得出下面結(jié)論：

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

進(jìn)而就能得出：

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

如果假設(shè)[xjk（0）=0]，然后就能推出：[xjk（t）=vjk（0）t]，很明顯這個時候是積分的環(huán)節(jié)過程。

（2）假設(shè)速度的進(jìn)化方程式是（5）式，h1=c1r1，[h1]，[pjk]作為常數(shù)，[rt=1t]作為單位的階躍函數(shù)，經(jīng)過化簡計算，能得出：

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

由于積分的差分形式，有[dxjk（t）dt=xjk（t+1）-xjk（t）]，進(jìn)而上面的方程式轉(zhuǎn)換成：

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

然后針對上述的方程應(yīng)用拉普拉斯變換，得到下面的方程式：

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

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

運(yùn)用拉普拉斯反變換之后，得到：[xjk（t）=pjk（1-e-h1t）]

進(jìn)而，發(fā)現(xiàn)T2（t）實際上相當(dāng)一個慣性環(huán)節(jié)，并且極限位置是[pjk]。

（3）假設(shè)速度的進(jìn)化方程式為（6）式，運(yùn)用同樣的方法，得到下面的方程式：

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

h2=c2r2，得出結(jié)論，T3（t）相當(dāng)一個慣性環(huán)節(jié)，相應(yīng)的極限位置是[pgk]。

2.2 標(biāo)準(zhǔn)微粒群算法的分析

針對標(biāo)準(zhǔn)的微粒群算法來說，因為導(dǎo)入了慣性因子w，所以只有T1（t）不一樣，如下面的計算公式：

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

如果w=1，就會變成基本微粒群算法，因此可以假設(shè)w≠1.

又因為[vjk（t+1）=wvjk（t）]，進(jìn)而推導(dǎo)出：[vjk（t+1）=wt+1vjk（0）]

把方程式代到位置進(jìn)化方程式里面，能到下面的方程式：

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

進(jìn)而推導(dǎo)出： [dxjk（t）dt=wt+1vjk（0）]

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

如果假設(shè)[Xj（0）]=0，得到下面方程式：

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

所以，當(dāng)[ln1w]>0，也就是w<1的時候，得出一個慣性環(huán)節(jié)，其極限位置是[-wvjk（0）lnw]。發(fā)現(xiàn)對于標(biāo)準(zhǔn)微粒群算法能夠看成三個慣性環(huán)節(jié)組成的。

2.3 帶有收縮因子的微粒群算法的分析

為了有利于分析，把帶有收縮因子的微粒群算法的進(jìn)化方程式重新改寫為下面方程式：

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

同理，針對速度進(jìn)化的方程進(jìn)行相應(yīng)分解，能得到相應(yīng)的三個特殊進(jìn)化方程式：

[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）方程式進(jìn)行深入分析。

針對（9）方程式來說，如果假設(shè)X（0）=0，會得出下面方程式：

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

顯而易見，這個時候是積分環(huán)節(jié)，只是軌跡的斜率相對發(fā)生了改變。

針對（10）方程式來說，假設(shè)h1=c1r1，[h1]，[pjk]作為常數(shù)，[rt=1t]作為單位的階躍函數(shù)，通過簡化，得出下面的方程式：

[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）]

對上面的方程式運(yùn)用拉普拉斯轉(zhuǎn)變，得出：[sXjk（s）=-kh1Xjk（s）+kh1pjks]

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

運(yùn)用拉普拉斯轉(zhuǎn)換，得出：[xjk（t）=pjk（1-e-kh1t）]

進(jìn)而，會得出結(jié)論T2（t）實際上相當(dāng)于是一個慣性環(huán)節(jié)，而且他的極限位置就是[pjk]。

針對（11）方程式來說，[xjk（t）=pgk（1-e-kh1t）]

會發(fā)現(xiàn)T3（t）相當(dāng)于一個慣性環(huán)節(jié)，并且他的極限位置就是[pgk]。

通過上面的深入推論研究，很容易發(fā)現(xiàn)，針對基本微粒群算法、標(biāo)準(zhǔn)微粒群算法以及帶有慣性因子的微粒群算法來說，他們其實都可以被看成一個積分環(huán)節(jié)與兩個慣性環(huán)節(jié)組成的或者三個慣性環(huán)節(jié)組成的。并且慣性環(huán)節(jié)（圖1）和積分環(huán)節(jié)（圖2）都是能用一階積分方程來論述，為了更好地提升微粒群算法的效率，導(dǎo)入二階積分方程論述的震蕩環(huán)節(jié)（圖3）。并且從圖3能看出，慣性環(huán)節(jié)只能在它的極限位置下面進(jìn)行搜查，積分環(huán)節(jié)只能在他的直線四周來搜查，會很大程度限制微粒群算法的搜索性能。但是，震蕩環(huán)節(jié)就可以在他的極限位置四周開展幅度從大到小的有效搜索，進(jìn)而更好的提升算法的全面搜索性能。

3 控制理論的改進(jìn)微粒群算法

為了更好提升微粒群算法的搜索性能，提出了一種改進(jìn)的微粒群算法，這里T2（t）、T3（t）都是作為震動環(huán)節(jié)，因此進(jìn)化方程是：

[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）

可以在速度進(jìn)化方程式里面運(yùn)用[xjk（t）]和[xjk（t-1）]的某一函數(shù)f來代替[xjk（t）]。比如下面的線性組合方程式：

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

這里面α是在0到1之間的隨機(jī)的數(shù)字，參數(shù)k是步長，用來調(diào)整位置[xjk（t+1）]里面的[xjk（t）]的利用率。接下來，進(jìn)行更深入的推論，針對速度的進(jìn)化方程進(jìn)行深入分析解答，得出下面的方程式：

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

率先分析相應(yīng)單獨(dú)的進(jìn)化方程式：

（1）針對T1來說，進(jìn)化方程式是：

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

當(dāng)w=1的時候，方程式就和帶慣性因子的微粒群算法T1一樣，成為積分環(huán)節(jié)。不然，和基本的微粒群算法T1相似；當(dāng)w<1的時候，得到一個慣性環(huán)節(jié)，極限位置是[-kwvjk（0）lnw]。

（2）針對T2來說，進(jìn)化方程式是：

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

假設(shè)α是常數(shù)，得出下面的方程式：

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

運(yùn)用[x''jk（t）=xjk（t+2）-2xjk（t+1）+xjk（t）]，[rt=1t]作為單位的階躍函數(shù)，推導(dǎo)出：

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

進(jìn)而他的傳遞函數(shù)就是：

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

這里，[f=1kh1]，[a=1+Th1k2kh1]，運(yùn)用拉普拉斯原理反變換，出：

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

這里，[wn=1f]表示無阻尼自然震蕩環(huán)節(jié)；[wd=wn1-a2]表示阻尼自然震蕩頻率。依照控制理論，震蕩環(huán)節(jié)的單位階躍是有阻尼的正弦震蕩曲線。震蕩程度和阻尼比是有關(guān)系的，a值越小，震蕩就會越強(qiáng)。當(dāng)a≥1的時候，[Xj（t）]作為單調(diào)上升曲線，不再是震蕩環(huán)節(jié)。因此，需要思考ξ<1的條件。

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

依照隨機(jī)數(shù)選擇范圍，得出：0<[2kh1-1kh1]<1又或者1<[2kh1-1kh1]

通過推導(dǎo)，得出φ1的選取范圍區(qū)間是：[h1]>[14k]

因此，推導(dǎo)出震蕩環(huán)節(jié)的參數(shù)選擇區(qū)間范圍是[h1]>[14k]

利用標(biāo)準(zhǔn)算法（PSO）、結(jié)合震蕩環(huán)節(jié)的改進(jìn)微粒群算法（MPSO），對函數(shù)f1和f2分析。對于函數(shù)f1來說，不管是平均收斂代數(shù)還是平均收斂率，改進(jìn)微粒群算法都比標(biāo)準(zhǔn)微粒群算法，尤其是平均收斂率得到很大提升。針對函數(shù)f2來說，得到的效果更好，平均收斂率到巨大提升，主要是因為震蕩環(huán)節(jié)的導(dǎo)入。正因為算法的全局搜索性能全面提升，在計算量都一樣的情況下，局部搜索性能就一定會降低，所以平均收斂代數(shù)會有適量提升，總體來說，微粒群里面加入震蕩環(huán)節(jié)，很好地提升了算法的全局搜索性能。

（3）按照相同的原理分析T3（t），結(jié)果作為震蕩環(huán)節(jié)的參數(shù)范圍[h2<14k]，得出相應(yīng)的微粒群算法的框架論述：

Step1.初始化種群和隊形參數(shù)；

Step2.依據(jù)計劃的方程式（12）、（13）、（14）計算微粒速度和位置；

Step3.評價每一個微粒的適應(yīng)度；

Step4.對于每一個微粒，把他的使用值和他經(jīng)歷的最優(yōu)位置作比較，并保留最佳；

Step5.對于每一個微粒，把他的使用值和群體所經(jīng)歷的最佳位置對比，保留最佳；

Step6.最后論證是否滿足結(jié)束條件。如果滿足條件，算法結(jié)束；不滿足條件，轉(zhuǎn)到Step2。

4 結(jié)論

這篇文章主要是運(yùn)用控制理論，通過分析比較三種微粒群算法，推導(dǎo)出速度進(jìn)化方程式僅僅用到了可以用一階微分方程式表示的積分環(huán)節(jié)和慣性環(huán)節(jié)。為了更好地提升全局搜索性能，進(jìn)而提出了可以運(yùn)用二階微分方程表示的震蕩環(huán)節(jié)。發(fā)現(xiàn)，提升速度的利用率，全局收斂性能也得到巨大提升。

參考文獻(xiàn)：

[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].計算機(jī)研究與發(fā)展，2004，41（8）： 1333-1338.