胡福年,董倩男
(江蘇師范大學電氣工程及自動化學院, 江蘇 徐州 221000)
差分進化DE(Differential Evolution)算法是與遺傳算法GA(Genetic Algorithm)[1]、粒子群算法PSO(Particle Swarm Optimization)[2,3]、蟻群算法ACO(Ant Colony Optimization)[4]等相似的一種啟發(fā)式優(yōu)化算法,因其簡單易實現(xiàn),可調參數(shù)少,具有強大的尋優(yōu)能力,目前在許多領域的復雜優(yōu)化問題中得到了應用[5 - 8]。但是,與其它智能算法相同的是,DE算法也存在提早收斂、收斂精度低、搜索停滯等問題。為了提高算法的優(yōu)化性能,許多學者對此進行了改進,改進方法主要包括以下幾個方面:自適應調整控制參數(shù)(種群規(guī)模NP、縮放因子F和交叉概率因子CR)、設計新的變異算子、變異策略的改進以及混合算法的使用。文獻[9]提出了一種自適應DE算法SaDE(Self-adaptive Differential Evolution),通過對之前的方法進行學習逐漸形成選擇策略,在算法進化的不同階段自適應地選擇合適的變異策略和控制參數(shù)。文獻[10]根據(jù)解搜索的狀態(tài),提出一種自適應種群調整策略APTS(Adaptive Population Tuning Scheme),能夠通過排序的方法去除種群中的不良個體,從而達到動態(tài)調整種群大小的目的。文獻[11]通過對前代個體尋優(yōu)性能的判斷和學習,自適應地對變異策略和參數(shù)進行選擇,同時加入了具有學習功能的擾動閾值擴大搜索范圍。文獻[12]提出了一種混合算法,將粒子群優(yōu)化(PSO)和貪婪隨機自適應搜索程序GRASP(Greedy Randomized Adaptive Search Procedure)相結合,增強了算法的搜索性能。以上方法均能在一定程度上提高算法的收斂精度,增強算法跳出局部最優(yōu)的能力,但在解決一些問題時仍然存在收斂解精度不高、收斂速度慢的現(xiàn)象。
針對上述問題,本文提出一種多策略自適應變異的差分進化MsA-DE(Multi-strategy Adaptive mutation Differential Evolution)算法,根據(jù)進化程度隨機控制2種變異策略的權重,自適應地選擇不同的變異策略,實現(xiàn)算法在解空間的探索與開發(fā)能力的平衡。將本文提出的算法與4種常用的改進差分進化算法分別對單峰、多峰等類型的測試函數(shù)進行對比分析,結果驗證了本文算法的正確性,通過對高速鐵路牽引系統(tǒng)功率調節(jié)器RPC(Railway Power Conditioner)的容量優(yōu)化進行仿真分析,驗證了該算法的有效性。
復雜函數(shù)優(yōu)化問題在經(jīng)濟、計算機科學、工程技術等領域十分常見,從數(shù)學的角度來說,對問題的優(yōu)化就是求解函數(shù)極值的過程。采用運籌學的數(shù)學規(guī)劃理論對其進行分析,最小值優(yōu)化問題可描述如下:
minf(x1,x2,…,xD)
(1)
y′z=[yz+δ-yz-δ]/(2δ),
(2)
差分進化算法利用了差分的思想,通過群體內(nèi)個體之間的相互合作與競爭產(chǎn)生的群體智能來指導最優(yōu)解的搜尋方向,通過不斷地進化,保留優(yōu)良個體,淘汰劣質個體,引導搜索向最優(yōu)解逼近。下面給出與DE算法優(yōu)化過程相關的一些定義:
定義1(加權系數(shù)法) 為強調某一要素在整個要素體系中的重要程度而賦予該要素某一特征值的過程,特征值即為這一要素的加權系數(shù)。
定義2(優(yōu)劣性) 對于任意2個個體xr1,xr2,若?j∈{1,2,…,D},(xr1j≤xr2j)∧(?j,xr1j 針對DE算法在優(yōu)化復雜問題時易過早陷入局部最優(yōu)、收斂速度較慢等缺點,對變異策略進行改進。通過分析現(xiàn)有的典型變異算子的優(yōu)點及不足,提出多策略自適應變異MsA(Multi-strategy Adaptive mutation)算子,同時將隨機法和中值法結合,對越界的變異個體進行處理。 3.1.1 經(jīng)典變異策略 變異操作是DE算法的關鍵部分,對于算法的優(yōu)化性能起著重要的作用。在算法進化初期,應當使算法在解空間進行充分的搜索以保證種群多樣性;而在算法進化后期,應當將重心從全局最優(yōu)轉移到提升收斂速度上來。為了保證種群的多樣性,平衡算法的全局搜索和局部搜索能力,選取3種常用的變異操作結合,以適應算法在不同的搜索階段中的探索和開發(fā)能力的差異。在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次迭代后變異產(chǎn)生的個體。F為縮放因子。 3.1.2 新變異策略 由于全局尋優(yōu)和局部尋優(yōu)是對立的,因而單一的變異算子很難同時滿足2種功能。本文借鑒前人的研究,提出MsA算子,引入動態(tài)權重因子ω,將選出的算子集合中不同的2種變異策略進行組合,形成2種新的算子,同時定義1個表示進化程度的值τ,能夠在不同的進化時期選擇不同的變異策略,表達式如式(7)所示: (7) 其中,τ=G/Gmax,表示當前進化程度,Gmax為總進化代數(shù),ω的產(chǎn)生方法如式(8)所示: ω=ωmin+(ωmax-ωmin)·G/Gmax (8) MsA算子采用算術交叉方式,將當前個體、最優(yōu)個體和隨機個體進行組合,全局最優(yōu)個體為種群進化提供方向,隨機個體則防止種群陷入局部最優(yōu),增加種群多樣性。MsA算子變異具體過程如下所示: (1)當τ<0.5時,算法進化處于前期,此時變異策略為式(7i),當前個體與隨機個體交流,改善了種群多樣性,增強了全局搜索能力。 (2)當τ≥0.5時,算法進化處于中后期,此時變異策略為(7ii),當前個體和最優(yōu)個體與隨機個體進行算術交叉,產(chǎn)生變異個體,有利于提高收斂速度和解的精度。 考慮到變異后可能會有個體跳出事先設定的空間范圍,此時需要對個體的越界情況進行處理,當個體發(fā)生越界時,在對應的目標個體和對應邊界值之間隨機取值,同時考慮一定概率的邊界值。具體處理流程如下所示: ifrand<0.5 else else ifrand<0.5 else endif 在經(jīng)歷過變異交叉等操作后,當前解正在向最優(yōu)解靠近。但是,最優(yōu)解可能是全局最優(yōu),也可能是局部最優(yōu)。若是全局最優(yōu),在選擇操作中不會被過濾掉,若是局部最優(yōu),則會使種群陷入局部最優(yōu)而提早收斂。為避免這種現(xiàn)象的發(fā)生,本文所提MsA-DE算法加入了2種擾動操作:小概率擾動和柯西擾動。 Figure 1 Comparison map of probability distribution圖1 概率分布對比圖 柯西分布是一個連續(xù)型分布函數(shù),其重要特性之一就是期望和方差均不存在??挛鞣植挤腦~Cauchy(μ,λ),μ和λ是局部參數(shù),μ=0,λ=1時為標準柯西分布。標準正態(tài)分布服從X~N(0,1),取μ=0,λ=1。標準柯西分布與標準正態(tài)分布的概率分布對比如圖1所示。 可以看出,2種圖形均似鐘型,相比于正態(tài)分布,柯西分布的曲線降落至0的速度慢很多,減小了取值為0的概率,擴大了尋優(yōu)范圍。使用柯西分布產(chǎn)生的隨機數(shù)擾動最優(yōu)個體的方法,可避免算法陷入局部最優(yōu)??挛麟S機數(shù)分布服從Cauchyi~randci(μ,λ),Cauchyi為個體i對應的柯西隨機數(shù),randci為個體i對應的柯西分布函數(shù)局部參數(shù),分別取μ=0,λ=0.01。 為進一步增強算法跳出局部最優(yōu)的能力,加入小概率擾動[13]。為有效結合自適應變異策略和擾動策略,設置1個調和參數(shù)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 控制參數(shù)的改進主要是針對F、CR,它們的取值對于算法能否平衡全局尋優(yōu)和局部尋優(yōu)的能力有著至關重要的意義,通常取固定值,但是這樣難以適應算法進化的全過程。本文根據(jù)個體最優(yōu)信息和進化程度對F、CR進行自適應調整,將實驗個體和父代個體進行比較,若個體進化成功,則參數(shù)繼承上一代的值;否則,參數(shù)將在0~1內(nèi)重新產(chǎn)生。 3.3.1 自適應變異因子 對于F,在進化的前期應當盡可能地大,這樣可以增加搜索空間,快速向全局最優(yōu)解靠攏,避免陷入局部最優(yōu);在進化后期,種群聚集在全局最優(yōu)解附近,因而需要F值盡可能地小,以提高搜索精度,找到全局最優(yōu)解。F的自適應調整如式(9)所示,初代種群的進化參數(shù)采用式(10)產(chǎn)生。 Fi,G+1= (9) (10) 其中,F(xiàn)i,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)產(chǎn)生,隨著迭代次數(shù)的增加F變大,在算法進化前期擴大尋優(yōu)范圍;否則,使用式(9iii)重新生成,隨著迭代次數(shù)的增加F逐漸變小,在算法進化后期加快收斂到最優(yōu)解。 3.3.2 自適應交叉概率 CR決定變異后的個體能夠進入選擇操作的數(shù)量。若CR的值較大,則子代從父代個體繼承的信息較少,種群的更新主要依賴于變異的過程,能夠增加種群多樣性,有利于全局搜索;若CR的值較小,則子代的搜索主要集中在父代周圍,縮小尋優(yōu)范圍,但會提升收斂速度,有利于局部尋優(yōu)。CR與F的調整方法基本一致,如式(11)和式(12)所示: CRi,G+1= (11) CRi,1=CRmin+rand·(CRmax-CRmin) (12) 交叉操作即通過一些方案將變異個體與種群父代個體進行混合,產(chǎn)生候選個體。傳統(tǒng)的DE算法交叉策略是由交叉率決定保留父代個體或變異個體。這里采用Liu等[14]提出的中心解方法,表達式如下: (13) (14) xCenter,G為第G代的中心解,每次參與變異和交叉操作的有NP個向量粒子,但是在求解G+1代最優(yōu)值時需要將上一代的中心解加入;xCenter j,G為第G代中心解的變量,且新個體取代了父代個體,和變異個體共同組成實驗個體uij,G+1;jr為[1,D]上的隨機整數(shù)。 選擇的主要目的是挑選更優(yōu)的個體組成子代個體,通常采用“貪婪原則”選擇實驗個體和父代個體,本文采用傳統(tǒng)DE算法的選擇策略。對于最小化問題,具有小適應度函數(shù)值的個體更優(yōu),如式(15)所示: (15) 其中,xi,G+1為經(jīng)過選擇進入下一代的個體,ui,G+1為經(jīng)過變異、交叉的實驗個體,xi,G為父代個體,f(x)為個體適應度值,由于DE算法采用的是“一對一”選擇,因此可以保證精英解不會丟失。 算法實現(xiàn)流程圖如圖2所示。 Figure 2 Flowchart of MsA-DE algorithm圖2 MsA-DE算法流程圖 為驗證MsA-DE算法的性能,選取14個測試函數(shù)[15-17]對其進行測試,函數(shù)包括單峰和多峰函數(shù),均屬于最小優(yōu)化問題。另外選取DE算法、MDE(Modified Differential Evolution)算法[18]、RMDE(Random Mutation Differential Evolution)算法[13]、HSDE(Hybrid mutation operator and Self-adapting Differential Evolution)算法[19]和本文算法進行比較,對算法優(yōu)化測試函數(shù)的結果進行對比。測試函數(shù)的表達式、變量范圍和理論最優(yōu)值如表1所示。 各算法的參數(shù)設置如表2所示,均與各自對應文獻中的一致。算法的種群規(guī)模NP=100,每種算法均獨立運行30次,迭代次數(shù)為1 500代,記錄下5種算法在20維,50維,100維中得到的平均值、標準差,即可對比出算法性能的優(yōu)劣。 Table 1 14 test functions表1 14個測試函數(shù) Table 2 Parameter settings表2 參數(shù)設置 為了更直觀地得出結論,采用以顯著性水平為0.05的Wilcoxon 秩和檢驗指標[20,21]和勝率進行進一步分析。Wilcoxon 秩和檢驗是由Mann,Whitney和Wilcoxon共同設計的一種檢驗,可以用來檢測2個獨立樣本之間的差異性。它和T檢驗均可用于測試2組獨立樣本的差異性,但是T檢驗要求數(shù)據(jù)必須符合正態(tài)分布且具有相同方差。因而當這2個條件無法確定時,通常采用Wilcox-on秩和檢驗。檢驗結果存在2種情況:差異顯著和差異不顯著。若是有顯著性差異無法判斷哪個算法性能更優(yōu),則需要用“勝率”作為進一步判斷算法性能優(yōu)劣的方案?!皠俾省?,即將2種算法每次運行得出的最優(yōu)值兩兩進行比較,若勝,加1分;若平,加0.5分;若敗,加0分。將每個算法得到的分數(shù)除以比較的次數(shù)(30×30=900次),得到的值就是它們各自的勝率。仿真實驗使用Matlab軟件編程實現(xiàn)。 根據(jù)4.1節(jié)所述的參數(shù)設置及分析指標,測試函數(shù)的優(yōu)化結果如表3~表5所示。表3中用“+”“-”和“=”分別表示比較算法性能優(yōu)于、劣于和相近于MsA-DE算法;表4為MsA-DE算法與對比算法的勝率;表5用ARM和ARSTD分別表示算法在平均值和標準差上的平均排名,排名越低則算法性能越好。 Table 3 Experimental simulation results表3 實驗仿真結果 續(xù)表 表3和表4顯示了在20維,50維和100維搜索空間中f1~f14的仿真結果。不難看出,低維時,在函數(shù)f1,f3,f4,f8,f9,f13,f14上,只有MsA-DE算法能夠精準地找到理論最優(yōu)值,在f5上MsA-DE與DE算法取得并列最優(yōu)解,f2,f6,f7上MsA-DE雖然未能找到理論最優(yōu)值,但是尋優(yōu)結果非常接近理論最優(yōu)解,因此MsA-DE算法具有較好的尋優(yōu)性能。此外,MsA-DE算法的平均值和標準差排名最低,可知MsA-DE算法具有較好的穩(wěn)定性。在中、高維上,除函數(shù)f2,f6和f7外,MsA-DE算法均找到了全局最優(yōu)解,且MsA-DE算法在所有的測試函數(shù)上的平均值和標準差均為最優(yōu)值,排名最低。由此可知,MsA-DE算法不僅對低維函數(shù)有著良好的優(yōu)化性能,隨著維數(shù)的升高,MsA-DE算法對于中、高維函數(shù)仍然具有較大的優(yōu)勢。 對算法優(yōu)化性能的評估指標除了最優(yōu)解的精度還有優(yōu)化速度,本文采用平均運行時間來評價各個算法的優(yōu)化速度,如表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種算法的平均排名及統(tǒng)計結果匯總 Table 6 Average running time comparison of five algorithms optimization test functions表6 5種算法優(yōu)化測試函數(shù)的平均運行時間對比 s 由表6可以看出,對于大多數(shù)函數(shù),MsA-DE算法的平均運行時間均最短,傳統(tǒng)DE算法用的時間最長,特別是在維度升高時,運行時間會大幅增加。例如函數(shù)f7,在20維,50維,100維時DE算法的平均運行時間分別為4.3 s,14.7 s和28.6 s,相比于20維,該算法在50維和100維搜索空間的運行時間大幅增加。再比如在20維的函數(shù)f5上,MsA-DE算法和DE算法的平均值和標準差相同,因為MsA-DE算法運行時間小于DE算法的,所以MsA-DE算法優(yōu)化性能更好。 為使MsA-DE算法的效果更加直觀,現(xiàn)選取6個測試函數(shù)的優(yōu)化收斂曲線圖。圖3和圖4為20維搜索空間中函數(shù)f5,f12的平均收斂曲線,圖5和圖6為50維搜索空間中函數(shù)f6,f10的平均收斂曲線,圖7和圖8為100維搜索空間中函數(shù)f2,f7的平均收斂曲線,橫軸表示迭代次數(shù),縱軸表示平均函數(shù)值。 Figure 3 Average convergence curve of function f5 when D=20圖3 20維搜索空間中函數(shù)f5的平均收斂曲線 Figure 4 Average convergence curve of function f12 when D=20圖4 20維搜索空間中函數(shù)f12的平均收斂曲線 Figure 5 Average convergence curve of function f6 when D=50圖5 50維搜索空間中函數(shù)f6的平均收斂曲線 Figure 6 Average convergence curve of function f10 when D=50圖6 50維搜索空間中函數(shù)f10的平均收斂曲線 Figure 7 Average convergence curve of function f2 when D=100圖7 100維搜索空間中函數(shù)f2的平均收斂曲線 Figure 8 Average convergence curve of function f7 when D=100圖8 100維搜索空間中函數(shù)f7的平均收斂曲線 由仿真圖可知,與對比算法相比,MsA-DE算法的收斂速度最快,而對比算法的收斂速度明顯低于MsA-DE的,這說明MsA-DE算法跳出局部最優(yōu)的能力最強,能夠快速準確地找到全局最優(yōu)解。因此可以得出結論,MsA-DE算法的優(yōu)化性能明顯強于對比算法的,能夠有效地增加種群多樣性,提高算法找到全局最優(yōu)解的可能性。 RPC的容量優(yōu)化問題,就是在滿足治理要求的前提下對RPC的補償容量進行合理配置,使補償成本最小化的問題。對其進行建模分析,可知屬于復雜函數(shù)優(yōu)化問題,因而采用MsA-DE算法對其進行優(yōu)化。在滿足各項約束條件的同時,算出RPC的補償容量最小值,在電能質量符合標準的同時提高治理系統(tǒng)的經(jīng)濟性。主要包括目標函數(shù)的設定和約束條件的處理。 以RPC補償容量為目標函數(shù),根據(jù)補償策略,將RPC容量配置為: minS=S1+S2 (16) 其中,S1=ΔSa+ΔSb為負序補償容量;S2=S′a+S′b為諧波補償容量。 5.1.1 負序補償 在V/v接線牽引變壓器的情況下,令α=ej120°,K為電壓器變比,可得正序、負序電流的計算公式為: (17) 其中,IA,IB,IC為網(wǎng)側三相電流,Ia,Ib為供電臂電流。假設2個供電臂均處于牽引工況下,需要轉移的電流有功量為: ΔIP=0.5λ(Ia-Ib) (18) 需要轉移的有功功率為: (19) 需要優(yōu)化補償?shù)臒o功功率分別為: (20) a、b供電臂所需的補償能量分別為: (21) 其中,Pa、Pb分別為補償前a、b供電臂的負荷有功功率;Iap、Iaq、Ibp、Ibq分別為補償前a、b供電臂的負荷有功、無功電流;λ為有功轉移度,一般取值為[0,1],λ值越大則有功轉移量越多,當λ=1時,RPC進行完全補償;φ為無功補償度,即優(yōu)化補償前后電流間的夾角,取值為[0,π/6]。 5.1.2 諧波補償 根據(jù)優(yōu)化補償?shù)乃枷?,將最嚴重?,5,7次諧波補償至國標要求值,其它次數(shù)諧波均完全補償,設a、b供電臂上諧波電流總值分別為Ialh、Iblh,將3,5,7次諧波進行優(yōu)化補償后的電流值分別為I′alh,I′blh,則2個供電臂諧波優(yōu)化補償所需的諧波能量為: (22) 其中,Ua,Ub分別為a,b供電臂電壓。 (23) 綜上: (24) 其中,K為變壓器變比,εu≤1.2%,SK為公共連接點的三相短路容量,UL為公共連接點的額定線電壓,且對于特定的牽引系統(tǒng),SK、UL已知。 為了驗證本文算法的有效性,設計2種工況,利用Matlab建模進行仿真驗證。系統(tǒng)仿真參數(shù)如表7所示。接在電力機車變壓器二次側的電阻負載為0.7 Ω,不可控整流負載為1 Ω電阻串聯(lián)1個200 mH電感的阻感負載,用來模擬諧波源。 Table 7 Simulation parameter表7 仿真參數(shù)設置 工況1:設a供電臂負載功率為4 800 kW,b供電臂空載。由表8可知RPC補償前完全補償所需的補償能量較大,此時可以由前述方法算得所補償能量為7.253 MV·A,此時轉移的有功量較多,功率因數(shù)高,治理效果好但是經(jīng)濟性較差;采用MsA-DE算法進行優(yōu)化,可得出最優(yōu)值λ=0.376,φ=11.74°,此時消耗的能量為4.142 MV·A,僅為完全補償時的57.1%,既滿足了電能質量治理條件,又提高了裝置的經(jīng)濟性。 Table 8 Compensation result of working condition 1表8 工況1的補償結果 工況2:設a供電臂負載功率為4 800 kW,b供電臂負載功率為2 400 kW。表9為補償情況對比。此時的最優(yōu)點為λ=0.26,φ=15.81°,消耗的能量為3.794 MV·A,僅為完全補償時的50.2%,且電壓不平衡度滿足εu<1.2%這一要求。 Table 9 Compensation result of working condition 2表9 工況2的補償結果 本文提出的MsA-DE算法引入了表示進化程度的閾值,將不同變異操作的優(yōu)點進行有效結合,提高了算法的尋優(yōu)能力;采用越界處理方法對變異個體進行改進,保證了種群的多樣性;參數(shù)的自適應調整可在進化后期快速收斂至全局最優(yōu)解;擾動機制能夠避免算法過早陷入局部最優(yōu),彌補了傳統(tǒng)DE算法收斂精度低、易陷入局部最優(yōu)等缺陷。通過對14個Benchmark測試函數(shù)和RPC容量優(yōu)化問題進行實驗對比,結果表明,MsA-DE算法是一種有效的優(yōu)化算法。3 改進差分進化算法
3.1 變異策略
3.2 擾動策略
3.3 控制參數(shù)自適應
3.4 交叉操作
3.5 選擇操作
3.6 算法實現(xiàn)流程圖
4 算法仿真測試
4.1 測試函數(shù)、性能指標與參數(shù)設置
4.2 函數(shù)測試結果及對比
5 RPC容量優(yōu)化模型
5.1 目標函數(shù)
5.2 約束條件
5.3 仿真分析
6 結束語