一種動態壓縮因子的分數階粒子群優化

翟兆睿，蘇守寶

(1.江蘇科技大學 計算機學院, 江蘇 鎮江 212003；2.金陵科技學院 數據科學與智慧軟件江蘇省重點實驗室, 南京 211169)

粒子群優化(particle swarm optimization,PSO)算法最早由Kennedy和Eberhart提出，是一種群體智能隨機優化算法[1-4]。算法源于對鳥群覓食行為的研究和模擬，并將社會學中的合作與競爭引入到優化問題的求解中。由于PSO算法具有結構簡單、易于編程實現、有較強的全局優化能力等優點，使其迅速發展成為群體智能方向中最活躍的研究課題之一，成為工程實際中全局優化和復雜問題求解的重要工具。目前，研究者采用多學科方法，對PSO算法理論、模型改進、參數設置、實驗設計、混合方法及應用等方面做了一定的創新性研究[5-6]，提出了包括量子粒子群等多種改進型PSO算法，并廣泛應用于路徑規劃、移動隱私保護、大規模協同進化、大數據挖掘等多個研究領域[7-9]。Solteiro Pires等[9]利用分數階微積分的概念來控制粒子群中粒子的速度變化，從而提出基于分數階速度粒子群(FV-PSO)算法；同時利用分數階微積分的概念來控制粒子群中粒子的位置狀態，從而提出基于分數階位置粒子群(FP-PSO)算法，利用粒子的位置和速度信息動態調整分數階次，逐步形成分數階粒子群優化方法(FoPSO)[10-12]。最近，分數階粒子群優化得到了更多國內外學者的進一步關注和研究[13-16]，他們陸續提出改進型或混合型分數階POS算法[17]，如Micael等[12]引入Darwin分數階次，提出了一種自適應的分數階達爾文粒子群優化(AFO-DPSO)算法，并將其成功應用于圖像分割、Kalman濾波等領域。

為了克服粒子群優化算法在復雜多峰問題中容易陷入早熟收斂和局部最優、收斂精度不高等問題，已有學者從不同角度對算法進行了改進，以有效緩解全局尋優和局部搜索之間的矛盾。文獻[18]提出一種慣性權重線性遞減的粒子群(linearly decreasing weight,LDIW-PSO)算法，Clerc和Kennedy等[19]在假設全局最優、個體最優及加速度和慣性權重保持不變的前提下，引入壓縮因子，有效地改善了算法魯棒性。由于分數階粒子群(FoPSO)算法依賴于分數階次a線性遞減的策略，使算法在全局尋優能力方面性能大幅降低，導致易陷入局部最優。受Clere啟發，本文提出了一種動態自適應壓縮因子的分數階粒子群優化算法，分析了壓縮因子不動定形式，通過迭代步動態控制壓縮因子的變化，以解決FV-PSO算法在后期難以跳出局部搜索能力最優的缺點。

1 分數階粒子群FPSO算法

1.1 標準粒子群算法

PSO算法源于對鳥類捕食行為的研究。當鳥類捕食時，尋找食物最有效的范圍是尋找距離食物最近的鳥的周圍區域。假設在一個D維的空間中有m個粒子，其中第i個粒子的位置表示為Xi=(xi1,xi2,…,xiD)，速度表示為Vi=(vi1,vi2,…,viD)，每個粒子根據當前種群中最好粒子在解空間內進行搜索。同時，在每次迭代過程中，粒子通過跟蹤2個“極值”來更新自己：第1個是根據粒子本身得到的最優解，即個體極值，用坐標p表示，記為pi=(pi1,pi2,…,piD)；另一個極值是根據整個種群目前得到的最優解，即群體極值，用坐標g表示，記為pg=(pg1,pg2,…,pgD)。粒子也會隨個體最優位置和群體最優位置不斷更新，當終止條件達到最大迭代次數或滿足精度要求其一即可停止，并根據以下公式來更新自己的速度和位置：

vid(t+1)=w×vid(t)+c1×

r1×(pid(t)-xid(t))+

c2×r2×(pgd(t)-xgd(t))

(1)

xid(t+1)=xid(t)+vid(t)

(2)

其中：c1r1(pid(t)-xid(t)) 為自我認知項，具有使粒子具有全局搜索的能力；c2r2(pgd(t)-xid(t))為社會認知項，表示粒子在搜索空間中在尋找最優位置時的趨勢；vid(t)是粒子i在第i次迭代中第j維的速度；xid(t)是當前粒子的位置；r1、r2是(0,1)之間的隨機數；c1、c2是學習因子；w是慣性權重，表示粒子對自身速度的保留程度。文獻[4]指出，在進化過程中，將w初始化為0.9之后會以線性規律降低到0.4，允許在迭代跟隨時進行局部搜索的初始探索，并按式(3)線性遞減，可稱為慣性權重遞減PSO算法，即LDIW-PSO。

(3)

其中：t為當前的迭代次數；tmax為迭代總次數。

1.2 分數階粒子群算法

分數階微積分的概念可以追溯到差異理論的開始，隨著學者對其理論概念研究的成熟，分數階微積分的研究也開始逐漸被應用在生物學、工業控制和物理等領域[16-17]。

分數階微積分作為數學分析領域的一個分支，其定義可以被擴展到實數或者多個微分和積分算子，可以用幾種分數導數來定義，其中， Grünwald-Letnikov定義的分數導數公式可定義為：

(4)

分數導數相比整數導數需要無限數量的序列，可以在離散時間內實現其近似值，如式(5)所示：

(5)

其中：T是采樣周期；r是截斷階數。分數階模型由于其固有的記憶特性，更加適合描述諸多不可逆性和混沌之類的現象。

利用分數階a的記憶特性，并通過其遞減規律對粒子速度進行更新。起初，為修改速度導數的順序，原始速度排列方式由式(6)通過左右變換為式(7)：

vt+1=vt+φ1(b-x)+φ2(g-x)

(6)

vt+1-vt=φ1(b-x)+φ2(g-x)

(7)

其中vt+1-vt是分數階次a=1時離散狀態的導數，并假定采樣周期T=1以及慣性權重w=1，通過文獻[14]的方法得到如式(8)所示的表達式。

Dα[vt+1]=φ1(b-x)+φ2(g-x)

(8)

隨著迭代次數的增加，當代粒子群中粒子與最初幾代粒子的關系逐漸淡化，并考慮到式(5)給出的r=4的微分導數項，即只保留前4代的速度向量，并取T=1，得到式(9)。

(9)

通過式(8)(9)，得到最終分數階粒子群算法的速度更新表公式，如式(10)所示[18-19]。

vt+1=αvt+φ1(b-x)+φ2(g-x)+

(10)

2 動態壓縮因子的分數階粒子群優化

2.1 動態壓縮因子

借鑒Clerc和Kennedy提出的壓縮因子的概念，為了有效地控制和約束粒子的飛行速度，使算法在全局探索和局部搜索兩者之間達到平衡，本文給出了一種融合c1、c2值的方法，使用χ來收縮速度，并通過式(11)(12)進行速度更新。

vt+1=χ(vt+φ1β1(b-x)+φ2β2(g-x))

(11)

(12)

其中：χ為壓縮因子；φ=c1+c2，φ>4。

在帶壓縮因子的粒子群算法中，壓縮因子的大小直接影響算法的收斂性能，但壓縮因子依賴于加速常數c1和c2的大小，當取值過大時，算法具有全局收斂性，可能會將一些空間忽略掉；而當取值過小時，算法容易收斂，存在易陷入局部最優的風險。本文在迭代過程中，通過每次迭代步的變化控制壓縮因子的大小，提出了動態壓縮因子的方法，如式(13)所示。

(13)

其中：κ為大于1的正整數；tmax為最大迭代次數；t為當前迭代次數；χ為壓縮因子，一般χ的取值范圍為(0,1)，而κ的取值大小直接影響壓縮因子的變化。因此，當κ取不同值時，壓縮因子χ變化情況如圖1所示。為保證算法的收斂性，實驗研究常數κ并不顯著影響壓縮因子的變化，所以在本文實驗中將κ設置為3。

圖1 不同κ值時的壓縮因子χ變化

2.2 基于動態壓縮因子的FoPSO

動態壓縮因子的方法改變了原有壓縮因子χ值的固定性，可更好地控制粒子的飛行速度，使算法在搜索的早期階段具有一定的全局尋優能力。隨迭代次數的增加，壓縮因子逐漸減小，使得算法在搜索后期具有一定的局部搜索能力。為此，本文提出的動態壓縮因子的分數階粒子群(a fractional order PSO with dynamic constriction factor )算法主要過程描述如下：

if (t>Tmax) //條件判斷

V=Vmin+(Vmax-Vmin)*rand(1)

//隨機初始化種群速度

X=Xmin+(Xmax-Xmin)*rand(1)

//隨機初始化種群位置

fort=1:Tmax

forp=1:Mmax

f(t)= fitness_function(y(t));

//計算粒子的適應度值

r1=rand(1);

r2=rand(1);

//生成[0,1]之間隨機數

v=range_check(v);

x=range_check(x);

//更新粒子速度、位置及位置范圍

end

end

end

其中:Tmax為種群最大迭代次數；Mmax為種群數；fitness_function計算粒子的適應度；range_check更新粒子的速度、位置范圍；Vmin和Vmax代表速度范圍最小值和最大值；V為粒子的速度向量矩陣；X為粒子位置向量矩陣。

3 實驗結果與分析

3.1 測試函數

本文采用的仿真軟件為MATLABR2014a，仿真環境：Inter(R) Core(TM)i5-4210H CPU@2.90 GHz 2.90 GHz，內存為4 GB，操作系統為Windows 10。

為了驗證本文提出DFFV-PSO算法的性能，筆者選取6個典型的基準函數進行測試，它們是在群智能優化算法中被廣泛采用的測試函數(求最小值)，即Sphere、Rosenbrock、Axis parallel hyper-ellipsoid、Rastrigin、Ackley和Griewank函數，表達式分別如下：

1)f1：Sphere函數

(14)

其中-100≤xi≤100,d={1,2,…,D}，全局最優值：min(f1)=f1(0,0,…,D)=0。

2)f2：Rosenbrock函數

(15)

其中-200≤xi≤200,d={1,2,…,D}，全局最優值：min(f2)=f2(0,0,…,D)=0。

3)f3：Axis parallel hyper-ellipsoid函數

(16)

其中-5.12≤xi≤5.12,d={1,2,…,D}，全局最優值：min(f3)=f3(0,0,…,D)=0。

4)f4：Rastrigin函數

(17)

其中-200≤xi≤200,d={1,2,…,D}，全局最優值：min(f4)=f4(0,0,…,D)=0。

5)f5：Ackley函數

(18)

其中-32≤xi≤32,d={1,2,…,D}，全局最優值：min(f5)=f5(0,0,(…,D)=0。

6)f6：Scaffer’sf6函數

(19)

其中-100≤x,y≤100,全局最優值：min(f6)=f6(0,0,)=0。

在這些函數中，f1、f2、f3為單峰函數，該類函數是連續的，在區間上呈現凸狀。對于函數f2很難求得全局最優點，而函數f3是對函數f1的變形，增加了各維函數的相互作用。f4、f5、f6為非線性的多峰函數，大量的局部極小值點被認為是很難處理的問題。

3.2 常數k對壓縮因子的影響

一般地，k的取值大小直接作用于壓縮因子上，從而影響分數階粒子群算法在函數適應度上的變化。為了實驗測試式(13)中常數k對壓縮因子χ的影響，本文算法的具體參數設置如下：粒子群群規模設置為30，最大迭代次數設置為200，維度設置如表1所示，學習因子c1=c2=2時，k=2,3,4,5,10。

用本文提出的算法在不同k值時，6個基準函數適應值變化如圖2～7所示。從實驗結果來看，不同的k值均能保證算法的收斂性，說明常數k并不顯著影響壓縮因子的變化，所以不失一般性，可在本文實驗中將k設置為3，能夠保證算法的穩定收斂性能。

圖2 函數Sphere適應度曲線

圖3 函數Rosenbrock適應度曲線

圖4 函數Axis parallel hyper-ellipsoidk適應度曲線

圖5 函數Rastrigin適應度曲線

圖6 函數Ackley適應度曲線

圖7 函數Scaffer’s 適應度曲線

3.3 實驗結果與分析

在實驗中，將提出的DFFV-PSO算法與慣性權重遞減粒子群LDIW-PSO算法、分數階速度粒子群FV-PSO算法、分數階位置粒子群FP-PSO算法進行比較。參數設置如下：粒子群群規模設置為30，最大迭代次數設置為200，維度設置如表1所示。學習因子c1=c2=2、k=3。為減少統計誤差，采用4種不同的算法分別對每個函數獨立運行50次，并將50次所得到的結果進行統計，計算算法的適應度值的最優值、最差值和平均值。表1給出了部分實驗結果。

表1 測試函數的部分實驗結果

由表1測試結果可以看出，無論是在單峰函數f1、f2、f3上，還是在多峰函數f4、f5、f6上，速度分數階粒子群算法的測試結果相比其他2種FP-PSO和LDIW-PSO算法都較好，但是在搜索到的最優值的平均值方面均不如本文提出的DFFV-PSO算法性能好。

4種算法對6種函數的優化曲線比較如圖8～13所示。

圖8 函數Sphere測試結果曲線

圖9 函數Rosenbrock測試結果曲線

圖10 函數Axis parallel hyper-ellipsoid測試結果曲線

觀察圖8～13可以發現：

1) FV-PSO算法和PSO算法的尋優性能測試結果幾乎相差不大。

2) 對于多峰函數，無論是在2維還是在10維下，DFFV-PSO算法的尋優結果均相比其他算法好，魯棒性更強，收斂速度更快更穩定。

3) 通過將壓縮因子的策略融入到算法中，使得改進的DFFV-PSO算法收斂速度更快，尋優能力更強，同時達到優化的精度也最高。

圖11 函數Rastrigin測試結果曲線

圖12 函數Ackley測試結果曲線

圖13 函數Scaffer’s 測試結果曲線

4 結束語

自適應壓縮因子的分數階粒子群算法實際上是在分數階速度粒子群算法的基礎上，結合改變壓縮因子的變化，使算法有效地避免了陷入局部最優。實驗分析了影響壓縮因子的常數k的經驗取值，并通過多種基準函數實驗仿真結果表明：該算法的收斂速度更快，收斂精度及魯棒性更好，改進的算法具有可行性和有效性。