胡福年 董倩男 呂 璐

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

0 引 言

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

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

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

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

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

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

1 差分進化算法

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

(1)

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

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

(2)

(3)

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

表1 變異策略

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

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

(4)

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

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

(5)

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

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

2.1 變異策略

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

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為權(quán)重因子，wmin=0，wmax=1；Gmax為總進化代數(shù)。

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

結(jié)合RMDE[18]中擾動策略的思想，設(shè)置一個調(diào)和參數(shù)Mr，隨機選擇現(xiàn)有的變異操作和擾動策略，稱為小概率擾動，進一步增強算法跳出局部最優(yōu)的能力，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 自適應二次變異

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

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

圖1 概率分布對比圖

圖2 柯西隨機數(shù)

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

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 選擇策略

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

(8)

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

(9)

2.4 控制參數(shù)

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

本文考慮將產(chǎn)生優(yōu)秀個體的參數(shù)值保留，將產(chǎn)生淘汰個體的參數(shù)值重新設(shè)定，根據(jù)個體適應值來決定是否將參數(shù)值保留至下一代，具體表達式如下：

(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 電力系統(tǒng)經(jīng)濟調(diào)度模型

電力系統(tǒng)經(jīng)濟調(diào)度[19]問題是指在滿足系統(tǒng)的約束條件下對機組的發(fā)電功率進行合理分配，降低發(fā)電成本，從而達到經(jīng)濟性最高的目標。主要內(nèi)容包括目標函數(shù)的設(shè)定和約束條件的處理。

3.1 目標函數(shù)

以機組發(fā)電成本為目標函數(shù)，在T時間段內(nèi)，常規(guī)發(fā)電機組的發(fā)電成本主要考慮發(fā)電機組燃料成本而不考慮閥點效應的情況下，機組燃料成本可表示為：

(14)

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

3.2 約束處理

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

FP=FC+M·p(x)

(15)

(1) 功率平衡約束。

(16)

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

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

(17)

4 仿真實驗

4.1 函數(shù)與參數(shù)設(shè)置

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

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

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

(3) HSDE算法中，縮放因子Fmax=0.9，F(xiàn)min=0.1，交叉概率CR=rand。

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

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

表2 測試函數(shù)

4.2 測試函數(shù)的實驗結(jié)果

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

表3 實驗結(jié)果

續(xù)表3

表4 秩和檢驗結(jié)果

續(xù)表4

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

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

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

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

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

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

(a) f1

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

(a) f2

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

(a) f6

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

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

4.3 算子性能分析

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

表8 3種算子排序

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

圖7 三種算子平均排名

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

5 電力系統(tǒng)經(jīng)濟調(diào)度仿真

建立38機組火電機組經(jīng)濟調(diào)度模型，進行30次獨立計算。將ASVDE算法的計算結(jié)果與文獻[22]的幾種算法結(jié)果進行對比，結(jié)果如表9所示，其中種群規(guī)模為40，最大迭代次數(shù)為1 500。ASVDE算法的最優(yōu)解為(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 不同方法優(yōu)化38機組電力系統(tǒng)經(jīng)濟調(diào)度問題的對比

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

6 結(jié) 語

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