翟兆睿，蘇守寶

(1.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 江蘇 鎮(zhèn)江 212003；2.金陵科技學(xué)院 數(shù)據(jù)科學(xué)與智慧軟件江蘇省重點(diǎn)實(shí)驗(yàn)室, 南京 211169)

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

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

1 分?jǐn)?shù)階粒子群FPSO算法

1.1 標(biāo)準(zhǔn)粒子群算法

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

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)) 為自我認(rèn)知項(xiàng)，具有使粒子具有全局搜索的能力；c2r2(pgd(t)-xid(t))為社會認(rèn)知項(xiàng)，表示粒子在搜索空間中在尋找最優(yōu)位置時的趨勢；vid(t)是粒子i在第i次迭代中第j維的速度；xid(t)是當(dāng)前粒子的位置；r1、r2是(0,1)之間的隨機(jī)數(shù)；c1、c2是學(xué)習(xí)因子；w是慣性權(quán)重，表示粒子對自身速度的保留程度。文獻(xiàn)[4]指出，在進(jìn)化過程中，將w初始化為0.9之后會以線性規(guī)律降低到0.4，允許在迭代跟隨時進(jìn)行局部搜索的初始探索，并按式(3)線性遞減，可稱為慣性權(quán)重遞減PSO算法，即LDIW-PSO。

(3)

其中：t為當(dāng)前的迭代次數(shù)；tmax為迭代總次數(shù)。

1.2 分?jǐn)?shù)階粒子群算法

分?jǐn)?shù)階微積分的概念可以追溯到差異理論的開始，隨著學(xué)者對其理論概念研究的成熟，分?jǐn)?shù)階微積分的研究也開始逐漸被應(yīng)用在生物學(xué)、工業(yè)控制和物理等領(lǐng)域[16-17]。

分?jǐn)?shù)階微積分作為數(shù)學(xué)分析領(lǐng)域的一個分支，其定義可以被擴(kuò)展到實(shí)數(shù)或者多個微分和積分算子，可以用幾種分?jǐn)?shù)導(dǎo)數(shù)來定義，其中， Grünwald-Letnikov定義的分?jǐn)?shù)導(dǎo)數(shù)公式可定義為：

(4)

分?jǐn)?shù)導(dǎo)數(shù)相比整數(shù)導(dǎo)數(shù)需要無限數(shù)量的序列，可以在離散時間內(nèi)實(shí)現(xiàn)其近似值，如式(5)所示：

(5)

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

利用分?jǐn)?shù)階a的記憶特性，并通過其遞減規(guī)律對粒子速度進(jìn)行更新。起初，為修改速度導(dǎo)數(shù)的順序，原始速度排列方式由式(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是分?jǐn)?shù)階次a=1時離散狀態(tài)的導(dǎo)數(shù)，并假定采樣周期T=1以及慣性權(quán)重w=1，通過文獻(xiàn)[14]的方法得到如式(8)所示的表達(dá)式。

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

(8)

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

(9)

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

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

(10)

2 動態(tài)壓縮因子的分?jǐn)?shù)階粒子群優(yōu)化

2.1 動態(tài)壓縮因子

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

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

(11)

(12)

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

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

(13)

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

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

2.2 基于動態(tài)壓縮因子的FoPSO

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

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

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

//隨機(jī)初始化種群速度

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

//隨機(jī)初始化種群位置

fort=1:Tmax

forp=1:Mmax

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

//計(jì)算粒子的適應(yīng)度值

r1=rand(1);

r2=rand(1);

//生成[0,1]之間隨機(jī)數(shù)

v=range_check(v);

x=range_check(x);

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

end

end

end

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

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

3.1 測試函數(shù)

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

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

1)f1：Sphere函數(shù)

(14)

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

2)f2：Rosenbrock函數(shù)

(15)

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

3)f3：Axis parallel hyper-ellipsoid函數(shù)

(16)

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

4)f4：Rastrigin函數(shù)

(17)

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

5)f5：Ackley函數(shù)

(18)

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

6)f6：Scaffer’sf6函數(shù)

(19)

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

在這些函數(shù)中，f1、f2、f3為單峰函數(shù)，該類函數(shù)是連續(xù)的，在區(qū)間上呈現(xiàn)凸?fàn)睢τ诤瘮?shù)f2很難求得全局最優(yōu)點(diǎn)，而函數(shù)f3是對函數(shù)f1的變形，增加了各維函數(shù)的相互作用。f4、f5、f6為非線性的多峰函數(shù)，大量的局部極小值點(diǎn)被認(rèn)為是很難處理的問題。

3.2 常數(shù)k對壓縮因子的影響

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

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

圖2 函數(shù)Sphere適應(yīng)度曲線

圖3 函數(shù)Rosenbrock適應(yīng)度曲線

圖4 函數(shù)Axis parallel hyper-ellipsoidk適應(yīng)度曲線

圖5 函數(shù)Rastrigin適應(yīng)度曲線

圖6 函數(shù)Ackley適應(yīng)度曲線

圖7 函數(shù)Scaffer’s 適應(yīng)度曲線

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

在實(shí)驗(yàn)中，將提出的DFFV-PSO算法與慣性權(quán)重遞減粒子群LDIW-PSO算法、分?jǐn)?shù)階速度粒子群FV-PSO算法、分?jǐn)?shù)階位置粒子群FP-PSO算法進(jìn)行比較。參數(shù)設(shè)置如下：粒子群群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)置為200，維度設(shè)置如表1所示。學(xué)習(xí)因子c1=c2=2、k=3。為減少統(tǒng)計(jì)誤差，采用4種不同的算法分別對每個函數(shù)獨(dú)立運(yùn)行50次，并將50次所得到的結(jié)果進(jìn)行統(tǒng)計(jì)，計(jì)算算法的適應(yīng)度值的最優(yōu)值、最差值和平均值。表1給出了部分實(shí)驗(yàn)結(jié)果。

表1 測試函數(shù)的部分實(shí)驗(yàn)結(jié)果

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

4種算法對6種函數(shù)的優(yōu)化曲線比較如圖8～13所示。

圖8 函數(shù)Sphere測試結(jié)果曲線

圖9 函數(shù)Rosenbrock測試結(jié)果曲線

圖10 函數(shù)Axis parallel hyper-ellipsoid測試結(jié)果曲線

觀察圖8～13可以發(fā)現(xiàn)：

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

2) 對于多峰函數(shù)，無論是在2維還是在10維下，DFFV-PSO算法的尋優(yōu)結(jié)果均相比其他算法好，魯棒性更強(qiáng)，收斂速度更快更穩(wěn)定。

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

圖11 函數(shù)Rastrigin測試結(jié)果曲線

圖12 函數(shù)Ackley測試結(jié)果曲線

圖13 函數(shù)Scaffer’s 測試結(jié)果曲線

4 結(jié)束語

自適應(yīng)壓縮因子的分?jǐn)?shù)階粒子群算法實(shí)際上是在分?jǐn)?shù)階速度粒子群算法的基礎(chǔ)上，結(jié)合改變壓縮因子的變化，使算法有效地避免了陷入局部最優(yōu)。實(shí)驗(yàn)分析了影響壓縮因子的常數(shù)k的經(jīng)驗(yàn)取值，并通過多種基準(zhǔn)函數(shù)實(shí)驗(yàn)仿真結(jié)果表明：該算法的收斂速度更快，收斂精度及魯棒性更好，改進(jìn)的算法具有可行性和有效性。