基于反向?qū)W習的自適應差分進化算法

李龍澍，翁晴晴

(安徽大學 計算機科學與技術學院，合肥 230601)(*通信作者電子郵箱ahuwqq@126.com)

0　引言

1997年，Storn等[1]提出了一種簡單且高效的差分進化(Differential Evolution, DE)算法。該算法具有良好的收斂性及簡單易懂的特性，在解決全局優(yōu)化問題中受到越來越多研究者的青睞，被廣泛應用于解決工程設計優(yōu)化[2]、人工神經(jīng)網(wǎng)絡[3]等問題。

但是，標準差分進化算法需要設計者根據(jù)先驗知識提前設置縮放因子F和交叉概率Cr，在算法進化過程中無法根據(jù)進化方向和優(yōu)化問題的復雜性動態(tài)地改變控制參數(shù)的取值，致使在處理高維問題及多峰值問題時算法易陷入局部最優(yōu)而過早收斂[4-5]；另外在算法后期時，種群往往集中于最優(yōu)值附近，導致種群的多樣性減少，無法產(chǎn)生更好的個體。因此，許多研究者集中于差分進化算法自適應方面的研究[6-8]。其中，SaDE(Self-adaptive Differential Evolution)算法[9]首次實現(xiàn)動態(tài)調(diào)整縮放因子F及交叉概率Cr，其通過高斯分布動態(tài)地調(diào)整F和Cr的取值。另外一種是由Brest等[10]提出的自適應參數(shù)差分進化jDE(self-adapting control parameters in Differential Evolution)算法，利用均勻分布調(diào)整相關的控制參數(shù)，并采用啟發(fā)式規(guī)則為每一個體賦予不同的值。最經(jīng)典的自適應差分進化算法是由Zhang等[11]提出的自適應差分進化JADE(Adaptive Differential Evolution with optional external archive)算法，其采用了一種全新的current-to-pbest/1變異策略，即在每一次迭代過程中，從100*p(p為概率)種群中隨機選取一個個體作為當前最優(yōu)個體，并應用于變異策略中；另外利用柯西分布和標準正態(tài)分布動態(tài)地更新F和Cr，提高了種群向最優(yōu)值聚攏的速度。Tanabe等[12]在JADE的基礎上提出了SHADE(Success-History based parameter Adaptation for Differential Evolution)算法，其利用每一代控制參數(shù)的平均值來引導控制參數(shù)動態(tài)調(diào)整，提高了算法的魯棒性，使得該算法運行更加穩(wěn)定。Yi等[13]在JADE的基礎上提出了pbest-JADE算法，該算法在100*p種群中使用輪盤賭的方式選擇最優(yōu)個體，進一步提高了算法的收斂性和精確性。

以上研究主要集中于自適應差分進化算法的控制參數(shù)調(diào)整和變異策略的改進，并沒有考慮到每代種群中單個個體的局部開發(fā)能力。研究表明在進化算法迭代過程中引入機器學習能夠獲得更高的收斂精度和收斂速度[14]。這是因為機器學習通過對進化算法迭代搜索過程中所存儲的搜索空間、問題特征和種群信息等大量數(shù)據(jù)進行分析，即在全局優(yōu)化過程中，通過特征提取等方式提取有用信息引導種群的搜索方向。許多應用領域通過引入機器學習的進化算法都使得收斂速度與問題收斂精度有所提高。

由Tizhoosh[15]提出的反向?qū)W習的機器學習方法通過同時對當前解集與其反向解集進行適應度評估，選擇更優(yōu)的解集，用以進行下一迭代過程，以期提高算法整體搜索能力，現(xiàn)已被廣泛應用于各智能搜索算法，如差分進化(DE)算法[16]、粒子群優(yōu)化(Particle Swarm Optimization， PSO)算法[17]、智能蜂群(Artificial Bee Colony， ABC)算法[18]等，以提高算法的收斂速度。 Rahnamayan等[19]首次提出了基于反向?qū)W習的差分進化算法，在該算法中，采用基于反向?qū)W習的機制來初始化種群。之后越來越多的研究學者提出改進后的基于反向?qū)W習的差分進化算法。Omran等[20]結(jié)合反向?qū)W習、差分進化算法并引入混沌搜索策略提出了CODEQ(Chaotic search, Opposition-based learning for Differential Evolution and Quantum mechanics)算法，較好地解決了種群易陷入局部最優(yōu)的問題。 Wang 等[21]改進了基礎的反向?qū)W習的機制，提出了一種基于GOBL(Generalized Opposition-Based Learning)的差分進化算法。實驗結(jié)果表明，以上改進后的反向?qū)W習機制應用于差分進化算法中不僅提高了算法的尋優(yōu)能力，而且能夠保證在較短的時間內(nèi)收斂到最優(yōu)值附近。

因此，本文在已有JADE算法的基礎上，提出一種增強型反向?qū)W習的自適應差分進化(Opposition-based Learning of Adaptive Differential Evolution， OL-ADE)算法，通過反向精英學習，增加種群的局部搜索能力，獲取更加精確的最優(yōu)個體；同時，采用高斯分布隨機性提高單個個體的開發(fā)能力；提高了種群的多樣性，避免算法進入早熟，從而實現(xiàn)整體上平衡全局與局部的搜索能力。為了驗證本文OL-ADE算法的性能，采用CEC(Congress on Evolutionary Computation)2014中的6個基準測試函數(shù)進行仿真實驗，實驗結(jié)果表明OL-ADE算法具有較高的精確性、收斂性和可靠性。

1　基礎概念

1.1　差分進化算法

按照進化過程中控制參數(shù)能否根據(jù)當前種群進化信息進行動態(tài)調(diào)整，可將差分進化算法分為普通差分進化算法和適應性差分進化算法。差分進化算法屬于貪婪性進化算法，其主要有三個操作，即變異、交叉和選擇；算法利用種群中多個個體的差異性作為個體的擾動量，使得算法在跳躍距離和搜索方向上具有自適應性。在標準及其改進的差分進化算法中，變異操作對種群的進化方向起著決定性作用。因而現(xiàn)有的改進方法都是在原有變異策略基礎上加入新的選擇或評判標準，以期提高算法整體性能。以下列舉了應用較廣泛的適應性差分進化算法的幾種變異策略[13]：

DE/best/1:

vi(t)=xbest(t)+Fi(xr1(t)-xr2(t))

(1)

DE/current-to-best/1:

vi(t)=xi(t)+Fi(xbest(t)-xr1(t))+

Fi(xr1(t)-xr2(t))

(2)

DE/current-to-pbest/1:

vi(t)=xi(t)+Fi(xpbest(t)-xr1(t))+

Fi(xr1(t)-xr2(t))

(3)

其中：Fi為適應性差分進化算法中隨迭代次數(shù)增加而動態(tài)調(diào)整的縮放因子，取值范圍為(0,1)；xr1(t)、xr2(t)和xr3(t)是從當前代數(shù)種群集合{1,2,…,NP}{i}中隨機選擇的互不相同的個體；xpbest(t)為當前種群中最優(yōu)個體；NP表示種群規(guī)模大小。

1.2　反向?qū)W習

Tizhoosh[15]提出的反向?qū)W習是用于機器學習的一種優(yōu)化策略，即在算法每一次迭代時，同時檢測這些當前解的所有反向解，并從當前解集合與反向解集合中選擇更利于算法進化的解，從而減少算法的盲目性。隨著反向?qū)W習的發(fā)展，越來越多的研究學者開始關注這一機器學習算法，并在改進反向?qū)W習方法的工作中取得了較好的成果。以下對基本反向?qū)W習及幾種改進的反向?qū)W習作簡單介紹。相關概念定義如下：

(4)

在Rahnamayan等[22]于2007年提出的QODE(Quasi Oppositional Differential Evolution)算法中，對反向?qū)W習作出如下改進：

(5)

Mi=(ai+bi)/2

(6)

其中rand(x,y)為在區(qū)間(x,y)均勻分布的隨機數(shù)。數(shù)理邏輯證明，在黑盒優(yōu)化問題中，通過改進后的QODE所求得的擬反向解更接近優(yōu)化問題的最優(yōu)解。

Wang等[23]于2011年提出了GOBL策略，在反向求解的過程中通過引入權重來控制反向解的取值范圍：

(7)

其中k為(0,1)區(qū)間的隨機數(shù)。

在Seif等[24]于2015年所發(fā)表的文章中引入了新的反向解集求解模式，如式(8)所示：

(8)

與式(8)所求反向解對應的是根據(jù)原有解集通過均勻分布獲得與當前反向解相對的反向解集，如式(9)所示，通過對三個解集的評估，選取其中最優(yōu)解。

(9)

2　OL-ADE算法

由于優(yōu)化問題復雜性各不相同，而同一問題在不同的進化階段所需的變異策略和控制參數(shù)也應有所改變。因此，如何在差分進化算法進化過程中動態(tài)調(diào)控控制參數(shù)取值一直是研究的創(chuàng)新點與熱點。由于JADE算法的變異策略是從100*p(p為概率)個種群中隨機選取一個個體作為xpbest取代當前最優(yōu)個體用以變異操作，該策略豐富了種群多樣性也降低了差分進化算法的收斂速度。而本文在JADE算法的基礎上提出一種基于反向?qū)W習的變異策略，對用于變異操作的個體定義了新的選擇標準，具體如下：

vi(t)=φi(t)+Fi(xopbest(t)-φi(t))+

Fi(xr1(t)-xr2(t))

(10)

其中：xopbest和φi由本文所述方式進行選擇；xr1、xr2為隨機選擇的互不相同的個體；Fi使用JADE中的方式確定。

2.1　基于反向?qū)W習的最優(yōu)個體xopbest的選擇

在JADE中， 100*p個個體為精英種群，從中隨機選擇一個個體作為最優(yōu)個體。本文采用如下過程獲取最優(yōu)個體：

1)隨機取精英種群NP1={x1(t),x2(t),…,xN(t)}，xi(t)=(xi,1(t),xi,2(t),…，xi, j(t),…,xi,D(t))，其中N=100*p，i=1,2,…,N。

M=(x1+x2+…+xN)/N

(11)

(12)

其中：i=1,2,…,N,j=1,2,…D，N為精英種群中個體個數(shù)。充分利用精英種群中每一個體信息求取反向精英種群，這一策略提高了算法的探測能力，進而增強算法的整體尋優(yōu)能力。

3)從NP1∪NPop中選擇適應度值最好的個體xxbest，并計算xmean=(x1+x2+…+x2N)/2N，利用式(13)計算xopbest:

(13)

根據(jù)此方法求得xopbest能夠保證算法在更大的搜索空間內(nèi)搜尋最優(yōu)值，從而引導個體向最優(yōu)值進化，提高算法的收斂速度。

2.2　φi 的選擇標準

許多改進的智能優(yōu)化算法都繼承了原算法過早收斂的特性，差分進化算法亦是如此。而本文根據(jù)反向?qū)W習機制確定的xopbest的選擇標準，雖然提高了算法的局部搜索能力，增加了最優(yōu)解的精確度，但在多峰值問題尋優(yōu)過程中，同其他差分進化算法一樣，容易陷入局部最優(yōu)。為解決這一問題，本文在一定的概率下對用于變異階段的個體引入高斯分布隨機搜索，在每個個體搜索可行解的過程中進行擾動，提高單個個體的開發(fā)能力，具體如下：

(14)

2.3　改進的自適應差分進化算法

不同于現(xiàn)有的一些反向?qū)W習應用于算法的種群初始化階段，本文將其應用于差分進化算法的選擇策略中，這樣減少了算法對大量冗余數(shù)據(jù)的計算量；且本文算法選擇自適應的差分進化算法，即將反向?qū)W習機制與自適應機制中最優(yōu)個體的選擇相結(jié)合，選擇出更適用于變異策略的最優(yōu)個體。原有的自適應差分進化算法用于變異策略的個體種群為NP1，而經(jīng)過反向?qū)W習機制后，形成的反向解集NPop可以加強算法對精英個體鄰域的探測，即將原有NP1與現(xiàn)有NPop相結(jié)合，反向精英個體也參與競爭，選擇當前適應度值最好的個體，并利用式(13)計算出xopbest。

圖1　個體間差異曲線Fig. 1　Individual difference curve

在差分進化算法中，基于反向?qū)W習的xopbest的選擇不僅保證算法能在更大的搜索空間內(nèi)搜尋最優(yōu)值，而且還提高了算法的局部搜索能力，提高了算法的收斂速度。同時利用高斯分布進行φi個體的選擇，豐富了種群多樣性，減輕了算法因應用反向?qū)W習所帶來的過早收斂的壓力。φi與xopbest相結(jié)合，在增強種群局部搜索能力的同時，整體上平衡了全局搜索與局部尋優(yōu)的能力。自適應控制參數(shù)的引入，能夠動態(tài)調(diào)整算法中的各個控制參數(shù)，減少人為設置參數(shù)的影響。OL-ADE偽代碼具體如算法1。

算法1Procedure of OL-ADE。

1)

Begin

2)

SetμCR=0.5;μF=0.5;p=0.05;c=0.1;

//μCR為交叉概率，μF為縮放因子，

//p為選擇精英種群的概率，c為常量

3)

Initial population {xi(0)|i=1,2,…,NP}

4)

Fort=1 toT

5)

SCR=?;SF=?;

//SCR和SF分別存放變異及

//交叉成功的后代個體所對應的自適應的μF和μCR

6)

Fori=1 toNP

7)

GenerateCRi=rand(μCR,0.1)，F(xiàn)i=rand(μF,0.1);

8)

Choosexopbestby formulate (13);

9)

Randomly choosexr1(t)≠xi(t) from current populationP;

10)

Randomly choosexr2(t)≠xi(t) andxr1(t)≠xr2(t) from current populationP;

11)

vi(t)=φi(t)+Fi(xopbest(t)-φi(t))+

Fi(xr1(t)-xr2(t))

12)

Generatejrand=rand(1,D)

13)

Forj=1 toD

14)

Ifj=jrandor rand(0,1)

15)

ui, j(t)=vi, j(t);

16)

Elseui, j(t)=xi, j(t);

17)

End for

18)

Iff(xi(t))≤f(ui(t))

19)

xi(t+1)=ui(t);CRi→SCR;Fi→SF;

20)

Elsexi(t+1)=xi(t)

21)

End for

22)

μCR=(1-c)·μCR+c·meanA(SCR);

//meanA(SCR)表示算術平均值

23)

μF=(1-c)·μF+c·meanL(SF);

//meanL(SF)表示Lehmer平均值

24)

t=t+1

25)

End for

26)

End

3　實驗分析

在對比實驗中，本文研究選擇了四個經(jīng)典的差分進化算法包括DE、jDE、JADE和pbest-JADE進行對比，其中JADE又分為存檔JADE(JADE with Archive)和不存檔JADE(JADE w/o Archive)。

3.1　實驗參數(shù)

為評估本文所提方法的性能，從CEC 2014上選擇如下6個基準函數(shù)進行實驗：

為了保證實驗的公平性，實驗參數(shù)值設為文獻[13]建議的參數(shù)值，即μCR=0.5,μF=0.5;p=0.05;c=0.1；所有算法種群規(guī)模NP=100，維度D=30;另外，每個算法最大迭代次數(shù)為2 000；同時，為了減少實驗環(huán)境對實驗結(jié)果造成的誤差，每個算法獨立運行30次。所有實驗程序在Matlab R2010a版本下運行，PC環(huán)境為Windows操作系統(tǒng)Intel Core i3 CPU 2.0 GHz和4 GB內(nèi)存。

3.2　收斂精度

本組實驗主要測試本文算法OL-ADE與其他五種算法在維度為30的情況下獨立運行30次所獲得的最優(yōu)解的平均值與方差。

表1中將每一個測試函數(shù)中結(jié)果最好的以粗體標記，以方便辨識。從表1中可以看到，本文算法的每一測試函數(shù)適應值均值與方差都比其他算法低，表明本文算法更加精確地趨于理論最優(yōu)值，且穩(wěn)定性較高。為進一步分析實驗結(jié)果，表1還給出了每個算法的Friedman平均排名(Friedman Average Rank, FAR)[25]，可以發(fā)現(xiàn)本文算法表現(xiàn)最好。

圖2分別展示了在30維情況下這六種對比算法運行6個基準測試函數(shù)找到最優(yōu)解的變化曲線，其中X軸表示算法的迭代次數(shù)，Y軸采用log坐標表示函數(shù)的適應值。從圖2可以看出，本文算法大部分函數(shù)的收斂速度要高于其他算法，而且收斂精度也略高于其他算法，主要原因取決于通過反向精英學習能夠獲得最優(yōu)當前個體，快速引導算法向最優(yōu)值靠近。

圖2　測試函數(shù)收斂曲線(D=30)Fig.2　Convergence curve of test functions (D=30)

3.3　算法可靠性

為了驗證本文算法的可靠性，為每個測試函數(shù)的適應值設置一個閾值，觀察算法達到閾值的成功率，其中，假定所有函數(shù)的閾值為1.0E-5。在表2中列出了每個測試函數(shù)到達閾值的平均迭代次數(shù)及成功率，其中NA表示在算法達到最大迭代次數(shù)時都沒有收斂到事先所設置的閾值。另外，為便于辨識，在表2中將每一個測試函數(shù)中最好的結(jié)果設置為粗體?？梢钥吹?，除了f5函數(shù)以外，本文OL-ADE都是最先達到預設收斂閾值，體現(xiàn)了OL-ADE算法具有較高的收斂速度。本文方法是通過豐富種群多樣性來提高收斂精度，而f5函數(shù)的可行解定義域較大，所以OL-ADE算法在進化初期因在可行解定義域內(nèi)形成的種群豐富度大導致進化初期算法收斂速度較慢，因此達到固定收斂閾值所需迭代次數(shù)較多。另外，本文提出的OL-ADE算法的成功率基本上都達到100%，從而表明OL-ADE算法更加可靠。

綜上所述，本文算法OL-ADE與DE、jDE、JADE with Archive、JADE w/o Archive 和pbest-JADE相比，在精確性、收斂速度和可靠性上表現(xiàn)更加優(yōu)越。

表1　測試函數(shù)的均值和方差(D=30)Tab. 1　Mean value and standard deviation for test functions (D=30)

表2　不同算法對各測試函數(shù)的平均迭代次數(shù)和成功率Tab. 2　Average number of iterations and success rate for test functions under different algorithms

4　結(jié)語

本文提出了一種基于反向?qū)W習自適應差分進化算法OL-ADE。該算法利用反向?qū)W習機制求取反向解集，提高了種群的局部搜索能力；同時在變異階段引入高斯分布，有效減輕了算法因使用反向?qū)W習引起的收斂過快而使得種群陷入局部最優(yōu)的負擔；另外，OL-ADE算法將反向?qū)W習與高斯分布相結(jié)合，在增強種群局部搜索能力的同時，整體上平衡了全局搜索與局部尋優(yōu)的能力。最后，本文使用CEC 2014中6個基準測試函數(shù)對本文所提算法與其他差分進化算法進行仿真實驗，結(jié)果表明本文OL-ADE算法收斂更快、精度更高，即OL-ADE算法總體性能和可靠性較高。在下一步工作中，將在多目標優(yōu)化問題中對增強型反向?qū)W習的自適應算法在收斂性及可靠性方面作進一步研究。

參考文獻:

[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]LIAO T W. Two hybrid differential evolution algorithms for engineering design optimization [J]. Applied Soft Computing, 2010, 10(4): 1188-1199.

[3]PIOTROWSKI A P. Differential evolution algorithms applied to neural network training suffer from stagnation [J]. Applied Soft Computing, 2014, 21: 382-406.

[4]ZHOU Y-Z, YI W-C, GAO L, et al. Adaptive differential evolution with sorting crossover rate for continuous optimization problems [J]. IEEE Transactions on Cybernetics, 2017, 47(9): 2742-2753.

[5]FAN Q, YAN X. Self-adaptive differential evolution algorithm with zoning evolution of control parameters and adaptive mutation strategies [J]. IEEE Transactions on Cybernetics, 2016, 46(1): 219-232.

[6]薛羽,莊毅,顧晶晶,等.自適應離散差分進化算法策略的選擇[J]. 軟件學報,2014,25(5):984-996. (XUE Y, ZHUANG Y, GU J J, et al. Strategy selecting problem of self-adaptive discrete differential evolution algorithm [J]. Journal of Software, 2014, 25(5): 984-996)

[7]YANG M, LI C, CAI Z, et al. Differential evolution with auto-enhanced population diversity [J]. IEEE Transactions on Cybernetics, 2015, 45(2): 302-315.

[8]GUO J, LI Z, XIE W, et al. Dissipative differential evolution with self-adaptive control parameters [C]// CEC 2015: Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2015: 3088-3095.

[9]QIN A K, SUGANTHAN P N. Self-adaptive differential evolution algorithm for numerical optimization [C]// CEC 2005: Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2005: 1785-1791.

[10]BREST J, GREINER S, BOSKOVIC B, et al. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems [J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657.

[11]ZHANG J, SANDERSON A C. JADE: adaptive differential evolution with optional external archive [J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958.

[12]TANABE R, FUKUNAGA A. Success-history based parameter adaptation for differential evolution [C]// CEC 2013: Proceedings of the 2013 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2013: 71-78.

[13]YI W, ZHOU Y, GAO L, et al. An improved adaptive differential evolution algorithm for continuous optimization [J]. Expert Systems with Applications, 2016, 44: 1-12.

[14]ZHANG J, ZHAN Z-H, LIN Y, et al. Evolutionary computation meets machine learning: a survey [J]. IEEE Computational Intelligence Magazine, 2011, 6(4): 68-75.

[15]TIZHOOSH H R. Opposition-based learning: a new scheme for machine intelligence [C]// CIMCA ’05： Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06). Washington, DC: IEEE Computer Society, 2005: 695-701.

[16]WANG W, WANG H, SUN H, et al. Using opposition-based learning to enhance differential evolution: a comparative study [C]// CEC 2016: Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 71-77.

[17]WANG H, LI H, LIU Y, et al. Opposition-based particle swarm algorithm with Cauchy mutation [C]// CEC 2007: Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2007: 4750-4756.

[18]EL-ABD M. Opposition-based artificial bee colony algorithm [C]// GECCO ’11: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2011: 109-116.

[19]RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Opposition-based differential evolution algorithms [C]// CEC 2006: Proceedings of the 2006 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2006: 2010-2017.

[20]OMRAN M G H, SALMAN A. Constrained optimization using CODEQ [J]. Chaos, Solitons & Fractals, 2009, 42(2): 662-668.

[21]WANG H, RAHNAMAYAN S, WU Z. Parallel differential evolution with self-adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems [J]. Journal of Parallel and Distributed Computing, 2013, 73(1): 62-73.

[22]RAHNAMAYAN S, TIZHOOSH H R, SALAMA M M A. Quasi-oppositional differential evolution [C]// CEC 2007: Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2007: 2229-2236.

[23]WANG H, WU Z, RAHNAMAYAN S, et al. Enhancing particle swarm optimization using generalized opposition-based learning [J]. Information Sciences, 2011, 181(20): 4699-4714.

[24]SEIF Z, AHMADI M B. An opposition-based algorithm for function optimization [J]. Engineering Applications of Artificial Intelligence, 2015, 37: 293-306.