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

羅 慶 儀 李 秦

（蘭州交通大學數理學院，甘肅 蘭州 730070）

1 引言

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

2 基本PSO算法

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

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

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

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

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

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

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

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

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

其中ωmax和ωmin分別表示最大和最小權重值，k 表示當前迭代步數，k_max 表示最大迭代步數.

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

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

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

3 SPPSO算法

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

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

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

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

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

3.2 粒子陷入局部最優值時候的掙脫機制

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

目標值f4函數名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 引入布朗運動的吸收與反射思想

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

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

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

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

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

3.4 算法實現

本文算法的具體實現流程如下：

Step 1：初始化算法和參數；

Step 2：計算目標函數值；

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

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

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

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

Step 7：檢查粒子是否越界，是則轉Step 8，反之轉Step 9；

Step 8：根據式（8）更新粒子位置；

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

Step 10：輸出并保存結果，結束.

4 實驗與結果分析

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

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

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

圖1 測試函數尋優過程曲線圖

圖2 Sphere函數尋優過程曲線圖

圖3 Schwefel 2.22函數尋優過程曲線圖

圖4 Rosenbrock函數尋優過程曲線圖

圖5 Ackley函數尋優過程曲線圖

圖6 Griewank函數尋優過程曲線圖

4.1 尋優過程可視化分析

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

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

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

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

4.2 粒子位置分析

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

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

4.3 結果分析

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

5 結束語

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