Logistic型混合自適應分數階達爾文粒子群優化算法

榮 兵，陳 華

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

Logistic型混合自適應分數階達爾文粒子群優化算法

榮 兵，陳 華

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

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

分數階；粒子群；達爾文；自適應；速度更新；收斂速度

0 引言

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

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

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

1 分數階達爾文粒子群(FDPSO)算法改進

1.1 PSO算法基本原理

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

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；ω是慣性系數，c1、c2是加速系數；r1d、r2d是[0,1]之間的隨機數；pid是第i個粒子本身找到的歷史最優位置，即局部最優值點；pgd是該粒子群找到的群體中的最優位置，即全局最優值點。粒子群中每個粒子可以根據式(1)和式(2)進行迭代，最終使得算法逼近全局最優值處。

1.2 DPSO算法基本原理

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

(3)

其中:Nkill為在粒子適應值沒有任何改善的一段時間內粒子群中被刪除的粒子的數目。

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

p=f/Ns

(4)

其中:f為[0, 1]之間的隨機數，Ns為粒子群數目。

1.3 FDPSO算法中分數階速度更新策略的改進

根據文獻[13-16]，可以得出對傳統導數的極限定義為：

(5)

把這個定義擴展到任意的實數α就得到了Grunwald-Letnikov分數階導數的定義：

(6)

即α階Grunwald-Letnikov分數階導數。整理得另一種表達式的形式為：

(7)

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

(8)

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

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

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

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

(9)

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

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

(10)

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

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

(11)

其形式不同于文獻[11，17]等論文中的分數階速度更新策略：

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

(12)

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

2 Logistic型混合分數階自適應動態調整策略的引入

傳統的調整分數階α的方法是在[0.5,0.8]之間線性減小，具體策略為：

(13)

其中:t為當前的迭代步數，nger為總的迭代步數。

這種方法采取的是對分數階的線性減少，在算法的后期，算法陷入局部最優的可能性會變大，為了更好地避免算法的早熟問題的出現，本文提出一種基于logistic模型之上的混合調整分數階α的自適應策略。根據粒子最優位置15步沒有發生較好變化的前后將算法分為前后兩個階段，在每一階段采取不同的分數階α自適應調整策略。

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

(14)

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

(15)

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

在算法的第二階段，分數階α值比較小，為了有效避免其早熟現象的發生概率及增大粒子的拓展搜索空間的能力，我們采取一種根據粒子的狀態和最優粒子的軌跡信息進行動態調整，具體方法如下：

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

(16)

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

3)計算分數階α的階數。

(17)

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

(1)初始化

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

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

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

(2)終止條件判斷

a)如果終止條件已經達到，gbest即為最優解；

b)否則執行步驟3；

(3)循環i從1到n

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

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

c) 計算第i個粒子的適應值；

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

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

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

(4)結束循環

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

(6)返回步驟2。

3 LFDPSO算法的收斂性分析

(18)

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

(19)

整理得出遞推公式：

(20)

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

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

(21)

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

(22)

其中:k1,k2,k3,k4,k5,k6均是常數。

下證xt的收斂性，即：

(23)

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

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

(24)

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

4 數值實驗及結果分析

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

Sphere函數:

(25)

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

Rosenbrock函數:

(26)

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

DeJong F4函數:

(27)

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

Rastrigin函數:

(28)

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

Griewank函數:

(29)

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

Ackley函數:

(30)

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

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

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

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

5 結束語

分數階導數的應用對于改進粒子群算法來說具有非常重要的意義，使得粒子群算法中局部和全局速度特點更容易被算法理解，換句話說，即為粒子群算法更加智能化。

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

[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] 陳華,范宜仁,等.一種動態加速因子的自適應微粒群優化算法[J].中國石油大學學報,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] 郭 通,蘭巨龍,李玉峰,等.自適應的分數階達爾文粒子群優化算法[J].通信學報, 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。

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

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

1671-4598(2017)08-0221-05

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

TP3

A

陳 華(1972- )，男，山東聊城人，碩士生導師，副教授，主要從事數學領域方向的研究。