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

榮 兵，陳 華

(中國石油大學(xué)(華東)理學(xué)院, 山東 青島 266580)

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

榮 兵，陳 華

(中國石油大學(xué)(華東)理學(xué)院, 山東 青島 266580)

針對傳統(tǒng)的粒子群優(yōu)化算法中存在的問題及分?jǐn)?shù)階達(dá)爾文微粒群優(yōu)化(FDPSO)算法收斂速度慢，收斂精度不高的問題，改進(jìn)其算法中分?jǐn)?shù)階速度更新策略，同時引入Logistic型混合分?jǐn)?shù)階自適應(yīng)動態(tài)調(diào)整策略，得到一種改進(jìn)的自適應(yīng)分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化(LFDPSO)算法，并通過相應(yīng)理論分析，證明了該算法在給定條件下的收斂性，并由6個經(jīng)典函數(shù)的數(shù)值測驗表明，Logistic型混合自適應(yīng)分?jǐn)?shù)階達(dá)爾文粒子群(LFDPSO)算法在收斂精度和收斂速度上得到了有效改善與提高，粒子在局部最優(yōu)時的逃逸能力、全局尋優(yōu)及智能搜索能力顯著增強(qiáng)。

分?jǐn)?shù)階；粒子群；達(dá)爾文；自適應(yīng)；速度更新；收斂速度

0 引言

粒子群優(yōu)化(PSO，partical swarm optimization)算法是近年來快速發(fā)展的一種智能全局尋優(yōu)方法[1]。這種方法有它不可取代的尋優(yōu)特點，在優(yōu)化組合[2]、多目標(biāo)聯(lián)合搜索[3]、任務(wù)分配[4]、聚類分析[5]、神經(jīng)網(wǎng)絡(luò)[6]等眾多領(lǐng)域得到了比較廣泛的使用。PSO算法在使用中存在著一些不盡人意的地方，如在尋優(yōu)的開始階段，算法的收斂速度較快，而在全局尋優(yōu)的后期，單純的粒子群算法容易陷入早熟，進(jìn)而影響粒子群算法尋優(yōu)的精度，這也是群智能優(yōu)化算法的一種通病。

最近幾年，為了改進(jìn)粒子群算法的不足之處，諸多學(xué)者做了較為深刻的探索，Jason等[7]提出達(dá)爾文粒子群優(yōu)化(DPSO，Darwinian partical swarm optimization)算法，將生態(tài)環(huán)境中的自然選擇的策略引入到粒子群算法之中。分?jǐn)?shù)階微積分理論(FOC，fractional ordercalculus) 作為一種快速發(fā)展的、非常重要且有用的數(shù)學(xué)工具在自然科學(xué)利于如水文建模，神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得的成果越來越明顯[8-9]，Pires等[10]提出了分?jǐn)?shù)階粒子群優(yōu)化(FPSO)算法，將分?jǐn)?shù)階微積分的相關(guān)知識引入到粒子群優(yōu)化算法中，進(jìn)而，通過改進(jìn)其速度導(dǎo)數(shù)的階數(shù)來控制FPSO算法的收斂效率。由Pires等所研究的FPSO算法中得到啟示，Micael等[11]提出了一種分?jǐn)?shù)階達(dá)爾文粒子群(FDPSO，fractional order Darwinian partical swarm optimization)算法，將分?jǐn)?shù)階這一數(shù)學(xué)工具同達(dá)爾文粒子群優(yōu)化算法結(jié)合起來，集中起兩者的優(yōu)點，較大程度上提高了收斂速度及收斂精度，實驗結(jié)果也表明，較之傳統(tǒng)的其它粒子群優(yōu)化算法，該算法其在計算精度和收斂速度上均表現(xiàn)不俗。

本文為了進(jìn)一步提高其收斂的精度及速度，改進(jìn)了FDPSO算法的分?jǐn)?shù)階更新公式，但算法在后期任然存在多樣性漸失，收斂速度減慢，精度降低，且算法容易陷入局部最優(yōu)。陳華等[12]提出了基于logistic模型之上的一種動態(tài)加速因子的自適應(yīng)微粒群優(yōu)化(APSO，adaptive partical swarm optimization)算法，該算法能夠有效地提高相應(yīng)算法的收斂速度及收斂精度，尤其是在提高收斂速度方面，有著較好的效果，主要通過把這種logistic型的動態(tài)調(diào)整策略運用到FDPSO算法之中形成Logistic FDPSO算法，在下文中簡稱LFDPSO，且考慮到此模型在算法后期面臨的易陷入局部最優(yōu)的問題，提出了一種混合的自適應(yīng)動態(tài)調(diào)整策略，在后期通過粒子群中粒子本身的狀態(tài)信息來對分?jǐn)?shù)階進(jìn)行調(diào)整，使其具有逃逸局部最優(yōu)的能力，提高其算法的收斂速度和收斂精度。

1 分?jǐn)?shù)階達(dá)爾文粒子群(FDPSO)算法改進(jìn)

1.1 PSO算法基本原理

在一個有N個粒子所構(gòu)成的D維目標(biāo)搜索空間的粒子群中， 用Xi=(xi1,xi2,…，xiD)表示第i個粒子的位置向量，用Vi=(vi1,vi2,…,viD)表示第i個粒子的速度向量。對應(yīng)的粒子的速度和位置更新公式如下：

vid(t+1)=ωvid(t)+c1r1d(pid(t)-xid(t))+

c2r2d(pgd(t)-xid(t))

(1)

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

(2)

在式(1)中，i=1,2,…N;d=1,2,…，D；ω是慣性系數(shù)，c1、c2是加速系數(shù)；r1d、r2d是[0,1]之間的隨機(jī)數(shù)；pid是第i個粒子本身找到的歷史最優(yōu)位置，即局部最優(yōu)值點；pgd是該粒子群找到的群體中的最優(yōu)位置，即全局最優(yōu)值點。粒子群中每個粒子可以根據(jù)式(1)和式(2)進(jìn)行迭代，最終使得算法逼近全局最優(yōu)值處。

1.2 DPSO算法基本原理

DPSO基本思想是粒子群中每個粒子可以通過找到更好的適應(yīng)值來獲得增加自己的存活壽命的機(jī)會，同時可以通過增加新的種群粒子來提高全局尋優(yōu)過程的后期搜索的速度。如果粒子存活的時間越長，則它產(chǎn)生后代的概率也就越大，而且后代中保存了一些適應(yīng)值比較好的粒子。在粒子群中，粒子的壽命是否會縮短取決于它在目標(biāo)搜索過程中有沒有找到更好的適應(yīng)值位置，相應(yīng)的，如果沒能找到延長壽命的較好的適應(yīng)值，粒子群中那些較差性能的粒子可能就會被刪除，當(dāng)粒子群中粒子的數(shù)量減少到一定值時，該粒子群淘汰。

(3)

其中:Nkill為在粒子適應(yīng)值沒有任何改善的一段時間內(nèi)粒子群中被刪除的粒子的數(shù)目。

在該算法的實現(xiàn)過程中，若要產(chǎn)生一個新的粒子群，必須保證粒子群中沒有粒子被刪除，并且所存在的最大粒子群數(shù)量不能超過給定的最大值。綜合上述所有要求，該算法創(chuàng)建新的粒子群概率僅僅為：

p=f/Ns

(4)

其中:f為[0, 1]之間的隨機(jī)數(shù)，Ns為粒子群數(shù)目。

1.3 FDPSO算法中分?jǐn)?shù)階速度更新策略的改進(jìn)

根據(jù)文獻(xiàn)[13-16]，可以得出對傳統(tǒng)導(dǎo)數(shù)的極限定義為：

(5)

把這個定義擴(kuò)展到任意的實數(shù)α就得到了Grunwald-Letnikov分?jǐn)?shù)階導(dǎo)數(shù)的定義：

(6)

即α階Grunwald-Letnikov分?jǐn)?shù)階導(dǎo)數(shù)。整理得另一種表達(dá)式的形式為：

(7)

式(7)，離散時間的實現(xiàn)表達(dá)式可以被定義為：

(8)

其中:T為采樣周期，r為截斷階數(shù)。

假定式(1)的慣性權(quán)重ω=1以及采樣周期T=1，由文獻(xiàn)[17]我們可以得到下面的表達(dá)式：

aDtαvid(t+ 1) =c1r1d(pid(t)-xid(t))+

c2r2d(pgd(t)-xid(t))

(9)

隨著迭代次數(shù)的增加，當(dāng)代粒子群中的粒子與最初幾代的關(guān)系逐漸淡化，在本文中我們?nèi)=4，即我們只保留前4代的速度向量，并取T=1，由式(7)和式(8)，可以得到：

aDtαvid(t+ 1) =vid(t+ 1)-αvid(t) +

(10)

再由式(9)和式(10)，得改進(jìn)的速度更新策略如下：

c1r1d(pid(t)-xid(t))+c2r2d(pgd(t)-xid(t))

(11)

其形式不同于文獻(xiàn)[11，17]等論文中的分?jǐn)?shù)階速度更新策略：

c2r2d(pgd(t)-xid(t))

(12)

雖然形式相似，但數(shù)值實驗結(jié)果表明無論在收斂精度還是收斂速度上均有較明顯的改善。

2 Logistic型混合分?jǐn)?shù)階自適應(yīng)動態(tài)調(diào)整策略的引入

傳統(tǒng)的調(diào)整分?jǐn)?shù)階α的方法是在[0.5,0.8]之間線性減小，具體策略為：

(13)

其中:t為當(dāng)前的迭代步數(shù)，nger為總的迭代步數(shù)。

這種方法采取的是對分?jǐn)?shù)階的線性減少，在算法的后期，算法陷入局部最優(yōu)的可能性會變大，為了更好地避免算法的早熟問題的出現(xiàn)，本文提出一種基于logistic模型之上的混合調(diào)整分?jǐn)?shù)階α的自適應(yīng)策略。根據(jù)粒子最優(yōu)位置15步?jīng)]有發(fā)生較好變化的前后將算法分為前后兩個階段，在每一階段采取不同的分?jǐn)?shù)階α自適應(yīng)調(diào)整策略。

在算法的第一階段，分?jǐn)?shù)階α調(diào)整策略在算法過程中，為避免其早熟,α值在第一階段初期應(yīng)較大，并且α值減小的速度應(yīng)較大些，能加快算法的收斂速度；在第一階段后期，α值減小的速度應(yīng)趨緩,易搜索局部最優(yōu)值，使算法趨于穩(wěn)定。設(shè)α的最小值和最大值分別為αmax和αmin，若迭代開始時α的衰減率為a，隨著迭代次數(shù)的增加而衰減率減小，當(dāng)α減小到最小值αmin時，α停止減小，即衰減率為零。因此，α的變化規(guī)律符合logistic模型[18-19]，即：

(14)

對式(14)使用分離變量法來求解，可得到相應(yīng)縮放因子α的動態(tài)調(diào)整公式：

(15)

可以通過調(diào)整a值來調(diào)整加速因子α的下降速度。給定的初始衰減率a值越大些，α在算法前期的下降速度就越快寫，反之，c1的下降速度則比較慢。當(dāng)t=0時，α=αmax，而當(dāng)t→+∞時，比較容易證明α=αmin。

在算法的第二階段，分?jǐn)?shù)階α值比較小，為了有效避免其早熟現(xiàn)象的發(fā)生概率及增大粒子的拓展搜索空間的能力，我們采取一種根據(jù)粒子的狀態(tài)和最優(yōu)粒子的軌跡信息進(jìn)行動態(tài)調(diào)整，具體方法如下：

1)求出粒子群中每個粒子與其他粒子之間距離的和。

(16)

2)參照式(14)求出最優(yōu)粒子與其它粒子的距離之和dgbest。

3)計算分?jǐn)?shù)階α的階數(shù)。

(17)

Logistic型混合自適應(yīng)粒子群優(yōu)化算法(LFDPSO)算法流程如下：

(1)初始化

a)隨機(jī)生成所有粒子的速度和位置向量；

b)pi=Xi，i=1，2…,n；

c)將arg{minf(Xi)}賦給gbest其中f(·)為適應(yīng)值函數(shù)；

(2)終止條件判斷

a)如果終止條件已經(jīng)達(dá)到，gbest即為最優(yōu)解；

b)否則執(zhí)行步驟3；

(3)循環(huán)i從1到n

a) 判斷粒子處于第幾階段，根據(jù)(15)及(17)更新α；

b) 根據(jù)式(11)和式(2)更新Vi和Xi；

c) 計算第i個粒子的適應(yīng)值；

d)如果粒子群變得更好則獎勵粒子群：產(chǎn)生后代粒子、延長粒子壽命；

e)否則懲罰粒子群：銷毀粒子群、縮短其壽命；

f)如果f(Xi)優(yōu)于f(pi)，則pi=Xi；

(4)結(jié)束循環(huán)

(5)更新gbest=arg{minf(pi)}

(6)返回步驟2。

3 LFDPSO算法的收斂性分析

(18)

由式(2)xt+1=xt+vt+1得到vt=xt-xt-1，進(jìn)一步得到：

(19)

整理得出遞推公式：

(20)

式(20)可以用下面的矩陣乘積的形式表示：

上面矩陣的特征多項式為：

(21)

該特征多項式的一個根為λ1=1.0，設(shè)其他的特征根分別為λ2，λ3，λ4，λ5，λ6，則式(20)的當(dāng)前關(guān)系式為：

(22)

其中:k1,k2,k3,k4,k5,k6均是常數(shù)。

下證xt的收斂性，即：

(23)

當(dāng)λ>1時，特征多項式中(λ-1)恒正，如果此時另一部分，此處我們記為f(λ)恒正則證畢，當(dāng)λ<1時，特征多項式中(λ-1)恒負(fù)，此時f(λ)如果恒負(fù)則證畢，由前面的條件容易求出f(λ)當(dāng)λ=1時大于0，當(dāng)λ=-1時小于0，對f(λ)求導(dǎo)得：

f′(λ)=5λ4-4λ3(1+α-φ1-φ2)+3λ2[α+

(24)

由前面的條件容易求出當(dāng)|λ|>1時f′(λ)恒大于0，故當(dāng)λ>1時f(λ)>f(1)>0，當(dāng)λ<1時f(λ)1時，特征多項式恒大于0，故不存在比1大的特征根，證畢，并且對于所有的截斷r都成立。

4 數(shù)值實驗及結(jié)果分析

為了驗證Logistic型混合自適應(yīng)粒子群優(yōu)化(LFDPSO)算法的較之傳統(tǒng)的分?jǐn)?shù)階粒子群優(yōu)化(FO-PSO)算法，達(dá)爾文粒子群優(yōu)化(DPSO)算法，分?jǐn)?shù)階達(dá)爾文粒子群(FDPSO)算法的性能，選取該6個典型的實驗函數(shù)進(jìn)行測試，它們是在群智能優(yōu)化算法中被廣泛采用的測試函數(shù)(求最小值)，即Sphere、Rosenbrock、DeJong F4、Rastrigin、Griewank和Ackley函數(shù)[20]，其表達(dá)式為：

Sphere函數(shù):

(25)

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

Rosenbrock函數(shù):

(26)

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

DeJong F4函數(shù):

(27)

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

Rastrigin函數(shù):

(28)

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

Griewank函數(shù):

(29)

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

Ackley函數(shù):

(30)

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

這6個函數(shù)中前3個為單峰函數(shù)，后三個為多峰函數(shù)，它們的全局最優(yōu)值為f(x*)=0.0。本章試驗中的算法均選取相同參數(shù)r1d、r2d∈[0.3,0.6]，ω=1，c1=1.5，c2=1.5，其中除LFDPSO算法外的分?jǐn)?shù)階α采取的是線性減小，具體策略如式(12)。

其數(shù)值實驗結(jié)果如圖1所示，通過對比可以得到在迭代步數(shù)相同的情況下(本文為迭代200步)，改進(jìn)后的LFDPSO算法其最終收斂精度明顯高于分?jǐn)?shù)階粒子群優(yōu)化(FO-PSO)算法，達(dá)爾文粒子群優(yōu)化(DPSO)算法，分?jǐn)?shù)階達(dá)爾文粒子群(FDPSO)算法，在收斂速度方面，尤其在迭代后期收斂的速度的改善較為明顯，且有比較知道算法在后期具備了逃逸局部最優(yōu)的能力，全局收斂能力及智能搜索能力加強(qiáng)。

圖 LFDPSO算法在不同的測試函數(shù)上的性能比較

5 結(jié)束語

分?jǐn)?shù)階導(dǎo)數(shù)的應(yīng)用對于改進(jìn)粒子群算法來說具有非常重要的意義，使得粒子群算法中局部和全局速度特點更容易被算法理解，換句話說，即為粒子群算法更加智能化。

本文通過改進(jìn)FDPSO算法中分?jǐn)?shù)階速度更新策略，將分?jǐn)?shù)階更好的融入到PSO算法中來，充分利用了粒子群在尋優(yōu)過程中的歷史信息，并采取了Logistic型混合的分?jǐn)?shù)階自適應(yīng)動態(tài)調(diào)整策略，使得再改善收斂精度及收斂速度的基礎(chǔ)上，提高了粒子擴(kuò)展搜索空間的能力，通過實驗驗證，LFDPSO算法達(dá)到了較好的效果，但是在求解某些多峰函數(shù)的時候結(jié)果仍有陷入局部最優(yōu)的情況，在陷入局部最優(yōu)時，粒子如何逃逸仍然是下面一段時期的工作重點，在下一步工作中，將慣性權(quán)重因子及加速因子的調(diào)整策略與我們的方法結(jié)合，尋找效果更好的方法，并將其應(yīng)用到電磁計算如隨鉆側(cè)井的參數(shù)反演問題中，加快問題求解速度及提高問題的精度。

[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, et al. An improved particle swarm optimization for solving believed mulitiobjective programming problem[J]. Journal of Applied Mathematics, 2012, 2(4): 1-13.

[4] Ho S Y, Lin H S, Liauh W H, et al. 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, et al. K-Harmonic means data clusteing 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] Tillett J, Rao T, Sahin F, et al. Darwinian particle swarm optimization[A]. Indian International Conference on Artificial Intelligence[C]. 2005:1474-1487.

[8] Gutierrez R E, Rosario J M, Machado J T. Fractional order calculus: basic concepts and engineering applications[J]. Mathematical Proble- ms in Engineering,2010, 2010:1-19

[9] Machado J A T, Jesus I S, Barbosa R, et al. Application of fractional calculus in engineering[J]. Dynamics, Games and Science I, Springer Proceedings in Mathematics, 2011, 1: 619-629.

[10] Pires J A, Moura P B, Oliveir A M, et al. Particle swarm optimization with fractional-order velocity[J]. Nonlinear Dynamics, 2010, 61(1-2): 295-301.

[11] Couceiro M S, Rocha R P, Fonseca F N M, et al.Introducing the fractional - order Darwinian PSO[J]. Signal, Image and Video Processing, 2012,6(3):343-350.

[12] 陳華,范宜仁,等.一種動態(tài)加速因子的自適應(yīng)微粒群優(yōu)化算法[J].中國石油大學(xué)學(xué)報,2010, 34(6): 173-176.

[13] Podlubny I. Fractional differential equations[M]. San Diego: Academic Iess, 1999.

[14] Lshehawey E, Elbarbary E F, et al.On the solution of the endolymph equation using fractional calculus[J]. Appl. Math. Comput., 2001, 124(3): 337-341.

[15] Camargo R F, Chiacchio A O, Oliveira E C. Differentiation to fractional orders and the fractional telegraph equation [J]. Math.Phys., 2008,49(3): 033-505.

[16] Diethelm K. The analysis of fractional differential equations[M]. Berlin:Springcr-Vd:lag, 2010.

[17] Pires E J S, Machado J A T, Oliveira P B M, Cunha, et al. Particle swarm optimization with fractional-order velocity[J]. Nonlinear Dyn,2010,61(1/2): 295-301.

[18] Munkres J R. Topology [M]. 2nd ed. London: Prentice-Hall Inc, 2000.

[19] Guez-Lopez J S R, Romaguera S. The relationship between the Vietoris topology and the Hausdorff quasiuniformity[J]. Topology and Its Applications, 2002, 124: 451-464.

[20] 郭 通,蘭巨龍,李玉峰,等.自適應(yīng)的分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法[J].通信學(xué)報, 2014, 35(4): 130-140.

Logistic-model Hybrid Adaptive Fractional Order Darwinian Partical Swarm Optimization Algorithm

Rong Bing， Chen Hua

(College of Science, China University of Petroleum (East China), Qingdao 266580, China)

Aiming at the problems existing in the traditional particle swarm optimization algorithm and the problems existing in convergence speed and precision of fractional order Darwin particle swarm optimization (FDPSO) algorithm, improved the fractional order velocity update strategy of the algorithm, at the same time introduce dynamic logistic model hybrid adaptive strategy of the fractional order to form LFDPSO algorithm, through theoretical analysis and prove the convergence of the iterative algorithm under given conditions, and the experiments by six classical test functions show that the LFDPSO algorithm on the convergence accuracy and convergence speed has been further improved and enhanced, the escape ability of particles in local optimum, global optimization and intelligent search ability have achieved effective improvement.

fractional order; particle swarm; Darwinian; adaptive; speed-update; convergence rate

2017-02-23；

2017-03-14。

國家自然科學(xué)基金(41474100)；山東省自然科學(xué)基金(ZR2013DM015)。

榮 兵(1991- )，男，山東濱州人，碩士研究生，主要從事應(yīng)用數(shù)學(xué)(群智能優(yōu)化算法、并行算法) 方向的研究。

1671-4598(2017)08-0221-05

10.16526/j.cnki.11-4762/tp.2017.08.057

TP3

A

陳 華(1972- )，男，山東聊城人，碩士生導(dǎo)師，副教授，主要從事數(shù)學(xué)領(lǐng)域方向的研究。