郭通，蘭巨龍，李玉峰，陳世文

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002)

1 引言

粒子群優(yōu)化（PSO, particle swarm optimization）算法是一種基于群體智能的隨機(jī)全局優(yōu)化計(jì)算方法[1]。該算法以其建模簡單、收斂速度快且易于實(shí)現(xiàn)等優(yōu)點(diǎn)，在組合優(yōu)化[2]、多目標(biāo)辨識[3]、任務(wù)分配[4]、聚類分析[5]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練[6]等領(lǐng)域得到了廣泛的應(yīng)用。類似于其他全局優(yōu)化算法，PSO算法在實(shí)際應(yīng)用中也表現(xiàn)出了一些有待改進(jìn)的問題，即算法在搜索初期往往收斂較快，但在后期粒子群會趨向同一化(失去了多樣性)，使得收斂速度明顯變慢，搜索精度降低，算法容易陷入局部最優(yōu)，因此很多學(xué)者致力于提高PSO算法的性能。

Naka等[7]將遺傳算法中的選擇操作引入到PSO中，提出了混合粒子群優(yōu)化(HPSO, hybrid particle swarm optimization)算法，對每次迭代產(chǎn)生的新的粒子群依照一定選擇率復(fù)制較優(yōu)個體，在提高收斂速度的同時(shí)保證了一定的全局搜索能力。Krohling[8]將高斯函數(shù)引入PSO算法中，用于引導(dǎo)粒子的運(yùn)動，進(jìn)而提出了高斯粒子群優(yōu)化（GPSO, Gaussian particle swarm optimization）算法，GPSO不再需要慣性權(quán)重，且加速系數(shù)由服從高斯分布的隨機(jī)數(shù)產(chǎn)生，以克服傳統(tǒng)PSO搜索能力和收斂性能嚴(yán)重依賴加速系數(shù)和慣性權(quán)重設(shè)置的不足。Jason等[9]提出了一種利用自然選擇進(jìn)化思想的達(dá)爾文粒子群優(yōu)化（DPSO, Darwinian particle swarm optimization）算法，動態(tài)地將種群分為若干個子群，每個子群相對獨(dú)立地展開搜索，以提高粒子的多樣性，增強(qiáng)算法的全局尋優(yōu)能力。Xu等[10]提出了一種新的混沌粒子群優(yōu)化（NCPSO, new chaos-particle swarm optimization）算法，將混沌融入到粒子運(yùn)動過程中，使粒子群在混沌與穩(wěn)定之間交替向最優(yōu)點(diǎn)靠近，能夠跳出局部最優(yōu)，提高了算法的收斂速度和精度。

作為應(yīng)用自然科學(xué)中的一種有用的數(shù)學(xué)工具，分?jǐn)?shù)階微積分（FOC, fractional order calculus）理論在水文建模、統(tǒng)計(jì)力學(xué)、圖像分割、模式識別、信號處理等實(shí)際工程領(lǐng)域的應(yīng)用越來越廣泛[11～14]。最近，Pires等[15]將分?jǐn)?shù)階微積分引入到PSO中，提出了分?jǐn)?shù)階粒子群優(yōu)化（FO-PSO）算法，通過對粒子群的原始速度進(jìn)行重新排列來修正速度導(dǎo)數(shù)的階數(shù)，以便于控制算法的收斂率。在此基礎(chǔ)上，Micael等[16]給出了一種分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化（FO-DPSO）算法，用于控制DPSO算法的收斂速度，實(shí)驗(yàn)結(jié)果表明，F(xiàn)O-DPSO算法在計(jì)算精度和收斂速度上均要優(yōu)于傳統(tǒng)的PSO、DPSO以及FO-PSO算法。但同F(xiàn)O-PSO算法一樣，F(xiàn)O-DPSO算法的收斂性能也直接依賴于分?jǐn)?shù)階次α，當(dāng)α值增加時(shí)，粒子群的收斂速度就變慢，而當(dāng)α值減小時(shí)，種群陷入局部最優(yōu)的概率就變高。

針對此不足，本文受文獻(xiàn)[17]提出的自適應(yīng)粒子群優(yōu)化（APSO, adaptive particle swarm optimization）算法的啟發(fā)，并在此基礎(chǔ)上改進(jìn)，結(jié)合FO-DPSO算法，提出了一種自適應(yīng)的分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化（AFO-DPSO）算法。對幾種典型函數(shù)的測試結(jié)果表明，相比于現(xiàn)有的粒子群優(yōu)化算法，本文的AFO-DPSO算法能夠避免陷入局部最優(yōu)，收斂速度、穩(wěn)定性和精度都有了顯著提高，進(jìn)一步提高了全局尋優(yōu)能力。

2 PSO和DPSO算法概述

2.1 PSO算法基本原理

設(shè)在一個D維的目標(biāo)搜索空間中，有N個粒子組成一個群落，其中，第i個粒子的位置表示為向量Xi=(xi1,xi2,…,xiD)，速度為向量Vi=(vi1,vi2,…,viD)，第i個粒子“飛行”歷史中的過去最優(yōu)位置為Pi=(pi1,pi2,…,piD)，整個粒子群搜索到的最優(yōu)位置Pg=(pg1,pg2,…,pgD)。將Xi代入目標(biāo)函數(shù)計(jì)算其適應(yīng)值，每個粒子的速度和位置更新策略分別為

其中，i=1,2,…,N；d=1, 2,…,D；在式(1)中，w是慣性加權(quán)；c1、c2是加速系數(shù)；r1d、r2d為[0,1]之間的隨機(jī)數(shù)；pid為粒子本身所找到的最優(yōu)解，即個體極值；pgd是整個粒子群目前找到的最優(yōu)解，稱之為全局極值。應(yīng)用式(1)和式(2)對種群中每個粒子群循環(huán)更新，可使整個種群逐步逼近全局最優(yōu)解。

2.2 DPSO算法基本思想

DPSO是一種進(jìn)化算法，其基本思想[9]如下所示。

1) 一個粒子群存在的時(shí)間越長，它產(chǎn)生后代（構(gòu)造一個新的粒子群）的機(jī)會也就越大，當(dāng)其產(chǎn)生后代時(shí)，后代還會繼承一些適應(yīng)度較好的粒子。

2) 一個粒子群可以通過找到更好的適應(yīng)值來延長其壽命，同時(shí)還可以增加新的粒子來加快搜索速度。

3) 粒子群如果沒能找到更好的適應(yīng)值，它的壽命將會縮短，同時(shí)也可能刪除群中那些性能較差的粒子，當(dāng)粒子的數(shù)量減少到一定閾值時(shí)，該粒子群被銷毀。

在DPSO算法中，為了追蹤粒子群適應(yīng)值沒有改變的次數(shù)，設(shè)置一個搜索計(jì)數(shù)器為SC，如果搜索計(jì)數(shù)器超過最大門限，將該粒子從群中刪除，而創(chuàng)建一個粒子群時(shí)，SC置為0。在刪除粒子后，SC值并不置為0，而是按照式(3)重置為一個接近的值。

其中，Nkill為在適應(yīng)值沒有任何改善的一段時(shí)期內(nèi)從粒子群中所刪除的粒子數(shù)目。在產(chǎn)生一個新的粒子群之前，粒子群中必須沒有任何粒子被刪除，并且粒子群數(shù)量不能超過其最大數(shù)目。盡管如此，創(chuàng)建新的粒子群概率也僅僅為

其中，f為[0,1]范圍內(nèi)的隨機(jī)數(shù)，Ns為粒子群數(shù)目。

3 自適應(yīng)分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法

由文獻(xiàn)[16]可知，在絕大多數(shù)情形下，當(dāng)分?jǐn)?shù)階次 α在[0.5,0.8]范圍內(nèi)時(shí)，算法能夠獲得更快的收斂速度，并給出了如下的表達(dá)式來調(diào)整α。

其中，t為當(dāng)前迭代次數(shù)，算法最大迭代次數(shù)為200。

然而，式(5)中的α卻會隨著迭代次數(shù)的增加而線性減小，這無疑增大了種群陷入局部最優(yōu)的概率。為了能有效避免算法的早熟收斂問題，同時(shí)能加快算法的收斂速度，本文提出一種根據(jù)粒子的狀態(tài)信息來動態(tài)調(diào)整分?jǐn)?shù)階次α的自適應(yīng)控制策略，并在算法中引入變異操作的處理方式，在此基礎(chǔ)上給出了自適應(yīng)的分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化（AFO-DPSO）算法。

3.1 分?jǐn)?shù)階次α的自適應(yīng)控制

對于每個粒子i，它與其他粒子的平均距離與平均速率差異分別采用式(6)和式(7)來估計(jì)。

其中，N和D分別為粒子群個數(shù)和空間維數(shù)，dix代表平均距離，div表示平均速率差異。

眾所周知，PSO區(qū)別于其他進(jìn)化算法的重要標(biāo)志就是粒子的進(jìn)化狀態(tài)由位置和速度來共同描述，綜合式(6)和式(7)，定義一種混合了粒子平均距離與平均速率差異信息的平均進(jìn)化狀態(tài)差異dis如下所示。

其中，iiXVρ為位置Xi和速度Vi的皮爾遜相關(guān)系數(shù)（PCC, Pearson correlation coefficient）。

比較所有的dis，確定粒子進(jìn)化狀態(tài)的最大差異值dsmax和最小差異值dsmin。設(shè)dsg為全局最優(yōu)粒子與其他粒子的進(jìn)化狀態(tài)差異的平均值，定義進(jìn)化因子fs為

將fs值通過模糊集映射函數(shù)將粒子進(jìn)化狀態(tài)分類為探測、開拓、收斂和躍出4種[17]。

基于進(jìn)化因子fs，給出分?jǐn)?shù)階次α的調(diào)整等式為

α的變化不再與迭代次數(shù)相關(guān)，而是根據(jù)粒子進(jìn)化狀態(tài)信息的改變而進(jìn)行動態(tài)調(diào)整。

3.2 加速系數(shù)自適應(yīng)控制與粒子狀態(tài)更新

將式(1)中慣性加權(quán)w設(shè)置為1，依據(jù)分?jǐn)?shù)階微分的Grünwald-Letnikov定義，粒子速度按式(12)進(jìn)行更新。

其中，α(fs)即分?jǐn)?shù)階次。粒子位置按照式(2)進(jìn)行更新，并根據(jù)表1中的規(guī)則來調(diào)整不同狀態(tài)時(shí)的加速系數(shù)，且c1和c2滿足

表1中的“微”調(diào)采用式(14)來定量定義。

其中，δ為[0.05,0.1]范圍內(nèi)均勻產(chǎn)生的隨機(jī)數(shù)。

表1 速系數(shù)c1和c2的調(diào)整策略

3.3 基于進(jìn)化狀態(tài)的自適應(yīng)變異處理機(jī)制

當(dāng)粒子群陷入局部最優(yōu)時(shí)，算法將出現(xiàn)早熟收斂。為了克服早熟收斂問題，ALFI[18]在對動態(tài)系統(tǒng)的參數(shù)進(jìn)行估計(jì)時(shí)提出了一種采用自適應(yīng)變異機(jī)制的PSO算法；Chen等[19]在PID控制參數(shù)的優(yōu)化設(shè)計(jì)中給出了一種變異概率隨算法迭代次數(shù)逐步減少的新PSO算法。當(dāng)算法發(fā)生早熟收斂時(shí)，變異操作可以改變粒子的前進(jìn)方向，從而讓粒子進(jìn)入其他區(qū)域進(jìn)行搜索，直到最后找到全局最優(yōu)解，使得算法能夠跳出局部最優(yōu)。

借鑒文獻(xiàn)[18]和文獻(xiàn)[19]的思想，本文設(shè)計(jì)了一種隨粒子進(jìn)化狀態(tài)動態(tài)變化的變異算子，根據(jù)變異概率pm對滿足變異條件的全局最優(yōu)位置Pg實(shí)施變異。

定義1 pm由進(jìn)化因子fs和迭代次數(shù)t共同表示，其選取遵照以下基本原理：

1) 進(jìn)化狀態(tài)為探測與開拓階段時(shí)，t占主導(dǎo)地位；

2) 進(jìn)化狀態(tài)為收斂和躍出階段時(shí)，fs占主導(dǎo)地位；

3) pm(t,fs)為一致凸函數(shù)。

為給出直觀的解釋，按照定義1選擇了一個特殊的pm(t,fs)函數(shù)，其計(jì)算公式為

對于全局最優(yōu)位置Pg的變異操作，本文算法將采用增加高斯隨機(jī)擾動的方法，設(shè)gkp為Pg的第k維取值，η是服從Gauss(0,1)分布的隨機(jī)變量，則

由于0≤fx≤1，0≤tanh(·)≤1，由此可以推斷出1≤1+ηtanh(fx)≤2，Pg變異后的第k維取值隨進(jìn)化因子在范圍內(nèi)變化。

3.4 算法的收斂性分析

由式(2)可知

因此，

將式(19)代入式(17)，可得

式(20)可以寫成如下矩陣向量乘積形式。

矩陣的特征多項(xiàng)式為

該特征多項(xiàng)式的一個解為 λ=1.0，令其他4個解分別為β、γ、δ和ε，則給出式(17)的當(dāng)前關(guān)系式為

其中，k1、k2、k3、k4和k5均為常數(shù)。

考慮x(t)的收斂性，即

明顯地，只要 β、γ、δ和 ε滿足max(||β||, ||γ||, ||δ||,||ε||)＜1，則

只需證明在任意max(||β||, ||γ||, ||δ||, ||ε||)＞1條件下，特征多項(xiàng)式(21)均不成立即可。假設(shè)||β||＞1，代入式(21)可得

由于r1d, r2d在[0,1]范圍內(nèi)，3≤c1+c2≤4，α(fs)在[0.5,0.8]區(qū)間內(nèi)，為單調(diào)遞減函數(shù)，故其最大值為令

則

這就與||β||＞1為z=0的解相矛盾，故假設(shè)不成立，β、γ、δ 和 ε始終滿足max(||β||, ||γ||, ||δ||, ||ε||)＜1。

因此，本文提出的AFO-DPSO算法在給定的參數(shù)范圍內(nèi)是全局收斂的。

3.5 AFO-DPSO算法描述

AFO-DPSO算法的實(shí)現(xiàn)步驟可概括如下。

step1 初始化粒子群，確定粒子數(shù)N及空間維數(shù)D，設(shè)定最大迭代代數(shù)tmax、加速系數(shù)c1和c2，指定位置和速度的上限及下限，隨機(jī)生成粒子速度Vi和位置Xi。

step2 對每個粒子進(jìn)行適應(yīng)度評估，將粒子的個體極值pid設(shè)置為當(dāng)前位置，全局極值pgd設(shè)置為初始群體中最佳粒子的位置。

step3 判斷算法收斂準(zhǔn)則是否滿足，如果滿足，轉(zhuǎn)向step8；否則，執(zhí)行step4。

step4 開始迭代，進(jìn)化代數(shù)增加1。

step5 對粒子群中所有粒子執(zhí)行如下操作：

① 根據(jù)式(6)～式(9)得到粒子的平均進(jìn)化狀態(tài)差異，根據(jù)式(10)獲得進(jìn)化因子，在此基礎(chǔ)上，應(yīng)用式(11)更新分?jǐn)?shù)階次；

② 根據(jù)表1中規(guī)則和式(13)、式(14)調(diào)整加速系數(shù)，在上述參數(shù)更新的基礎(chǔ)上，應(yīng)用式(12)與式(2)實(shí)現(xiàn)粒子位置與速度的更新；

③ 對更新狀態(tài)后粒子的適應(yīng)度值進(jìn)行評估，如果粒子適應(yīng)度優(yōu)于當(dāng)前的個體極值，則將pid設(shè)置為該粒子的位置，且更新個體極值；如果所有粒子的個體極值中最好的優(yōu)于當(dāng)前全局極值，則將pgd設(shè)置為該粒子的位置，且更新全局極值。

step6 對粒子群的適應(yīng)度值進(jìn)行追蹤，判斷是否需要刪除粒子或創(chuàng)建新的粒子群，若刪除粒子，則根據(jù)式(3)重置搜索計(jì)數(shù)器值，若構(gòu)造新的粒子群，則根據(jù)式(4)得到產(chǎn)生粒子群的概率；否則，轉(zhuǎn)向step7。

step7 根據(jù)式(15)計(jì)算變異概率pm。每個粒子設(shè)定一個(0,1)間隨機(jī)數(shù)rndi，若rndi＜pm，按式(16)執(zhí)行變異操作；否則，轉(zhuǎn)向step8。

step8 判斷是否滿足算法的收斂條件或達(dá)到代數(shù)最大限制，如果滿足，執(zhí)行step9；否則，轉(zhuǎn)向step4。

step9 輸出最終的全局極值pgd與最佳適應(yīng)度函數(shù)值，算法運(yùn)行結(jié)束。

上述算法既繼承了FO-DPSO算法的優(yōu)點(diǎn)，同時(shí)又能根據(jù)粒子的狀態(tài)信息來自適應(yīng)地調(diào)整分?jǐn)?shù)階次 α，從而加快了算法的收斂速度，并降低了種群陷入局部最優(yōu)的概率。而自適應(yīng)的變異處理方式在提高粒子多樣性的同時(shí)也增強(qiáng)了算法的全局尋優(yōu)能力。

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

4.1 測試函數(shù)與算法配置

為了考察AFO-DPSO算法的性能，選取6個典型函數(shù)進(jìn)行測試，它們是在群智能優(yōu)化算法中廣泛采用的測試函數(shù)（求最小值），即Sphere、Rosenbrock、DeJong F4、Rastrigin、Griewank和Ackley函數(shù)，它們的表達(dá)式如式(27)～式(32)所示[20]。

Sphere函數(shù)

其中，xi∈[-50,50]，i={1,2,…,D}且f*(x)=0.0。

Rosenbrock函數(shù)

其中，xi∈[-100,100]，i={1,2,…,D}且f*(x)=0.0。

DeJong F4函數(shù)

其中，xi∈[-20,20]，i={1,2,…,D}且f*(x)=0.0。

Rastrigin函數(shù)

其中，xi∈[-5.12,5.12]，i={1,2,…,D }且f*(x)=0.0。

Griewank函數(shù)

其中，xi∈[-600,600]，i={1,2,…,D}且f*(x)= 0.0。

Ackley函數(shù)

其中，xi∈[－32,32]，i={1,2,…,D}且f*(x)=0.0。

這些函數(shù)有D=30個參數(shù)，且它們的全局極值為f*。在這些函數(shù)中，f1，f2，f3為單峰函數(shù)，而f4，f5，f6為多峰函數(shù)，算法采用實(shí)數(shù)編碼方案。

本文中所用的仿真軟件為MATLABR2008b，仿真環(huán)境：CPU為Intel Pentium 4 3.20 GHz，內(nèi)存為2 GB，操作系統(tǒng)為Microsoft Windows XP Professional SP2。選取PSO、HPSO、DPSO、APSO、FO-PSO、FO-DPSO、NCPSO算法與本文提出的AFO-DPSO算法進(jìn)行比較，并將式(27)～式(32)作為適應(yīng)度函數(shù)。

各PSO算法的初始參數(shù)設(shè)置如表2所示。為了確保測試的公平性，所有PSO均采用：粒子數(shù)N=30，空間維數(shù)D為30，最大迭代次數(shù)tmax=1 000。

4.2 搜索精度比較

為了減少統(tǒng)計(jì)誤差，采用各PSO算法對每個函數(shù)進(jìn)行30次測試，取其平均值的結(jié)果如表3所示，其中，APSO算法結(jié)果來自文獻(xiàn)[17]，而NCPSO算法結(jié)果來自文獻(xiàn)[10]。

對比表3中的結(jié)果可以看出，無論是在單峰函數(shù)f1、f2、f3上，還是在多峰函數(shù)f4、f5、f6上，本文提出的自適應(yīng)分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法的測試結(jié)果均要明顯好于現(xiàn)有的PSO、HPSO、DPSO、APSO、FO-PSO、FO-DPSO與NCPSO算法的測試結(jié)果，且本文算法在f5上獲得了全局最優(yōu)值。

4.3 算法穩(wěn)定性能比較

進(jìn)一步地，本文引入文獻(xiàn)[21]中定義的最優(yōu)解方差函數(shù)來評價(jià)算法的穩(wěn)定性能。設(shè)fi為算法第i次運(yùn)行所得的最優(yōu)解適應(yīng)度，favg為算法運(yùn)行30次的最優(yōu)解的平均值，fmax為歸一化因子，算法最優(yōu)解方差δ定義為

當(dāng)∣fi-favg∣＞1時(shí)，fmax取值為max(|fi-favg|)，否則取1。表4列出了各PSO算法對6個測試函數(shù)進(jìn)行優(yōu)化所得到的最優(yōu)值方差結(jié)果。從中可以看出，本文提出的AFO-DPSO算法的最優(yōu)值方差比其他7種方法均要小。這說明AFO-DPSO算法搜索到的最優(yōu)解最穩(wěn)定。

表2 各PSO算法的參數(shù)設(shè)置

表3 不同粒子群優(yōu)化算法對6個測試函數(shù)的搜索結(jié)果比較

表4 測試函數(shù)的最優(yōu)值方差比較

4.4 收斂速度比較

圖1為現(xiàn)有DPSO、FO-PSO、FO-DPSO算法與本文提出的改進(jìn)的分?jǐn)?shù)階粒子群優(yōu)化算法對6個典型測試函數(shù)進(jìn)行優(yōu)化的過程中種群收斂性能的對比。為了便于比較，圖1中的縱坐標(biāo)都采用適應(yīng)度的對數(shù)值表示。

由圖1中4種不同粒子群算法在6個測試函數(shù)上的收斂性能比較可以看出，相比于DPSO、FOPSO和FO-DPSO算法，本文提出的AFO-DPSO算法具有更快的全局收斂速度，粒子群在經(jīng)過若干次迭代運(yùn)算后仍具備從局部最優(yōu)中跳離出來的能力，即使是在多?？臻g，由于采用了自適應(yīng)參數(shù)調(diào)整策略，也能夠快速地搜尋到潛在的最優(yōu)極值，從而極大地提高了對最優(yōu)值的全局搜索能力，并有效避免了現(xiàn)有粒子群優(yōu)化算法中存在的早熟收斂問題。

綜上所述，與現(xiàn)有的7種PSO算法相比，AFO-DPSO算法展示出更令人滿意的整體優(yōu)化性能，其收斂速度、穩(wěn)定性和搜索精度都得到了顯著提高。

4.5 算法的計(jì)算復(fù)雜度分析

按照“天下沒有免費(fèi)的午餐（NFL, no free lunch）”理論[22]，一種算法不可能在每一個方面或在每一個問題上都能夠提供比其他所有算法更好的性能。在本文的實(shí)驗(yàn)結(jié)果中也觀察到了這點(diǎn)?？疾?種算法在1 000次的迭代次數(shù)內(nèi)對上文6個函數(shù)的平均計(jì)算復(fù)雜度，對各函數(shù)分別進(jìn)行30次實(shí)驗(yàn)，每種算法所需的平均計(jì)算時(shí)間如圖2所示。

圖1 4種粒子群算法在不同測試函數(shù)上的收斂性能比較

從圖2中可以看出，AFO-DPSO算法的算法復(fù)雜度要明顯高于其他算法，F(xiàn)O-DPSO算法與DPSO算法次之，其主要原因?yàn)椋篋PSO算法需要根據(jù)粒子群的適應(yīng)度值刪除粒子或創(chuàng)建新的粒子群，導(dǎo)致算法運(yùn)算時(shí)間過長，F(xiàn)O-DPSO算法對粒子速度的分?jǐn)?shù)階運(yùn)算進(jìn)一步增加了時(shí)間復(fù)雜度，本文的AFO-DPSO算法由于利用了粒子的位置和速度信息來動態(tài)調(diào)整分?jǐn)?shù)階次，使得粒子每次更新都要增加O(2(N-1)D+N)的計(jì)算復(fù)雜度。這表明，AFO-DPSO算法具有的較高搜索精度、較快收斂速度和較好穩(wěn)定性是以犧牲一定計(jì)算復(fù)雜度為代價(jià)獲得的，并進(jìn)一步驗(yàn)證了文獻(xiàn)[22]中NFL理論的正確性。

圖2 8種不同算法的計(jì)算復(fù)雜度比較

4.6 算法參數(shù)的自適應(yīng)性分析

為了觀察進(jìn)化因子fs與分?jǐn)?shù)階次 α的變化情況，在單峰函數(shù)f1上運(yùn)行AFO-DPSO算法，并繪制出隨迭代次數(shù)變化的fs值和α值，分別如圖3與圖4所示。從圖3中可以看出，在1 000次的迭代次數(shù)中，進(jìn)化因子fs值在早期階段（大約10代內(nèi)）很大，然后迅速減少（直至100代），緊接著可以發(fā)現(xiàn)AFO-DPSO處于躍出狀態(tài)，并導(dǎo)致fs突變至一個較大值，在此之后，fs值迅速下降直至一個收斂狀態(tài)（在135代時(shí)）；大約經(jīng)過150代后，粒子群從該局部最優(yōu)中躍離出來，期間（在300～700代內(nèi)）經(jīng)歷多個“搜尋－收斂－跳離”階段后，達(dá)到全局（1 000代內(nèi)）最優(yōu)收斂狀態(tài)。在整個進(jìn)化過程中，fs值始終在[0,1]范圍內(nèi)變化，且較為明晰地展示出了粒子群的進(jìn)化狀態(tài)信息。

圖3 測試函數(shù)f1上進(jìn)化因子fs所顯示的進(jìn)化狀態(tài)信息

由圖4中可以看到，分?jǐn)?shù)階次α值隨著進(jìn)化因子fs的改變而在[0.5,0.8]區(qū)間內(nèi)動態(tài)變化，這表明分?jǐn)?shù)階次α能夠依據(jù)粒子群的進(jìn)化狀態(tài)進(jìn)行自適應(yīng)調(diào)整。為了驗(yàn)證算法的通用性，在函數(shù)f2～f6上重復(fù)這一實(shí)驗(yàn)，進(jìn)化因子與分?jǐn)?shù)階次變化情況展現(xiàn)出與在函數(shù)f1上類似的模式，在此不再贅述。

圖4 測試函數(shù)f1上的時(shí)變分?jǐn)?shù)階次α

為了追蹤變異概率pm的變化，類似地，圖5給出了對f1函數(shù)進(jìn)行測試時(shí)，在1 000次的迭代次數(shù)內(nèi)pm的變化曲線。可以看出，在起始階段由于粒子群在探測最優(yōu)值，混合進(jìn)化因子f值還較大，在一定代數(shù)內(nèi)，AFO-DPSO算法會維持一個大的變異概率pm；隨著f的急劇減小，pm值降至接近于0；當(dāng)f發(fā)生躍變時(shí)，pm也隨之產(chǎn)生一定的波動；至粒子群搜索達(dá)到收斂狀態(tài)后，pm基本保持在0值附近。

圖5 f1上變異概率pm的變化曲線

為了追蹤加速系數(shù)的變化，圖6給出了在f1上1 000次的迭代次數(shù)內(nèi)c1和c2的變化曲線。

筆者發(fā)現(xiàn)：在起始階段，由于粒子群在探測最優(yōu)值，在一定代數(shù)內(nèi)，c1在增加的同時(shí)c2在減少；然后在開拓收斂狀態(tài)時(shí)，c1和c2倒轉(zhuǎn)了它們的變化方向；躍出狀態(tài)也能夠被檢測出來，其中，c2的值在增加而c1的值卻在減少。

圖6 測試函數(shù)f1上加速系數(shù)的自適應(yīng)變化曲線

綜上，進(jìn)化因子、分?jǐn)?shù)階次、加速系數(shù)和變異概率的搜索行為表明經(jīng)過改進(jìn)后的FO-DPSO算法能夠識別出粒子的進(jìn)化狀態(tài)，并能根據(jù)粒子的狀態(tài)信息來自適應(yīng)地調(diào)整控制參數(shù)。同時(shí)，這也說明本文提出的AFO-DPSO算法是有效且可行的。

5 結(jié)束語

為了能有效解決分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法的收斂性能嚴(yán)重依賴于分?jǐn)?shù)階次α取值這一問題，同時(shí)進(jìn)一步加快算法的收斂速度，本文提出一種根據(jù)粒子的狀態(tài)信息來動態(tài)調(diào)整分?jǐn)?shù)階次α的自適應(yīng)控制策略，并引入自適應(yīng)的加速系數(shù)控制準(zhǔn)則和變異處理機(jī)制，在此基礎(chǔ)上給出了AFO-DPSO算法。對幾種典型函數(shù)的測試結(jié)果表明，相比于現(xiàn)有的PSO、HPSO、DPSO、APSO、FO-PSO、FO-DPSO與NCPSO算法，本文的AFO-DPSO算法的搜索精度、收斂速度和穩(wěn)定性都有了顯著提高，全局尋優(yōu)能力得到了極大提升。此外，對進(jìn)化因子、分?jǐn)?shù)階次、加速系數(shù)和變異概率的搜索行為分析進(jìn)一步驗(yàn)證了本文提出算法的有效性和可行性。下一步研究方向是如何確保收斂性能不變的同時(shí)降低AFO-DPSO算法的計(jì)算復(fù)雜度。

[1] KENNEDY J, EBERHART R. Particle swarm optimization[A]. Proc IEEE International Conf on Neural Networks[C]. 1995.1942-1948.

[2] CHEN, W N, ZHANG. A novel set-based particle swarm optimization method for discrete optimization problem[J]. IEEE Transactions on Evolutionary Computation, 2010, 14 (2): 278-300.

[3] ZHANG T, HU T S, ZHENG Y, GUO X N. An improved particle swarm optimization for solving bi-level mulitiobjective programming problem[J]. Journal of Applied Mathematics, 2012, 2(4): 1-13.

[4] HO S Y, LIN H S, LIAUH W H, etal. OPSO: Orthogonal particle swarm optimization and its application to task assignment problems[J].IEEE Transactions on Systems, Man, Cybernetics A: Systems, Humans, 2008, 38(2):288-298.

[5] NIE F, TU T, PAN M, etal. K-Harmonic Means Data clustering with PSO Algorithm[M]. Springer Berlin Heidelberg, 2012.67-73.

[6] VARSHNEY S, SRIVASTAVA L, PANDIT M. Parameter tuning of statcom using particle swarm optimization based neural network[J].Intelligent and Soft Computing, 2012, 130(3): 813-824.

[7] NAKA S, GENJI T, YURA T, etal. A hybrid particle swarm optimization for distribution state estimation[J]. IEEE Trans on Power Syst,2003,18(1):60-68.

[8] KROHLING R. Gaussian particle swarm with jumps[A]. Proc IEEE Congr Evol Comput[C]. 2005.1226-1231.

[9] TILLETT J, RAO T, SAHIN F, etal. Darwinian particle swarm optimization[A]. Indian International Conference on Artificial Intelligence[C]. 2005.1474-1487.

[10] 胥小波, 鄭康鋒, 李丹等. 新的混沌粒子群優(yōu)化算法[J]. 通信學(xué)報(bào),2012, 33(1): 24-31.XU X B, ZHENG K F, LI D, etal. New chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012, 33(1): 24-31.

[11] GUTIéRREZ R E, ROSáRIO J M, MACHADO J T. Fractional order calculus: basic concepts and engineering applications[J]. Mathematical Problems in Engineering, 2010, 2010:1-19.

[12] MACHADO J A T, JESUS I S, BARBOSA R, etal. Application of fractional calculus in engineering[J]. Dynamics, Games and Science I,Springer Proceedings in Mathematics, 2011, 1: 619-629.

[13] BENSON D A, MEERSCHAERT M M, REVIELLE J. Fractional calculus in hydrologic modeling: a numerical perspective[J]. Water Resources, 2013,51:479-497.

[14] GHAMISI P, COUCEIRO M S, BENEDIKTSSON J A, etal. An efficient method for segmentation of images based on fractional calculus and natural selection[J]. Expert Systems with Applications, 2012,39(16): 12407-12417.

[15] PIRES J A, MOURA P B, OLIVEIR A M, etal. Particle swarm optimization with fractional-order velocity[J]. Nonlinear Dynamics, 2010,61(1-2): 295-301.

[16] COUCEIRO M S, ROCHA R P, FONSECA FERREIRA N M, etal.Introducing the fractional-order Darwinian PSO[J]. Signal, Image and Video Processing, 2012,6(3):343-350.

[17] ZHAN Z, ZHANG J, LI Y, etal. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems, Man, Cybernetics B: Cybernetics, 2009,39(6):1362-1381.

[18] ALIREZA A. PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems[J]. Acta Automatic Sinica, 2011, 37(5):541-549.

[19] CHEN X, ZHANG Y. Optimum design of PID controller parameters by improved particle swarm optimization algorithm[J]. Computer Science and Information Engineering, Lecture Notes in Electrical Engineering, 2012, 2(2):79-84.

[20] BERGH F V, ENGELBRECHT A P. A study of particle swarm optimization particle trajectories[J]. Inf Sci, 2006, 176(8): 937-971.

[21] 周殊, 潘煒, 羅斌等. 一種基于粒子群優(yōu)化方法的改進(jìn)量子遺傳算法及應(yīng)用[J]. 電子學(xué)報(bào), 2006, 34(5):897-901.ZHOU S, PAN W, LUO B, etal. A novel quantum genetic algorithm based on particle swarm optimization method and its application[J].Acta Electronica Sinica, 2006, 34(5):897-901.

[22] WOLPERT D H, MACREADY W G. No free lunch theorems for optimization[J]. IEEE Trans Evol Comput, 1997, 1(1):67-82.