自適應權重差分進化算法

王建芹， 高興寶

(陜西師范大學 數(shù)學與信息科學學院，陜西 西安 710062)

0 引言

差分進化(Differential Evolution,DE)算法[1]是一種新興的智能計算技術，現(xiàn)已成功應用于模式識別、信息處理、人工神經(jīng)網(wǎng)絡等多個領域[1,2].與遺傳算法、粒子群算法類似，DE算法也是一種基于種群的啟發(fā)式搜索技術，由于它采用實數(shù)編碼，具有受控參數(shù)少，魯棒性強等特點，該算法引起了廣泛的關注，并已提出多種改進的算法.這些改進大多是通過改變中間向量遺傳策略(學習策略)來提高算法的性能[3-6].文獻[7]根據(jù)種群進化過程中已有的學習經(jīng)驗對中間向量遺傳策略和控制參數(shù)進行適應性改變，提出自適應差分進化算法(SaDE).文獻[8]將3種中間向量遺傳策略和3組參數(shù)設置隨機組合，提出了混合差分進化算法(CoDE).受這些啟發(fā)，本文提出一種新的改進差分進化算法，稱之為自適應權重差分進化算法(AWDE).該算法對已存在的兩種具有不同優(yōu)點的中間向量遺傳策略(“rand/1/bin”和“current-to-best/1/bin”)引入自適應權重，由此設計一個新的中間向量遺傳策略.通過對基準函數(shù)進行性能測試，并且在相同的參數(shù)設置下與分別使用上述兩個學習策略的對比算法進行比較，說明了本文所提算法的有效性.

1 差分進化算法

(1)變異：在每一代中，對種群中的每個個體xi(目標向量)利用中間向量遺傳策略(學習策略)產(chǎn)生變異向量vi=(vi,1,vi,2,…,vi,D) ，這里列舉5種常用的中間向量遺傳策略：

“rand/1/bin” :

vi,G=xr1,G+F·(xr2,G-xr3,G) (1)

“best/1/bin”:

vi,G=xbest,G+F·(xr2,G-xr3,G) (2)

“current-to-best/1/bin”:

vi,G=xi,G+F·(xbest,G-xi,G)+F·(xr1,G-xr2,G)

(3)

“Best/2/bin”:

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

(4)

“rand/2/bin”:

vi,G=xi,G+F·(xr1,G-xr2,G)+F·(xr3,G-xr4,G)

(5)

其中，r1,r2,r3,r4,r5從1,2,…,NP中隨機選取，且r1≠r2≠r3≠r4≠r5≠i.F為縮放比例因子，G為當前迭代步數(shù)，xbest,G為當前種群中的最優(yōu)個體.

(2)交叉：父代個體xi,G與變異個體vi,G依據(jù)交叉概率CR生成實驗個體

ui,G=(ui1,G,Ui2,G,…,uiD,G)

j=1,2,…,D

(6)

其中，CR為交叉因子，jrand是從[1,NP]中隨機選取的一個整數(shù)以確保實驗向量ui,G與相應的目標向量xi,G至少有一個元素不同.

(3)選擇：將交叉后得到的實驗個體ui,G與目標個體xi,G按(7)式進行選擇操作，生成子代個體xi,G+1，并將xi,G+1作為下一次迭代的父代個體.

(7)

在每一代執(zhí)行上面3個步驟，依此循環(huán)，直到滿足終止條件為止.

2 改進的差分進化算法

差分進化算法(DE)涉及的控制參數(shù)和學習策略主要依賴于所考慮的問題.使用不同學習策略的差分進化算法在求解問題時表現(xiàn)出的性能不同，有些學習策略適用全局搜索問題，而有些學習策略對于解決旋轉問題是非常有效的.例如，“rand/1/bin”策略能夠保持種群的多樣性，而“DE/best/1”策略有更好的尋優(yōu)方向和收斂速度.受到文獻[7,8]的啟發(fā)，本文提出一種新的改進差分進化算法，稱為自適應權重差分進化算法(AWDE).該方法根據(jù)不同學習策略所表現(xiàn)出的不同性能，將不同的學習策略組合起來以充分利用它們的優(yōu)點.這里我們選擇了兩個學習策略“rand/1/bin”((1)式) 和“current-to-best/1/bin”((3)式)，利用這兩個學習策略產(chǎn)生一個新的自適應學習策略：

vi,G=p{xr1,G+F·(xr2,G-xr3,G)}

+F·(xr1,G-xr3,G)} (8)

步1隨機初始化種群，假設種群規(guī)模為NP.

步2依(8)式對種群中的每個個體進行變異操作，產(chǎn)生變異個體.

步3依(6)式對種群中每個變異個體與其目標個體進行交叉操作，得到NP個實驗個體.

步4依(7)式對每個實驗個體與它的目標個體進行選擇操作生成子代個體，且作為下一次迭代的父代個體.

步5檢查是否滿足終止條件，如果當前迭代次數(shù)達到初始指定的最大次數(shù)，則停止迭代，輸出最優(yōu)值；否則，轉步2.

3 數(shù)值仿真

為了驗證改進算法的性能，用4個基準測試函數(shù)在Matlab上進行數(shù)值實驗，并與分別使用“rand/1/bin”和“current-to-best/1/bin”兩種學習策略的差分進化算法(“DE/rand/1/bin”和 “DE/current-to-best/1/bin”)進行比較.由于不同的控制參數(shù)影響了算法的性能，文獻[9]認為 應該從[0.4,0.95]中選擇，并且當F=0.9時，算法的收斂速度和魯棒性會達到一個很好的折中.這里對于每一個測試函數(shù)改進算法和對比算法的參數(shù)設置是完全相同的，如下：縮放比例因子F=0.9,交叉因子CR=0.1,種群規(guī)模為30，每個個體的維數(shù)都為10，如下前兩個測試函數(shù)F1和F2的最大迭代次數(shù)是500，后兩個測試函數(shù)F3和F4的最大迭代次數(shù)是1000.為消除隨機干擾，對每一個測試函數(shù)，獨立運行30次后取其平均值，并在同樣的參數(shù)設置下，與學習策略分別為“rand/1/bin”和“current-to-best/1/bin”的差分算法進行比較.

圖1 F1函數(shù)最優(yōu)值進化曲線圖

圖2 F2函數(shù)最優(yōu)值進化曲線圖

F1：Sphere 函數(shù)

圖3 F3函數(shù)最優(yōu)值進化曲線圖

圖4 F4函數(shù)最優(yōu)值進化曲線圖

(n=10,xi∈[-5.12,5.12]) minf1(x)=0

F2：Schwefel′s Problem 函數(shù)

(n=10,xi∈[-5.12,5.12]) minf2(x)=0

F3：Rastrigin 函數(shù)

(n=10,xi∈[-10,10]) minf3(x)=0

F4：Griewank 函數(shù)

(n=10,xi∈[-64,64]) minf4(x)=0

f1(x)和f2(x)是單峰函數(shù)，f3(x)和f4(x)都為多峰函數(shù).表1給出了各函數(shù)在不同算法下得到的最大值、最小值和平均值之間的比較. 圖1～4為改進算法和比較算法對于測試函數(shù)最優(yōu)值的進化曲線圖.

表1 函數(shù)運行30次比較表

由表1可以看出，對于F3和F4函數(shù)，改進算法達到了理論最優(yōu)值，對F1和F2函數(shù)，雖然沒有達到理論最優(yōu)值，但尋優(yōu)效果優(yōu)于對比算法.對于本文所有測試函數(shù)，由圖1～4可以看出：改進算法在尋優(yōu)性能和收斂速度方面都明顯優(yōu)于“DE/ rand/1/bin”，且避免了早熟收斂；與“DE/current-to-best/1/bin”相比，改進算法提高了收斂速度，具有較好的尋優(yōu)性.

通過上述分析，可以得出改進算法與分別使用“rand/1/bin”和“current-to-best/1/bin”學習策略的差分進化算法相比，避免了早熟收斂，提高了算法的收斂速度，并且具有較好的尋優(yōu)性能，說明了改進后的算法具有一定的有效性.

4 結束語

使用不同學習策略的差分進化算法對于求解的問題表現(xiàn)出不同的性能.本文選取兩種常用且具有不同優(yōu)點的學習策略，對其進行自適應組合，提出一種改進的差分進化算法.對基準函數(shù)進行數(shù)值試驗并與對比算法相比，改進的算法在要求的精度范圍內達到了全局最優(yōu)值，避免了早熟收斂并且具有較好的收斂性和收斂速率.

[1] R.Storn,K.Price. Differential evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces[R].Berkeley,CA,Tech.Rep.TR-95-012,1995.

[2] J. Ilonen, J.K. amarainen,J. Lampinen. Differential evolution training algorithm for feed-forward neural networks[J].Neural Processing Letters,2003,7(1):93-105.

[3] H. Y.Fan,J. Lampinen. A trigonometric mutation operator to differential evolution[J].J.Global Optim., 2003, 27(1):5-129.

[4] V. Feoktistov, S. Janaqi.Generalization of the strategies in differential evolution[C].Proc. of the 18th Int Parallel and Distributed Processing Symposium. Santa Fe, 2004,165-170.

[5] E.Mezura-Montes, J.Velazquez-Reyes, C.A.Colleo.Coello.Modified differential evolution for constrained optimization[C].Proceedings of the Congress on Evolutionary Computation(CEC′2006), IEEE Press, Sheraton Vancouver Wall Centre Hotel , Vancouver,BC, Canada,2006,332-339.

[6] J.Zhang,A.C.Sanderson.JADE:adaptive differential evolution with optional extemal archive[J].IEEE Trans Evolut Comput,2009,13(5):945-958.

[7] A.K.Qin,P.N.Suganthan. Self-adaptive differential evolution algorithm for numerical optimization[J].IEEE Trans .Evolut. Comput,2005,(2):1 785-1 791.

[8] Yong Wang,Zixing Cai,Qingfu Zhang.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Trans.Evolut.Comput, 2011,15:55-66.

[9] J.Ronkkonen, S.Kukkonen, K.V.Price.Real parameter optimization with differential evolution[J].Proc.IEEE Congr. Evol. Comput,2005,1:506-513.