自適應二次變異的改進差分進化算法及其應用

胡福年 董倩男 呂 璐

(江蘇師范大學電氣工程及自動化學院 江蘇 徐州 221116)

0 引 言

差分進化(Differential Evolution，DE)算法[1]是一種基于群體差異的隨機搜索算法，其原理與遺傳算法類似，但不包括編碼和解碼，受控參數少，同時因其本身具有強大的魯棒性和全局尋優能力，因而在約束優化[2]、電力系統調度[3]等領域得到廣泛運用。

與常用進化算法類似[4-7]，DE算法也存在容易陷入局部最優和過早收斂的問題。因此，學者們對DE算法進行不同方面的改進，以提高算法收斂精度并跳出局部最優。改進方法大致分為以下幾類。

一是控制參數的改進，主要涉及種群規模、變異策略、交叉策略等。文獻[8]對變異因子、交叉概率進行自適應控制，增強了算法的尋優性能。文獻[9]對變異策略進行改進，采用隨機選擇的方式在兩種變異策略之間進行選擇。文獻[10]使用動態加權因子對兩種變異策略進行權值動態分配，增強算法的全局尋優性能，同時采用了控制參數的自適應方法。

二是種群結構的改變，如種群重構、多種群差分。文獻[11]提出一種基于平均熵的初始化策略，將種群拆分為兩個群體，分別采用不同的變異策略，進行種群間的信息交流。文獻[12]將種群以適應值大小進行分類成為多個種群，采用不同的策略進化，實現全局優化。文獻[13]將種群隨機動態分為多個子群體，增強個體間的信息交換。

三是與其他算法交叉使用，結合不同算法的尋優思想對DE進行改進。文獻[14]將粒子群算法與差分進化算法結合使用，充分發揮兩種算法的優點，改善了差分算法的收斂性能。文獻[15-16]將人工蟻群算法與差分進化算法混合使用，增強了算法的搜索性能和尋優速度。文獻[17]將免疫克隆算法與差分進化算法結合，增強算法的搜索能力。

DE進化算法的改進方式多樣，為進一步增強算法的尋優性能和收斂精度，本文結合現有的幾種改進方法的思想，充分利用各種改進策略的優勢，提出一種基于自適應二次變異的改進差分進化算法。通過記錄最優解連續不更新的次數，自適應地對種群進行二次重構。為證明該算法的有效性，對9個測試函數進行仿真，并且選用3種常用的改進差分進化算法與其進行對比，對算法性能進行分析。將算法實際應用于38機組的電力系統調度問題中，驗證算法的收斂性能。

1 差分進化算法

差分進化算法的基本思想是從某一隨機種群開始，按規則進行迭代，對個體進行一定操作，最后淘汰適應值差的個體，保留優秀個體。對于最小值優化問題描述如下：

(1)

(1) 初始化。DE基于實數編碼，在可行域中隨機生成NP個D維的初始種群：

xi,0=(xi1,0,xi2,0,…,xiD,0)

(2)

(3)

(2) 變異。DE通過差分策略實現個體變異，利用兩個不同的父代向量做差，產生相應的差分向量，將其向量差縮放后與待變異個體進行向量合成，這也是差分進化算法和遺傳算法之間的差異。在DE中最常用的變異策略是DE/rand/1、DE/best/1、DE/current-to-rand/1、DE/current-to-best/1等。具體操作如表1所示。

表1 變異策略

其中：r1、r2、r3為兩兩互不相同的隨機整數且r1≠r2≠r3≠i；F為縮放因子，取值在0～1之間；vi,G+1表示變異后個體；xi,G表示第G代第i個個體；xr1,G、xr2,G、xr3,G表示當前種群中隨機選取的不同個體；xbest,G表示第G代最優個體。

(3) 交叉。對第G代個體及變異個體進行交叉操作。DE算法的交叉操作有兩種方式：二項式交叉和指數交叉。一般選取較為簡單的交叉方式，即二項式交叉，具體操作如式(4)所示，得到實驗個體:ui,G+1=(ui1,G+1,ui2,G+1,…，uiD,G+1)。

(4)

式中：CR為交叉率，取值在0～1之間；jr指1,2,…，D上的隨機整數。

(4) 選擇。選擇操作的主要目的是選擇一個好的個體作為下一代的父代。通常，采用貪婪算法選擇進入下一代群體的個體。對于最小化問題，選擇具有小適應度函數值的個體作為下一代群體的成員。

(5)

式中：xi,G+1表示選擇操作后，進入下一代的個體。

2 自適應二次變異的改進差分進化算法

2.1 變異策略

傳統DE進化算法僅使用單一的變異策略，使得每下一代個體的產生都通過父代個體之間不變的變異操作，容易過早聚集收斂陷入局部最優。因而在差分算法進化的開始階段，應當保證種群的多樣性。DE/rand/1具有較大的尋優范圍，它有利于全局搜索，故適用于算法初期。而到了算法進化中后期，因前期已經完成了全范圍的搜索，此時應重點關注最優個體及其附近區域。DE/current-to-best/1尋優速度較快，有利于局部的精確搜索，故適用于算法進化后期。針對各種策略在各階段所發揮的作用不同這一特點，采用多變異策略，將DE/rand/1與DE/current-to-best/1相結合，加入動態權重因子平衡兩種策略的權重，充分發揮兩種變異策略的優勢。

w=wmin+(wmax-wmin)·(G/Gmax)

(6)

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

w·(xi,G+F·(xqbest,G-xi,G)+F·(xr4,G-xr5,G))

(7)

式中：w為權重因子，wmin=0，wmax=1；Gmax為總進化代數。

w值隨著進化種群數的增加呈線性遞增趨勢，有利于平衡兩種變異策略的權重。在算法進化初期，w值較小，DE/rand/1策略起主導作用，有利于增加解空間的搜索范圍；在算法演化的中后期，w值較大，DE/current-to-best/1策略起決定性作用，有利于局部精確搜索。

結合RMDE[18]中擾動策略的思想，設置一個調和參數Mr，隨機選擇現有的變異操作和擾動策略，稱為小概率擾動，進一步增強算法跳出局部最優的能力，Mr一般取大于0.9的值，部分偽代碼為：

ifrand

w=wmin+(wmax-wmin)·(G/Gmax)

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

w·(xi,G+F·(xqbest,G-xi,G)+F·(xr4,G-xr5,G))

else

end

2.2 自適應二次變異

針對差分進化算法的早熟問題，并提高算法跳出局部最優的能力，本文通過記錄算法進化過程中適應值連續不更新的次數來及時檢測算法的停滯狀況，以便進行自適應二次變異。設定一個停滯代數最大值Max_count，當最優適應值連續Max_count代不更新時，即認為之后的算法進化是無用的停滯迭代，采用二次變異策略打破停滯，并提供更好的進化方向。

二次變異策略中利用全局最優信息和柯西分布，決定算法跳出局部最優的方向和步長?？挛鞣植寂c正態分布的概率分布對比如圖1所示，其中正態分布服從N～(0,1)，柯西分布服從Cauchyi～randci(μ,λ)，μ和λ是局部參數，分別取μ=0,λ=1。圖2顯示了取200個數，柯西隨機數Cauchyi～randci(μ,λ)的數值，分別取μ=0,λ=0.01。由圖知，相比于正態分布，柯西分布降低了取值為0的概率，能夠增加取除0以外其他值的概率。

圖1 概率分布對比圖

圖2 柯西隨機數

自適應二次變異的偽代碼為：

count=0;

forG=1:Gmax

ifxbest,G+1=xbest,G

count=count+1;

else

count=0;

end

ifcount=Max_count

fori=1:NP

end

count=0;

end

end

2.3 選擇策略

為進一步加大算法的尋優范圍，加入反向學習策略，可以增加算法解的多樣性，增加在搜索過程中找到全局優解的機會，并加快算法收斂速度。選擇策略時，在交叉后得到的實驗個體與反向個體之間進行選擇，反向個體的產生過程如下：

(8)

根據適應值的大小，選擇下一代的個體。

(9)

2.4 控制參數

控制參數F和CR直接影響下一代群體的搜索方向和搜索范圍，在傳統的差分進化算法中通常取固定值。但是這樣無法滿足算法在進化的各階段中對控制參數的不同要求，如算法多樣性、魯棒性等，因而漸漸產生了參數自適應的改進差分進化算法。參數自適應使得算法能夠在進化的不同時間段內，根據自身種群的分布情況與適應值之間的相對位置關系，改變自身的搜索范圍與搜索方向，以增強整個算法的尋優性能。參數F和CR通常取0～1以內的值。

本文考慮將產生優秀個體的參數值保留，將產生淘汰個體的參數值重新設定，根據個體適應值來決定是否將參數值保留至下一代，具體表達式如下：

(10)

(11)

(12)

CRi,1=0.9

(13)

式中：Fi,1、Fi,G、Fi,G+1分別表示第一代縮放因子、第G代縮放因子、第G+1代縮放因子；Fmin、Fmax表示縮放因子的最小值和最大值；CRi,1、CRi,G、CRi,G+1分別表示第一代交叉概率、第G代交叉概率、第G+1代交叉概率。

ASVDE算法流程如圖3所示。

圖3 ASVDE算法流程

3 電力系統經濟調度模型

電力系統經濟調度[19]問題是指在滿足系統的約束條件下對機組的發電功率進行合理分配，降低發電成本，從而達到經濟性最高的目標。主要內容包括目標函數的設定和約束條件的處理。

3.1 目標函數

以機組發電成本為目標函數，在T時間段內，常規發電機組的發電成本主要考慮發電機組燃料成本而不考慮閥點效應的情況下，機組燃料成本可表示為：

(14)

式中：Cj表示第j臺機組的發電成本；aj、bj、cj表示第j臺機組的發電成本系數，通常取正的常數。

3.2 約束處理

約束條件主要考慮兩方面約束，一是所有發電機組的發電輸出等于系統總的負荷需求，忽略電能的傳輸損耗；二是考慮發電機組輸出功率的上、下邊界。對約束條件的處理采用最常用的方法——懲罰函數法。

FP=FC+M·p(x)

(15)

(1) 功率平衡約束。

(16)

式中：PL表示系統總的負載需求，Pj表示第j臺機組的輸出功率。

(2) 發電機組輸出功率的上、下邊界。

(17)

4 仿真實驗

4.1 函數與參數設置

為了驗證ASVDE算法的搜索能力，選用9個函數對其進行測試，并且另外選取3種差分進化算法作為對比。測試函數的類型分為單峰函數和多峰函數，它們的優化均為最小值問題。使用的對比算法有DE算法、RMDE算法、HSDE算法[20]，根據各種算法在參考文獻內的描述，將參數設置如下。

(1) DE算法中，縮放因子F=0.5，交叉概率CR=0.3。

(2) RMDE算法中，縮放因子F=rand，交叉概率CR=0.3，擾動因子Mr=0.9。

(3) HSDE算法中，縮放因子Fmax=0.9，Fmin=0.1，交叉概率CR=rand。

(4) ASVDE算法中，縮放因子Fmax=1，Fmin=0.1；擾動因子Mr=0.99，Max_count=5。

表2給出了測試函數的定義、自變量范圍與理論最優值。算法的種群規模NP=100，每種算法均獨立運行30次，迭代次數為1 500代，分別計算四種算法在20維、50維、100維中得到的平均值、標準差。通過30次運行獲得的平均值、標準差和以顯著性水平為0.05的Wilcoxon rank-sum test指標[21]可得出ASVDE算法與其他3種對比算法性能的優劣。Wilcoxon秩和檢驗和T檢驗均可用于測試兩組獨立樣本的差異性，但是Wilcoxon秩和檢驗不要求數據必須符合正態分布。測試結果存在兩種情況：差異顯著和差異不顯著。結果用p值表示，當兩組數據完全相等時檢驗結果為NaN。但若有顯著性差異，則無法比較兩組數據所對應的算法的優劣。因此，為進一步判斷算法的優劣，采用“勝率”作為下一步的分析方案?！皠俾省?，即兩種算法每次運行得出的最優值兩兩進行比較。若勝，加1分；若平，加0.5分；若敗，加0分。將每個算法得到的分數除以比較的次數(30×30=900)，得到的值就是它們各自的勝率。此外，對每個算法測試函數在各個維度獲得的平均值進行排序，以便得出更直觀的結論。仿真實驗使用MATLAB軟件編程實現。

表2 測試函數

4.2 測試函數的實驗結果

根據文中所述的參數設置及采用的分析指標，對4種算法優化測試函數的結果進行分析。表3為4種算法在20維、50維、100維三種的情況下搜索得到的平均值、標準差，表4為秩和檢驗結果，其中最優解加粗標記。

表3 實驗結果

續表3

表4 秩和檢驗結果

續表4

從表3和表4可以看出，與其他3種算法相比，ASVDE算法的優化性能占絕對優勢。對于20維的測試函數，除了在函數f5上ASVDE與DE取得并列最優解，其余函數上ASVDE算法的平均值和標準差均達到最優水平；除函數f2、f6和f7外，ASVDE算法均能找到全局最優解，因此，在低維時，ASVDE算法具有較好的平均優化性能、穩定性和魯棒性。根據Wilcoxon rank-sum test和勝率指標來看，除函數f4和f5外，ASVDE算法明顯優于其他算法且勝率達到100%。在50維和100維時，除函數f2、f6和f7外，ASVDE算法均找到了全局最優解，且ASVDE算法在所有的測試函數上的標準差均為最優值。因此，在中、高維時，ASVDE算法的優化性能也顯著優于對比算法。根據Wilcoxon rank-sum test和勝率指標來看，除函數f5外，ASVDE的勝率均達到了100%。

綜上所述，ASVDE算法不僅對低維函數有著良好的優化性能，隨著維數的升高，ASVDE在中、高維函數上仍然占據絕對的優勢。相較于對比算法，ASVDE具有較強的穩定性，對各維數的函數均具有較好的全局尋優能力。為了更直觀地凸顯ASVDE算法的性能，現對4種算法在各維度取得的最佳平均值進行排序，結果如表5-表7所示。

表5 最佳平均值排序(D=20)

表6 最佳平均值排序(D=50)

表7 最佳平均值排序(D=100)

為直觀地顯現出ASVDE算法的搜索性能，現選取6種情況的優化收斂曲線，如圖4-圖6所示，即在低、中、高維度各選取2個測試函數。圖中，橫坐標為迭代次數，縱坐標為平均函數值，表示了測試函數的30次運算的均值隨迭代次數增加而變化的過程。

(a) f1

(b) f5圖4 測試函數的收斂曲線(D=20)

(a) f2

(b) f4圖5 測試函數的收斂曲線(D=50)

(a) f6

(b) f9圖6 測試函數的收斂曲線(D=100)

可以看出，ASVDE算法的所有曲線下降最快，能夠快速準確地找到全局最優解，而DE、RMDE和HSDE算法的收斂速度明顯低于ASVDE。在整個進化過程中，ASVDE算法在各維度都能避免陷入局部最優并快速收斂到全局最優解，具有更好的穩定性，收斂性能遠遠超過其他3種方法。因此可以認為，ASVDE算法能夠有效地增加種群多樣性，提高算法找到全局最優解的可能性，是一種有效的優化算法。

4.3 算子性能分析

為了對ASVDE算法中雙策略自適應二次變異算子(ASV)的作用進行分析，在此算法的框架上，另外選擇兩種經典的算子(DE/rand/1、DE/current-to-best/1)與其作對比。將3種算子在每個測試函數上運行得到的平均值和標準差分別進行排序，再將算子在每個函數上的名次相加然后除以函數的個數就可得到算子的平均排名，結果如表8所示。

表8 3種算子排序

平均排名的數值越低，證明算子的性能越好，3種算子的平均排名如圖7所示。

圖7 三種算子平均排名

由圖可知，相比其他兩種算子，無論是平均值還是標準差，ASV算子的平均排名最低，這說明改進算法中ASV算子的平均優化性能和穩定性最好。

5 電力系統經濟調度仿真

建立38機組火電機組經濟調度模型，進行30次獨立計算。將ASVDE算法的計算結果與文獻[22]的幾種算法結果進行對比，結果如表9所示，其中種群規模為40，最大迭代次數為1 500。ASVDE算法的最優解為(220.000 0,359.314 9,500.000 0,500.000 0,500.000 0,500.000 0,500.000 0,500.000 0,137.000 0,114.000 0,114.000 0,114.000 0,110.000 0,90.000 0,82.000 0,120.000 0,65.000 0,65.000 0,65.000 0,306.824 1,390.602 0,110.000 0,80.000 0,10.000 0,60.000 0,136.259 0,35.000 0,20.000 0,20.000 0,20.000 0,20.000 0,20.000 0,25.000 0,18.000 0,8.000 0,25.000 0,20.000 0,20.000 0)。

表9 不同方法優化38機組電力系統經濟調度問題的對比

由表9可知，在滿足約束的條件下，ASVDE算法得到的最優目標函數值為9 489 279.336 2，比其他四種算法得到的最優目標函數值都要小。由此可知，ASVDE算法可以優化出發電成本最小的值，有較優的尋優性能。

6 結 語

本文提出了一種自適應二次變異的改進差分進化算法。改進算法采用了多變異策略，加入動態權重因子，能夠有效地平衡算法全局搜索和局部搜索的能力。利用二次變異對種群結構進行更新，通過記錄適應值保持不更新的次數并在其達到設定值時自適應地進行二次變異，保證種群的多樣性。變異策略利用全局最優信息和柯西擾動，控制算法及時跳出局部最優，進一步提高了算法的全局尋優能力。選擇策略中加入的反向學習能夠增加算法解的多樣性，提高算法的收斂速度。將改進算法應用在測試函數和電力系統經濟調度問題中進行仿真測試，并與其他算法的測試結果進行對比，結果證明ASVDE有著更高的收斂精度。