隨機選擇變異及自適應差分進化算法的研究

郭義波, 程際云, 李　芹, 楊　平

(1.上海電力學院, 上海　200090; 2.上海明華電力技術工程有限公司, 上?！?00437)

?

隨機選擇變異及自適應差分進化算法的研究

郭義波1, 程際云2, 李芹1, 楊平1

(1.上海電力學院, 上海200090; 2.上海明華電力技術工程有限公司, 上海200437)

摘要:為兼顧搜索速度和精度,提高搜索效率,克服不易跳出局部最優(yōu)的缺點,提出了隨機選擇變異策略、自適應調整變異率和自適應調整交叉率3種改進設想.利用3種改進設想改進DE算法,得到了7種改進算法,將7種改進算法應用到雙容水箱液位模型閉環(huán)辨識案例中.結果表明,7種改進算法都提高了跳出局部最優(yōu)的能力,綜合比較可知,3種改進設想同時應用的改進算法性能最優(yōu).

關鍵詞：差分進化算法; 隨機選擇變異; 自適應調整; 閉環(huán)辨識

差分進化算法(Differential Evolution,DE)是基于群體智能的優(yōu)化算法,它保留了基于種群的全局搜索策略,其特有的記憶功能使其能夠動態(tài)跟蹤搜索情況,從而調整搜索策略,具有較強的全局搜索能力和魯棒性[1].憑借算法參數(shù)少、搜索能力強、算法簡單等特點,差分進化算法在多目標路徑規(guī)劃[2]、梯級水庫調度優(yōu)化[3]、PID優(yōu)化[4]、模型參數(shù)辨識[5-6]等方面得到了廣泛的應用.然而與其他智能優(yōu)化算法相類似,差分進化算法也存在局部最優(yōu)、收斂精度不高及收斂速度慢等問題.為此,對基本差分進化算法進行了改進研究.文獻[7]提出了一種依據(jù)種群中個體的分布情況來調整算法參數(shù)的自適應差分進化算法,應用于模型參數(shù)辨識中,結果優(yōu)于遺傳算法及基本差分進化算法.文獻[8]針對常用變異策略DE/rand/1和DE/best/1的缺點提出了一種新的變異策略,為了平衡全局搜索與局部搜索能力采用自適應變異因子,辨識精度及速度優(yōu)于其他兩種改進算法及基本差分進化算法.文獻[9]提出了一種利用模糊邏輯來調整變異因子的自適應差分進化算法,仿真結果表明改進是可行的.文獻[10]引入一個新的變異參數(shù),根據(jù)算法的搜索情況自適應調整變異率,將改進算法應用于非線性系統(tǒng)模型參數(shù)的辨識中,性能較優(yōu).

為了平衡算法搜索速度和搜索精度,本文綜合兩種變異策略(DE/best/1和DE/rand/1)的優(yōu)點,提出了隨機選擇變異策略的改進設想;為了提高算法搜索的效率,根據(jù)文獻[11]中對自適應調整變異率和自適應調整交叉率的理論描述,應用新公式對交叉率和變異率進行調整,從而提出了新型自適應調整變異率和自適應調整交叉率的改進設想.利用3種改進設想的多種組合來改進基本算法得到7種改進算法,并將7種改進DE算法應用在雙容水箱液位模型辨識案例中進行性能驗證.結果表明,7種改進DE算法跳出局部最優(yōu)的能力都高于基本算法.綜合考慮跳出局部最優(yōu)能力、時耗、快速性3項性能,3種改進設想同時應用的改進算法性能最優(yōu).

1差分進化算法

差分進化算法的思想是在父代種群中任意選取兩個或多個個體進行差分操作,并以一定的變異率進行放縮,然后與種群中另一個個體相加得到變異個體,變異個體與父個體以一定的交叉率進行交叉,得到試驗個體,比較試驗個體與父個體的適應度值,選擇較優(yōu)的個體保存在下一代種群中.當滿足終止條件時,結束搜索,輸出最優(yōu)個體.首先,DE算法在問題的解空間內(nèi)生成一組隨機個體形成初始種群,然后通過變異、交叉、選擇操作,產(chǎn)生下一代種群.

1.1變異

變異操作就是從父代個體中任意選取兩個或多個父代個體進行差分操作,再按一定的變異率進行放縮,然后與另一個父代個體進行相加得到變異向量.變異交叉策略的命名一般約定為DE/x/y/z形式,其中x表示從父代種群中選取的基向量的形式,y表示差分向量的個數(shù),z表示采用的交叉方式.PRICE和STORN提出了以下5種變異策略[11].

DE/rand/1:

(1)

DE/best/1:

(2)

DE/rand-to-best/1:

vi,g=xr1,g+F(xbest,g-xr1,g)+F(xr2,g-xr3,g)

(3)

DE/rand/2:

vi,g=xr1,g+F(xr2,g-xr3,g)+F(xr4,g-xr5,g)

(4)

DE/best/2:

vi,g=xbest,g+F(xr1,g-xr2,g)+F(xr3,g-xr4,g)

(5)

式中:xbest,g——當前種群中最優(yōu)個體;

xr1,g,xr2,g,xr3,g,xr4,g,xr5,g——當前種群中任意選取的互不相同的個體；

i,r1,r2,r3,r4,r5——個體編號;

g——代數(shù);

vi,g——得到的變異向量;

F——變異率.

上述5種變異策略中，DE/rand/1與DE/best/1使用較為廣泛.

1.2交叉

由變異操作得到的變異向量與父個體進行交叉操作,目的是使交叉后的試驗向量擁有父個體和變異向量的信息,保留父個體優(yōu)良特性的同時又增加了種群的多樣性.DE算法有指數(shù)交叉(用exp表示)和二項式交叉(用bin表示)兩種交叉方式.

指數(shù)交叉操作方式為:

(6)

式中：ui,j,g——試驗向量;

vi,j,g——變異向量;

xi,j,g——父個體;

i——個體編號;

g——代數(shù);

j——個體分量編號;

(l)C——取大于l的最小整數(shù),l是零與個體向量維數(shù)D之間的隨機數(shù);

L——整數(shù),在1與D之間.

指數(shù)交叉的具體操作是,首先在0與D之間選取一個隨機數(shù),并進行取整作為交叉的起點,起點處的試驗向量分量取自變異向量,自起點后根據(jù)隨機數(shù)與交叉率(CR)的比較結果選取一個整數(shù)L作為取自變異向量分量的長度,試驗向量的其他分量都取自父個體.

二項式交叉操作方式為:

(7)

式中:jrand——[1,D]內(nèi)的隨機整數(shù),j=1,2,3,…,D.

二項式交叉的具體操作是,由試驗向量的第一個分量開始,根據(jù)隨機數(shù)與交叉率CR的比較結果決定試驗向量分量是取自變異向量還是父個體,如果隨機數(shù)小于或者等于CR,則取自變異向量,否則,取自父個體,同時,保證每個試驗向量至少有一個分量取自變異向量.二進制交叉操作在DE算法中使用較為廣泛.

1.3選擇

DE采用“貪婪”策略進行選擇,比較父個體xi,g與試驗向量ui,g的適應度值f(·)來決定最優(yōu)個體;對于求取最小值問題,選擇操作方式為:

(8)

式中:xi,g+1——下一代個體.

2差分進化算法的改進設想

2.1隨機選擇變異策略

5種變異策略與2種交叉策略相結合,共可以得到10種變異交叉策略:DE/best/1/bin,DE/rand/1/bin,DE/rand-to-best/1/bin,DE/rand/2/bin,DE/best/2/bin,其中常用是DE/best/1/bin和DE/rand/1/bin.變異策略DE/best/1以當前種群中最優(yōu)個體為基向量,隨著進化的進行,變異操作使種群中的個體趨向于最優(yōu)個體附近,算法收斂速度快.缺點是對于存在局部最優(yōu)解的問題,收斂容易陷入局部最優(yōu).變異策略DE/rand/1以當前種群中隨機個體為基向量,有利于保持種群的多樣性,加大了搜索到最優(yōu)個體的概率,缺點是算法收斂速度太慢或者搜索不到最優(yōu)解.為了綜合兩種變異策略的優(yōu)點,本文提出了一種隨機選取兩種變異策略的改進設想,引入選擇因子C,在進行變異操作前,首先比較隨機數(shù)與選擇因子C,根據(jù)比較情況選擇兩種變異策略中的一種.即:

(9)

2.2自適應調整變異率

變異率F的作用是對差分向量進行放縮,生成變異向量.如果基向量的適應度值較優(yōu),則希望變異向量中包含較多的基向量成分,故此時需要較小的F對差分向量進行較小的放縮,使算法在基向量附近搜索,易于找到較優(yōu)解;當基向量的適應度較差時,則希望變異向量中包含較少的基向量成分,故此時需要較大的F,對差分向量進行較大的放縮,使搜索范圍擴大,能夠探索到較大解空間,增加搜索到最優(yōu)解的概率.因此,可以根據(jù)基向量的適應度值合理地自適應調整變異率F,基向量的適應度越優(yōu),變異率F就越小.對于求取最小值問題,調整策略為:

(10)

式中:Fmin,Fmax——變異率的下限與上限;

fmin,fmax——當前種群中個體的最小適應度值與最大適應度值;

i——個體編號;

fi——基向量的適應度值.

2.3自適應調整交叉率

交叉率CR決定了試驗向量中包含變異向量成分的多少.如果變異向量的適應度值較優(yōu),則試驗向量中應包含較多的變異向量成分,交叉率CR的選取也應較大.當變異向量的適應度值較差時,則試驗向量應包含較少的變異向量成分,交叉率CR的選取也應較小.根據(jù)以上分析,對于求取最小值問題,調整策略為:

(11)

式中:CRmin,CRmax——交叉率的下限與上限;

fi——變異向量的適應度值.

2.47種改進算法

利用3種改進設想分別應用于DE算法得到改進算法1,算法2,算法3;利用3種改進設想兩兩結合應用于DE算法,可得到改進算法4,算法5,算法6;利用3種改進設想同時應用于DE算法可得到改進算法7.具體如表1所示.

表1　7種改進算法

37種改進算法在閉環(huán)辨識案例中的應用及性能分析

3.1雙容水箱液位模型

設雙容水箱液位模型的傳遞函數(shù)形式為:

(12)

該模型中共有4個待辨識參數(shù)K,T1,T2,τ,由于4個參數(shù)相互影響,利用基本DE算法進行辨識時,往往因陷入局部最優(yōu)使參數(shù)T1和T2的辨識結果不夠準確.

3.2閉環(huán)辨識困難及應用智能優(yōu)化算法的需求

閉環(huán)辨識比開環(huán)辨識更困難一些.用傳統(tǒng)的最小二乘方法不可能辨識的閉環(huán)辨識問題,用現(xiàn)代的智能優(yōu)化算法就有了可行解,但其對智能優(yōu)化算法也提出了更高的要求.因此,改進DE算法用于閉環(huán)辨識驗證具有一定的現(xiàn)實意義.

3.37種改進算法的閉環(huán)辨識案例驗證試驗

由雙容水箱試驗裝置獲取閉環(huán)狀態(tài)下雙容水箱液位試驗數(shù)據(jù),包括上水閥開度數(shù)據(jù)及下水箱液位數(shù)據(jù),采樣周期取1 s,數(shù)據(jù)長度為900,其采集點位置如圖1所示.上水閥開度曲線及下水箱液位曲線如圖2和圖3所示.

圖1　水箱液位控制系統(tǒng)框示意

圖2　上水閥開度曲線

圖3　下水箱液位曲線

分別采用基本差分進化算法(DE/best/1/bin)和以上7種改進算法在Matlab環(huán)境下辨識出雙容水箱液位模型中K,T1,T2,τ這4個參數(shù).在辨識計算中所用的算法參數(shù)F的范圍取[0.3,0.6],CR的范圍取[0.6,0.9][1];選擇因子取0.6.具體設置如表2所示.4個參數(shù)的搜索范圍取[0.000 1 100],[0.000 1 500],[0.000 1 500],[0.000 1 100];種群規(guī)模數(shù)取待辨識參數(shù)個數(shù)的10倍(即40);最大迭代次數(shù)取100.適應度函數(shù)及辨識誤差函數(shù)為:

(13)

式中:n——數(shù)據(jù)長度;

yi——第i個待辨識數(shù)據(jù);

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

3.47種算法的應用性能分析

為了分析不同算法的性能,記錄20次辨識計算中陷入局部最優(yōu)的次數(shù)、仿真時耗、誤差降至10所需迭代次數(shù),得到的結果如表3所示.

表3　20次辨識結果

由表3可知.局部最優(yōu)辨識結果為K=1.024 8,T1=236.390 9,T2=56.898 3,τ=21.233 6,辨識誤差為11.533 8.最優(yōu)辨識結果為K=1.062 5,T1=291.769 8,T2=0.000 1,τ=61.231 7,辨識誤差為5.427 4.則最優(yōu)辨識結果及局部最優(yōu)辨識結果的傳遞函數(shù)模型分別為:

(14)

(15)

利用Simulink仿真平臺,可得到最優(yōu)模型和局部最優(yōu)模型在實際的上水閥門開度數(shù)據(jù)輸入下的響應曲線,與實際的液位曲線對比結果如圖4所示.

由圖4可知,最優(yōu)模型響應曲線與實際液位曲線吻合較好,說明最優(yōu)模型的傳遞函數(shù)能夠反映實際對象的特性,而局部最優(yōu)模型響應曲線與實際液位曲線相差明顯.局部最優(yōu)模型的時延參數(shù)τ=61.231 7,局部最優(yōu)模型響應曲線與實際液位曲線相比,時延明顯偏大.究其原因可知,由于純延遲后的一段時間內(nèi)實際液位值與零非常接近,對適應度影響較小,其在整個適應度值中所占的比重也較小,容易被忽略,從而造成時延參數(shù)辨識不準[12].

圖4　實際曲線與辨識結果仿真曲線對比

由表3可知,7種改進算法陷入局部最優(yōu)的次數(shù)都少于基本算法,說明改進算法提高了跳出局部最優(yōu)的能力.從時耗數(shù)據(jù)來看,算法1在7種改進算法中平均用時最少;從誤差降到10所需代數(shù)(即快速性)來看,算法3所需代數(shù)最少;從陷入局部最優(yōu)的次數(shù)來看,算法6和算法7在20次辨識中都沒有陷入局部最優(yōu).

分析表明,算法1只進行了隨機選擇變異策略的改進,而算法2至算法7都進行了自適應調整算法參數(shù)的改進,自適應調整算法參數(shù)的改進都需要計算粒子的適應度信息,并以此信息計算每代的變異率和交叉率,這必將增大每次迭代的計算量,從而增加總體搜索時耗.因此,除算法1與基本算法時耗較接近外,其他改進算法的平均時耗都要大大超過基本算法.

算法3只進行了自適應調整交叉率的改進,自適應調整交叉率提高了算法的搜索效率;同時,由于變異策略選用的是與基本算法類似的DE/best/1策略,其優(yōu)點就是搜索快速,因此算法3表現(xiàn)出優(yōu)于其他算法的快速性.

算法6是對兩個算法參數(shù)同時進行自適應調整,對變異率進行自適應調整采用的是DE/rand/1變異策略,這增加了種群的多樣性,從而增大了跳出局部極值點的能力.算法7是3種改進方案相結合的改進算法,隨機選擇變異策略綜合了DE/rand/1和DE/best/1的優(yōu)點,即增加了種群的多樣性,又提高了搜索的快速性.由于算法7在部分代中采用了DE/rand/1變異策略,減少了計算變異率的次數(shù),導致算法7的時耗及快速性都要優(yōu)于算法6.

在跳出局部極值點能力、時耗、快速性3個指標中,最重要的指標是跳出局部極值點的能力,它是辨識成敗與否的關鍵.因此,綜合考慮,算法7的性能最優(yōu).

4結語

將3種改進設想,隨機選擇變異策略、自適應調整變異率和自適應調整交叉率組合應用于基本DE算法,提出了7種改進算法并應用于雙容水箱液位模型閉環(huán)辨識案例中進行性能驗證.對比基本DE算法辨識結果表明,7種算法跳出局部最優(yōu)的能力都得到了提高;綜合跳出局部最優(yōu)能力、時耗、快速性3項性能表明,3種改進設想同時應用的改進算法性能最優(yōu).

參考文獻：

[1]劉金琨,沈曉蓉,趙龍.系統(tǒng)辨識理論及MATLAB仿真[M].北京:電子工業(yè)出版社,2013:32-58.

[2]裴振奎,劉真,趙艷麗.差分進化算法在多目標路徑規(guī)劃中的應用[J].遼寧工程技術大學學報:自然科學版,2010,29(5):899-902.

[3]鄭慧濤,梅亞東,胡挺,等.改進差分進化算法在梯級水庫優(yōu)化調度中的應用[J].武漢大學學報:工學版,2013 (1):57-61.

[4]?？×?李亞朋,馬小平,等.基于改進差分進化算法的PID優(yōu)化設計[J].控制工程,2010,17(6):807-810.

[5]許津津,馬進,唐永紅,等.基于改進DE算法的負荷建模參數(shù)辨識[J].電力系統(tǒng)保護與控制,2009,37(24):36-40.

[6]薛曉岑,向文國,呂劍虹.基于差分進化與 RBF 神經(jīng)網(wǎng)絡的熱工過程辨識[J].東南大學學報:自然科學版,2014,44(4):769-774.

[7]陶國正.基于改進微分進化算法的過程模型參數(shù)辨識[J].電氣應用,2011(4):40-44..

[8]唐德翠,鄧曉燕,朱學峰,等.改進差分進化算法辨識加藥凝絮過程參數(shù)[J].控制工程,2010(4):80-82.

[9]任甜甜,張宏立.基于改進差分進化算法的非線性系統(tǒng)辨識[J].計算機仿真,2014,31(7):342-345.

[10]熊偉麗,陳敏芳,張乾,等.基于改進差分進化算法的非線性系統(tǒng)模型參數(shù)辨識[J].計算機應用研究,2014,31(1):124-127.

[11]張美春.差分進化算法與應用[M].北京:北京理工大學出版社,2014:10-11.

[12]張洪濤,胡紅麗,徐欣航,等.基于粒子群算法的火電廠熱工過程模型辨識[J].熱力發(fā)電,2010,39(1):59-61.

(編輯胡小萍)

Research on Random Selection Mutation and Adaptive Differential Evolution Algorithm

GUO Yibo1, CHENG Jiyun2, LI Qin1, YANG Ping1

(1.ShanghaiUniversityofElectricPower,Shanghai200090,China; 2.ShanghaiMingHuaElectricPowerTechnologyEngineeringCo.,Ltd.,Shanghai200437,China)

Abstract:In order to take into account search speed and search accuracy,improve search efficiency,overcome the shortcoming which does not easily escape from local optimum value,three improved assumptions are proposed,namely,random selection mutation strategy,adaptive adjustment of mutation rate and adaptive adjustment of crossover rate.Three kinds of improved assumptions are used to improve the basic algorithm and get seven kinds of improved algorithms,which are applied to two-tank water level model closed-loop identification case.Case verification shows that seven kinds of improved algorithms increase the ability to jump out of local optimum value.Comprehensive comparison shows that the performance of improved algorithm where three improved assumptions are applied simultaneously is the best.

Key words:differential evolution algorithm; random selection mutation; adaptive adjustment; closed-loop identification

DOI：10.3969/j.issn.1006-4729.2016.02.012

收稿日期：2015-07-22

作者簡介：通訊郭義波(1990-),男,在讀碩士,河南商丘人.主要研究方向為熱工過程模型辨識.E-mail:913672133@qq.com.

基金項目：上海市電站自動化技術重點實驗室項目(13DZ2273800); 上海市科技創(chuàng)新行動計劃(13111104300).

中圖分類號：TP181

文獻標志碼：A

文章編號：1006-4729(2016)02-0162-05