差分進化算法的改進研究

蔣兵兵

（湖南鐵路科技職業技術學院 湖南 株洲 412007）

0 引言

作為基于群體差異進行隨機搜索的算法，差分進化算法的應用無需進行編碼和解碼，在受控參數較少的情況下獲得了較強魯棒性，在全局尋優方面的性能良好，目前在電力調度、多目標路徑規劃等多個領域應用廣泛。但在實際應用過程中，差分進化算法同樣存在過早收斂等問題，需要通過算法改進獲得更高收斂精度?，F階段，改進差分進化算法的方法較多，還應掌握不同方法優勢，以便結合實際需求合理進行算法改進和應用。

1 差分進化算法概述

1.1 算法原理

根據算法原理可知，對個體進行初始化操作，從種群中隨機選擇互異個體進行差分、縮放，與第3 個隨機個體生成變異個體。而利用父代個體和變異個體進行交叉操作，可以獲得試驗個體，完成適應度值比較，選擇較優個體繼續迭代，直至達到終止準則[1]。從本質上來講，就是對生物體的“優勝略汰”進化過程進行模擬，通過自適應自組織解決問題。將種群當成是操作對象實施并行優化，在迭代次數達到最大或找到最優解后可以停止尋優。

1.2 算法流程

標準的差分進化算法可以劃分為種群初始化和進化迭代兩個階段，前者需在可行域內通過均勻分布等概率獲得初始空間解向量，后者包含變異、交叉、選擇等操作，在達到進化條件時將進行尋優，直至算法結束，見圖1。該種算法具有記憶功能，經典變異操作包含DE/rand/1、DE/best/1 等。從算法步驟來看，假設種群中含NP 個個體，每個代表一個問題解，各解為D 維向量，個體表達為Xi，0={xi，1，0，xi，2，0，L，xi，D，0}，滿足i=1，2，L，NP。

初始種群則為xi，j，0=xj，low+rand（0，1）·（xj，highxj，low），其中rand（0，1）服從均勻分布，在0 到1 之間隨機取值，xj，high 和xj，low 分別指的是變量分量的上下限。在變異操作中，各目標向量將生成對應變異向量，引入新算子參與優解變異操作，能夠適應種群動態變化過程。采用不同變異策略，將得到不同的變異公式。如采用DE/rand/1，能夠得到：

式中，ui，jG+1、vi，jG+1和xi，jG+1分別指的是第i個試驗向量、變異向量和目標向量的G+1 代j分量，j=1，L，D。CR 為交叉概率，Jrand 為根據維數j生成的隨機數，能夠改善算法多樣性，確保至少一維分量來自變異個體，達到進化目的。利用C R 確定試驗向量中的變異向量個數，取值在0 ～1 范圍內。將變異向量和目標向量交叉獲得的試驗向量UiG，需限制產生個體向量范圍，確保在規定上下限范圍內。利用選擇算子完成目標和試驗向量選擇，能夠保存適應度好的個體，作為解向量繼續迭代。

2 差分進化算法的改進方法

2.1 控制參數調整

該算法需要對多峰復雜函數進行求解，容易因參數設置不當導致種群多樣性下降，因早熟而無法找到全局最優解。從算法控制參數來看，除了涉及縮放因子F，還包含種群規模NP 和交叉概率CR。在F 數值過大時，能夠完成潛力解挖掘，反之則能為全局最優解的查找提供便利。而N 數值小能夠加快算法收斂，出現早熟或停滯情況，反之可以提高種群多樣性，但容易因計算量過大出現收斂慢的問題。而CR 過大，將引發多個個體變化，提高種群多樣性，有助于尋解，數值過小則能保留更多個體信息。從早期研究來看，傾向于在較小數值范圍內取值，如使F 在（0.5，1）范圍內取值，使CR 在（0.9，1）范圍內取值等，缺少算法執行過程中的信息反饋，導致相同參數在解決不同問題時取得的效果不同[2]。采取動態調整策略，在各代種群中根據個體目標函數完成參數自適應調節，能夠取得更好的算法改進效果。如采用FADE 算法，通過模糊邏輯控制器和知識系統完成不一致參數實時調整，能夠完成各代F 和CR 值調節。對前期進化優質解找尋經驗進行借鑒，可以采用SaDE 算法進行F 和CR 值調整，設定為統一服從高斯分布，F 的服從均值為0.5，標準差為0.3，CR 服從均值為0.5，標準差為0.1，每25 代需要完成一次成功CR 值的更新。在NP 數值調整方面，可以采用DESAP 算法，隨機生成（10×n）種群后，n 為參數變量個數，能夠得到初始化的NPi為round（10+randn(0，1)），將縮放因子設定為1 后進化至預先指定種群大小，能夠確定下代新種群大小。

2.2 操作算子改進

在算法操作中，包含變異、交叉和選擇算子。選擇算子僅根據適應度值確定，相對簡單，因此算子改進研究主要針對變異算法和交叉算子。在變異算子改進方面，目前提出的策略包含DE/current-to-rand/1、三角變異策略、DE/rand/1/either-or 等多種。采用不同算子，能夠通過取長補短適應種群進化。如在JADE 算法中，可以采用DE/current-to-pbest/1 策略，得到vi，G=xi，G+Fi（xbest，G-xi，G）+Fi（xr1，G-xr2，G），可知指的是種群目前尋到的最優個體，Fi則為個體j 的縮放因子，除了來自外部較差個體存檔A和種群P 的并集，其余個體均來自種群P。此外，也可以將個別解協方差矩陣特征向量當成是算子進行交叉操作，具有旋轉不變性特征。運用該算子進行算法改進，能夠使供體個體得到修改，然后投影至替代坐標系特征向量上，適用于變化小的交叉策略[3]。

2.3 種群結構優化

通過優化種群結構方式進行算法改進，能夠對算法收斂性能產生影響。如使用環形網絡拓撲實施并行運算，能夠提高算法收斂速度。而采用分布式算法或自適應算法，能夠優化算法性能。如采用平均熵初始化策略完成種群拆分，利用不同變異策略加強種群信息交流，能夠完成種群差分運算。利用自適應值大小完成多種群分類，實施不同進化策略可以完成全局優化。采用反向的差分進化算法，需要進行反向搜索，能夠使種群的多樣性得到改善，達到跳出局部最優的目的。此外，利用島嶼模型進行并行分布運算，將種群劃分為多個獨立亞種群，然后完成不同控制參數分配，可以得到固定世代間隔。使不同種群相互遷移，能夠確保亞種群始終體現良好多樣性，有助于算法改良。

2.4 混合算法分析

各種智能算法是基于不同現象和行為產生的，適用于不同場景?？紤]到采用單一算法存在較大局限性，可以通過將不同算法結合實現原有算法改進。如在解決電力系統參數配置問題時，將DE 算法和粒子群算法融合，能夠加強種群開發和探索。利用標準測試函數進行算法驗證，能夠保證算法穩定性。MDE-WOA 算法同樣為混合算法，可以在差分進化運算中嵌入壽命機制，通過增強算法搜索能力解決局部最優問題，形成的算法不僅具有較強魯棒性，也能獲得較高準確性。在解決車輛路徑規劃問題時，將DE算法與蜂群算法結合，在迭代中引入進化算子，改善蜂群進化速度慢的問題，能夠使形成的算法獲得較強魯棒性，并能實現全局收斂，保證算法的有效性[4]。針對組合優化問題，可以將DE 算法和量子算法結合在一起，增強算法魯棒性，提高數據運算效率?，F階段，能夠與差分進化算法結合的人工智能算法有較多，需要結合實際應用需求選擇，確保算法混合能夠解決收斂、尋優等問題，取得理想的算法應用效果。

3 差分進化算法的改進實踐

3.1 約束優化問題

約束優化問題在生活中較為常見，但求解算法較少，面臨搜索空間復雜、約束條件難處理等困難。在解決約束優化問題時，可知包含等式、不等式和邊界等不同約束條件，得到：

式中，f(x)為目標函數，x=（x1，x2，...xn），取值范圍D 為n 維度決策空間，gj(x)和hj(x)分別為不等式和等式約束，p、q 分別為約束個數，ui和li為xi的上下界。根據x 到j 個約束的距離，可知x 到可行域間距離為約束違反程度G(x)：

式中，Gj(x)指的是x 到j 約束距離，δ 為正容忍因子，取值為0.000 1。

3.2 基于GOBL 的算法

在差分進化算法改進方面，采用自適應約束方式過于強調判斷個體是否達到約束條件，導致種群中不可行個體數量過多，容易出現尋解精度不高問題。采用反向學習策略（GOBL）進行種群結構優化，利用反向種群約束種群搜索空間，能夠根據反向解信息加快運算[5]。根據可行率采取不同變異策略，實現算子自適應設計，能夠提高種群多樣性。將變異前后的種群混合，排序后完成不同個體選擇，可以獲得新種群。應用該算法，可知n 維空間中xi存在對應反向解，得到：

式中，k 在0 到1 范圍內取值，xi在j 維取值在aj和bj之間，超出這一區域需要采用rand 函數隨機生成xi，j數值。根據反向解縮小搜索空間，可以在初始化種群P 和新種群P1中選取數量為Np的個體。在處理無法滿足條件的個體時，應利用自適應權衡模型ATM 將種群劃分為可行、不可行、半可行3 種狀態，將目標函數轉換為：

式中，σ 指的是可行率，xbest 和xworst 則為最好和最差個體，Z1和Z2分別為滿足和不滿足約束條件的個體序號。通過完成目標函數值和違約值的標準化處理，能夠得到個體適應值：

式中，ffanal(xi)指的是最終適應值，fnor(xi)和Gnor(xi)分別為目標函數值和違約值的標準化值，在可行時說明可以滿足全部約束條件，可以利用目標函數值代表。按照傳統差分進化算法，需要將父代向量中個體和新種群個體逐個比較，選擇適應值更優的個體，可能出現兩個適應值均較差個體相互比較，導致留下的個體適應值較大，影響收斂速度的同時，出現局部最優問題。為改進這一情況，需要完成父代種群和新種群合并，完成適應值排序，然后進行個體優選。

3.3 改進算法步驟

按照算法改進方法，需要先根據適應值完成個體排序，然后計算選擇概率：

式中，Ri為個體排序值，N 為種群個體數量，λ 取值將影響參與變異個體，決定最優解搜索范圍，體現個體支配關系。在λ 取值為2 的情況下，個體選擇概率差值較大，支配關系更加顯著。而λ 取值為0.5，支配關系相對模糊。因此將λ 取值為2，能夠在進化初期使不可行個體達到約束，獲得更多個體，依靠適應值大的個體加快搜索。在種群可行時，則能降低稍差個體選擇概率，減少參與變異的個體，容易陷入局部最優問題，因此應使λ 取值為0.5。在采取變異策略時，比較不同策略可知，想要提高種群多樣性需要進行自適應變異，得到：

式中，各x 變量為t 代不同個體，vi，t為變異后試驗向量，xgbest為適應值最優個體。縮放因子F 在0 到2 之間取值，可知早期進化時個體較少，可行率較小，應選擇DE/best/2 策略，利用最優個體資源對其他變異個體進行引領，達到快速收斂效果。在進化后期可行個體增加，可行率也有所增大，應選擇DE/rand/2 策略改善種群多樣性?？紤]到控制參數F 和CR 將給算法尋優帶來影響，需要采用自適應算子，得到：

式中，Gen 指的是最大迭代次數，t 為當前迭代次數，F0則為常數，在0 到1 范圍內取值。在F0數值較小時，算法收斂慢，但過大將出現尋優能力下降問題，通過反復測試最終取值0.5。在早期進化過程中，多數個體適應值不佳，應增加F 數值以獲得更大搜索范圍，提升種群多樣性。而經過多次迭代后，可以逐漸使F 趨近于F0，盡可能保留優秀個體，增加最優解查找概率。

3.4 算法測試分析

為確定算法改進效果，需要在問題處理時與標準DE算法和常見RMDE 算法進行比較。在算法種群規模NP 達到100 時，將各算法迭代次數設定為1 500 代，利用g02、g03 和g06 函數分別執行不同算法，然后對3 種算法的平均值等指標進行比較。如表1 所示，最終驗證改進算法可以獲得更好的尋優精度。

表1 測試結果

4 結論

對差分進化算法進行改進，可以采取調整控制參數、優化種群結構等多種方法。實際在改進方法運用過程中，需要結合實際需解決的問題選擇適合的改進方法，如在解決約束優化問題時需同時采取調整控制參數、改進操作算子等措施，確保能夠加強優秀個體資源利用，達到提高算法精度的目標。