吳玫

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

1 引言

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

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

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

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

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

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

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

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

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

計(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)前最好性能評價，但此方法實(shí)現(xiàn)困難，需要專家知識建立模糊規(guī)則，計(jì)算較復(fù)雜。

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

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

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

2.1.3 改進(jìn)進(jìn)化公式

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

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

2.2 拓?fù)浣Y(jié)構(gòu)的改進(jìn)

2.2.1 局部版粒子群

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

2.2.2 空間鄰域法

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

2.2.3 鄰域拓?fù)浞?/p>

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

2.2.4 社會趨同法

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

2.3 混合算法

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

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

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

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

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

3 結(jié)語

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