基于RMSprop的粒子群優(yōu)化算法

張?zhí)鞚?，李元香，項正龍，李夢?/p>

(武漢大學 計算機學院，湖北 武漢 430072)

0 引 言

粒子群算法(particle swarm optimization，PSO)[1]是由Kennedy和Eberhart提出的一種結構簡單、收斂速度快的進化算法。在粒子群算法中，每個解都表示為種群的一個飛行粒子，根據歷史最優(yōu)和全局最優(yōu)更新當前位置。粒子群算法的優(yōu)點在于收斂速度快、尋優(yōu)能力強、算法簡單易實現(xiàn)。但粒子群算法容易出現(xiàn)收斂過早、陷入局部最優(yōu)的現(xiàn)象。為了解決此缺點，近些年學者提出了很多改進思想。一類是融合其它算法提高，利用其它算法的優(yōu)勢提高其尋優(yōu)能力。文獻[2]中將分群策略、混沌優(yōu)化算法與粒子群算法結合，改善了算法易陷入早熟的問題。文獻[3]中將基于PID控制器的控制理論思想和粒子群算法結合，能夠讓粒子群算法在收斂中調整搜索方向以擺脫局部最優(yōu)。另一類是改進算法本身，文獻[4]提出基于近鄰粒子交流的粒子群算法；文獻[5]提出了基于自適應高斯分布的簡化粒子群算法，使用自適應調節(jié)策略強化局部搜索能力；文獻[6]提出了自適應慣性權重的粒子群優(yōu)化算法，利用粒子聚集度、迭代次數(shù)來動態(tài)改變慣性權重，以此來平衡局部尋優(yōu)能力和全局尋優(yōu)能力；文獻[7]提出了改進后的自適應慣性權重粒子群算法，利用神經網絡中神經元的非線性函數(shù)建立數(shù)學模型，提高了算法的穩(wěn)定性和收斂速度；文獻[8]將混沌優(yōu)化算法和粒子群算法結合，提出了一種在搜索過程中動態(tài)修正的混沌動態(tài)權值粒子群優(yōu)化算法。不同策略的改進算法都在一定程度上提高了粒子群的收斂速度，但還是避免不了在粒子后期尋優(yōu)的過程中，隨著粒子差異性減小，收斂速度下降，無法跳出局部最優(yōu)的情況。

粒子群算法屬于優(yōu)化算法一個分支，而經典優(yōu)化算法在近年取得了更多的發(fā)展和應用。在機器學習[9]領域，經典的梯度下降[10]算法是求解最優(yōu)化問題中最典型的方法。隨機梯度下降算法(stochastic gradient descent，SGD)源于1951年Robbins和Monro提出的隨機選擇一個或者幾個樣本的梯度替代總體梯度，從而降低了計算復雜度。后續(xù)改進策略包括經典動量算法(classical momentum，CM)、Nestero梯度算法(Nesterov’s accelerated gradient，NAG)[11]、Adam(adaptive moment estimation)[12]和Nadam(Nesterov-accelerated adaptive moment estimation)[13]等。文獻[14]將Adam算法優(yōu)化思路與粒子群位置更新相結合，提出了Adam和PSO結合的混合算法AdamPSO，使用Adam方法拓展求解空間進行多一步搜索，提高了粒子群算法的收斂速度。因此，我們可以借鑒經典優(yōu)化算法中的思想來改進和拓展粒子群算法。

本文則是借鑒了在機器學習梯度下降算法中，學習率自適應變化的思想。與粒子群算法中慣性權重的設置相結合，提出了一種自適應慣性權重的粒子群算法(RMSPSO)。根據每個粒子每個維度的迭代變化設置恰當?shù)膽T性權重，提高粒子的局部和全局搜索能力。通過選取對比算法在經典的測試函數(shù)進行驗證比較分析，結果表明本文提出的RMSPSO在大部分情況下取得了更好的結果，加快了收斂速度的同時還保持了更高的精度。

1 粒子群算法和RMSprop算法

1.1 粒子群算法

(1)

(2)

其中，ω是慣性權重系數(shù)，慣性權重決定了粒子歷史飛行速度對當前飛行速度的影響程度。c1是粒子在其歷史搜索中找到的最優(yōu)值的權重系數(shù)，通常設為2；c2是粒子在群體搜索中找到最優(yōu)值的權重系數(shù)，通常設為2，c1和c2通常稱為加速度常數(shù)。r1和r2是(0,1)范圍內的兩個隨機分布值。

基本粒子群算法流程見表1。

表1 粒子群算法流程

1.2 RMSprop算法[15]

在機器學習中，學習率的選擇對最終的結果有很大的影響。太小的學習率會導致收斂緩慢，太大的學習率會導致波動增大，妨礙收斂到最優(yōu)解。目前可采用的方法是在訓練過程中調整學習率的大小，如模擬退火[16]算法：預先定義一個迭代次數(shù)m，每迭代m次便減小學習率，或者當適應值函數(shù)低于一個閾值便減小學習率，然而迭代次數(shù)和閾值需要提前定義，因此無法適應數(shù)據的特點。

在SGD和Nesterov Momentum[17]中，對于所有參數(shù)使用相同的學習率。AdaGrad算法[18,19]的思想是：每一次更新參數(shù)，不同參數(shù)使用不同的學習率。如式(3)和式(4)所示。其中α是學習率，默認值為0.001。εt是為了防止分母為0的參數(shù)，默認值為1e-6

(3)

(4)

AdaGrad在實際使用中發(fā)現(xiàn)，從訓練開始累計梯度的平方會導致學習率過早的減小，使得訓練提前結束。

RMSprop為了克服AdaGrad的缺點，只累計過去w窗口大小的梯度，采用指數(shù)加權平均，如式(5)所示，ρ是指數(shù)加權參數(shù)，一般取0.9

(5)

該算法更新下一位置采用式(6)所示，其中α是學習率，默認值為0.001，εt是為了防止分母為0的參數(shù)，默認值為1e-6

(6)

RMSprop相當于計算之前所有梯度平方對應的平均值，可緩解AdaGrad算法學習率下降較快的問題。

2 RMSprop算法在粒子群算法上的應用

2.1 基于RMSprop算法的粒子群算法

(7)

針對粒子群算法存在的這個問題，我們借鑒RMSprop算法的思想，提出了一種基于RMSprop算法的自適應慣性權重取值策略。自適應慣性權重能夠根據不同粒子不同維度的搜索信息而提供合適的取值，因此可以得到更快的收斂速度和更好的求解精度。

gij=gbesti-xij

(8)

隨著迭代次數(shù)的增加，每個粒子i都趨向群體最優(yōu)位置，則粒子i的梯度gij逐漸減小。因此，我們采用指數(shù)加權平均，采用式(9)更新當前維度的梯度和累加∑[g2]t。ρ是加權系數(shù)，取值為(0,1)之間

(9)

最后，按照式(10)更新粒子i維度j上的慣性權重ωij，其中α和β是調節(jié)系數(shù)，α取值為(90,100)，β取值為(0.4,0.5)

(10)

從粒子群中的某些維度的粒子來看，在迭代過程中某些粒子當前維度全局最優(yōu)gbestj到xij的距離gij較大，粒子這一維度的慣性權重ωij就相對較大，有利于粒子探索更多區(qū)域；某些粒子當前維度全局最優(yōu)gbestj到xij的距離gij較小，粒子這一維度的慣性權重ωij則相對較小，有利于局部挖掘。

從粒子群的粒子群體來看，在粒子群算法初期，粒子當前維度全局最優(yōu)gbestj到xij的距離gij較大，計算的慣性權重ωij較大，有利于粒子全局探索；在粒子群算法末期，粒子當前維度全局最優(yōu)gbestj到xij的距離gij較小，計算的慣性權重ωij較小，有利于局部挖掘，找到最優(yōu)解。從而該策略保證了粒子群的多樣性和收斂性。

2.2 算法流程

改進的粒子群算法與基本的粒子群算法流程相似，只是在基本粒子群算法的基礎上，對慣性權重進行自適應更新，具體的算法流程見表2。

表2 RMSPSO算法流程

3 數(shù)值實驗和對比分析

為了驗證基于RMSprop算法的粒子群算法RMSPSO的收斂性能。本文選取了經典的數(shù)值優(yōu)化函數(shù)進行了實驗驗證，包括單峰函數(shù)、多峰函數(shù)和組合函數(shù)。同時與經典PSO算法GPSO、經典改進算法LPSO、基于CAS理論的粒子群優(yōu)化算法DAPSO[20]、基于自適應高斯分布的簡化粒子群算法IPSO3進行對比實驗。

3.1 實驗條件及結果

數(shù)值優(yōu)化問題引入了10個數(shù)值優(yōu)化測試函數(shù)。分別是經典的測試函數(shù)Sphere函數(shù)和Ellipsoid和CEC 2013測試函數(shù)集中的6、12、13、18、21、23、24、28號函數(shù)。分別記為f1、f2、f3、f4、f5、f6、f7、f8、f9、f10。 其中f1和f2是單峰函數(shù)，f3、f4、f5、f6是多峰函數(shù)，f7、f8、f9、f10是組合函數(shù)。以完整檢測算法的收斂速度、脫離局部最優(yōu)的能力和在較小梯度下的收斂能力。測試函數(shù)的定義、取值范圍和最優(yōu)解詳見表3。

表3 數(shù)值優(yōu)化測試問題

在本節(jié)中,將RMSPSO算法和GPSO、LPSO、DAPSO、IPSO3進行比對實驗。所有實驗的粒子種群為20，每個函數(shù)的最大迭代次數(shù)為5000。PSO慣性系數(shù)ω從0.9到0.5隨代數(shù)衰減，加速度常數(shù)c1和c2設置為2.0。LPSO的參數(shù)φ和χ采用默認參數(shù)2.01和0.729 844。對測試函數(shù)分別在30維和50維進行測試，每個函數(shù)獨立運行50次，記錄實驗結果的平均值和方差。

3.2 實驗結果分析

為了更加清晰、直觀觀察改進后的粒子群算法 RMSPSO 的收斂效果，通過10個測試函數(shù)的實驗仿真圖來比較RMSPSO、GPSO、LPSO、DAPSO和IPSO3這5種不同粒子群算法的收斂情況。如圖1～圖3所示。

圖1 f1測試函數(shù)維度=30

圖2 f2測試函數(shù)維度=30

圖3 f3～f10測試函數(shù)維度=30

圖1和圖2反映了單峰函數(shù)f1和f2在30維度上的實驗對比結果。通過實驗結果可以明顯發(fā)現(xiàn)，RMSPSO相比GPSO、DAPSO和IPSO3可以在算法早期維持更高收斂速度，在迭代完成后，收斂精度大幅度提高。在迭代中后期，RMSPSO相比LPSO尋優(yōu)能力更強?？梢缘贸鯮MSPSO在單峰函數(shù)上尋優(yōu)精度大幅提高，在算法前期、中期和后期始終保持更高的收斂速度，算法尋優(yōu)效果大幅增強。

圖3反映了多峰函數(shù)f3、f4、f5、f6和組合函數(shù)f7、f8、f9、f10在30維度上的實驗比對結果。

可知在多峰函數(shù)f3、f4、f5、f6上RMSPSO相比GPSO、LPSO、DAPSO和IPSO3大多取得了更好的收斂精度。充分說明了RMSPSO解決某些多峰函數(shù)的優(yōu)越性，跳出局部最優(yōu)能力更強?？芍趶碗s的組合函數(shù)f7、f8、f9、f10上RMSPSO相比GPSO、LPSO、DAPSO和IPSO3上大多也取得了更好的收斂精度，也充分說明了RMSPSO解決某些組合函數(shù)的優(yōu)越性，解決復雜函數(shù)能力更強。

算法多次運行的最優(yōu)解均值和最優(yōu)解方差是衡量算法性能的重要指標。將GPSO、LPSO、IPSO3、DAPSO和RMSPSO分別在30維度和50維度的10個測試函數(shù)上運行50次，取平均最優(yōu)解和最優(yōu)解方差，運算結果見表4。

由表4可以看出，分別在30維度和50維度在測試函數(shù)f1～f10上執(zhí)行50次數(shù)值實驗后得到的平均值和平均方差中，30維度下RMSPSO最優(yōu)解均值取得了8個最優(yōu)，最優(yōu)解方差取得了5個最優(yōu)；在50維度下RMSPSO最優(yōu)解均值取得了8個最優(yōu)，最優(yōu)解方差取得了7個最優(yōu)。在非最優(yōu)解的情況下，RMSPSO計算的結果與最優(yōu)解相差較小。因此可以充分支持本文提出的算法在單峰問題、多峰問題和組合問題上大部分能夠取得較好的實驗結果。與GPSO、DAPSO和IPSO3相比，結果有較大提升。在少數(shù)測試函數(shù)上，與LPSO不相上下。由此可以驗證本文提出的賦予粒子自適應權重的改進PSO算法增強了粒子在迭代過程中的尋優(yōu)能力，加快了算法的收斂速度，提高了算法的收斂精度。

從整體的實驗效果上看，本文提出的改進算法RMSPSO在單峰、多峰、組合等數(shù)值優(yōu)化問題上都具備一定的適應性。從實驗統(tǒng)計結果中平均值可以分析得出，本文提出的改進算法RMSPSO在大部分測試函數(shù)的多個維度上可以取得更優(yōu)的計算結果，這充分說明了本文對每個粒子每個維度設置自適應慣性權重提高了粒子的尋優(yōu)能力，從而更易跳出局部最優(yōu)找到更優(yōu)值，提高了算法的收斂能力和計算精度。從實驗統(tǒng)計結果中5個算法運行的最優(yōu)解方差可以分析得出，本文提出的改進算法RMSPSO在具備更好的收斂能力的同時，計算結果方差更小，計算結果更加穩(wěn)定，這充分說明了本文提出的RMSPSO具備更佳的魯棒性。

4 結束語

在粒子群算法中，速度由慣性權重乘以上一代速度加上到局部最優(yōu)和全局最優(yōu)的距離更新而來，其中慣性權重ω隨迭代次數(shù)遞減。而在機器學習梯度下降算法Momentum引入了動量的概念，下一梯度由學習率乘以歷史梯度加上當前梯度更新而來。可以發(fā)現(xiàn)兩種算法具有一定的相似性，而基于Momentum改進算法RMSprop是一種自適應學習率方法。因此，本文將RMSprop的自適應學習率的設置策略與粒子群算法相結合，提出了一種自適應慣性權重的粒子群算法RMSPSO。根據每個粒子每一維度上位置的變化設置合適的慣性權重，因此在每一代中不同粒子和不同維度的慣性權重都不同。相比原始粒子群算法，結合自適應慣性權重的粒子群算法能夠根據粒子各個維度上的變化設置慣性權重，提高了粒子的尋優(yōu)能力。實驗結果表明，本文提出的改進算法RMSPSO在單峰、多峰、組合數(shù)值優(yōu)化問題多數(shù)可以得到比粒子群算法GPSO、改進粒子群算法LPSO、DAPSO和IPSO3更好的結果。這說明本文提出的改進算法RMSPSO在提高粒子尋優(yōu)能力和加快算法收斂速度和精度上有明顯的效果。本文只是將自適應慣性權重設置策略應用于傳統(tǒng)粒子群算法，后續(xù)工作將著重于研究將自適應慣性權重設置策略和其它粒子群優(yōu)化算法相結合，進一步驗證本文提出改進策略的普適性。

表4 粒子群算法在30維和50維的f1～f10測試函數(shù)上的實驗結果