多變異策略差分進(jìn)化算法的研究與應(yīng)用

呂銘晟,沈洪遠(yuǎn),李志高,王 汐,龔 明,王俊年

(湖南科技大學(xué)信息與電氣工程學(xué)院,湖南 湘潭 411201)

1 概述

差分進(jìn)化(Differential Evolution,DE)算法[1]采用模擬生物進(jìn)化的機(jī)制,通過種群內(nèi)個體差異度生成差異個體,然后進(jìn)行交叉、選擇操作實(shí)現(xiàn)種群的進(jìn)化。DE 算法適用性強(qiáng),不依賴于問題輔助信息,容易實(shí)現(xiàn),需要調(diào)整的參數(shù)少,非常適合于求解一些利用常規(guī)數(shù)學(xué)規(guī)劃方法不能或難以求解的復(fù)雜優(yōu)化問題。

許多文獻(xiàn)對標(biāo)準(zhǔn)差分進(jìn)化的不足提出了改進(jìn),如文獻(xiàn)[2-3]分別將交叉概率和縮放因子設(shè)計(jì)為自適應(yīng),文獻(xiàn)[4]提出采用動態(tài)更新種群的策略,文獻(xiàn)[5]提出一種自適應(yīng)差分進(jìn)化算法(SDE)；文獻(xiàn)[6]提出基于模糊控制的自適應(yīng)差分進(jìn)化算法(FADE)；文獻(xiàn)[7]提出基于適應(yīng)值的自適應(yīng)差分進(jìn)化算法；文獻(xiàn)[8]提出自適應(yīng)群體差分進(jìn)化算法；文獻(xiàn)[9]提出廣義的變異策略方案,用戶可以方便選擇適合自己所求問題的變異操作類型；文獻(xiàn)[10]提出基于鄰域搜索的DE/target-to-best/1 算子；文獻(xiàn)[11]提出多策略和控制參數(shù)自適應(yīng)差分進(jìn)化算法；文獻(xiàn)[12]提出DE/rand/1/Either-or 算子。文獻(xiàn)[13]提出雙種群偽并行差分進(jìn)化算法。迄今為止DE 已發(fā)展為一種在求解非線性、不可微、多峰值及高維復(fù)雜函數(shù)等類型問題的高性能強(qiáng)魯棒的方法,已經(jīng)在濾波器設(shè)計(jì)、聚類分析等領(lǐng)域取得了較好的應(yīng)用[14-15]。

根據(jù)變異機(jī)制的不同,DE 有多種不同版本,其中,DE/rand/1 是標(biāo)準(zhǔn)差分進(jìn)化所采用的變異策略,相對而言該變異策略操作簡單,在低維單峰函數(shù)優(yōu)化問題中具有收斂速度快、尋優(yōu)精度高等優(yōu)點(diǎn)。但在高維多峰復(fù)雜函數(shù)優(yōu)化時,存在算法易早熟或后期收斂速度慢等不足。針對該問題,本文提出一種多變異策略差分進(jìn)化算法(MDE)。通過引入改進(jìn)的DE/best/1 變異策略對種群進(jìn)行二次變異操作,以拓展算法搜索空間,使算法在交叉操作時能夠有更大概率獲取更多優(yōu)秀的變異向量分量,進(jìn)而從種群個體的“基因”上有效控制種群在進(jìn)化過程中的多樣性。為避免算法進(jìn)化的盲目性,在其變異操作中都采用精英保留原則,并對其中部分優(yōu)秀基因采用基因擴(kuò)散處理。

2 標(biāo)準(zhǔn)差分進(jìn)化算法的變異策略

與其他進(jìn)化類算法類似,DE 算法首先初始化種群,然后對種群個體依次執(zhí)行變異、交叉和選擇操作,產(chǎn)生出子代種群,經(jīng)過反復(fù)迭代最終得到所需的結(jié)果。

標(biāo)準(zhǔn)差分的變異策略如下：

(1) 第1 種變異策略DE/rand/1：

(2) 第2 種變異策略DE/best/1：

其中,r1,r2,r3∈[1,N]為隨機(jī)選擇的整數(shù),且須滿足：r1≠r2≠r3≠i；F為變異操作縮放因子,取值在(0,2)之間,控制變異向量的幅值。

3 多變異策略差分進(jìn)化算法

3.1 變異策略

差分進(jìn)化算法的核心操作為變異。對變異策略的選取決定了算法在進(jìn)化過程中種群的走向,而貪婪的選擇策略本身具有兩面性,在低維單峰函數(shù)優(yōu)化時能夠保證算法始終向更小的方向進(jìn)化,但在高維多峰復(fù)雜函數(shù)優(yōu)化時,因?yàn)閮H用貪婪選擇策略,致使算法一旦搜索到某一較優(yōu)秀局部最小時,算法在最優(yōu)適應(yīng)度上出現(xiàn)停滯,隨著時間的累積,最終導(dǎo)致種群個體某些維變量陷入特定范圍。根據(jù)式(1)和式(2)可知,如果所有個體某維變量過早趨于一致,在沒有其他操作的干預(yù)下,種群喪失多樣性,算法就會出現(xiàn)早熟。

為了增強(qiáng)貪婪算法的全局最優(yōu)能力,使算法在處理多峰高維復(fù)雜函數(shù)問題優(yōu)化時,避免算法在某一局部最小值時可能出現(xiàn)的停滯,避免個體種群多樣性過早地喪失。本文采用2 種變異共存的方式優(yōu)化經(jīng)典差分算法。

改進(jìn)變異策略DE/best/1：

本文優(yōu)化算法將2 種策略縱向結(jié)合,增加了種群的多樣性,使算法的全局搜索能力得到有效增強(qiáng)。將DE/rand/1 作為變異策略1。將式(3)作為變異策略2,α為向量相關(guān)參數(shù),α的加入使本次變異有了更多的選擇空間；結(jié)合成多變異策略差分進(jìn)化算法。變異策略2 的加入極大增強(qiáng)算法的搜索空間和在局部區(qū)域的搜索能力。MDE 算法較標(biāo)準(zhǔn)差分進(jìn)化增加了多個控制參數(shù)和種群,使算法的搜索能力得到有效的加強(qiáng)且提供了更靈活的選擇。

差分算法使用精英保留的原則。在此基礎(chǔ)之上,本文研究采取了精英擴(kuò)散和限制原則,使優(yōu)秀的精英個體能影響其他個體的部分基因,而一些帶有欺騙性的精英個體對其影響力進(jìn)行限制。這也符合生物社會的規(guī)律,即優(yōu)秀的個體對整個種群的進(jìn)步應(yīng)產(chǎn)生更大的影響力。反之,應(yīng)減少。

在算法中加入擴(kuò)散數(shù)值k,以決定精英的影響大小。本文算法中采取每一代進(jìn)化,最優(yōu)個體影響其他某一個體k維基因的方法。

采取精英擴(kuò)散原則后,算法能在各階段更有效地保留優(yōu)勢個體,更好地發(fā)揮了多變異策略的優(yōu)勢,提高了收斂速度。

3.2 算法流程

多變異策略差分進(jìn)化算法的具體流程(圖1)如下：

(1) 初始化種群,對參數(shù)進(jìn)行設(shè)定。

(2) 計(jì)算種群個體適應(yīng)度。

(3) 采用策略1 進(jìn)行變異、交叉和選擇操作。計(jì)算適應(yīng)度,記錄當(dāng)前最優(yōu)個體。更新整個種群的適應(yīng)度。

(4) 采用策略2 進(jìn)行變異、交叉和選擇操作。計(jì)算適應(yīng)度,記錄當(dāng)前最優(yōu)個體。更新整個種群的適應(yīng)度。將策略2 中最優(yōu)個體的部分基因根據(jù)擴(kuò)散數(shù)值k替代隨機(jī)個體的對應(yīng)基因。

(5) 判斷步驟(4)得到的結(jié)果是否達(dá)到退出條件,若滿足,結(jié)束,否則,跳轉(zhuǎn)到步驟(2)繼續(xù)執(zhí)行。

圖1 多變異策略差分進(jìn)化算法流程

4 算法測試與結(jié)果分析

4.1 測試環(huán)境與結(jié)果

為驗(yàn)證MDE 的有效性,以常用的4 個Benchmark測試函數(shù)為例對MDE 進(jìn)行測試,同時,與標(biāo)準(zhǔn)差分DE/rand/1 進(jìn)行對比。算法最大函數(shù)評價次數(shù)為2.5e +05,各算法對于每個函數(shù)都獨(dú)立連續(xù)運(yùn)行20 次。

表1 中,CR1,CR2分別表示DE/rand/1、DE/best/1 2 種變異策略下算法的交叉概率；F1,F2分別表示縮放因子；α為相關(guān)系數(shù)；k為擴(kuò)散系數(shù)。

表1 MDE 算法各控制參數(shù)設(shè)置

由表2 結(jié)果可知,當(dāng)DE/rand/1 出現(xiàn)早熟現(xiàn)象時,DE/best/1 能夠通過參數(shù)的調(diào)節(jié)防止算法早熟,可見其穩(wěn)定性不如DE/rand/2。正是由于F2的存在彌補(bǔ)了DE/rand/1 穩(wěn)定性的不足。而DE/rand/1 和DE/best/1 串行組合并非簡單疊加,在結(jié)合兩者優(yōu)點(diǎn)的基礎(chǔ)上,MDE 性能有了進(jìn)一步的提高,使其整體性能在測試中表現(xiàn)最為優(yōu)秀。

表2 20 次獨(dú)立運(yùn)行的最優(yōu)解平均值

從算子的結(jié)構(gòu)上進(jìn)行分析,式xr1+F×(xr2-xr3)可分為2 個部分理解,xr1作為隨機(jī)選擇的基向量,F1×(xr2-xr3)可理解為以基向量為中心在其周圍進(jìn)行局部搜索。可見式(1)本身就兼有全局與局部搜索的特性,只是其全局搜索強(qiáng)于局部搜索。將式(2)改寫為(xbest+F2× (xr2-xr3)) +α×F2×(xr4-xr5)),當(dāng)α≠0 時,改進(jìn)后的DE/best/1 相對于DE/best/1 而言多進(jìn)行了一次變異,可以理解為改進(jìn)后DE/best/1 其實(shí)是局部搜索能力得到加強(qiáng)的DE/best/1。并且DE/best/1 以當(dāng)前最優(yōu)個體為指引進(jìn)行局部搜索,減少了其盲目性。同時,其隨機(jī)性也擴(kuò)展了算法的搜索空間,有利于增加種群的多樣性。有效地提升了算法的整體性能。

4.2 參數(shù)設(shè)置

交叉概率CR雖不能對交叉操作提供精確的指導(dǎo)信息,但是通過對其數(shù)值大小的調(diào)節(jié)能夠控制算法獲取變異向量分量的能力,當(dāng)CR較大時,在交叉操作中能以較大的概率從變異向量獲取更多的分量,擴(kuò)展算法的搜索空間；相反,則利于種群的多樣性。CR2取值應(yīng)該不小于CR1,原因是DE/best/1 策略較DE/rand/1 策略能產(chǎn)生更多的優(yōu)秀變異向量分量,而這些分量需要較大的交叉概率獲取。F2取值應(yīng)少于F1,這是因?yàn)榻?jīng)過DE/rand/1 策略優(yōu)化后問題的解已經(jīng)向最優(yōu)靠攏,而策略2 可以理解為是在前者的基礎(chǔ)上微調(diào),根據(jù)向量合成法則,F2和α×F2不宜較F1大。這有利于平衡算法的全局和局部搜索能力。當(dāng)然還應(yīng)該由具體問題的特性來設(shè)置F2和α,使算法的性能發(fā)揮出較好的優(yōu)勢,提高解決問題的效率。對于單峰函數(shù)的求解CR2取較大的值,有利于從DE/best/1 變異中獲取更多優(yōu)秀變異分量,使結(jié)果的精度越高。對于其他復(fù)雜的多峰函數(shù),由于存在大量局部最小值欺騙,算法只能同時以較小的CR2逐步從DE/best/1 變異中獲取優(yōu)秀變異分量。

對縮放因子F的設(shè)置也必須考慮具體問題的特性,從數(shù)學(xué)表達(dá)式可以看出F2和α×F2是2 個可以互換的參數(shù),因此,實(shí)驗(yàn)中3 個取值比較接近,也可以理解α×F2是在F2基礎(chǔ)上的一種微調(diào)。因此,α的取值一般在1 附近。

擴(kuò)散參數(shù)k的加入是為了使算法能在各階段更有效地保留真正的優(yōu)勢個體及其潛在優(yōu)勢基因段,是對策略2 的很好補(bǔ)充,有效避免陷入早熟的問題。k的選取以種群個體維數(shù)M為度量,實(shí)驗(yàn)表明,k取(0.1～0.5)M,能對算法產(chǎn)生較好影響。

圖2～圖5 為4 個測試函數(shù)的仿真對比,本文將MDE 的實(shí)驗(yàn)結(jié)果和標(biāo)準(zhǔn)DE/rand/1 的結(jié)果以及將標(biāo)準(zhǔn)DE/rand/1 策略2 倍線性疊加的結(jié)果就行了比較。其中,DE 為標(biāo)準(zhǔn)差分；2XDE 為標(biāo)準(zhǔn)DE 線性疊加；MDE 為改進(jìn)后的差分算法。

圖2 Schwefel 2.22 函數(shù)適應(yīng)度比較

圖3 Schwefel 2.26 函數(shù)適應(yīng)度比較

圖4 Rosenbrock 函數(shù)適應(yīng)度比較

圖5 Sphere 函數(shù)適應(yīng)度比較

5 電力負(fù)載分配問題

本文采用一個經(jīng)典的38 個發(fā)電機(jī)的電力負(fù)載分配問題,發(fā)電機(jī)成本與發(fā)電量之間的關(guān)系如下：

電機(jī)功率約束為：

電力平衡約束為：

當(dāng)電力系統(tǒng)覆蓋密集時可以忽略網(wǎng)絡(luò)損耗,本文在計(jì)算中忽略了網(wǎng)絡(luò)損耗,故電力平衡約束可簡化為：

目標(biāo)函數(shù)：

總負(fù)荷PD=6 000 mW。為了克服隨機(jī)性影響,算例獨(dú)立計(jì)算20 次。

表3 給出了算法的運(yùn)算結(jié)果,以及與ISPO[16]算法的比較。本次測試中樣本個數(shù)為50 個,迭代次數(shù)為10 00 次,F1=0.4,F2=0.4,α=0.75,CR1=0.3,CR2=0.3,k=5。由表3 可知,此算法取得了相對較好的結(jié)果。

表3 2 種算法的目標(biāo)函數(shù)計(jì)算結(jié)果比較

MDE 算法的目標(biāo)函數(shù)值最優(yōu)曲線如圖6 所示,由圖可知,此方法求解經(jīng)典電力負(fù)載分配問題快速有效。表4 為各發(fā)電機(jī)目標(biāo)函數(shù)最優(yōu)解。

圖6 MDE 算法的目標(biāo)函數(shù)最優(yōu)曲線

表4 各發(fā)電機(jī)MDE 算法的目標(biāo)函數(shù)最優(yōu)解

6 結(jié)束語

本文針對標(biāo)準(zhǔn)差分進(jìn)化在高維多峰復(fù)雜函數(shù)優(yōu)化中存在的不足,設(shè)計(jì)一種多變異策略差分進(jìn)化算法。在4 個Benchmark 函數(shù)上與標(biāo)準(zhǔn)差分進(jìn)化算法進(jìn)行了對比,結(jié)果表明,改進(jìn)算法在對算法的控制方面較標(biāo)準(zhǔn)差分進(jìn)化算法更為靈活而且穩(wěn)定,收斂速度和所得最優(yōu)解精度方面都比標(biāo)準(zhǔn)差分進(jìn)化算法有明顯優(yōu)勢。通過電力負(fù)載分配模型求解結(jié)果表明,該算法是求解大規(guī)模電力系統(tǒng)經(jīng)濟(jì)負(fù)荷分配問題的有效方法。今后將在多變異的基礎(chǔ)上,研究參數(shù)的自適應(yīng)設(shè)置。

[1]Storn R,Price K.Differential Evolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4)：341-359.

[2]許小健,黃小平,錢德玲.自適應(yīng)加速差分進(jìn)化算法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2008,5(1)：87-92.

[3]鄧澤喜,劉曉冀.差分進(jìn)化算法的交叉概率因子遞增策略研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(27)：33-36.

[4]肖術(shù)駿,朱學(xué)峰.一種改進(jìn)的快速高效的差分進(jìn)化算法[J].合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版,2009,32(11)：1700-1703.

[5]Salman A,Engelbrecht A P,Omran M G H.Empirical Analysis of Self-adaptive Differential Evolution[J].European Journal of Operational Research,2007,183(2)：785-804.

[6]Liu J,Lampinen J.A Fuzzy Adaptive Differential Evolution Algorithm[J].Soft Computing,2005,9 (6)：448-462.

[7]Ali M M,T?rn A.Population Set-based Global Optimization Algorithms：Some Modifications and Numerical Studies[J].Computers &Operations Research,2004,31(10)：1703-1725.

[8]Teng N S,Teo J,Hijazi M H A.Self-adaptive Population Sizing for a Tune-free Differential Evolution[J].Soft Computing,2009,13(7)：709-724.

[9]Feoktistov V,Janaqi S.Generalization of the Strategies in Differential Evolution[C]//Proceedings of the 18th International Parallel and Distributed Processing Symposium.[S.l.]：IEEE Press,2004：165-170.

[10]Das S,Abraham A,Chakraborty U K,et al.Differential Evolution Using a Neighborhood-based Mutation Operator[J].IEEE Transactions on Evolutionary Computation,2009,13(3)：526-553.

[11]Pan Quanke,Suganthan P N,Wang Ling,et al.A Differential Evolution Algorithm with Self-adapting Strategy and Control Parameters[J].Computers &Operations Research,2011,38(1)：394-408.

[12]Price K,Storn R M,Lampinen J A.Differential Evolution：A Practical Approach to Global Optimization[M].[S.l.]：Springer,2006.

[13]吳亮紅,王耀南,周少武,等.雙種群偽并行差分進(jìn)化算法的研究與應(yīng)用[J].控制理論與應(yīng)用,2007,24(3)：453-459.

[14]Paterlini S,Krink T.Differential Evolution and Particle Swarm Optimisation in Partitional Clustering[J].Computational Statistics &Data Analysis,2006,50(5)：1220-1247.

[15]Storn R.Designing Nonstandard Filters with Differential Evolution[J].Signal Processing Magazine,2005,22(1)：103-106.

[16]Chaturvedi K T,Pandit M,Srivastava L.Particle Swarm Optimization with Time Varying Acceleration Coefficients for Non-convex Economic Power Dispatch[J].International Journal of Electrical Power &Energy Systems,2009,31(6)：249-257.