粒子群優(yōu)化算法進展研究

吳玫

（江蘇城鄉(xiāng)建設(shè)職業(yè)學(xué)院，江蘇 常州 213002）

1 引言

粒子群優(yōu)化算法由Eberhart博士和Kennedy博士提出[1]，是一種源于對鳥群捕食行為的研究而發(fā)明的進化計算技術(shù)，后來演化為一種簡單有效的優(yōu)化計算技術(shù)，也是EA中一項新發(fā)展起來的技術(shù)。由于對粒子群優(yōu)化算法的研究時間較短，尚缺乏理論基礎(chǔ)，一些參數(shù)也需要根據(jù)具體問題依經(jīng)驗而定，更多深入細致的工作還有待進一步展開。

2 粒子群優(yōu)化算法的改進

粒子群算法計算形式簡單，參數(shù)設(shè)置少且算法收斂性良好，被應(yīng)用到各個領(lǐng)域。但在應(yīng)用的過程中，發(fā)現(xiàn)粒子群算法易陷入局部，得不到最優(yōu)解且收斂速度慢[2]，因此，各種改進的粒子群優(yōu)化算法被相繼研究如何提高粒子群的求解性能和速度。

2.1 算法參數(shù)的改進

粒子群算法中的參數(shù)很多，其中，粒子種群大小M，粒子的最大速度Vmax等可以采用數(shù)值實驗的方法來確定大致范圍，而慣性權(quán)重W和加速常數(shù)C1、C2粒子運行的軌跡有著直接的影響，因此，算法的效果與這幾個參數(shù)有著更直接的關(guān)系[3]。

2.1.1 改進參數(shù)慣性權(quán)重W

粒子群優(yōu)化算法是以種群行為來激勵粒子的運動。每個潛在的解與粒子的速度有關(guān)，為使粒子朝著更好的方向發(fā)展，需要不斷地根據(jù)粒子與鄰居粒子的經(jīng)驗來調(diào)整。

目前對W參數(shù)較典型的改進主要有[4]：

①線性調(diào)整W：隨著迭代的進行，線性減少W的值。根據(jù)公式

計算，使粒子在初期能較快更新搜索區(qū)域，搜索到較大的解空間，從而加快收斂速度。

②非線性調(diào)整W：根據(jù)相應(yīng)規(guī)則來動態(tài)調(diào)整W，如一種模糊規(guī)則動態(tài)調(diào)整W的算法[5]，該算法是通過隸屬度函數(shù)和模糊規(guī)則來確定慣性權(quán)重的增量，根據(jù)當(dāng)前最好性能評價，但此方法實現(xiàn)困難，需要專家知識建立模糊規(guī)則，計算較復(fù)雜。

③隨機選取W：隨機選取的W值，其數(shù)學(xué)期望值會根據(jù)最優(yōu)解的變化而自適應(yīng)地調(diào)節(jié)，因為隨機的W值會使粒子的歷史速度隨機的影響當(dāng)前的速度。慣性權(quán)重的變化由粒子群的進化速度和聚集度綜合決定，受算法運行態(tài)勢的影響，因而能提高收斂速度和精度。

2.1.2 改進加速常數(shù)C1、C2

加速常數(shù)C1、C2代表了粒子的隨機加速權(quán)值。通過實驗取非對稱的 C1、C2的變化范圍，發(fā)現(xiàn) C1取 2.75～1.25，C2取 0.50～2.25時，大多數(shù)的基準函數(shù)都可以獲得相對較好的適應(yīng)值。

2.1.3 改進進化公式

主要是更新速度公式。利用個體平均極值取代算法中的個體極值，使粒子獲得更多其他粒子的有用信息，從而提高收斂穩(wěn)定性和精度。將全局最優(yōu)模型與局部最優(yōu)模型結(jié)合得到一種復(fù)合模型的算法。速度更新公式為：

其中，c1=2，c2+c3=2。

2.2 拓撲結(jié)構(gòu)的改進

2.2.1 局部版粒子群

粒子群有全局版和局部版兩種。與全局版選擇整個種群作為粒子鄰居不同的是，局部版選擇其中一部分作為粒子的鄰居，局部極值是所有鄰居中的最好解，每個粒子追隨個體極值和局部極值。

2.2.2 空間鄰域法

“空間鄰域法”由Suganthan提出，是一種基于粒子的空間位置劃分的方法。在該方法的迭代中，計算每一個粒子與群中其他粒子的距離，任何2個粒子間的最大距離為dmax。如果要計算粒子a的鄰居：對每一粒子b按照||Xa-Xb||/dmax計算一個比值，當(dāng)b滿足||Xa-Xb||/dmax

2.2.3 鄰域拓撲法

Kennedy等對粒子群的拓撲結(jié)構(gòu)進行了研究，通過分析粒子間的信息流提出了環(huán)形、輪形和星形等一系列的改進的拓撲結(jié)構(gòu)。另外還有動態(tài)粒子群拓撲結(jié)構(gòu)。

2.2.4 社會趨同法

Kenney提出了社會趨同法，該算法混合了空間鄰域和環(huán)形拓撲，粒子用聚類中心代替?zhèn)€體極值，能提高算法的性能，但也會增加復(fù)雜度。

2.3 混合算法

粒子群優(yōu)化算法容易早熟收斂、局部尋優(yōu)能力差，這基本上是所有隨機算法都有的弊病，而模擬退火算法、直接搜索法、梯度法、爬山法等一些優(yōu)化算法卻具有很強的局部搜索能力，因此，混合粒子群算法是改進粒子群算法的一個研究方向。

Nocl等人提出了利用梯度信息的混合粒子群算法，使算法搜索到局部最優(yōu)點，并且節(jié)省了比較的計算量，加快了收斂速度。Wachowiak等人提出在粒子群算法中嵌入Powell方法，提高了解的精度。

Shi等人提出將遺傳算法與粒子群算法混合，并介紹了兩種混合方法：粒子群遺傳并行混合進化算法(PGPHEA)和粒子群遺傳串行混合進化算法(PGSHEA)。

俞歡軍通過對參數(shù)進行適當(dāng)?shù)卣{(diào)節(jié)將局部搜索和變異操作同時混合到粒子群算法中，此算法發(fā)揮了局部搜索和變異操作的優(yōu)點。高鷹將模擬退火算法與粒子群算法結(jié)合，利用模擬退火較強的跳出局部最優(yōu)解的能力和粒子群全局尋優(yōu)能力，實現(xiàn)簡單的優(yōu)點，提高了進化后期算法的收斂速度和精度。

除此，目前還有自適應(yīng)粒子群算法、帶收縮因子的粒子群算法、離散粒子群算法以及協(xié)同粒子群、隨機粒子群、智能粒子群等改進的粒子群算法。

3 結(jié)語

粒子群優(yōu)化算法是一種新型的演化算法，其概念簡單，參數(shù)較少，易于實現(xiàn)，自提出以來就被廣泛研究與應(yīng)用。但粒子群算法無論是理論還是實踐都尚未成熟，存在隨機性強，易陷入局部最優(yōu)導(dǎo)致收斂慢、精度低等問題。因此，尋求更加有效的粒子群改進算法是很有意義的。近年來，粒子群算法的改進引入了許多新的數(shù)學(xué)工具，吸收了生物學(xué)的最新成果，隨著新技術(shù)的進步與研究的深入，粒子群算法在操作技術(shù)和方法上將更通用、更有效。