學習因子隨權重調整的混合粒子群算法

曹曉月，張旭秀

(大連交通大學 電氣信息工程學院，遼寧 大連 116021)

0 引 言

粒子群算法(particle swarm optimization，PSO)是Kennedy和Eberhart教授于1995年聯合提出的一種基于群體智能的隨機進化優化算法[1]。PSO算法因其需要調整的參數較少、收斂速度快、精度高等優點被快速接受并運用在電磁優化[2-3]、參數優化[4-5]和電力系統[6]等領域。對粒子群算法的改進也層出不窮。其中對慣性權重和學習因子的改進最為簡單快捷。Shi等人引入隨進化次數而線性遞減的慣性權重w[7]，這使得PSO算法的運行速度和搜索能力得到了大幅度提升。文獻[8]中通過隨機分布的方式獲取慣性權重，文獻[9-10]將sigmoid函數引入到慣性權重中構造動態調整因子，這些都提高了算法的全局和局部的搜索能力。有的學者將學習因子進行改進[11-13]。

但是慣性權重和學習因子等參數的獨立調整削弱了算法的智能性。該文結合對上述文獻中對粒子群算法改進的分析，使學習因子隨慣性權重非線性變化，并且加入差分進化算法中的交叉算子來增加種群多樣性，并對算法進行復雜性分析。最后同相關算法進行對比，證明算法的有效性。

1 基本粒子群算法

PSO算法首先初始化一群粒子Xi=(xi1,xi2,…,xin)，在每一次迭代過程中，粒子通過個體極值pbest和全局極值gbest更新自身的速度和位置，更新公式如下：

(2)

其中，w為慣性權重，表示粒子繼承了當前速度的程度，w越大，全局的搜索能力越強，w越小，局部的搜索能力越強；c1,c2為速度因子，其中c1是“自我認知”，表示粒子向自我的學習能力強弱，其中c2是“社會認知”，表示粒子向社會的學習能力強弱；rand1和rand2是分布在[0,1]之間的隨機數;t為當前迭代次數；vid為粒子的運行速度。粒子群算法存在的主要問題是隨著迭代次數的增加，搜索速度變慢和易陷入局部尋優。而w則是控制速度和全局搜索的重要因素，學習因子反映了微粒之間的交流情況，平衡了算法的全局探測和局部開采的能力。因此，對慣性權重和學習因子的改進使具有重要意義。

2 改進的粒子群算法

2.1 狀態因子的提出

粒子在每次迭代都是將當前值與最優值比較，更新出全局最優值。但并不是所有粒子都具有這種趨向最優的特性。在搜索過程中，總會有一些粒子會離最優值較遠或者集中于一個“自認為”最優的區域進行搜索。這時，就需要統籌兼顧所有粒子，用類似數學上的方差來表示粒子的當前質量。則提出粒子狀態因子如下：

(3)

全局最優值的取值決定于個體極值的變化，全局和個體的關系也反映了粒子的當前狀態。在求極小值問題時，個體極值要小于全局最優值，當然也小于平均值。平均值反映了所有粒子的平均質量。

2.2 慣性權重的改進

Shi等人[7]提出線性遞減w的方法，實驗表明雖然LDW在函數優化速度和精度方面有了提升，但是隨迭代次數改變的慣性權重的方法對于最優解附近才有效。如果搜索初期沒有找到最優解，隨著搜索次數的增加，慣性權重逐漸減小，局部的搜索能力增強，粒子就會跳過最優解而陷入局部最優。該文提出了一種新的慣性權重更新公式，使慣性權重隨粒子的迭代次數和搜索狀態進行更新。公式如下：

(4)

2.3 學習因子的改進

粒子在搜索過程中通過跟蹤個體最優值和全局最優值進行更新，所以加強粒子個體之間和全局之間的交流對提高算法速度有著重要意義。通過借鑒對學習因子已有的研究發現，w和c1，c2的關系變化如圖1和圖2所示。

圖1 w-t變化曲線

圖2 c1-t變化曲線

由圖分析可知，c1與w的關系類似于logistic回歸分析，圖形是一個s型變化曲線，二者呈正相關變化。并且滿足:

綜上，將w表示為c1的函數，并且滿足c1+c2=2.5。c1和c2的更新規則如下：

(5)

其中，c1采用logistic回歸曲線方程，這個函數滿足了中期隨w快速變化，加快算法的速度；后期緩慢變化，配合w進行精細搜索，平衡算法的全局和局部的搜索能力。c1+c2=2.5，是此消彼長設置。前期c1較大而c2較小，此時粒子的自我學習能力較強而社會學習能力較弱，有利于加強算法的全局搜索；后期c1較小而c2較大，此時粒子的社會學習能力較強而自我學習能力較弱，有利于算法局部的精細搜索。

3 種群多樣性的保持

粒子群算法的缺陷之一是隨著搜索的進行多樣性會降低，并且隨著上述提出的非線性因子的加入，粒子多樣性缺失會更加嚴重，導致陷入局部尋優。為了解決這一現象，加入差分進化算法中的交叉算子來提高算法的全局探索能力，保持種群多樣性，利用DE算法的變異策略產生候選解來更新位置公式。

3.1 變異策略的加入

差分進化算法是基于種群的隨機優化算法[14-15]，此算法在同一種群中將父代個體和其他個體之間通過交叉得到差異信息，從而獲得候選解。

變異操作的主要目的是生成變異個體。該文采用策略一來產生變異個體。變異策略如下：

3.2 交叉算子的加入

圖3 5維向量交叉原理示意圖

綜上提出新的位置更新公式：

(6)

r1,r2,r3∈{1,2,…,N}是隨機的三個個體且互不相同。這里縮放因子F取0.5。CR為交叉算子，這里取0.1。當rand產生的隨機數小于CR時，采用差分交叉算子來更新位置公式；當rand產生的隨機數大于CR時，采用經典粒子群算法的更新位置公式。

3.3 算法流程

學習因子隨權重調整的混合粒子群算法的流程如下：

Step1:初始化粒子，令其值約束在規定的范圍內，并令每個粒子都具有位置向量Xi，速度向量Vi；

Step2:計算粒子的適應度值，將fi設置為粒子當前位置的適應度，計算出favg為平均適應度值；

Step3:將粒子的適應度值與自身經過的粒子的所有位置進行比較，將較好的一個作為當前的最好位置，記為pbest；將粒子的適應度值與所有粒子經過的位置進行比較，將較好的一個作為全局的最好位置，記為gbest；

Step4:如果rand<變異率，采用差分交叉算子更新粒子位置，否則根據標準粒子群算法來調整微粒速度和位置；

Step5:對所有粒子相繼按式(6)更新位置公式；按式(4)、式(5)計算慣性權重w,c；計算適應度值；

Step6：如果算法達到最大迭代次數,執行步驟8，否則執行步驟3；

Step7:將迭代次數加一，執行步驟3；

Step8:達到最大迭代次數，輸出gbest。

4 收斂性分析

4.1 收斂準則

在分析DSPSO算法時，需要用到一些假設和定理，下面簡要給出它們的內容。

定義：給出一個函數f，其解空間為Dn～D,S為Dn的一個子集；在S中存在一個點z，它能夠使函數f的值最小或能夠使函數f的值在S上能夠有較小的下確值。

假設1：f(H(z,δ))≤f(z)，若δ∈s，則f(H(z,δ))≤f(δ)。H是在待求解空間產生的一個解的函數，并且應保證H所產生的所有新個體優于當前個體。

4.2 DSPSO算法的全局收斂證明

引理1：DSPSO算法滿足假設1。

證明 由式(1)、式(6)可知，DSPSO算法的可描述為：

所以假設1很容易證明。

引理2：收斂性證明。

證明：不考慮式(1)中的隨機分量rand(i=1,2)，并假設pd為一常量且定義如下：

將上式帶入到式(1)中

vt+1=w*vt+c(pd-xt)

其中，c=c1+c2。

設yt=pd-xt，則速度和位置更新公式可簡寫為：

vt+1=ω*vt+c*yt

yt+1=-ω*vt+(1-c)*yt

當(ω+1-c)2≠4ω時，可以定義矩陣N滿足下式:

其中，

假設Qt=NPt，則Qt=LtQ0。對于L為對角矩陣，可得下式:

(7)

由動力系統的穩定性理論，可得如下定理：

定理：要使DSPSO算法模型穩定，即收斂于pd，當且僅當max{|λ1|,|λ2|}<1。

推論1：當(ω+1-c)2≠4ω且0<ω<1時要使DSPSO算法模型穩定，即收斂于pg,當且僅當0

推論2：當(ω+1-c)2=4ω，且0<ω<1時要使DSPSO算法模型穩定，即收斂于pg，當且僅當ω-1

推論3：當0<ω<1時要使IDWPSO算法模型穩定，即收斂于pg,當且僅當0

綜上，學習因子和慣性權重之間的收斂關系如圖4所示。

圖4 c與w的收斂關系

DSPSO算法中學習因子表示為慣性權重的函數，既學習因子隨慣性權重而決定。在實際算法中，學習因子往往乘以[0,1]隨機數randi(i=1,2)，所以只需要確定算法收斂模型學習因子的上限值，而乘以隨機數后必然收斂于此條件，在此算法中慣性權重取值在[0.4,0.9]，滿足上述條件。

5 仿真測試與分析

5.1 實驗設計

為了驗證改進算法的有效性，用SPSO和LPSO與提出的DSPSO進行對比。用四個測試函數進行測試。在收斂精度、收斂速度和維度方面進行對比。

在實驗中，種群規模為30，迭代次數為1 000，LPSO慣性權重從0.9線性遞減到0.4；DSPSO的參數設置：慣性權重wmax=0.9，wmin=0.4。

實驗將從以下三方面進行測試分析：

(1)對四個函數在三種算法下的3維、10維和30維運行50次求平均值，對其各維度收斂精度進行分析；

(2)通過多次實驗的平均適應度進化曲線來比較四種算法的收斂速度；

(3)固定收斂精度，規定迭代次數，比較四個函數在三種算法下的成功率。

測試函數如表1所示。

表1 測試函數信息

5.2 測試結果分析

5.2.1 算法收斂精度比較

對四個函數分別在3維、10維和30維進行50次運行取平均值，最優值和平均值如表2所示。

表2 函數測試結果

續表2

由表2可知，宏觀來看，對于函數f1,f3,f4，DSPSO不管在3維、10維或是30維，平均值都優與SPSO和LPSO。對于函數f2，三種算法的最優值都一樣，但平均值卻不同，SPSO和LPSO在3維和30維的精度在10-6左右，而DSPSO不管在3維、10維還是30維，其最優值和平均值都是8.881 8E-16，這也就說明了DSPSO對處理f2這種用于許多局部最優值并且自變量之間相互獨立的函數具有很好的穩定性。

隨著4個函數的維數增加，函數變得逐漸復雜。SPSO和LPSO的搜索精度漸漸變低，說明SPSO和LPSO對于處理高維度的函數的搜索能力逐漸減弱；而對于DSPSO，雖然隨著四個函數的維度增加，精度在逐漸減低，但對于f1，DSPSO的精度逐漸由10-29到10-26最后到10-6；在函數f2中，DSPSO的值一直是8.881 8e-16,體現了DSPSO的穩定性；在函數f3中，DSPSO的算法平均值由0到0.085 173再到0.019 103,由此表明，雖然在3維時搜索結果最優，但隨著維數增加，30維的結果優于10維，但二者精度是一樣的；在函數f4中，DSPSO的精度由10-46到10-32再到10-6，但都是遠遠優于同維度的其他兩種算法。綜上表明DSPSO算法對于搜索精度和解決高維度的函數問題有很好的效果。

5.2.2 算法進化速度比較

四個函數的適應度進化曲線如圖5和圖6所示。

在圖5左中，由于DSPSO算法在700次左右完成迭代，而SPSO和LPSO沒有完成迭代，所以附上程序運行后的迭代最優值，如圖7所示。

圖5 函數f1、f2適應度進化曲線

圖6 函數f3、f4適應度進化曲線

圖7 函數f1的最優值

由圖5左和圖7可知，DSPSO在600完成迭代，而且精度是10-100，遠遠高于SPSO和LPSO的精度；SPSO和LPSO在1 000次內并沒有完成迭代，說明DSPSO的搜索速度遠高于其他兩種算法；在圖5右中，雖然三種算法最后搜索精度和迭代次數相近，但可以發現，DSPSO還是比較優中取精的，不管是速度還是精度都要優于其他兩種算法；在圖6左中，SPSO和LPSO早早陷入局部尋優，DSPSO在300次時陷入局部最優，但是隨后跳出局部最優，在600次左右完成迭代，增加了搜索的精度；在圖6右中，LPSO早早陷入局部尋優，DSPSO的最后收斂精度優于LPSO10-3個精度，并且DSPSO的搜索速度快于SPSO,并且DSPSO在700次迭代完成，而SPSO要900次迭代完成。

5.2.3 算法成功率比較

對每個函數進行50次仿真，其中對f1、f2、f3、f4設置1 000次迭代次數。當每個函數達到設定迭代次數時仍未收斂的則認定收斂失敗。收斂成功率分析如表3所示。

表3 函數成功率

其中f1是單峰函數，f2、f3、f4為雙峰函數。

由表3可知,在處理f1之類的單峰函數問題時，DSPSO算法并不比SPSO和LPSO具有很大優勢；但在f2、f3、f4多峰問題上，DSPSO算法成功率明顯高于其他兩種算法。這表明，DSPSO算法的改進對處理多峰復雜函數問題有明顯優勢。

6 結束語

經過實驗分析，提出了學習因子隨權重調整的混合粒子群算法。首先對慣性權重進行改進，使其隨迭代次數和粒子狀態改變；將學習因子表示為慣性權重的函數，加強了粒子的統一性和智能性；引入差分進化算法保持種群多樣性，利于算法跳出局部收斂；最后對算法的收斂性進行分析，證明算法可行性。仿真結果表明該算法的尋優性能明顯提升。在今后的算法研究中，應加強群算法的實際工程應用，可以將其應用到電機控制參數調整中，減小超調。