粒子群優化算法進展研究

吳玫

（江蘇城鄉建設職業學院，江蘇 常州 213002）

1 引言

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

2 粒子群優化算法的改進

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

2.1 算法參數的改進

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

2.1.1 改進參數慣性權重W

粒子群優化算法是以種群行為來激勵粒子的運動。每個潛在的解與粒子的速度有關，為使粒子朝著更好的方向發展，需要不斷地根據粒子與鄰居粒子的經驗來調整。

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

①線性調整W：隨著迭代的進行，線性減少W的值。根據公式

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

②非線性調整W：根據相應規則來動態調整W，如一種模糊規則動態調整W的算法[5]，該算法是通過隸屬度函數和模糊規則來確定慣性權重的增量，根據當前最好性能評價，但此方法實現困難，需要專家知識建立模糊規則，計算較復雜。

③隨機選取W：隨機選取的W值，其數學期望值會根據最優解的變化而自適應地調節，因為隨機的W值會使粒子的歷史速度隨機的影響當前的速度。慣性權重的變化由粒子群的進化速度和聚集度綜合決定，受算法運行態勢的影響，因而能提高收斂速度和精度。

2.1.2 改進加速常數C1、C2

加速常數C1、C2代表了粒子的隨機加速權值。通過實驗取非對稱的 C1、C2的變化范圍，發現 C1取 2.75～1.25，C2取 0.50～2.25時，大多數的基準函數都可以獲得相對較好的適應值。

2.1.3 改進進化公式

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

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

2.2 拓撲結構的改進

2.2.1 局部版粒子群

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

2.2.2 空間鄰域法

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

2.2.3 鄰域拓撲法

Kennedy等對粒子群的拓撲結構進行了研究，通過分析粒子間的信息流提出了環形、輪形和星形等一系列的改進的拓撲結構。另外還有動態粒子群拓撲結構。

2.2.4 社會趨同法

Kenney提出了社會趨同法，該算法混合了空間鄰域和環形拓撲，粒子用聚類中心代替個體極值，能提高算法的性能，但也會增加復雜度。

2.3 混合算法

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

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

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

俞歡軍通過對參數進行適當地調節將局部搜索和變異操作同時混合到粒子群算法中，此算法發揮了局部搜索和變異操作的優點。高鷹將模擬退火算法與粒子群算法結合，利用模擬退火較強的跳出局部最優解的能力和粒子群全局尋優能力，實現簡單的優點，提高了進化后期算法的收斂速度和精度。

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

3 結語

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