基于微分控制策略的快速粒子群優化算法

樊呂彬,劉亞紅,張 瑋

(太原理工大學 化學化工學院,太原 030024)

0 概述

粒子群優化(Particle Swarm Optimization,PSO)算法是一種基于種群全局隨機搜索策略的智能進化算法[1]。相比于其他智能算法,粒子群優化算法在解決多目標優化、動態尋優等問題上,具有結構簡單、易編程實現等特點,被廣泛應用于函數優化、資源配置、神經網絡訓練和路徑選擇等多個領域。

為提高粒子群優化算法種群在進化后期的多樣性,避免尋優過程陷入局部最優,克服早熟收斂,相關學者提出了多種改進方法,按照改進機制的不同主要是在參數設置[2]、學習機制[3]和拓撲結構[4]等3個方面。

相應的改進算法在避免陷入局部最優上取得了較好的效果,但對于加快算法的尋優速度、提高優化效率,則需要考慮研究算法本身的特性進而找到改進策略。比例-積分-微分(Proportional-Integral-Derivative,PID)控制是目前最常用的控制策略,已大量應用于各種控制問題。受PID控制的啟發,文獻[5]認為PSO是一種有2個輸入和1個輸出的反饋控制系統,通過在粒子群優化算法中引入加速度項,使算法進化行為呈現三階系統特性,增加種群產生的多樣性;文獻[6]針對PIDPSO引入加速度項后可選參數多的問題,為提高算法的計算效率,使參數隨著進化代數而變化,提出了一種自適應PID粒子群算法;文獻[7]提出了一種增量型PID控制器PSO(IPID-PSO),通過對粒子軌跡特性的分析,經過變換后將粒子群速度更新機制解釋為一個增量型PID控制過程。

本文受前人工作的啟發,研究種群尋優過程的運行機制,推導出PSO近似于一種比例-積分(Proportional-Integral,PI)控制,而由于其固有積分屬性的存在,使算法收斂速度變慢。為使種群在尋優過程中快速向最優位置搜索,減少與全局最優值之間的偏差,避免尋優過程振蕩,通過添加微分項,提出微分控制的改進策略,利用該策略加快標準粒子群及其改進算法的收斂速度,改善搜索特性,提高尋優效率。

1 粒子群算法速度軌跡分析

在標準PSO中,整個種群隨機初始化m個粒子,每個粒子根據其速度和位置的不同,隨機分配一個速度向量vi(t)和位置向量xi(t)。粒子在多維空間的飛行過程中逐代搜索最優解,其中每個粒子都是潛在解。粒子根據其自身和整個種群所經過的最好適應度值的位置確定下一次飛行的速度和方向,個體所經過的適應度最好位置稱為個體最優點pbest,種群經過的適應度最好的位置稱為全局最優點gbest。種群根據個體最優點和全局最優點進行逐代進化,其速度更新公式為:

vi,d(t+1)=wvi,d(t)+c1r1(pbesti,d-xi,d(t))+

c2r2(gbestd-xi,d(t))

(1)

種群位置更新公式為:

xi,d(t+1)=xi,d(t)+vi,d(t+1)

(2)

其中,w稱為慣性權重,表示對上一代速度的慣性繼承。c1和c2為常數,分別稱為個體和社會加速因子,用以調節迭代步長。r1和r2為取值在[0,1]之間服從均勻分布的隨機數。

2 粒子群優化算法的控制策略分析及改進

2.1 粒子群算法控制策略分析

在標準粒子群算法中,加速因子c1和c2可以平衡種群在進化過程中的全局勘探和局部探索能力,通常取c1=c2=c,則由式(1)得:

(3)

其中,a1為取值在[0,1]之間的隨機數,a為取值在[0,2]之間的隨機數。

令B(t)=a1pi(t)+(1-a1)pg(t),則B(t)為個體最優值位置與全局最優值位置的矢量和,將其代入式(3)可得:

v(t+1)=wv(t)+ca{B(t)-x(t)}

(4)

根據控制策略理論,將粒子群優化算法視為反饋控制系統,把種群個體作為控制對象,B(t)位置為給定值,個體位置x(t)為測量值,則其反饋控制的系統偏差為e(t)=B(t)-x(t),通過負反饋調節,使粒子的當前位置向最優粒子靠近。

首先假設每次迭代時最優粒子位置B(t)固定,將式(4)帶入式(2)中得:

x(t+1)=x(t)+wv(t)+ca{B(t)-x(t)}

(5)

Ex(t+1)-Ex(t)=wEv(t)+c(B′-Ex(t))

(6)

利用式(6)的遞推關系可得:

(7)

根據偏差e(t)的定義將上式整理為:

x(1)-wx(0)-(1-w)B′

(8)

則其速度期望為:

(9)

式(9)通過與PID控制策略的位置型表達式(10)[8]相類比,可得粒子群優化算法的速度更新機制為比例-積分(Proportional-Integral,PI)控制。

(10)

其中,比例項為Kp=1-w,積分項Ki=c,速度初值為x(1)-wx(0)-(1-w)B′。因此可以將標準粒子群算法視為一種比例-積分(PI)控制策略。

2.2 微分項粒子群算法控制策略

文獻[9]認為不同的系統性能參數會使粒子群算法的尋優過程呈現出不同性能:超調量越大則種群將會在更大搜索空間中尋優,算法具有更強的探測能力;衰減比越大,則種群將以更快的速度靠近最優值位置,但會減弱粒子群的搜索能力,不利于跳出局部最優。

根據偏差的比例(P)、積分(I)、微分(D)進行控制,是控制系統中應用最為廣泛的一種控制規律。經過上節分析可知,粒子群優化算法的尋優過程為比例-積分(PI)控制。若在粒子群優化算法中加入微分控制項,則:

1)微分控制項會減小超調量和衰減比,克服系統振蕩,使響應過程更加柔和,提高系統的穩定性。

2)微分控制能夠加快系統的響應速度,減小調整時間,使得系統響應快速趨于穩態。

離散化的微分項位置型控制算式為:

D(t)=Kd(e(t)-e(t-1))

(11)

離散控制算式有位置型和增量型2種。位置型控制算式會使偏差逐代累積,同時占用較多的數據儲存單元,不利于計算機運算。因此,將微分項的位置型控制算式相減可得增量型控制算式:

ΔD(t)=D(t)-D(t-1)=

Kd(e(t)-e(t-1))-Kd(e(t-1)-e(t-2))=

Kd{(B(t)-x(t))-2(B(t-1)-x(t-1))+

(B(t-2)-x(t-2))

(12)

將上式帶入標準粒子群算法的速度迭代方程,可得帶微分控制項的速度迭代方程:

(13)

由于在進化過程中通過對標準粒子群算法引入微分項,利用微分控制策略對最優位置的偏差進行反饋調節,因此同樣可將微分環節引入到改進粒子群算法中。

通過將微分控制項引入標準粒子群優化(Standard SPO,SPSO)算法及全信息粒子群(Full Information Particle Swarm,FIPS)算法[10],分別可得其改進算法D-SPSO和D-FIPS的速度迭代方程。

D-SPSO算法速度迭代方程為:

vi,d(t+1)=wvi,d(t)+c1r1(pbesti,d-xi,d(t))+

c2r2(gbestd-xi,d(t))+ΔDi

(14)

D-FIPS算法速度迭代方程為:

vi,d(t+1)=wvi,d(t)+ck(FIPS(t)-xi,d(t))+ΔDi

(15)

其中,B=FIPS(t)。

2.3 軌跡特性分析

由于粒子群算法在解空間中進行隨機搜索,因此搜索軌跡的穩定性是衡量其性能的重要指標[11],以改進算法D-SPSO為例對其搜索軌跡的收斂性進行證明。

定理參數w、c1+c2和Kd滿足條件式(16)時,D-SPSO算法是穩定收斂的。

(16)

證明:通過進化方程可以看出,粒子在每一維的更新都是相互獨立的,且由于各粒子是隨機生成,因此可以將算法設為一維情況進行處理,其結果同樣適用于其他粒子。根據降維簡化,將式(14)帶入式(2),得到如下離散型迭代公式:

xt+3+(c1r1+c2r2-1-w+Kd)xt+2+(w-2Kd)xt+1+

Kdxt-c1r1pbest(t)-c2r2gbest(t)=0

(17)

(18)

根據Z變換平移定理[13]對式(18)進行變換操作,經整理后如下:

(z3+T1z2+T2z+T3)Ex(z)=S

(19)

z2[x(1)+T1x(0)]+z[x(2)+T1x(1)+T2x(0)]

Au3+Bu2+Cu+D=S

(20)

其中,A=1+T1+T2+T3,B=3+T1-T2-3T3,C=3-T1-T2+3T3,D=1-T1+T2-T3。

由式(20)可以得出,其特征方程為:

Au3+Bu2+Cu+D=0

(21)

離散系統穩定性判據:在勞斯陣列表第1列元素均大于0,且特征方程各系數均取正值時,系統趨于穩定。

根據離散系統穩定性判據可得,若要使系統趨于穩定,則特征方程式(21)應滿足下式:

(22)

即當參數w、c1+c2和Kd滿足條件式(22)時,每個粒子的尋優軌跡收斂,種群尋優過程趨于穩定。證畢。

2.4 算法流程

微分控制策略標準粒子群算法D-SPSO的執行流程如圖1所示。

圖1 D-SPSO算法流程

微分控制策略全信息粒子群算法D-FIPS的執行步驟如下:

步驟1初始化種群,隨機生成種群中各粒子位置和速度,并設置各參數值。

步驟2計算種群中每個粒子適應度值。

步驟3更新種群個體最優點pbest及個體最優值pbestval。

步驟4更新種群各鄰域中的全信息系數ck及全信息粒子FIPS[10]。

步驟5根據式(12)和式(15)計算微分控制項的增量型控制算式ΔD。

步驟6按照式(15)和式(2)對種群速度和位置進行更新。

步驟7判斷是否達到終止條件,若滿足,則停止迭代,輸出最優值;否則,迭代次數t=t+1,并轉至步驟2。

3 實驗仿真及性能分析

3.1 仿真實驗結果

為了驗證微分控制策略的有效性,分別利用標準粒子群算法SPSO和改進算法FIPS進行實驗,并選取7個經典測試函數,通過仿真實驗分析其性能。測試函數的尋優范圍、極值和目標精度如表1所示。

表1 經典測試函數

Sphere為單模態二次函數,在定義域中只有全局極小值點沒有局部極小值點,是評價算法收斂精度的經典函數;Rosenbrock為非凸、病態單峰函數,最優點不在空間中心,算法很難辨別搜索方向;Griewank為劇烈震蕩的多峰函數,其局部極小值隨維數不斷增加,在低維空間更難尋優;Ackely為具有大量局部最優點的多峰函數,全局最優解位于一個狹窄區域,多峰函數常用以評價算法跳出局部最優的性能。

在實驗過程中,每組實驗獨立運行30次,種群經過5 000次迭代后停止運行,即達到2.5E+05次函數計算次數(FE)時終止運算。種群規模設為50,在30維空間內進行尋優,粒子的最大尋優速度Vmax通常設置為尋優范圍的0.1倍。慣性權重w采用文獻[14]提出的線性遞減慣性權重策略,以平衡進化過程中的局部和全局搜索能力。

根據軌跡穩定性分析可得:當參數w、c1+c2取值為表2中時,Kd取值為[0,0.2]。分別對微分控制策略的Kd采用階躍值和固定值,采用階躍值時,前期較大的Kd有助于增加微分控制的作用,減小系統的超調量,加快收斂速度;后期采用較小的Kd,突出積分項的影響,增加種群的多樣性,同時進行精細搜索提高精度,從而在整個過程中提高尋優效率。各算法的參數設置如表2所示。

表2 各算法及參數設置

3.2 算法性能分析

3.2.1 優化精度分析

從表3中的尋優結果來看,相比于標準SPSO,D-SPSO1和D-SPSO2算法對各個函數的適應度均值都有提高,表明在相同的計算次數下,D-SPSO具有更高的計算效率。其中,Mean表示在經過2.5E+05次函數計算后,所得到的平均適應度值,Std表示2.5E+05次函數計算后的標準差,Min表示迭代達到終止條件時,函數所得到的最小適應度值,Imp表示改進算法的平均適應度值提升程度。在方差方面,D-SPSO對函數F1、F2、F4、F7取得的性能上的提高,有助于提高算法的穩定性。同樣對于改進算法FIPS,如表4所示,D-FIPS1和D-FIPS2算法對函數F1、F3、F5、F7的適應度均值都有較大提高,且方差優于FIPS,可見微分控制策略不但提高了計算效率也增強了算法的穩定性。

表3 測試函數仿真結果1

表4 測試函數仿真結果2

為便于比較微分策略對粒子群改進算法的性能提高程度,通過適應度均值[15]研究其性能的提升:

(23)

若微分控制改進粒子群算法得到的適應度均值更小,則Imp為正值,否則其為負值。

由表3、表4可以看出,D-SPSO和D-FIPS對原算法的平均適應度均有提高,其中,D-SPSO對函數F1、F2、F4、F5和F7的提高均在30%左右;D-FIPS對函數F1、F3、F5和F7取得了近似于100%的改進效果。對于改進算法較難優化的多峰函數和旋轉與偏移函數,D-SPSO和D-FIPS取得了較好的平均適應度提升度。同時根據平均提升度可以看出,在Kd采用階躍值時,對于優化性能的提升度要高于采用固定值,說明在不同時期微分控制作用的強弱,對粒子群算法性能的改進具有明顯的影響。

3.2.2 算法復雜度及平均計算次數分析

算法復雜度[16]是評估算法性能的一個重要指標,決定了算法的尋優速度和優化效率。以標準粒子群算法SPSO為例,設求解問題的維數為D,種群規模為N,最大迭代次數為T。在每次進化過程中,算法主要的計算量包括粒子個體最優位置更新與全局最優位置更新兩部分,在引入微分控制策略后,由于位置B(t)為pbest和gbest的矢量和,其更新由后者位置更新來確定。最復雜情況下最大計算時間復雜度為T×O(N×D),保留最優個體的存儲空間復雜度為O(N×D),所以該算法的最大復雜度:

O(T,N,D)=T×O(N×D)+O(N×D)

(24)

由式(24)可以得到,相對于基本粒子群算法,在引入微分項后,微分策略的粒子群算法并沒有明顯地增加算法的復雜度。

圖2和圖3為各算法在經過30次實驗仿真后所需的平均計算次數,其中函數計算次數(FE)反映了各算法在尋優過程中調用測試函數的次數。從圖中可以看出:對各測試函數,SPSO和FIPS算法的時間復雜度均最大,在引入微分策略后,使D-SPSO和D-FIPS算法達到尋優要求時的函數計算次數最少,加快了尋優速度。

圖2 SPSO與D-SPSO測試函數平均計算次數

圖3 FIPS與D-FIPS測試函數平均計算次數

3.2.3 優化成功率分析

表5、表6記錄了各算法的函數計算次數和收斂成功率。其中,Fe表示算法在固定函數迭代次數內滿足閾值所需的平均函數計算次數,反映了收斂速度的快慢,SR表示算法成功收斂試驗次數占總試驗次數的比例。算法SPSO、D-SPSO1和D-SPSO2的平均函數計算次數分別為116 745、19 466和73 826,平均收斂成功率分別為76.19%、84.76%和80.48%。算法FIPS、D-FIPS1和D-FIPS2的平均函數計算次數分別為127 772、24 210和81 170,平均收斂成功率均為100%。證明D-SPSO和D-FIPS不僅能以很少的函數計算次數達到尋優精度要求,同時也能取得較高的成功率,說明微分控制策略不僅提高了優化速度也能夠避免陷入局部最優,具有良好的優化效率。

表5 仿真所需函數計算次數及成功率1

表6 仿真所需函數計算次數及成功率2

3.2.4 優化過程曲線

為了更加直觀地反映各算法的搜索特性,對SPSO和FIPS分別選擇不同的測試函數,與相應的微分控制策略改進算法進行比較。從圖4～圖7可以看出,微分策略在保證足夠的尋優精度條件下,能夠加快種群尋優速度,提高優化效率,同時對于采用不同Kd的微分策略,在不同時期微分作用的強弱對取得不同的進化速度有明顯差異。

圖4 Sphere函數收斂曲線

圖5 ShiftedRosenbrock函數收斂曲線

圖6 Ackley函數收斂曲線

圖7 RotatedGriewank函數收斂曲線

4 結束語

本文通過對粒子群優化算法進行軌跡分析,認為其搜索過程為比例-積分(PI)控制策略,通過在標準粒子群及其改進算法中引入微分項,提出微分控制策略的快速粒子群算法。通過對D-SPSO和D-FIPS進行仿真實驗對比,認為微分控制策略的改進算法在解決大多數測試函數時能達到預設尋優精度,并且其函數計算次數少、尋優速度快。證明了引入該策略的改進粒子群優化算法在解決進化過程中出現的尋優效率低和尋優速度慢的問題上,取得了良好的效果,而且該策略不僅適用標準粒子群算法,對于改進優化算法也有較好的效果,對大多數粒子群算法都具有適用性,具有良好的應用拓展性。

[1] KENNEDY J,EBERHART R.Particle Swarm Optimization[C]//Proceedings of the 4th IEEE International Cofference on Neural Netwoks.Washington D.C.,USA:IEEE Press,1995:1942-1948.

[2] RATNAWEERA A,HALGAMUGE S K,WATSONH C.Self-organizing Hierarchical Particle Swarm Optimizer with Time-varying Acceleration coefficients[J].IEEE Transactions on Evolutionary Computation,2004,8(3):240-255.

[3] LIANG J J,QIN A K,SUGANTHAN P N,et al.Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions[J].IEEE Transactions on Evolutionary Computation,2006,10(3):281-295.

[4] KENNEDY J,MENDES R.Population Structure and Particle Swarm Performance[C]//Proceedings of the Evolutionary Computation Congress.Washington D.C.,USA:IEEE Press,2002:1671-1676.

[5] CUI Zhihua,CAI Xingjuan.Integral Particle Swarm Optimization with Dispersed Accelerator Information[J].Fundamenta Informaticae,2009,95(4):427-447.

[6] 蔡星娟,崔志華,曾建潮,等.自適應PID控制微粒群算法[C]//第二十六屆中國控制會議論文集.北京:[出版者不詳],2007.

[7] ZHANG J,YANG S.A Novel PSO Algorithm Based on an Incremental PID Controlled Search Strategy[J].Soft Computing,2016,20(3):991-1005.

[8] 于海生.計算機控制技術[M].北京:機械工業出版社,2007.

[9] ZHANG Wei,LIU Jiao,FAN Lübin,et al.Control Strategy PSO[J].Applied Soft Computing,2016,38(3):75-86.

[10] MENDES R,KENNEDY J,NEVES J.The Fully Informed Particle Swarm:Simpler,Maybe Better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[11] 韓 璞,孟 麗,王 彪,等.粒子群算法中粒子軌跡特性研究[J].計算機仿真,2015,32(12):235-240.

[12] 張 瑋,王化奎.粒子群算法穩定性的參數選擇策略分析[J].系統仿真學報,2009,21(14):4339-4344,4350.

[13] 李 寧,孫德寶,鄒 彤,等.基于差分方程的PSO算法粒子運動軌跡分析[J].計算機學報,2006,29(11):2052-2060.

[14] SHI Yuhui,EBERHART R.Parameter Selection in Particle Swarm Optimization[C]//Proceedings of International Conference on Evolutionary Programming.Berlin,Germany:Springer,1998:591-600.

[15] LIM W H,ISA M N A.Adaptive Division of Labor Particle Swarm Optimization[J].Expert Systems with Applications,2015,42(14):5887-5903.

[16] 王永貴,林 琳,劉憲國.基于CGA和PSO的雙種群混合算法[J].計算機工程,2014,40(7):148-153.