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

吳玫

【摘 要】粒子群優(yōu)化算法是一種新型的演化算法，概念簡單，參數(shù)較少，易于實(shí)現(xiàn)，但粒子群算法易陷入局部最優(yōu)導(dǎo)致收斂變慢。尋求解決實(shí)際問題的更加有效的粒子群優(yōu)化算法是論文研究的目標(biāo)。論文對(duì)粒子群算法的算法參數(shù)、拓?fù)浣Y(jié)構(gòu)及混合算法等方面的改進(jìn)措施進(jìn)行了概述，并對(duì)粒子群算法進(jìn)行了展望。

【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.

【關(guān)鍵詞】粒子群算法;算法參數(shù);拓?fù)浣Y(jié)構(gòu);混合算法

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

【中圖分類號(hào)】TP301.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 【文章編號(hào)】1673-1069（2018）12-0167-02

1 引言

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

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

粒子群算法計(jì)算形式簡單，參數(shù)設(shè)置少且算法收斂性良好，被應(yīng)用到各個(gè)領(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)行的軌跡有著直接的影響，因此，算法的效果與這幾個(gè)參數(shù)有著更直接的關(guān)系[3]。

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

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

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

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

2.2.1 局部版粒子群

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

2.2.2 空間鄰域法

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

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

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

2.2.4 社會(huì)趨同法

Kenney提出了社會(huì)趨同法，該算法混合了空間鄰域和環(huán)形拓?fù)洌Ｗ佑镁垲愔行拇鎮(zhèn)€體極值，能提高算法的性能，但也會(huì)增加復(fù)雜度。

2.3 混合算法

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

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

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

俞歡軍通過對(duì)參數(shù)進(jìn)行適當(dāng)?shù)卣{(diào)節(jié)將局部搜索和變異操作同時(shí)混合到粒子群算法中，此算法發(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ù)和方法上將更通用、更有效。

【參考文獻(xiàn)】

【1】何慶元，韓傳久.帶有擾動(dòng)項(xiàng)的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（7）：84-86.

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

【3】高海兵.粒子群優(yōu)化算法及其若干工程應(yīng)用研究[D].武漢：華中科技大學(xué)，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】吳啟迪，汪鐳.智能粒子群算法研究及應(yīng)用[M].江蘇：江蘇教育出版社，2005.