基于牛頓三次插值的自適應差分進化算法

陳恩茂，徐志剛，付 源

(1.東北大學 機械工程與自動化學院，遼寧 沈陽 110819；2.中國科學院沈陽自動化研究所，遼寧 沈陽 110016；3.中國科學院機器人與智能制造創新研究院，遼寧 沈陽 110169；4.湖南大學 機械與運載工程學院，湖南 長沙 410082)

0 引 言

差分進化(differential evolution，DE[1])算法自提出以來，由于其結構簡單、魯棒性強、收斂速度快等特點，被廣泛應用于各工程領域[2]。本文提出一種基于牛頓三次插值的自適應差分進化算法(adaptive differential evolution algorithm based on Newton cubic interpolation，ANCIDE)。該算法的改進特點如下：設計局部搜索半徑，在最優個體附近搜索4個節點運用牛頓三次插值進行局部搜索，提高算法收斂性能；提出自適應論證策略，根據當代運用牛頓三次插值的效果來調整下一代使用牛頓三次插值的概率，避免陷入局部最優；采用自適應學習策略控制F和CR，解決參數設置敏感的問題。

1 經典差分進化算法

步驟1 種群初始化。DE隨機產生NP個D維個體[3]

(1)

(2)

式中：NP表示種群數量，D表示個體維度，rand(0,1)代表(0,1)內服從均勻分布的隨機數。

步驟2 常見的變異策略有DE/rand/bin/1和DE/best/bin/1，分別如式(3)和式(4)所示[4]

Vr,G=Xr1,G+F·(Xr2,G-Xr3,G)

(3)

Vr,G=Xbest,G+F·(Xr2,G-Xr3,G)

(4)

式中：r1,r2,r3是3個不同的隨機數，且r1≠r2≠r3≠i。G表示第G代個體。Xbest,G表示第G代最優個體。Vr,G表示第G代變異個體。F是縮放因子，用來控制差分向量。

步驟3 交叉操作。對目標個體Xi,G和變異個體Vi,G進行交叉操作，產生實驗個體Ui,G，即

(5)

式中：CR為交叉概率，rand(0,1)為(0,1)內服從均勻分布的隨機數，jrand為[1,D]的隨機整數。

步驟4 選擇操作。DE采用貪婪算法來選擇適應值較小的作為進入下一代種群的個體。即

(6)

2 ANCIDE算法

2.1 牛頓三次插值

在區間[a,b]上f(x)關于兩個不同的節點xi，xj的一階差商定義如下[5]

(7)

在區間[a,b]上f(x)關于3個不同的節點xi，xj，xk的二階差商定義如下

(8)

一般地，稱式(9)為f(x)關于k+1個不同的節點

x0,x1,…,xk的k階差商

(9)

根據差商的定義，牛頓插值多項式表示為

Nn(x)=f(x0)+f[x0,x1]ω1(x)+
f[x0,x1,x2]ω2(x)+…+f[x0,x1,…,xn]ωn(x)

(10)

式中：ωn(x)=(x-x0)(x-x1)…(x-xn-1)。特別地，當選擇4個不同的節點進行插值時，得到的Nn(x)為牛頓三次插值多項式。與牛頓二次插值相比，牛頓三次插值選取節點更多，擬合曲線更接近函數圖像，插值精度更高。在第j維空間進行牛頓三次插值時，式(10)可以改寫為

(11)

式中

a=f[x0,j,x1,j,x2,j,x3,j]

(12)

b=f[x0,j,x1,j,x2,j]-
f[x0,j,x1,j,x2,j,x3,j](x0,j+x1,j+x2,j)

(13)

c=f[x0,j,x1,j]-f[x0,j,x1,j,x2,j](x0,j+x1,j)+
f[x0,j,x1,j,x2,j,x3,j](x0,jx1,j+x0,jx2,j+x1,jx2,j)

(14)

d=x0,j(f[x0,j,x1,j,x2,j]x1,j-f[x0,j,x1,j]-
f[x0,j,x1,j,x2,j,x3,j]x1,jx2,j)+f(x0,j)

(15)

如圖1和圖2所示，a、b、c共同影響局部最優點x4,j的位置。

圖1 a≠0時x4,j的搜索方向

圖中，x0,jx*,j′。根據x4,j的搜索方向，將求解x4,j的公式總結如下

(16)

圖2 a=0時x4,j的搜索方向

式中：r1、r2、r3、r4為(0,1)內服從均勻分布的隨機數。

2.2 運用牛頓三次插值局部搜索

2.2.1 局部搜索半徑

在第j維空間對最優個體xbest,j附近運用牛頓三次插值進行局部搜索。其中搜索半徑R、R′分別定義為

R=[max(xj)-min(xj)]·r

(17)

R′=[max(xj)-min(xj)]·r′

(18)

式中：max(xj)和min(xj)分別代表種群內所有個體在第j維空間xj的最大值和最小值，r和r′分別代表兩個不同的(0,1)的隨機數。由此可得除xbest,j外，其余3個插值節點為

x0,j=xbest,j-R

(19)

x1,j=xbest,j+R

(20)

x2,j=xbest,j-R′

(21)

2.2.2 自適應論證策略

為了評估是否在下一代運用牛頓三次插值在最優個體附近進行局部搜索，定義牛頓插值率(Newton interpolation rate, NIR)如式(22)表示[6]

(22)

式中：f(xbest)和f(xbest′)分別代表當代最優個體的適應值和使用牛頓三次插值得到最優個體的適應值。NIRmax表示牛頓插值率的最大值，NIRmin表示牛頓插值率的最小值。式(22)表明，如果使用牛頓三次插值進行局部搜索有效，則提高下一代使用牛頓三次插值的概率。反之，則降低使用牛頓三次插值的概率。

2.3 自適應學習策略控制參數

縮放因子F和交叉概率CR對DE的性能至關重要。F選擇較大的值、CR選擇較小的值可以提高DE的全局搜索能力；F選擇較小的值、CR選擇較大的值可以提高DE的局部搜索能力，加速收斂。變異操作階段，采用如下方案[7]調整F的值，并應用到DE/best/bin/1中

Fi=randcauchy(μF,0.1)

(23)

式中：randcauchy表示位置參數為μF，尺度參數為0.1的柯西分布函數。當Fi≥1時，Fi=1；當Fi≤0時，Fi根據式(23)重新計算。μF在積累每代成功進化個體的縮放因子F后如式(24)更新

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

(24)

式中：c∈(0,1]，SF為成功進化個體縮放因子F的集合。meanL()為Lehmer平均數，如式(25)計算

(25)

交叉操作階段，每個個體的交叉概率CRi根據式(26)進行更新

CRi=randni(μCR,0.1)

(26)

式中：randni表示數學期望為μCR，標準差為0.1的高斯分布函數。當CRi>1或CRi≤0時，CRi根據式(26)重新計算。與μF類似，μCR在積累每代成功交叉個體的交叉概率CR后如式(27)更新

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

(27)

式中：c∈(0,1]，SCR為成功交叉個體的交叉概率CR的集合。meanA()為算術平均數，如式(28)計算

(28)

2.4 ANCIDE算法步驟

總結以上改進策略，得到以下ANCIDE算法步驟：

步驟2 評估初代最優個體xbest及其對應的最優適應值f(xbest)。并置當前迭代次數G=1，當前函數訪問次數FEs=NP。

步驟3 判斷是否滿足終止準則，如果滿足，則輸出當前最優個體作為最優解；否則轉步驟4。

步驟4 若隨機數rand(0,1)

步驟5 在每個維度利用步驟4所求的4個插值節點xbest,j、x0,j、x1,j、x2,j分別根據式(12)、式(13)、式(14)、式(15)計算牛頓三次插值多項式及a、b、c、d。

步驟6 根據式(16)計算牛頓三次插值得到最優個體xbest′及其對應的適應值f(xbest′)， 若f(xbest′)

步驟7 對每個個體根據式(23)計算Fi，根據式(4)進行變異操作，并得到變異個體Vi。

步驟8 對每個個體根據式(26)計算CRi，根據式(5)進行交叉操作，并得到實驗個體Ui。

步驟9 對每個個體根據式(6)進行選擇操作，若f(Ui,G)

3 數值實驗及結果分析

3.1 基準測試函數

選取CEC2013上的由28個基準函數組成的測試集[8]進行算法測試。在這28個基準測試函數中，f1～f5為單峰函數，用于考察算法的收斂速度和收斂精度；f6～f20為多峰函數，局部最優點的數量隨維度指數遞增，用于考察算法的全局搜索能力；f21～f28為組合函數，通過將單峰函數和多峰函數組合，增大算法的搜索難度。

3.2 實驗結果及分析

為了驗證ANCIDE的可行性和有效性，與著名的jDE[9]、FiADE[10]、SaDE[11]、DE-EIG[12]進行測試比較。為保證實驗的公平性，每個算法的種群規模NP取4D，函數最大訪問次數FEsmax取10^4*D，均在處理器為Intel(R) i5-7500，內存為8 GB的計算機上，通過Matlab R2014a獨立運行30次。表1為各算法參數初始值，表2為30維下各算法的實驗結果(表中加粗部分為最優解)。

表1 各算法參數初始值

表2 30維運行結果

表2(續)

表2(續)

由表2分析可知，對于單峰函數f1,f5，大部分多峰函數f9,f13,f14,f15,f16,f17,f18,f19,f20，及組合函數f22,f23，ANCIDE算法收斂精度更高，更易找到全局最優點。尤其是對于多峰函數如f14,f15,f16,f17，組合函數如f22,f23, ANCIDE算法的競爭力十分顯著(如圖3所示)。因此，ANCIDE算法不失為一個解決復雜優化問題的好方法。

圖3 30維各算法的收斂曲線

4 結束語

經典差分算法存在易早熟收斂、對參數設置敏感的問題。為解決這些問題，本文提出基于牛頓三次插值的自適應差分進化算法。利用牛頓三次插值擬合目標函數圖像，為算法局部搜索提供方向，從而加快算法收斂速度；為了平衡全局搜索和局部搜索，設計自適應論證策略來評估下一代是否使用牛頓三次插值；采用自適應學習策略來調整縮放因子F和交叉概率CR，從而避免人為設置參數。實驗結果表明，對于大部分基準函數，該算法的性能均優于其它改進DE算法。今后的研究方向將致力于繼續提高算法性能和解決實際工程問題。