多策略自適應變異的差分進化算法及其應用*

胡福年，董倩男

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

1 引言

差分進化DE(Differential Evolution)算法是與遺傳算法GA(Genetic Algorithm)[1]、粒子群算法PSO(Particle Swarm Optimization)[2,3]、蟻群算法ACO(Ant Colony Optimization)[4]等相似的一種啟發式優化算法，因其簡單易實現，可調參數少，具有強大的尋優能力，目前在許多領域的復雜優化問題中得到了應用[5 - 8]。但是，與其它智能算法相同的是，DE算法也存在提早收斂、收斂精度低、搜索停滯等問題。為了提高算法的優化性能，許多學者對此進行了改進，改進方法主要包括以下幾個方面：自適應調整控制參數(種群規模NP、縮放因子F和交叉概率因子CR)、設計新的變異算子、變異策略的改進以及混合算法的使用。文獻[9]提出了一種自適應DE算法SaDE(Self-adaptive Differential Evolution)，通過對之前的方法進行學習逐漸形成選擇策略，在算法進化的不同階段自適應地選擇合適的變異策略和控制參數。文獻[10]根據解搜索的狀態，提出一種自適應種群調整策略APTS(Adaptive Population Tuning Scheme)，能夠通過排序的方法去除種群中的不良個體，從而達到動態調整種群大小的目的。文獻[11]通過對前代個體尋優性能的判斷和學習，自適應地對變異策略和參數進行選擇，同時加入了具有學習功能的擾動閾值擴大搜索范圍。文獻[12]提出了一種混合算法，將粒子群優化(PSO)和貪婪隨機自適應搜索程序GRASP(Greedy Randomized Adaptive Search Procedure)相結合，增強了算法的搜索性能。以上方法均能在一定程度上提高算法的收斂精度，增強算法跳出局部最優的能力，但在解決一些問題時仍然存在收斂解精度不高、收斂速度慢的現象。

針對上述問題，本文提出一種多策略自適應變異的差分進化MsA-DE(Multi-strategy Adaptive mutation Differential Evolution)算法，根據進化程度隨機控制2種變異策略的權重，自適應地選擇不同的變異策略，實現算法在解空間的探索與開發能力的平衡。將本文提出的算法與4種常用的改進差分進化算法分別對單峰、多峰等類型的測試函數進行對比分析，結果驗證了本文算法的正確性，通過對高速鐵路牽引系統功率調節器RPC(Railway Power Conditioner)的容量優化進行仿真分析，驗證了該算法的有效性。

2 復雜函數優化問題描述

復雜函數優化問題在經濟、計算機科學、工程技術等領域十分常見，從數學的角度來說，對問題的優化就是求解函數極值的過程。采用運籌學的數學規劃理論對其進行分析，最小值優化問題可描述如下：

minf(x1,x2,…,xD)

(1)

y′z=[yz+δ-yz-δ]/(2δ),

(2)

差分進化算法利用了差分的思想，通過群體內個體之間的相互合作與競爭產生的群體智能來指導最優解的搜尋方向，通過不斷地進化，保留優良個體，淘汰劣質個體，引導搜索向最優解逼近。下面給出與DE算法優化過程相關的一些定義：

定義1(加權系數法) 為強調某一要素在整個要素體系中的重要程度而賦予該要素某一特征值的過程，特征值即為這一要素的加權系數。

定義2(優劣性) 對于任意2個個體xr1,xr2，若?j∈{1,2,…,D}，(xr1j≤xr2j)∧(?j,xr1j

3 改進差分進化算法

3.1 變異策略

針對DE算法在優化復雜問題時易過早陷入局部最優、收斂速度較慢等缺點，對變異策略進行改進。通過分析現有的典型變異算子的優點及不足，提出多策略自適應變異MsA(Multi-strategy Adaptive mutation)算子，同時將隨機法和中值法結合，對越界的變異個體進行處理。

3.1.1 經典變異策略

變異操作是DE算法的關鍵部分，對于算法的優化性能起著重要的作用。在算法進化初期，應當使算法在解空間進行充分的搜索以保證種群多樣性；而在算法進化后期，應當將重心從全局最優轉移到提升收斂速度上來。為了保證種群的多樣性，平衡算法的全局搜索和局部搜索能力，選取3種常用的變異操作結合，以適應算法在不同的搜索階段中的探索和開發能力的差異。在DE中常用的變異策略為DE/rand/1、DE/best/1、DE/current-to-rand/1、DE/current-to-best/1等。具體形式如式(3)～式(6)所示：

DE/rand/1：

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

(3)

DE/best/1：

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

(4)

DE/current-to-rand/1：

vi,G+1=xi,G+F·(xr1,G-xi,G)+

F·(xr2,G-xr3,G)

(5)

DE/current-to-best/1：

vi,G+1=xi,G+F·(xbest,G-xi,G)+

F·(xr1,G-xr2,G)

(6)

其中，xi,G表示第G代的xi,vi,G+1表示第G次迭代后變異產生的個體。F為縮放因子。

3.1.2 新變異策略

由于全局尋優和局部尋優是對立的，因而單一的變異算子很難同時滿足2種功能。本文借鑒前人的研究，提出MsA算子，引入動態權重因子ω，將選出的算子集合中不同的2種變異策略進行組合，形成2種新的算子，同時定義1個表示進化程度的值τ，能夠在不同的進化時期選擇不同的變異策略，表達式如式(7)所示：

(7)

其中，τ=G/Gmax，表示當前進化程度，Gmax為總進化代數，ω的產生方法如式(8)所示：

ω=ωmin+(ωmax-ωmin)·G/Gmax

(8)

MsA算子采用算術交叉方式，將當前個體、最優個體和隨機個體進行組合，全局最優個體為種群進化提供方向，隨機個體則防止種群陷入局部最優，增加種群多樣性。MsA算子變異具體過程如下所示：

(1)當τ<0.5時，算法進化處于前期，此時變異策略為式(7i)，當前個體與隨機個體交流，改善了種群多樣性，增強了全局搜索能力。

(2)當τ≥0.5時，算法進化處于中后期，此時變異策略為(7ii)，當前個體和最優個體與隨機個體進行算術交叉，產生變異個體，有利于提高收斂速度和解的精度。

考慮到變異后可能會有個體跳出事先設定的空間范圍，此時需要對個體的越界情況進行處理，當個體發生越界時，在對應的目標個體和對應邊界值之間隨機取值，同時考慮一定概率的邊界值。具體處理流程如下所示：

ifrand<0.5

else

else

ifrand<0.5

else

endif

3.2 擾動策略

在經歷過變異交叉等操作后，當前解正在向最優解靠近。但是，最優解可能是全局最優，也可能是局部最優。若是全局最優，在選擇操作中不會被過濾掉，若是局部最優，則會使種群陷入局部最優而提早收斂。為避免這種現象的發生，本文所提MsA-DE算法加入了2種擾動操作：小概率擾動和柯西擾動。

Figure 1 Comparison map of probability distribution圖1 概率分布對比圖

柯西分布是一個連續型分布函數，其重要特性之一就是期望和方差均不存在。柯西分布服從X～Cauchy(μ,λ)，μ和λ是局部參數,μ=0,λ=1時為標準柯西分布。標準正態分布服從X～N(0,1)，取μ=0,λ=1。標準柯西分布與標準正態分布的概率分布對比如圖1所示。

可以看出，2種圖形均似鐘型，相比于正態分布，柯西分布的曲線降落至0的速度慢很多，減小了取值為0的概率，擴大了尋優范圍。使用柯西分布產生的隨機數擾動最優個體的方法，可避免算法陷入局部最優。柯西隨機數分布服從Cauchyi～randci(μ,λ)，Cauchyi為個體i對應的柯西隨機數，randci為個體i對應的柯西分布函數局部參數，分別取μ=0,λ=0.01。

為進一步增強算法跳出局部最優的能力，加入小概率擾動[13]。為有效結合自適應變異策略和擾動策略，設置1個調和參數Mr，隨機選擇變異操作和擾動策略。Mr一般取大于0.9的值，流程如下所示：

ifrand

τ=G/Gmax;

ifτ<0.5

vij,G+1=xij,G+ωF·(xr1j,G-xr2j,G)+(1-ω)F·(xr3j,G-xr4j,G)

else

vij,G+1=ω[xbestj,G+F·(xr1j,G-xr2j,G)]+(1-ω)[xij,G+F·(xbestj,G-xij,G)]

else

endif

3.3 控制參數自適應

控制參數的改進主要是針對F、CR，它們的取值對于算法能否平衡全局尋優和局部尋優的能力有著至關重要的意義，通常取固定值，但是這樣難以適應算法進化的全過程。本文根據個體最優信息和進化程度對F、CR進行自適應調整，將實驗個體和父代個體進行比較，若個體進化成功，則參數繼承上一代的值；否則，參數將在0～1內重新產生。

3.3.1 自適應變異因子

對于F，在進化的前期應當盡可能地大，這樣可以增加搜索空間，快速向全局最優解靠攏，避免陷入局部最優；在進化后期，種群聚集在全局最優解附近，因而需要F值盡可能地小，以提高搜索精度，找到全局最優解。F的自適應調整如式(9)所示，初代種群的進化參數采用式(10)產生。

Fi,G+1=

(9)

(10)

其中，Fi,1表示第1代、第i個個體的縮放因子；Fi,G表示第G代、第i個個體的縮放因子；Fi,G+1表示第G+1代、第i個個體的縮放因子；Fmin、Fmax分別表示縮放因子的最小值和最大值。ui,G+1為實驗個體，是由第G+1代的變異個體vi,G+1與第G代父代個體xi,G生成的。當上一代個體保留下來時，說明上一代的縮放因子較好，此時仍采用上一代的F值，如式(9i)；否則，進一步判斷算法是否處于進化前期，若是，則F由式(9ii)產生，隨著迭代次數的增加F變大，在算法進化前期擴大尋優范圍；否則，使用式(9iii)重新生成，隨著迭代次數的增加F逐漸變小，在算法進化后期加快收斂到最優解。

3.3.2 自適應交叉概率

CR決定變異后的個體能夠進入選擇操作的數量。若CR的值較大，則子代從父代個體繼承的信息較少，種群的更新主要依賴于變異的過程，能夠增加種群多樣性，有利于全局搜索；若CR的值較小，則子代的搜索主要集中在父代周圍，縮小尋優范圍，但會提升收斂速度，有利于局部尋優。CR與F的調整方法基本一致，如式(11)和式(12)所示：

CRi,G+1=

(11)

CRi,1=CRmin+rand·(CRmax-CRmin)

(12)

3.4 交叉操作

交叉操作即通過一些方案將變異個體與種群父代個體進行混合，產生候選個體。傳統的DE算法交叉策略是由交叉率決定保留父代個體或變異個體。這里采用Liu等[14]提出的中心解方法，表達式如下：

(13)

(14)

xCenter,G為第G代的中心解，每次參與變異和交叉操作的有NP個向量粒子，但是在求解G+1代最優值時需要將上一代的中心解加入；xCenter j,G為第G代中心解的變量，且新個體取代了父代個體，和變異個體共同組成實驗個體uij,G+1；jr為[1,D]上的隨機整數。

3.5 選擇操作

選擇的主要目的是挑選更優的個體組成子代個體，通常采用“貪婪原則”選擇實驗個體和父代個體，本文采用傳統DE算法的選擇策略。對于最小化問題，具有小適應度函數值的個體更優，如式(15)所示：

(15)

其中，xi,G+1為經過選擇進入下一代的個體，ui,G+1為經過變異、交叉的實驗個體，xi,G為父代個體，f(x)為個體適應度值，由于DE算法采用的是“一對一”選擇，因此可以保證精英解不會丟失。

3.6 算法實現流程圖

算法實現流程圖如圖2所示。

Figure 2 Flowchart of MsA-DE algorithm圖2 MsA-DE算法流程圖

4 算法仿真測試

4.1 測試函數、性能指標與參數設置

為驗證MsA-DE算法的性能，選取14個測試函數[15-17]對其進行測試，函數包括單峰和多峰函數，均屬于最小優化問題。另外選取DE算法、MDE(Modified Differential Evolution)算法[18]、RMDE(Random Mutation Differential Evolution)算法[13]、HSDE(Hybrid mutation operator and Self-adapting Differential Evolution)算法[19]和本文算法進行比較，對算法優化測試函數的結果進行對比。測試函數的表達式、變量范圍和理論最優值如表1所示。

各算法的參數設置如表2所示，均與各自對應文獻中的一致。算法的種群規模NP=100，每種算法均獨立運行30次，迭代次數為1 500代，記錄下5種算法在20維,50維,100維中得到的平均值、標準差，即可對比出算法性能的優劣。

Table 1 14 test functions表1 14個測試函數

Table 2 Parameter settings表2 參數設置

為了更直觀地得出結論，采用以顯著性水平為0.05的Wilcoxon 秩和檢驗指標[20,21]和勝率進行進一步分析。Wilcoxon 秩和檢驗是由Mann，Whitney和Wilcoxon共同設計的一種檢驗，可以用來檢測2個獨立樣本之間的差異性。它和T檢驗均可用于測試2組獨立樣本的差異性，但是T檢驗要求數據必須符合正態分布且具有相同方差。因而當這2個條件無法確定時，通常采用Wilcox-on秩和檢驗。檢驗結果存在2種情況：差異顯著和差異不顯著。若是有顯著性差異無法判斷哪個算法性能更優，則需要用“勝率”作為進一步判斷算法性能優劣的方案。“勝率”，即將2種算法每次運行得出的最優值兩兩進行比較，若勝，加1分；若平，加0.5分；若敗，加0分。將每個算法得到的分數除以比較的次數(30×30=900次)，得到的值就是它們各自的勝率。仿真實驗使用Matlab軟件編程實現。

4.2 函數測試結果及對比

根據4.1節所述的參數設置及分析指標，測試函數的優化結果如表3～表5所示。表3中用“+”“-”和“=”分別表示比較算法性能優于、劣于和相近于MsA-DE算法；表4為MsA-DE算法與對比算法的勝率；表5用ARM和ARSTD分別表示算法在平均值和標準差上的平均排名，排名越低則算法性能越好。

Table 3 Experimental simulation results表3 實驗仿真結果

續表

表3和表4顯示了在20維，50維和100維搜索空間中f1～f14的仿真結果。不難看出，低維時，在函數f1,f3,f4,f8,f9,f13,f14上，只有MsA-DE算法能夠精準地找到理論最優值，在f5上MsA-DE與DE算法取得并列最優解，f2，f6，f7上MsA-DE雖然未能找到理論最優值，但是尋優結果非常接近理論最優解，因此MsA-DE算法具有較好的尋優性能。此外，MsA-DE算法的平均值和標準差排名最低，可知MsA-DE算法具有較好的穩定性。在中、高維上，除函數f2，f6和f7外，MsA-DE算法均找到了全局最優解，且MsA-DE算法在所有的測試函數上的平均值和標準差均為最優值，排名最低。由此可知，MsA-DE算法不僅對低維函數有著良好的優化性能，隨著維數的升高，MsA-DE算法對于中、高維函數仍然具有較大的優勢。

對算法優化性能的評估指標除了最優解的精度還有優化速度，本文采用平均運行時間來評價各個算法的優化速度，如表6所示，加粗字體表示該算法平均運行時間最少。

當2種算法的平均值和標準差相同時，平均運行時間少的算法更有效。

Table 4 Winning rate calculation results of MsA-DE algorithm and other algorithms表4 MsA-DE算法與其它算法勝率計算結果 %

Table 5 Average ranking and statistical results of the five algorithms under different indicators表5 不同指標下5種算法的平均排名及統計結果匯總

Table 6 Average running time comparison of five algorithms optimization test functions表6 5種算法優化測試函數的平均運行時間對比 s

由表6可以看出，對于大多數函數，MsA-DE算法的平均運行時間均最短，傳統DE算法用的時間最長，特別是在維度升高時，運行時間會大幅增加。例如函數f7，在20維，50維，100維時DE算法的平均運行時間分別為4.3 s,14.7 s和28.6 s，相比于20維，該算法在50維和100維搜索空間的運行時間大幅增加。再比如在20維的函數f5上，MsA-DE算法和DE算法的平均值和標準差相同，因為MsA-DE算法運行時間小于DE算法的，所以MsA-DE算法優化性能更好。

為使MsA-DE算法的效果更加直觀，現選取6個測試函數的優化收斂曲線圖。圖3和圖4為20維搜索空間中函數f5，f12的平均收斂曲線，圖5和圖6為50維搜索空間中函數f6，f10的平均收斂曲線，圖7和圖8為100維搜索空間中函數f2，f7的平均收斂曲線，橫軸表示迭代次數，縱軸表示平均函數值。

Figure 3 Average convergence curve of function f5 when D=20圖3 20維搜索空間中函數f5的平均收斂曲線

Figure 4 Average convergence curve of function f12 when D=20圖4 20維搜索空間中函數f12的平均收斂曲線

Figure 5 Average convergence curve of function f6 when D=50圖5 50維搜索空間中函數f6的平均收斂曲線

Figure 6 Average convergence curve of function f10 when D=50圖6 50維搜索空間中函數f10的平均收斂曲線

Figure 7 Average convergence curve of function f2 when D=100圖7 100維搜索空間中函數f2的平均收斂曲線

Figure 8 Average convergence curve of function f7 when D=100圖8 100維搜索空間中函數f7的平均收斂曲線

由仿真圖可知，與對比算法相比，MsA-DE算法的收斂速度最快，而對比算法的收斂速度明顯低于MsA-DE的，這說明MsA-DE算法跳出局部最優的能力最強，能夠快速準確地找到全局最優解。因此可以得出結論，MsA-DE算法的優化性能明顯強于對比算法的，能夠有效地增加種群多樣性，提高算法找到全局最優解的可能性。

5 RPC容量優化模型

RPC的容量優化問題，就是在滿足治理要求的前提下對RPC的補償容量進行合理配置，使補償成本最小化的問題。對其進行建模分析，可知屬于復雜函數優化問題，因而采用MsA-DE算法對其進行優化。在滿足各項約束條件的同時，算出RPC的補償容量最小值，在電能質量符合標準的同時提高治理系統的經濟性。主要包括目標函數的設定和約束條件的處理。

5.1 目標函數

以RPC補償容量為目標函數，根據補償策略，將RPC容量配置為：

minS=S1+S2

(16)

其中，S1=ΔSa+ΔSb為負序補償容量；S2=S′a+S′b為諧波補償容量。

5.1.1 負序補償

在V/v接線牽引變壓器的情況下，令α=ej120°，K為電壓器變比，可得正序、負序電流的計算公式為：

(17)

其中，IA,IB,IC為網側三相電流，Ia,Ib為供電臂電流。假設2個供電臂均處于牽引工況下，需要轉移的電流有功量為：

ΔIP=0.5λ(Ia-Ib)

(18)

需要轉移的有功功率為：

(19)

需要優化補償的無功功率分別為：

(20)

a、b供電臂所需的補償能量分別為：

(21)

其中，Pa、Pb分別為補償前a、b供電臂的負荷有功功率；Iap、Iaq、Ibp、Ibq分別為補償前a、b供電臂的負荷有功、無功電流；λ為有功轉移度，一般取值為[0,1]，λ值越大則有功轉移量越多，當λ=1時，RPC進行完全補償；φ為無功補償度，即優化補償前后電流間的夾角，取值為[0,π/6]。

5.1.2 諧波補償

根據優化補償的思想，將最嚴重的3,5,7次諧波補償至國標要求值，其它次數諧波均完全補償，設a、b供電臂上諧波電流總值分別為Ialh、Iblh，將3,5,7次諧波進行優化補償后的電流值分別為I′alh,I′blh，則2個供電臂諧波優化補償所需的諧波能量為：

(22)

其中，Ua,Ub分別為a,b供電臂電壓。

5.2 約束條件

(23)

綜上：

(24)

其中，K為變壓器變比，εu≤1.2%，SK為公共連接點的三相短路容量，UL為公共連接點的額定線電壓，且對于特定的牽引系統，SK、UL已知。

5.3 仿真分析

為了驗證本文算法的有效性，設計2種工況，利用Matlab建模進行仿真驗證。系統仿真參數如表7所示。接在電力機車變壓器二次側的電阻負載為0.7 Ω，不可控整流負載為1 Ω電阻串聯1個200 mH電感的阻感負載，用來模擬諧波源。

Table 7 Simulation parameter表7 仿真參數設置

工況1：設a供電臂負載功率為4 800 kW，b供電臂空載。由表8可知RPC補償前完全補償所需的補償能量較大，此時可以由前述方法算得所補償能量為7.253 MV·A，此時轉移的有功量較多，功率因數高，治理效果好但是經濟性較差；采用MsA-DE算法進行優化，可得出最優值λ=0.376,φ=11.74°,此時消耗的能量為4.142 MV·A，僅為完全補償時的57.1%，既滿足了電能質量治理條件，又提高了裝置的經濟性。

Table 8 Compensation result of working condition 1表8 工況1的補償結果

工況2：設a供電臂負載功率為4 800 kW，b供電臂負載功率為2 400 kW。表9為補償情況對比。此時的最優點為λ=0.26,φ=15.81°,消耗的能量為3.794 MV·A，僅為完全補償時的50.2%，且電壓不平衡度滿足εu<1.2%這一要求。

Table 9 Compensation result of working condition 2表9 工況2的補償結果

6 結束語

本文提出的MsA-DE算法引入了表示進化程度的閾值，將不同變異操作的優點進行有效結合，提高了算法的尋優能力；采用越界處理方法對變異個體進行改進，保證了種群的多樣性；參數的自適應調整可在進化后期快速收斂至全局最優解；擾動機制能夠避免算法過早陷入局部最優，彌補了傳統DE算法收斂精度低、易陷入局部最優等缺陷。通過對14個Benchmark測試函數和RPC容量優化問題進行實驗對比，結果表明，MsA-DE算法是一種有效的優化算法。