粒子群優化算法進展研究

吳玫

【摘 要】粒子群優化算法是一種新型的演化算法，概念簡單，參數較少，易于實現，但粒子群算法易陷入局部最優導致收斂變慢。尋求解決實際問題的更加有效的粒子群優化算法是論文研究的目標。論文對粒子群算法的算法參數、拓撲結構及混合算法等方面的改進措施進行了概述，并對粒子群算法進行了展望。

【Abstract】Particle swarm optimization is a new evolutionary algorithm. It is simple in concept， and it has few parameters and is easy to implement. The goal of this paper is to find a more effective particle swarm optimization algorithm to solve practical problems. In this paper， the improvement measures of particle swarm optimization are summarized， including the algorithm parameters， topology and hybrid algorithm.

【關鍵詞】粒子群算法;算法參數;拓撲結構;混合算法

【Keywords】particle swarm algorithm; algorithm parameter; topology; hybrid algorithm

【中圖分類號】TP301.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 【文章編號】1673-1069（2018）12-0167-02

1 引言

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

2 粒子群優化算法的改進

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

2.1 算法參數的改進

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

2.1.1 改進參數慣性權重W

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

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

2.2 拓撲結構的改進

2.2.1 局部版粒子群

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

2.2.2 空間鄰域法

“空間鄰域法”由Suganthan提出，是一種基于粒子的空間位置劃分的方法。在該方法的迭代中，計算每一個粒子與群中其他粒子的距離，任何2個粒子間的最大距離為dmax。如果要計算粒子a的鄰居：對每一粒子b按照||Xa-Xb||/dmax計算一個比值，當b滿足||Xa-Xb||/dmax<farc時，則b成為當前粒子a的鄰居，所有滿足該條件的粒子組成a的鄰域，該方法在絕大多數測試中都能獲得更優良的性能，但因每一次迭代都需要計算每個粒子的鄰域，從而會增加算法的復雜度。

2.2.3 鄰域拓撲法

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

2.2.4 社會趨同法

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

2.3 混合算法

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

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

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

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

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

3 結語

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

【參考文獻】

【1】何慶元，韓傳久.帶有擾動項的改進粒子群算法[J].計算機工程與應用，2007，43（7）：84-86.

【2】張建科.幾類改進的粒子群算法[D].西安：西安電子科技大學，2007.

【3】高海兵.粒子群優化算法及其若干工程應用研究[D].武漢：華中科技大學，2007.

【4】Clerc， M.. The Swarm and the Queen： towards a Deterministic and Adaptive Particle Swarm Optimization[P]. Evolutionary Computation， 1999. CEC 99. Proceedings of the 1999 Congress on，1999.

【5】吳啟迪，汪鐳.智能粒子群算法研究及應用[M].江蘇：江蘇教育出版社，2005.