基于超球面擾動的指導粒子群算法

茅繼晨 楊閏

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

關鍵詞：粒子群算法；多種群初始化策略；指導策略；超球面擾動

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

0 引 言

1995年Kennedy和Eberhart首次提出了粒子群優化算

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

1 改進粒子群算法

1.1 種群迭代

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

（1）

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

1.2 超球面擾動

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

（2）

2 粒子群算法步驟

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

（1）種群初始化。

（2）計算適應度值，選取“精英”。

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

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

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

3 算法測試及結果分析

為了驗證算法的有效性和優越性，通過一些經典的高維多峰測試函數來對算法的性能進行測試。測試函數見表1所列。

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

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

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

4 結 語

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

參考文獻

[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，FU 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.