基于超球面擾動的指導(dǎo)粒子群算法

茅繼晨 楊閏

摘 要：粒子群算法（PSO）借助其原理簡單、易于實現(xiàn)的特點，已被應(yīng)用在諸多領(lǐng)域。為了改進基本PSO算法收斂精度低，易陷入局部最優(yōu)的缺點，提出了一種改進的PSO算法。在種群迭代更新中，引入精英指導(dǎo)策略加快粒子的收斂速度；引入超球面擾動策略，加強種群擺脫局部最優(yōu)的能力。通過高維多峰測試函數(shù)進行測試比較，驗證了該算法的優(yōu)越性和有效性。

關(guān)鍵詞：粒子群算法；多種群初始化策略；指導(dǎo)策略；超球面擾動

中圖分類號：TP181 文獻標識碼：A 文章編號：2095-1302（2018）08-00-03

0 引 言

1995年Kennedy和Eberhart首次提出了粒子群優(yōu)化算

法（Particle Swarm Optimization，PSO）[1-2]，該算法自問世以來就被廣泛應(yīng)用于實際問題中。但隨著優(yōu)化問題越來越復(fù)雜，算法的性能改進變得日趨重要，許多學(xué)者都對其做了改進。例如混沌優(yōu)化[3]、參數(shù)變異[4]、混合算法[5]、框架協(xié)同[6]等。這些改進方法都不同程度的提高了算法性能，但都存在局限性。受到啟發(fā)，本文將使用多種優(yōu)化策略取長補短，對算法性能進行改進。

1 改進粒子群算法

1.1 種群迭代

為了增強種群迭代的收斂精度和速度，從新種群中選出“精英”，對其他粒子的步進方向提供指導(dǎo)。“精英”由多個（本文取5個）適應(yīng)度值最好的粒子組成，其他粒子位置的更新在“精英”的指導(dǎo)下完成。“精英”自身的位置仍按照原始公式進行更新。其余粒子位置的更新公式如下所示：

（1）

式中：elite（d）kmin和elite（d）kmax分別表示“精英”中第d維位置信息的最小值和最大值。隨著種群迭代的進行，“精英”也要不斷更新完善才能適應(yīng)種群的指導(dǎo)要求。

1.2 超球面擾動

超球面坐標系統(tǒng)是一個抽象的高維球面坐標。將粒子信息用超球面坐標表示，R表示球面坐標的球面半徑，φ表征角度，保存粒子每一維度的方向夾角。將“精英”的速度轉(zhuǎn)化為超球面坐標，對半徑R做擾動，再進行逆操作轉(zhuǎn)回笛卡爾坐標。在超球面坐標做擾動的好處是只要對半徑做一個擾動就可以改變粒子速度，幫助“精英”跳出局部最優(yōu)，而φ值不變，相當(dāng)于保留了“精英”在之前迭代中學(xué)習(xí)到的經(jīng)驗。具體轉(zhuǎn)化過程如下：

（2）

2 粒子群算法步驟

粒子群算法步驟如下所示：

（1）種群初始化。

（2）計算適應(yīng)度值，選取“精英”。

（3）粒子在“精英”的指導(dǎo)下更新，同時“精英”也不斷更新完善。

（4）評估“精英”，判斷是否需要做擾動，若是，則使用式（2）做擾動，否則進行下一步。

（5）判斷結(jié)果是否符合停止條件，若不符合，則返回步驟（3）；若符合，則終止程序，輸出最優(yōu)解。

3 算法測試及結(jié)果分析

為了驗證算法的有效性和優(yōu)越性，通過一些經(jīng)典的高維多峰測試函數(shù)來對算法的性能進行測試。測試函數(shù)見表1所列。

為了便于比較，選出函數(shù)f1～f4與其他算法進行對比。例如f1函數(shù)，在搜索區(qū)域內(nèi)約有10n個局部最小值；f3函數(shù)有多個對稱分布的全局最優(yōu)點；f4則有幾個不對稱分布的全局最優(yōu)點。為保證數(shù)據(jù)盡可能客觀，本文保留文獻[7-9]中的數(shù)據(jù)和曲線，并采用一樣的設(shè)置：測試函數(shù)的維度為30，粒子25個，迭代次數(shù)為1 000，對每個測試函數(shù)獨立運行25次[10]。將算法與PSO，EPSO[11]，F(xiàn)DRPSO[7]，HEAPSO[8]，CPSO-DA[9]，DPVCPSO[12]，TeamEA[10]等這些改進的PSO算法進行對比。

測試結(jié)果見表2所列。表中列出了每個算法對函數(shù)尋優(yōu)的最佳值（Best）、最差值（Worst）、平均值（Mean）和標準差（Std）。從表中可以看到，在基本函數(shù)中，本文算法對f1，f4尋優(yōu)的平均值最好，對f2和f3的尋優(yōu)效果也在眾多算法中名列前茅。

為了更加直觀地展示本文算法的尋優(yōu)效果，在圖1中列出了HDGPSO與其他算法的收斂軌跡對比圖。從圖中可以看出，HDGPSO在多個函數(shù)的尋優(yōu)過程中保持著較快的收斂速度，雖然在函數(shù)f1，f4中前期收斂速度沒有TeamEA快，但是TeamEA算法在尋優(yōu)的前半階段保持著5個種群同時的并行優(yōu)化，時間復(fù)雜度高，耗時長，就優(yōu)化時間來說，本算法優(yōu)勢較明顯。函數(shù)f2和TeamEA的收斂精度不相上下，但TeamEA結(jié)束收斂的速度較快，而HDGPSO大致保持著收斂的趨勢，如果對收斂精度有要求，HDGPSO優(yōu)勢更加明顯。

4 結(jié) 語

本文提出的基于超球面擾動的指導(dǎo)粒子群算法在多種改進策略的共同作用下，比原有粒子群算法的收斂速度和收斂精度都有所提高。通過一些高維多峰的函數(shù)測試，證明了HDGPSO對復(fù)雜函數(shù)的尋優(yōu)有較好的效果。

參考文獻

[1] KENNEDY J，EBERHART R. Particle swarm optimization[C]// IEEE International conference on neural networks，1995. Proceedings. IEEE，2002：1942-1948.

[2] EBERHART R，KENNEDY J. A new optimizer using particle swarm theory[C]// International symposium on MICRO machine and human science. IEEE，2002：39-43.

[3] XUN Z，LI J，XING J，et al. The impact of parameter adjustment strategies on the performance of particle swarm optimization algorithm[C]//Control and decision conference. IEEE，2015：5206-5211.

[4] ABD‐ELAZIM S M，ALI E S. A hybrid particle swarm optimization and bacterial foraging for power system stability enhancement[J]. International journal of electrical power & energy systems，2013，46（2）：334-341.

[5] WANG Y S，JINGBO A I，SHI Y J，et al. Cultural-based particle swarmoptimization algorithm[J]. Journal of dalian university of technology，2007，47（4）：539-544.

[6] B?CK T. Evolutionary algorithms in theory and practice：evolution strategies，evolutionary programming，genetic algorithms[M].Oxford univ. Pr，1998.

[7] PERAM T，VEERAMACHANENI K，MOHAN C K. Fitness-distance-ratio based particle swarm optimization[C]// Swarm intelligence symposium，2003. Sis '03. Proceedings of the IEEE，2003：174-181.

[8] SABAT S L，ALI L. The hyperspherical acceleration effect particle swarm optimizer[J]. Applied soft computing，2009，9（3）：906-917.

[9] WANG R Y，HSIAO Y T，LEE W P. A new cooperative particle swarm optimizer with dimension partition and adaptive velocity control[C]// IEEE International conference on systems，man and cybernetics. IEEE，2012：103-109.

[10]陳偉，項鐵銘，徐捷.基于PSO的隊伍演化算法[J].模式識別與人工智能，2015，28（6）：521-527.

[11] ZHANG Y，ZHAO Y，F(xiàn)U X，et al. A feature extraction method of the particle swarm optimization algorithm based on adaptive inertia weight and chaos optimization for brillouin scattering spectra[J].Optics communications，2016，376：56-66.

[12] HSIAO Y T，LEE W P，WANG R Y. A hybrid approach of dimension partition and velocity control to enhance performance of particle swarm optimization[J]. Soft computing，2014，18（12）：2501-2523.

[13] KROHLING R A，COELHO L D S. PSO-E：Particle swarm with exponential distribution[C]// Evolutionary computation，2006. CEC 2006. IEEE congress on. IEEE，2006：1428-1433.