基于隨機過程的粒子群改進算法

羅 慶 儀 李 秦

（蘭州交通大學數(shù)理學院，甘肅 蘭州 730070）

1 引言

粒子群優(yōu)化算法（Particle Swarm Optimization，簡稱PSO）在Reynold 所提出Boids 模型［1］啟發(fā)下，由Eberhart和Kennedy提出的一種新型群智能優(yōu)化算法［2］.該算法的本質(zhì)是一種隨機并行搜索算法，能以較大的概率收斂于全局最優(yōu)解，且結(jié)構(gòu)簡單，操作方便，易于編程實現(xiàn).自PSO提出之日，便得到了許多學者的關(guān)注，并通過不斷的改進，現(xiàn)已成功應用到許多實際問題中，如鋰電池建模［3］，圖像分割［4］，優(yōu)化控制［5］等等.然而，PSO算法具有容易陷入局部最優(yōu)解和早熟的缺陷，為了克服這些不足，學者們通過對參數(shù)的調(diào)整，改進搜索方法以及增加輔助策略來改進PSO算法，如通過改變慣性權(quán)重［6］增加全局擾動［7］進而提高全局搜索能力，通過改進靜止的粒子的位置選取方式［3］避免陷入局部最優(yōu)的情況，還有一些與其他群智能算法融合的改進方法，如粒子群算法與遺傳算法、模擬退火算法、差分進化算法等的結(jié)合［8］. 本文提出一種基于隨機過程的粒子群優(yōu)化方法（Stochastic Process Particle Swarm Optimization，簡稱SPPSO）.仿真實驗結(jié)果表明，在尋優(yōu)精度，收斂速度，尋優(yōu)正確率等方面SPPSO算法具有優(yōu)越性.

2 基本PSO算法

PSO 算法中，將優(yōu)化問題在搜索空間中的潛在解定義為粒子，所有粒子都有一個由目標函數(shù)所決定的最適值，每個粒子由自己的速度矢量決定自身的飛行距離和方向.粒子最開始在搜索空間中隨機產(chǎn)生，通過追尋自身找到的最優(yōu)位置和整個種群找到的最優(yōu)位置，在解空間中通過不斷的迭代更新自身位置，找到最優(yōu)位置即最優(yōu)解.

假設(shè)在D 維的搜索空間中，有N 個粒子組成一個種群，其中第i 個粒子在第t 步迭代時的位置描述為：

第i 個粒子在第t 步迭代時的速度描述為：

第i 個粒子在第t 步迭代為止搜索到的自身最優(yōu)位置即個體極值描述為：

整個種群到目前為止搜索到的最優(yōu)位置即全局極值描述為：

在搜索到個體極值與全局極值之后，粒子通過如下公式更新自己的位置和速度：

其中i,d 為第i 個變量在d 維上的分量，c1和c2為學習因子，r1和r2是服從區(qū)間［0，1］上均勻分布的隨機變量.

式（1）右端由三項和組成［9］：

第一項“慣性”部分，反應了粒子在運動時候具有慣性，即有保持粒子自身先前速度的運動趨勢，其中ω 稱為慣性權(quán)重，反映了粒子局部和全局的搜索能力［10］.在搜索前期，粒子需要在整個解空間快速搜索，即要求全局搜索能力要強，粒子原有的速度占比就應該大一些，到了搜索后期，粒子的搜索空間會大幅度縮小，那么對局部搜索能力的要求增大，粒子原有的速度占比就應該要小一些.目前關(guān)于慣性權(quán)重選擇的研究已有不少文獻，如自適應權(quán)重法、隨機權(quán)重法、線性遞減權(quán)重法［8］等等，本文采用的是線性遞減權(quán)重法，具體描述公式如下：

其中ωmax和ωmin分別表示最大和最小權(quán)重值，k 表示當前迭代步數(shù)，k_max 表示最大迭代步數(shù).

第二項“認知”部分，反映了粒子對自身最優(yōu)位置的記憶，代表粒子對自身歷史最優(yōu)位置的置信程度，并且有向該位置逼近的趨勢.

第三項“社會”部分，反應了粒子與粒子之間的經(jīng)驗共享和知識交流，代表粒子對種群最優(yōu)位置的置信程度，并且有向該位置逼近的趨勢.

正如式（1）和式（2）所描述，基本粒子群算法單純的依賴整個種群的全局最優(yōu)個體的指導，在解空間搜索最優(yōu)解，常常容易陷入局部最優(yōu)解和早熟的情況［11］.

3 SPPSO算法

針對粒子群算法容易陷入早熟和局部最優(yōu)的情況，本文從三個方面進行改進，提出基于隨機過程的SPPSO.下面分別介紹三種改進策略，分別是采用隨機變量作為學習因子、粒子陷入局部最優(yōu)值時候的掙脫機制以及根據(jù)布朗運動的吸收與反射思想，提出粒子的越邊界處理機制.

3.1 采用隨機變量作為學習因子

本文認為，在搜索空間的粒子應當具有自己的認知和判斷能力，有些粒子會對自身尋找到的最優(yōu)位置的置信度高一些，有些粒子會更相信群體尋找到的最優(yōu)位置，這就導致了不同粒子應該要有不同的學習因子c1和c2.在自然現(xiàn)象和社會現(xiàn)象中，大量隨機變量都服從或者是近似服從高斯分布，鑒于此，本文采用高斯隨機分布生成學習因子. c1和c2的確定方式描述如下：

Step 1：根據(jù)文獻［12］將(c )2 的值取為1.494.

Step 3：將Step 2 生成的隨機變量Lk作為粒子的位置索引，并定義第Lk個粒子的學習因子c1為服從區(qū)間［1，2.988］上均勻分布的隨機變量，相對應的學習因子c2的值則為1.494×2-c1.

3.2 粒子陷入局部最優(yōu)值時候的掙脫機制

表1 6個測試函數(shù)的函數(shù)名、表達式、解空間以及目標值

目標值f4函數(shù)名Rosenbrock表達式f4( )n-1[ ]100( )xi+1-xi x =∑i=1 2+( )xi-12解空間[ ]-30,30 n f5 Ackley x2 i■ ■■■f5( )x =-20e■ ■■■-0.21 n∑i=1■ ■■n-e 1n∑i=1■ ■■cos 2πxi+20+e [ ]-32,32 f6 Griewank f6( )x =1 n ■xi nx2 4000∑i=1i -∏i=1■■ ■■■i+1[ ]-600,600 0 0 0

3.3 引入布朗運動的吸收與反射思想

粒子在解空間中搜索最優(yōu)解時，常常會超出解空間的范圍，從而導致算法不收斂或者是收斂不到目標值，為此，本文引入布朗運動的吸收與反射思想，定義描述［13］如下：

令{ X( t )}是布朗運動，回憶Tx是首次擊中x 的時刻，定義Z( t )為：

其中式（6）表示在布朗運動擊中x 時，就永遠保持，式（7）表示在布朗運動到負半軸時，就以直線y=0 為對稱軸，反射回正半軸.

式（6）和式（7）表明布朗運動在到達某個給定值后會被吸收且布朗運動不允許出現(xiàn)負值.本文借鑒這種思想，對要超過的粒子采取概率吸收或者映射的策略，防止粒子飛出解空間，具體公式描述如下：

其中bound_max,bound_min 分別為邊界的最大最小值，a,r 為服從區(qū)間［0，1］上均勻分布的隨機變量.

3.4 算法實現(xiàn)

本文算法的具體實現(xiàn)流程如下：

Step 1：初始化算法和參數(shù)；

Step 2：計算目標函數(shù)值；

Step 3：獲取粒子局部極值和全局極值；

Step 4：檢查局部極值是否有變化，有則轉(zhuǎn)Step 5，反之則轉(zhuǎn)Step 6；

Step 5：根據(jù)式（1）和式（2）更新粒子速度和位置；

Step 6：根據(jù)式（2）、式（3）、式（4）更新粒子速度、位置和局部極值；

Step 7：檢查粒子是否越界，是則轉(zhuǎn)Step 8，反之轉(zhuǎn)Step 9；

Step 8：根據(jù)式（8）更新粒子位置；

Step 9：是否滿足終止條件（達到最大迭代步數(shù)或者是滿足終止精度），是則轉(zhuǎn)Step 10，反之循環(huán)Step 2～Step 9；

Step 10：輸出并保存結(jié)果，結(jié)束.

4 實驗與結(jié)果分析

本文采用5個經(jīng)典的基準函數(shù)外加一個測試函數(shù)進行仿真實驗，并與標準粒子群算法、慣性權(quán)重線性遞減的粒子群算法在尋優(yōu)精度、收斂速度、尋優(yōu)正確率等方面的性能進行比較.6個目標函數(shù)如表1所示，其中f1為文獻［8］中標準粒子群算法的測試函數(shù)（該函數(shù)主要目的是為了凸顯PSO算法的缺點，故函數(shù)值較其他有所不同）， f2～f6為常用的標準測試函數(shù)［14-15］.

本文在Intel（R）Core（TM）i7-8750H CPU@2.20GHZ 的處理器，16.00GB 的內(nèi)存，windows 10系統(tǒng)的電腦環(huán)境下，利用python 3.7對每個函數(shù)進行20重復獨立的次仿真實驗并求平均值，分別對同一函數(shù)不同算法間收斂時所尋找到的最優(yōu)目標值、迭代步數(shù)和正確率進行數(shù)據(jù)的對比并分析實驗結(jié)果.

部分參數(shù)設(shè)置如下：最大迭代步數(shù)k_max=100，學習因子c1=c2=1.494，最大權(quán)重值w_max=0.9，最小權(quán)重值w_min=0.4（現(xiàn)有的文獻介紹中，最值權(quán)重的設(shè)定往往是根據(jù)經(jīng)驗，其中標準粒子群的權(quán)重設(shè)置為1），函數(shù)維數(shù)dim=30，種群大小M=30.

圖1 測試函數(shù)尋優(yōu)過程曲線圖

圖2 Sphere函數(shù)尋優(yōu)過程曲線圖

圖3 Schwefel 2.22函數(shù)尋優(yōu)過程曲線圖

圖4 Rosenbrock函數(shù)尋優(yōu)過程曲線圖

圖5 Ackley函數(shù)尋優(yōu)過程曲線圖

圖6 Griewank函數(shù)尋優(yōu)過程曲線圖

4.1 尋優(yōu)過程可視化分析

圖1～圖6 是算法在尋優(yōu)過程中，目標函數(shù)值隨著迭代步數(shù)增加而變化的曲線圖.該圖表明，SPPSO算法在迭代過程中，收斂速度明顯快于標準粒子群算法，較線性遞減權(quán)重法也有一定的優(yōu)勢，特別是面對多峰函數(shù)的時候；尋優(yōu)精度也明顯高于標準粒子群算法，在測試函數(shù)的仿真實驗中，SPPSO更是進一步體現(xiàn)了在尋優(yōu)精度上的優(yōu)勢.

圖7 第1次迭代粒子位置圖

圖8 第15次迭代粒子位置圖

圖9 第30次迭代粒子位置圖

4.2 粒子位置分析

圖7～9 是Ackley 函數(shù)（其他函數(shù)的實驗圖類似，這里不再贅述）在第5，10，15 以及20 個粒子第1，15，30次迭代時候的位置變化散點圖.該散點圖表明，在初始階段，粒子幾乎布滿整個解空間，在尋優(yōu)過程中，粒子位置不會超出解空間的邊界范圍.同時，體現(xiàn)了在尋優(yōu)過程中粒子的位置從一開始散亂的分布在整個解空間（如圖7所示），尋優(yōu)過程中有向最優(yōu)位置逼近的趨勢（如圖8所示），以及最后到達最優(yōu)位置（如圖9所示），這樣的一個變化過程.

表2 6個測試函數(shù)收斂時的指標對比

4.3 結(jié)果分析

表2是仿真實驗達所用的6個測試函數(shù)收斂時的指標對比表，該表表明基本粒子群算法收斂速度相較于其他兩種算法就顯得慢了許多，雖然線性遞減法和SPPSO算法都能快速的收斂，但在面對多峰函數(shù)f5和f6時候，SPPSO算法體在收斂速度上較線性遞減法會更勝一籌.而對于搜索到的平均最小值而言，基本粒子群相對其他兩種算法來說，效果最差，誤差也比較明顯，線性遞減法和SPPSO算法總體差異不是很大，但在精度上，SPPSO會較高一些，其中在測試函數(shù)f1中顯得特別明顯.同時，對于這6個測試函數(shù)的仿真實驗，SPPSO算法總能收斂到目標值的誤差許可范圍內(nèi)（允許誤差為1e-6），而基本粒子群算法常常收斂到局部最優(yōu)解，這進一步體現(xiàn)了SPPSO算法在面對陷入局部最優(yōu)解時，掙脫機制的良好性能，當然，較線性遞減法也有一定的優(yōu)勢.

5 結(jié)束語

本文從將隨機變量作為學習因子、增加陷入局部最優(yōu)時的掙脫機制以及增加粒子越邊界處理機制這三個方面對基本粒子群進行改進，使得算法能夠更快速準確地收斂到最優(yōu)目標函數(shù)值.5個經(jīng)典的基準函數(shù)和一個測試函數(shù)的仿真實驗結(jié)果表明，SPPSO 算法相比PSO 算法和權(quán)重線性遞減的PSO 算法，在尋優(yōu)精度、收斂速度以及平均正確率上都有所改善，特別是面對多峰函數(shù)的時候，效果更加明顯.此外，粒子群算法目前已應用于其他算法的優(yōu)化，比如代替?zhèn)鹘y(tǒng)的梯度算法在支持向量機參數(shù)方面的優(yōu)化.本文所提出算法是通過改進粒子群算法，并且優(yōu)于后者，故而有著和粒子群算法同樣的功能，且理論上效果更好.