羅 慶 儀 李 秦

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

1 引言

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

2 基本PSO算法

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

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

第i 個(gè)粒子在第t 步迭代時(shí)的速度描述為：

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

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

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

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

式（1）右端由三項(xiàng)和組成［9］：

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

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

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

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

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

3 SPPSO算法

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

3.1 采用隨機(jī)變量作為學(xué)習(xí)因子

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

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

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

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

表1 6個(gè)測試函數(shù)的函數(shù)名、表達(dá)式、解空間以及目標(biāo)值

目標(biāo)值f4函數(shù)名Rosenbrock表達(dá)式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ùn)動(dòng)的吸收與反射思想

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

令{ X( t )}是布朗運(yùn)動(dòng)，回憶Tx是首次擊中x 的時(shí)刻，定義Z( t )為：

其中式（6）表示在布朗運(yùn)動(dòng)擊中x 時(shí)，就永遠(yuǎn)保持，式（7）表示在布朗運(yùn)動(dòng)到負(fù)半軸時(shí)，就以直線y=0 為對(duì)稱軸，反射回正半軸.

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

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

3.4 算法實(shí)現(xiàn)

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

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

Step 2：計(jì)算目標(biāo)函數(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：是否滿足終止條件（達(dá)到最大迭代步數(shù)或者是滿足終止精度），是則轉(zhuǎn)Step 10，反之循環(huán)Step 2～Step 9；

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

4 實(shí)驗(yàn)與結(jié)果分析

本文采用5個(gè)經(jīng)典的基準(zhǔn)函數(shù)外加一個(gè)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，并與標(biāo)準(zhǔn)粒子群算法、慣性權(quán)重線性遞減的粒子群算法在尋優(yōu)精度、收斂速度、尋優(yōu)正確率等方面的性能進(jìn)行比較.6個(gè)目標(biāo)函數(shù)如表1所示，其中f1為文獻(xiàn)［8］中標(biāo)準(zhǔn)粒子群算法的測試函數(shù)（該函數(shù)主要目的是為了凸顯PSO算法的缺點(diǎn)，故函數(shù)值較其他有所不同）， f2～f6為常用的標(biāo)準(zhǔn)測試函數(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對(duì)每個(gè)函數(shù)進(jìn)行20重復(fù)獨(dú)立的次仿真實(shí)驗(yàn)并求平均值，分別對(duì)同一函數(shù)不同算法間收斂時(shí)所尋找到的最優(yōu)目標(biāo)值、迭代步數(shù)和正確率進(jìn)行數(shù)據(jù)的對(duì)比并分析實(shí)驗(yàn)結(jié)果.

部分參數(shù)設(shè)置如下：最大迭代步數(shù)k_max=100，學(xué)習(xí)因子c1=c2=1.494，最大權(quán)重值w_max=0.9，最小權(quán)重值w_min=0.4（現(xiàn)有的文獻(xiàn)介紹中，最值權(quán)重的設(shè)定往往是根據(jù)經(jīng)驗(yàn)，其中標(biāo)準(zhǔn)粒子群的權(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)過程中，目標(biāo)函數(shù)值隨著迭代步數(shù)增加而變化的曲線圖.該圖表明，SPPSO算法在迭代過程中，收斂速度明顯快于標(biāo)準(zhǔn)粒子群算法，較線性遞減權(quán)重法也有一定的優(yōu)勢，特別是面對(duì)多峰函數(shù)的時(shí)候；尋優(yōu)精度也明顯高于標(biāo)準(zhǔn)粒子群算法，在測試函數(shù)的仿真實(shí)驗(yàn)中，SPPSO更是進(jìn)一步體現(xiàn)了在尋優(yōu)精度上的優(yōu)勢.

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

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

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

4.2 粒子位置分析

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

表2 6個(gè)測試函數(shù)收斂時(shí)的指標(biāo)對(duì)比

4.3 結(jié)果分析

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

5 結(jié)束語

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