基于自適應差分進化算法的優(yōu)化

李麗蓉,王平

(1.山西警察學院 網絡安全保衛(wèi)系,山西 太原 030401;2.山西財經大學 資源環(huán)境學院,山西 太原 030006)

0 引言

差分進化(Differential Evolution,DE)算法是一種基于不同候選解集的優(yōu)化算法。Storn和Price首先提出差分進化算法[1]。差分進化算法,作為進化算法中的一種,由許多候選解組成,候選解組成種群,并且種群經過一代代更新來發(fā)現(xiàn)最優(yōu)解。差分進化算法與其他算法的不同處在于,每一個候選解自己不能尋找新的解,而是需要借助其他候選解的差異性來發(fā)現(xiàn)新的解。差分進化算法已經成功應用于各種領域解決不同現(xiàn)實問題,如電磁學、光學、模式識別和信號處理等[2-8]。差分進化算法目前已成為研究的熱點并取得顯著進展[9-13]。

差分進化算法主要利用獲選解間的不同性來搜索更多的可能的解。一個候選解當作一個個體,每個個體的更新需要利用不同個體間的差異來進行。但是獲取個體間的差異性的方式需要進一步的分析,以及怎么樣利用這些差異性,即設置其相關的參數(shù)來搜索更好的解需進一步的研究。在現(xiàn)有的差分進化算法中,這些參數(shù)的改變導致其最終的結果變化很大。本文提出一種新的自適應技術,使其求解的性能比其他的自適應算法具有更好的魯棒性。

1 差分進化算法

1.1 基本概念

差分進化的設計是基于一種隨機、并行的搜索算法,運用了進化計算中的共同點,但是其需要的參數(shù)更少。標準的差分進化算法描述如下:

(1) 種群

(1)

(2)

(2) 種群的初始化

(3)

這里xj,min和xj,max是其所求第j維的解的空間,rnd是一個隨機數(shù),其范圍從0到1。

(3) 基于差異的組合

(4)

這里s1、s2、s3為隨機整數(shù),其范圍從1到N,并且彼此不相等。不同變形版本的組合方法可以參考文獻[14]。

(4) 交叉操作

交叉操作用來提高種群的多樣性。最常見的交叉操作是均勻交叉,即

(5)

(5) 選擇操作

1.2 自適應差分進化方法分析

由于式(4)中F的改變而可能會導致無法發(fā)現(xiàn)全局最優(yōu)解,相關的研究運用自適應策略來控制F,使其適應于不同的情況,從而避免F太大而易陷入局部最優(yōu)解,太小而缺少足夠的擾動來尋找新的解。

Dither DE (DDE)差分算法[15]被認為是最早之一的自適應差分進化算法。Karaboga和?kdem也從事類似的研究工作[16]。在DDE中,自適應Fdither描述如式(6),其中Fmax和Fmin為F的最大值和最小值。Karaboga和?kdem[16]用一個固定的隨機數(shù)rnd來控制所有維數(shù)的F。文獻[17]建議rnd控制每一維,而不是所有的維。

Fdither=Fmin+rnd×(Fmax-Fmin) .

(6)

Jitter DE (JDE)[15]采用一個隨機因子來控制F的值，即

Fjitter=F×(1+δ×(rnd-0.5)) .

(7)

其中rnd是基于每維而不是一個固定的值對所有的維。JDE能對非欺騙性優(yōu)化函數(shù)問題具有非常好的求解能力[14]。Fdither和Fjitter都引入了新的參數(shù)來控制F而導致需要優(yōu)化新的參數(shù)值。在DDE中,Fmax和Fmin將會影響其尋找全局最優(yōu)解的能力和其算法的收斂速度。而JDE需要求解函數(shù)的先驗知識來設置參數(shù)δ,并且JDE對于目標欺騙性函數(shù)而言,難以找到最優(yōu)解。

2 新的自適應策略

在自適應進化差分算法中引入新的參數(shù)將影響算法的收斂速度并且需要解決新的參數(shù)優(yōu)化問題,為了避免此問題,本文提出了一種新的自適應策略來控制F，記為SinDE。這種新的自適應策略應滿足以下約束條件：1)自適應化后的F必須是正數(shù),擾動的方向僅由兩個不同個體的差異來控制,這樣利于往優(yōu)化的解的空間搜索; 2)F必須是可變而不是固定的,適當?shù)臄_動利于發(fā)現(xiàn)不同新的個體;3)對F的控制不能引入新的參數(shù),應該是非參數(shù)化自適應調制。根據以上約束條件,選擇三角函數(shù)sin用來調制F,因為當輸入的范圍從0到π時,三角函數(shù)sin的值從0到1,能夠滿足這3個條件。Fsin定義如下：

Fsin=F×(sin(rnd×π)) ,

(8)

其中rnd是基于每維的隨機數(shù)。

假設一個理想的自適應Fideal的范圍是從0到1,對于DDE而言,Fmax=1和Fmin=0;對于JDE而言,當δ大于2的時候,F可能會小于0,而δ設置太小,F遠遠大于0,這需要合理的設置F和δ;然而本文提出的自適應方法,當F為1時即可滿足條件。比較DDE、JDE和SinDE的自適應F的空間,可以得出Fdither和Fsin的空間寬于Fjitter的空間。進一步分析,Fdither和Fsin對于F的分布,Fsin的值絕大多數(shù)位于其中心位置,而Fdither則使F呈現(xiàn)為均勻分布，也就是說,在DDE算法中隨機選擇F,而SinDE算法中則是Fsin有針對性地選擇F,這樣的選擇更符合數(shù)據分布特征。因此，本文提出的自適應算法將進一步提高收斂速度并且可以克服局部最優(yōu)的問題。

3 仿真實驗

3.1 實驗設計

許多領域的問題都可以轉化為求解全局最優(yōu)化解,如工程設計、應用科學、分子生物學等[5]。許多全局最優(yōu)解的問題經常包含有許多局部極優(yōu)解,從而導致許多算法只能找到某個或多個局部解而無法發(fā)現(xiàn)最優(yōu)解。本文采用一些經典的測試函數(shù)[18]來測試SinDE的算法性能,并和DDE、JDE和StdDE(表示直接用F而不經過自適應處理)算法進行比較。以上算法均由Matlab2017實現(xiàn)。

四個標準測試函數(shù)描述如下:

(1) Shpere

(9)

minf1=f1(0,…,0)=0 .

(2) Generalised Schwefel 2.26

(10)

minf2=f2(420.968 7,…,420.968 7)=0 .

(3) Generalised Rastrigin

(11)

minf3=f3(0,…,0)=0 .

(4) Generalised Rosenbrock

(12)

minf4=f4(1,…,1)=0 .

其中Generalised Schwefel’s Problem 2.26 (公式(10)) 的最優(yōu)解的值被移到0, 其原公式為：

(13)

3.2 算法參數(shù)設置

為了比較這些算法的性能,在對這些函數(shù)優(yōu)化問題的求解時,不同的參數(shù)應用于實驗當中。這些參數(shù)主要包括F以及其相關的控制參數(shù),種群大小N和交叉概率pcr。為了統(tǒng)計相關的函數(shù)評價次數(shù),采用|fi(x)-minfi|<ε和有限的函數(shù)評價次數(shù)來判斷相關的算法能否找到最優(yōu)解,這里i=1,2,3,4。表1為其相關的參數(shù)設置。為確定算法魯棒性,所有實驗都獨立運行30次，結果為平均值。

3.3 實驗結果

表2為SinDE,StdDE,DDE和JDE基于不同F(xiàn)求解四個函數(shù)的最優(yōu)解的平均值和方差。表格中“0”表示其相關的最優(yōu)值滿足終止條件,小于ε。對于函數(shù)f2,其原始最優(yōu)值為-12 596.5 (30維),其ε一般都大于0.000 1。但是本文采用統(tǒng)一標準ε為0.000 1。從表2可得知,SinDE具有最好的魯棒性。對于F的改變,其最優(yōu)值變化的范圍最小。對于函數(shù)f3,不同的F值沒有影響SinDE找到最優(yōu)解,而當F=1.5,StdDE,DDE和JDE都無法尋找到最優(yōu)解。對于函數(shù)f4,所有的算法都無法尋找到最優(yōu)解,但是不同的F值,SinDE所求解的最小值變化不大,都接近于最優(yōu)值。而當F=1.5,StdDE,DDE和JDE都遠離最優(yōu)值。

表1 參數(shù)設置

表2 四種算法最優(yōu)解的平均值和方差(pcr=0.2,N=60)

表3為SinDE,StdDE,DDE和JDE基于這四個函數(shù)最優(yōu)問題的函數(shù)評價次數(shù)的平均值和方差。其中“300 000±0”意味著在其300 000有限的函數(shù)評價次數(shù)內,相關的算法無法找到最優(yōu)解。從函數(shù)f1,f2,f3可以看出,SinDE明顯用最少的評價次數(shù)來尋找到最優(yōu)解。

基于表2和表3的結果可以看出,當F變化時,SinDE比DDE和JDE更好地自適應調整F來尋找最優(yōu)解。

表4為SinDE,StdDE,DDE和JDE求解四個函數(shù)的最優(yōu)解的平均值和方差(pcr=0.5)。與表2比較,pcr=0.5差于pcr=0.2,其中當F為0.5時,DDE求解f2具有最優(yōu)值,F為1.0時, StdDE和JDE求解f2具有最優(yōu)值(兩者平均值無顯著性差異,基于顯著性水平0.05的t-test),F為0.5時,StdDE和JDE求解f4有最優(yōu)值。而對于其余結果,SinDE都表現(xiàn)為最優(yōu)。特別當F為1.5時,針對f4的求解,StdDE,DDE和JDE無法尋找其解。由此可見,在交叉概率變化時,SinDE搜索這四個函數(shù)最優(yōu)值的能力要優(yōu)于DDE和JDE。

表3 四種算法函數(shù)評價次數(shù)的平均值和方差(pcr=0.2,N=60)

表4 四種算法最優(yōu)解的平均值和方差(pcr=0.5,N=60)

圖1和圖2描述了這4種方法基于不同種群大小(N為30和100)的收斂狀態(tài),當N=30時，對于函數(shù)f1和f4,SinDE表現(xiàn)出了最好的收斂速度和搜索全局最優(yōu)解的能力。對于函數(shù)f2,DDE的收斂速度要優(yōu)于其他方法,但是SinDE的進化過程接近DDE。對于函數(shù)f3,DDE發(fā)現(xiàn)了全局最優(yōu)解,而其他算法都收斂于用一個局部解。當N=100時，對于函數(shù)f1,f2和f4,SinDE明顯要優(yōu)于其他3種方法。對于函數(shù)f3,整體而言SinDE仍然優(yōu)于其他的方法。對比求解函數(shù)f4的收斂情況,SinDE對其平均最小值的改變不大,但是StdDE、DDE和JDE用種群大小100求解的最小平均值要差于其用種群30求解的最小平均值。DDE在用種群大小100時,沒有成功找到函數(shù)f3的全局最優(yōu)解。從圖1和圖2可以看出,種群大小的變化對StdDE,DDE和JDE求解最優(yōu)值有一定明顯的影響,而SinDE所受的影響要低于其他3種算法,表現(xiàn)出一定的穩(wěn)定性。

Fig.1 Evolutionary process of solve functions for four algorithms (N=30)圖1 四種算法求解函數(shù)的進化過程(N=30)

Fig.2 Evolutionary process of solve functions for four algorithms (N=100)圖2 四種算法求解函數(shù)的進化過程(N=100)

4 結論

本文提出了一種新的自適應差分進化算法，可以自適應控制F因子。在標準函數(shù)的測試實驗結果表明，相比于其他的自適應算法,本文算法表現(xiàn)出了非常好的求解函數(shù)最優(yōu)值的能力,并且算法中的參數(shù)具有較好的魯棒性。

在未來工作中，將在更多的數(shù)據集上驗證本文算法，并且針對提出的自適應的3個條件,進一步研究更有效的自適應差分進化技術。