多策略協方差矩陣學習差分進化算法

鄒 杰，李 俊

1.武漢科技大學 計算機科學與技術學院，武漢 430065

2.智能信息處理與實時工業系統湖北省重點實驗室，武漢 430065

差分進化算法（Differential Evolution，DE）1995 年被Storn 和Price[1]提出，是一種模擬自然界生物生存進化的隨機模型，主要被用來解決連續變量的全局優化問題，因其結構簡單、容易實現、魯棒性強等特點，被廣泛的應用在工程科學的各個領域。相比其他的進化算法，差分進化算法簡單易實現、搜索能力強，并且不需要任何問題的特征信息，非常適合于求解常規數學方法無法解決的復雜優化問題。但同時，差分進化算法也存在對控制參數和變異策略比較敏感和局部探索能力不足容易陷入局部極值的問題。近年來差分進化算法在約束優化計算、模糊控制器優化設計、濾波器設計、神經網絡、路徑規劃、電力系統調度等方面得到了廣泛的應用，但是，差分進化算法的探索能力不足、早熟易收斂等問題也一定程度上影響了它的具體應用。本文的主要工作是通過一系列的改進措施來提高差分進化算法的搜索能力和收斂速度，使之適用于各種實際工程優化問題。

目前，針對DE算法的這些問題，國內外學者進行了大量的研究。在控制參數方面，差分進化算法的控制參數包括縮放因子F和交叉率CR。差分進化算法性能的優劣很大程度上取決于其控制參數的選擇[2]。文獻[3]提出了一種自適應參數設置的差分進化算法；Liu等[4]提出了一種基于模糊控制的適應差分進化算法FADE，通過模糊邏輯控制器來調節參數F和CR；Qin 等[5]提出一種新的自適應差分進化（SaDE）算法，F和CR借鑒前期產生優質解的經驗進行自適應調整。在變異策略方面，除差分進化算法所介紹的5 種基本變異策略外，研究人員對其他一些變異策略以及變異方式也進行了研究。Fan 等[6]提出三角變異策略；Zhang 等[7]提出DE/current-to-pbest策略，即JADE；Leon等[8]設計出一種新的變異策略DE/Alopex/1，其不同之處在于使用群體中個體的適應度值來計算移動方向的概率；文獻[9]提出一種基于三角骨架的差分進化算法；文獻[10]提出旋轉學習機制，并將旋轉學習運用到DE算法中；文獻[11]提出一種基于協方差學習的差分進化算法，協方差矩陣能反映種群的多樣性信息，以此來指導種群個體進化，從而提高算法的性能；文獻[12]提出了具有全局和局部鄰域變異算子的自適應文化基因差分進化算法，該算法隨機廣義的選擇全局和局部的變異策略，然后根據權重來自適應調整局部和全局對個體進化的影響；文獻[13]提出了將最優高斯隨機游走策略運用到DE 算法中；文獻[14]提出了一種基于鄰域差分和協方差信息的差分進化算法，該算法采用鄰域差分的方式來提高差分算子的有效性；文獻[15]將種群劃分為3個子種群，每個子種群分配一種變異策略，然后根據每種策略的貢獻度來動態調整子種群的規模，各變異策略之間相互配合協同進化；文獻[16]提出一種反向學習的跨種群的差分演化算法，運用3種策略對子種群進行操作；文獻[17]提出一種高效動態自適應差分進化算法，該算法在變異因子、變異策略及交叉概率上加入自適應操作，以此來平衡算法的全局探索能力和局部探索能力。

文獻[11]利用種群間的協方差矩陣，為交叉操作建立合適的旋轉坐標系，實驗證明協方差矩陣學習策略能極大的提高算法的性能，但是文獻[11]中的算法采用多種群策略，子種群構建操作繁瑣，且不同子種群根據進化狀態采用不同的變異策略，算法學習成本高。因此，基于文獻[11]提出的協方差矩陣學習的思想，本文提出了一種多策略協方差矩陣學習的差分進化算法（Multi-Strategy Covariance matrix learning Differential Evolution algorithm，MSCDE），該算法選取了3 種變異策略，根據個體變異過程中每種策略產生優秀個體的次數來確定每種策略選取的概率，個體在進化的過程中，根據每種策略的選取概率來隨機選擇，保證產生歷史優秀個體多的策略被選擇的概率更大；然后，通過一定概率的協方差矩陣學習，為變異和交叉操作建立一個基于協方差矩陣的旋轉坐標系，即特征坐標系。不同于文獻[11]中的算法，本文提出的算法將變異和交叉操作均放在了特征坐標系中；同時，使用自適應的交叉概率來平衡算法的全局探索能力和局部探索能力。最后，將算法同近幾年提出的若干優秀算法在CEC2017測試集的30個測試函數上進行了比較，根據算法在低維和高維上的實驗數據表明該算法相比其他算法在求解全局最優問題上優勢明顯。

1 基本差分進化算法

DE 算法主要用來解決連續變量的全局優化問題，主要由3 大算子（差分變異、雜交和選擇）組成。DE 算法是一種基于自適應全局優化的算法，類似于遺傳算法GA[18]，算法流程與遺傳算法類似，首先根據種群規模和問題維度來產生隨機初始化的種群，然后借助差分變異操作來進行種群空間的探索，接著利用雜交操作來產生實驗個體，最后根據貪婪原則來選擇適應度值優的個體，以此來產生下一代，

1.1 差分變異

差分變異是差分進化算法進入迭代后最先執行的算子，且差分變異是差分進化思想最顯著的特征。種群按照順序執行差分變異，按照差分變異策略隨機選擇多個不同的個體進行變異操作，最常見的差分變異策略有以下5種。

DE/rand/1：

其中XG i1、XGi2、XGi3、XGi4、XGi5表示從當前種群中隨機選取的5 個不同個體，XG i表示當前個體，XGbest表示當前全局最優個體，F為縮放因子。

1.2 雜交

雜交即交叉，根據交叉概率CR對變異算子產生的變異向量VG i與當前個體XG i進行重組，得到一個實驗個體UG i，具體公式如下：

其中，rand表示（0，1）之間均勻分布的隨機數，jrand是隨機生成的范圍在[1,D]之間的整數，CR為交叉概率，ViG,j為當前個體XiG通過變異操作產生的個體j維的變量值，XG i,j為當前個體在特征坐標系中的映射個體在j維的變量值。

1.3 選擇

實驗個體UG i和當前個體XG i會根據目標函數得到適應度值，然后比較兩個個體的適應度值，適應度值優的個體保留到下一代，反之適應度值差的個體則會被淘汰，具體公式如下：

式中，f(UG i)為實驗個體UG i的目標函數值，f(XG i)為當前個體XG i的目標函數值。

2 多策略協方差矩陣學習差分進化算法

2.1 協方差矩陣學習

差分進化算法的變異、交叉操作都是在標準的坐標系中完成的。然而，在標準的坐標系中無法反映各個變量之間的聯系，也無法反映種群的整體情況。因此，本文利用協方差矩陣構建一個新的具有關聯性的坐標系，稱為特征坐標系，然后將差分進化算法的變異和交叉操作在特征坐標系中進行，具體的計算公式以及操作如下：

種群第G代中第i維和第j維的協方差計算公式如下：

式中，表示種群中第i維中所有變量的平均值，同理，XG i,k表示個體k的i維變量值，XG j,k表示個體k的j維變量值，NP表示種群中個體的數量。為了減少種群協方差矩陣的計算開銷，本文采用隨機采樣的方式從種群中選取K個個體來計算種群的協方差。種群的協方差矩陣計算公式如下：

根據公式（9）得到的協方差矩陣為對稱矩陣，因此，對協方差矩陣進行特征分解得到特征向量矩陣，然后根據特征向量矩陣組成一個新的坐標系，即種群的特征坐標系。將變異操作所需要的個體映射到特征坐標系中，具體公式如下：

式中，QG為種群協方差矩陣的特征向量矩陣，XG i為在當前種群中隨機選取的個體，X"G i為個體XG i映射到特征坐標系中的新個體。然后在特征坐標系中根據下式（11）執行變異操作：

式中，X"G i1,j、X"G i2,j、X"G i3,j表示在當前種群中隨機選取的三個不同個體映射到特征坐標系中的新個體，F表示縮放因子。

其次，在特征坐標系中執行交叉操作：

式中，rand為（0，1）之間均勻分布的隨機數，CR為交叉概率，jrand是隨機生成的范圍在[1,D]之間的整數，UiG,j為式（11）產生的子個體i在j維的變量值，Xi",Gj為當前個體在特征坐標系中的映射個體在j維的變量值。

最后，將在特征坐標系中產生的實驗個體v"G i根據式（13）轉換到標準的坐標系中，然后根據擇優選擇的策略來更新種群。

式中，v"Gi為個體XG i在特征坐標系中產生的實驗個體，QG為種群協方差矩陣的特征向量矩陣。

2.2 多策略變異

在差分進化算法中，不同的變異策略在收斂性和探索性能上各有優勢，即便是對于同一個優化問題，在不同的進化階段，最優的變異策略也可能是變化的，因此，本文采用多種變異策略來平衡算法的收斂能力和探索能力，本文一共選擇了3 種變異策略，分別是DE/rand/1、DE/best/1、DE/current-to-best/1，這3 種變異策略中，DE/rand/1 的探索能力要強于其他兩種變異策略，DE/best/1的收斂能力要強于其他兩種變異策略，DE/currentto-best/1的收斂能力和探索能力適中。個體在進化的過程記錄每種變異策略產生優秀個體的次數，然后根據下式計算出每種變異策略的選擇概率：

式中，n為常量3，PG i,m表示個體i選擇變異策略m的概率，MG i,m表示個體i進化歷史中m變異策略產生優秀個體的次數，默認為1，保證初次迭代時各變異策略的選取概率相同。

2.3 參數自適應

在差分進化算法中，參數設置對算法性能有著較大的影響，交叉概率決定個體從實驗個體繼承基因的概率，因此，本文采取自適應的交叉概率來提高算法的性能。交叉概率根據個體累計連續的歷史停滯進化（即個體未被更新）次數來動態的計算，停滯次數多的個體，交叉概率大，提高個體的變異概率，從而提高個體繼承實驗個體基因的概率，進而來提高算法的探索能力。交叉概率的具體計算公式如下：

其中，CRGi表示個體i當前的交叉概率，表示個體i到G代為止累計連續停滯進化的次數，Gmax表示算法的最大迭代次數，交叉概率的初始值為0.5。

2.4 個體元素超出邊界處理方式

種群個體在進化的過程中，有概率會出現超出邊界的情況，對于超出邊界的情況，本文的修正策略如下：

其中，Xmax為種群探索空間的上限，Xmin為種群探索空間的下限，Xij表示個體i在j維的變量值，rand為范圍在（0，1）間均勻分布的隨機數。

2.5 算法實現過程

在MSCDE算法中取樣數量K是一個在(0,NP]的一個整數，協方差矩陣學習概率P是一個在（0，1）區間的常數，交叉概率CR初始為0.5，縮放比例F為[0，1]區間的常數。算法具體實現如下：

Begin

1. 隨機初始化種群，并計算目標函數值保存到Fit 數組中；

2. 初始化協方差矩陣學習概率P，取樣數量K,G=0；

3. whileG＜Gmax

4. ifrand＜=P

5. 隨機選取K個個體，根據式（9）計算種群的協方差矩陣

6. 計算協方差矩陣的特征矩陣

7. fori=1 toNPdo

8. 隨機選取三個不同于i的個體

9. 根據式（10）將i和3個父個體映射到特征坐標系中

10. 根據式（11）執行變異操作

11. 根據式（12）執行交叉操作

12. 根據式（13）將實驗個體轉換到標準坐標系

13. 根據式（16）對超邊界的變量進行處理

14. end for

15. else

16. 根據式（14）計算3種變異策略的選取概率

17. 根據選取的策略執行變異操作

18. 根據式（16）對超邊界的變量進行處理

19. 記錄3種變異策略產生優秀個體的次數

20. end

21. fori=1 toNPdo

22. 根據式（15）更新交叉概率

23. end for

24.end while

End

3 算法收斂性分析

一般來說，在理論上能確保收斂的算法具有較高的穩定性和更強的跳出局部極值的能力。Hu等[19]給出了改進DE 算法能依概率收斂的充分條件，本文在此充分條件的基礎上對MSCDE算法的收斂性進行分析。

考慮到實際問題中解的精度，為了不失一般性，令S*δ={x||f(x*)-f(x)|＜δ} 表示擴大的全局最優解集合，δ為求解精度，x*為全局最優個體。下面給出算法依概率收斂的定義以及DE算法依概率收斂的充分條件。

定義1[20]種群序列{Xt,t=0,1,…}依概率收斂到S*δ，當前僅當tl→im∞P(Xt?S*δ≠?)=1。

引理1[20]采用貪婪選擇策略的改進DE算法求解優化問題時依概率收斂，若存在單調遞增序列{tk;k≥1} ?{1,2,…}及非負序列{ξ(tk);k≥1} 使得算法在tk代目標種群中至少存在一個個體，通過繁殖算子產生的實驗個體Uc滿足P{Uc∈S*δ}≥ξ(tk)＞0 且ξ(tk)發散。

定理1 MSCDE算法是依概率全局收斂的。

證明本文用到的協方差矩陣學習策略起到了充分利用種群分布信息、提高算法計算能力的作用，但不改變算法整體的繁衍策略，收斂性主要由DE/rand/1 變異決定。多策略變異本質上是一種變異策略選擇機制，因此收斂性主要由其中的3 種基本變異策略決定。下面從兩個方面具體分析MSCDE算法的特征。

（1）MSCDE 能確保當前種群中的最優解保留到下一代。MSCDE 算法的選擇操作算子同基礎DE 算法的貪婪選擇策略一致，因此種群中的最優個體能保留到下一代。

（2）在MSCDE 的變異算子的作用下，每代種群中的實驗個體進入全局最優解集合S*δ的概率足夠大。

MSCDE 算法的變異算子包括DE/rand/1、DE/best/1、DE/current-to-best/1。實際上，實驗個體u進入全局最優解集合S*δ的概率P{u∈S*δ}不小于單獨由協方差矩陣學習策略中的DE/rand/1 變異算子產生的個體uc進入S*δ的概率，即：P{u∈S*δ}≥P{uc∈S*δ}。

pc為DE/rand/1 在每個個體上執行的概率，產生的實驗個體uc在解空間上是均勻分布的。用μ(·)表示集合的測度，ψ表示解空間，因此由協方差矩陣學習策略中的DE/rand/1 變異算子產生的新個體uc進入S*δ的概率為

由協方差矩陣學習策略中的DE/rand/1變異算子產生的新個體都不進入S*δ的概率為P{Uc?S*δ=?}=[1-，式中的Uc表示實驗個體組成的實驗種群，NP 表示種群規模。則由協方差矩陣學習策略中的DE/rand/1變異算子產生的新個體至少有一個個體進入S*δ的 概 率 為令，對任意自然數t，顯然發散。因此由引理1可知，MSCDE算法收斂。

4 函數仿真與分析

4.1 CEC2017測試集

為了驗證MSCDE算法的有效性、適用性、正確性，選擇在CEC2017[21]測試集中的30 個測試函數上同其他比較算法進行低維和高維的對比。在CEC2017測試函數中，f1、f2、f3 為單峰函數，f4 ～f10 為多峰函數，f11 ～f20 為混合函數，f21 ～f30 為復合函數，函數的具體定義如表1所示。

4.2 參數設置

各算法在低維D=30 的情況下，種群數量NP=150 ，最大演化代數Gmax=2 000 ，最大函數評價次數FES=300 000 ；在高維D=100 的情況下，種群數量NP=200，最大演化代數Gmax=5 000，最大函數評價次數FES=1 000 000。MSCDE 算法的協方差矩陣學習概率P=0.3，種群采樣數量K=0.3×NP，縮放因子F=0.5。為了全面客觀地對MSCDE算法進行評價，本文將MSCDE 算法與近年來優秀的算法AM_DEGL[12]、RDE[10]、tBBDE[9]、DE/Alopex/1[8]、GSDE[13]，以及標準DE算法和JADE[7]算法進行了比較，為了避免隨機因素對算法評估的影響，各算法均獨立運行20 次。其他比較算法的參數設置均與原文一致。實驗環境為：處理器Intel?Core?i7-7700HQ CPU @ 2.80 GHz，RAM 16 GB，Win10 64位操作系統，MATLAB R2016a。

4.3 仿真實驗結果

表2 以及表3 表示MSCDE 算法同其他比較算法在低維(D=30)以及高維(D=100)情況下平均值、方差的比較，表中最好的數據已加粗表示。

4.4 算法收斂曲線圖

Zitzler等[22]提出僅僅通過數值指標評價并不能完全的反映算法性能的好壞，因此本文繪制了如下算法收斂曲線圖。圖1～6 表示各算法在低維情況下求解測試函數f1、f12、f22 以及在高維情況下求解測試函數f3、f6、f21 的收斂曲線圖。

4.5 不同初始化方式搜索速度對比

MSCDE 算法采用的是隨機初始化種群的方式，為了測試隨機初始化方式對算法搜索速度的影響，本文將采用隨機初始化、佳點集初始化[23]、混沌序列初始化[24]3 種不同的初始化方式的MSCDE算法進行仿真實驗對比，MSCDE 算法的參數設置同上文D=30 的情況一致。采用固定精度的方式來測試算法的搜索速度，精度設置如表4所示。

表1 CEC2017標準測試函數

表2 MSCDE與其他算法的比較(D=30)

表3 MSCDE與其他算法的比較(D=100)

圖1 f1 函數測試結果(D=30)

圖2 f12 函數測試結果(D=30)

圖3 f22 函數測試結果(D=30)

圖4 f3 函數測試結果(D=100)

圖5 f6 函數測試結果(D=100)

表4 預設精度VTR

MSCDE 算法在不同的初始化種群方式下，獨立運行20 次，比較達到表4 預設精度所需要的平均時間，實驗結果如表5所示，表中最好的數據已加粗顯示。

圖6 f21 函數測試結果(D=100)

表5 給定精度下的搜索時間s

從表5中可以看出，采用隨機初始化種群的MSCDE算法在搜索速度上有明顯優勢，且隨機初始化相較于其他兩種方式來說更加簡單，容易實現。

4.6 實驗結果分析

表2 是各算法在低維D=30 的情況下實驗數據的對比結果，從表中數據可以看出，在平均值指標上，MSCDE算法在f1、f2、f3、f6、f9、f12、f13、f14、f15、f18、f19、f22、f30 測試函數上的結果優于或持平于其他算法，在f1、f2、f3、f6、f9 測試函數上均得到了實際最優值，且在其他測試函數上同最優結果之間的差距不大；在方差指標上，MSCDE 算法在測試函數f1、f2、f3、f12、f13、f15、f18、f19、f22、f30 上優于其他算法。綜上所述，MSCDE算法在低維情況下，在單峰函數f1 ～f3 以及在混合函數f11 ～f20 上平均值優勢明顯，在多峰函數和復合函數上也有不錯的效果，混合函數求解難度較高，因此說明了MSCDE 算法計算能力突出。

表3是各算法在高維D=100 的情況下實驗數據的對比結果，從表中的數據可以看出，在平均值指標上，MSCDE算法在f1、f2、f3、f5、f12、f16、f18、f21、f28、f30 測試函數上最優，在f6 測試函數上與其他算法持平，在f3、f6 測試函數上得到了實際最優值，且在其他測試函數上同最優結果之間的差距不大；在方差指標上，MSCDE算法在f2、f3、f18、f30 測試函數上為最優值。總體上可以看出，MSCDE 算法在高維情況下在單峰函數、混合函數以及復合函數上表現優秀。

圖1～6 表示的是各算法在不同測試函數上的收斂曲線圖，圖1～3是各算法在低維情況下的收斂圖，從圖1可以看出MSCDE 算法在f1 測試函數上在同等的收斂精度算法中收斂速度最快，圖2和圖3可以看出MSCDE算法在測試函數f12 上收斂精度最高，在測試函數f22上的收斂速度最快，從圖2 和圖3 上看出MSCDE 算法在函數f12 和函數f22 上的進化曲線很平緩，并沒有受到局部極值的影響。圖4～6 是各算法在高維情況下的收斂曲線圖，圖4可以看出MSCDE算法在f3 函數上收斂精度明顯優于其他算法，從圖4中還可以看出MSCDE算法在200 代左右出現早熟收斂的情況，在500 代左右跳出，之后朝著最優解的方向進化。從圖5中可以看出，MSCDE算法在f6 函數上收斂速度最快，并且進化曲線平緩，沒有受到局部極值的影響。圖6表示的是各算法在f21 測試函數上的收斂曲線，從中可以看出MSCDE算法的收斂精度最高，從收斂曲線中還可以看出，MSCDE算法在100 代左右陷入局部極值，在1 250 代左右跳出局部極值并朝著最優解的方向平穩進化。綜上所訴，MSCDE算法能有效解決標準DE算法早熟收斂的問題。

整體的實驗結果表明，MSCDE 算法不論是在低維還是高維的情況下均表現出不俗的性能，特別是在單峰函數f1 ～f3 上，MSCDE采用貪婪機制選擇最優的變異策略，使得算法有很快的收斂速度和很高的收斂精度，協方差矩陣學習的引入使得MSCDE 算法在復合函數和混合函數上表現突出。綜上所述，MSCDE 算法中提出的協方差矩陣學習、多策略變異以及交叉概率自適應確實能有效的提高算法的性能，進一步證明了MSCDE算法的正確性、適用性和有效性。

4.7 算法復雜度分析

根據算法的實現流程，分析MSCDE 算法的復雜度，種群規模為NP，問題維度為D，最大進化次數為G，協方差矩陣學習的復雜度為O(NP×D)，多策略變異的復雜度為O(NP×D)，協方差矩陣學習與多策略變異每次迭代只會執行其中一個，因此MSCDE算法的整體復雜度為O(G×NP×D)，與標準的DE算法復雜度一致。因此，MSCDE 算法中的協方差矩陣學習和多策略變異在提高算法性能的同時，并沒有增加多余的計算開銷。

5 結束語

本文提出了一種多策略協方差矩陣學習的差分進化算法（MSCDE），通過協方差矩陣學習，來充分利用種群的分布信息和各變量之間的關系，同時，根據歷史進化信息，來動態的選擇合適當前個體的變異策略，最后，隨個體進化狀態自適應變化的交叉概率，能更好地平衡算法的局部和全局探索能力。本文對MSCDE 算法的收斂性進行了證明，并通過一系列的實驗表明，在低維和高維的情況下，MSCDE算法均表現出不俗的性能，在算法的收斂性和穩定性上總體要強于其他比較算法。同時，分析得出MSCDE算法的時間復雜度與標準的DE算法一致。綜上所述，證明了本文提出算法的正確性、有效性和適用性。