多策略協(xié)方差矩陣學(xué)習(xí)差分進(jìn)化算法

鄒 杰，李 俊

1.武漢科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430065

2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，武漢 430065

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

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

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

1 基本差分進(jìn)化算法

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

1.1 差分變異

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

DE/rand/1：

其中XG i1、XGi2、XGi3、XGi4、XGi5表示從當(dāng)前種群中隨機(jī)選取的5 個不同個體，XG i表示當(dāng)前個體，XGbest表示當(dāng)前全局最優(yōu)個體，F(xiàn)為縮放因子。

1.2 雜交

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

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

1.3 選擇

實驗個體UG i和當(dāng)前個體XG i會根據(jù)目標(biāo)函數(shù)得到適應(yīng)度值，然后比較兩個個體的適應(yīng)度值，適應(yīng)度值優(yōu)的個體保留到下一代，反之適應(yīng)度值差的個體則會被淘汰，具體公式如下：

式中，f(UG i)為實驗個體UG i的目標(biāo)函數(shù)值，f(XG i)為當(dāng)前個體XG i的目標(biāo)函數(shù)值。

2 多策略協(xié)方差矩陣學(xué)習(xí)差分進(jìn)化算法

2.1 協(xié)方差矩陣學(xué)習(xí)

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

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

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

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

式中，QG為種群協(xié)方差矩陣的特征向量矩陣，XG i為在當(dāng)前種群中隨機(jī)選取的個體，X"G i為個體XG i映射到特征坐標(biāo)系中的新個體。然后在特征坐標(biāo)系中根據(jù)下式（11）執(zhí)行變異操作：

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

其次，在特征坐標(biāo)系中執(zhí)行交叉操作：

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

最后，將在特征坐標(biāo)系中產(chǎn)生的實驗個體v"G i根據(jù)式（13）轉(zhuǎn)換到標(biāo)準(zhǔn)的坐標(biāo)系中，然后根據(jù)擇優(yōu)選擇的策略來更新種群。

式中，v"Gi為個體XG i在特征坐標(biāo)系中產(chǎn)生的實驗個體，QG為種群協(xié)方差矩陣的特征向量矩陣。

2.2 多策略變異

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

式中，n為常量3，PG i,m表示個體i選擇變異策略m的概率，MG i,m表示個體i進(jìn)化歷史中m變異策略產(chǎn)生優(yōu)秀個體的次數(shù)，默認(rèn)為1，保證初次迭代時各變異策略的選取概率相同。

2.3 參數(shù)自適應(yīng)

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

其中，CRGi表示個體i當(dāng)前的交叉概率，表示個體i到G代為止累計連續(xù)停滯進(jìn)化的次數(shù)，Gmax表示算法的最大迭代次數(shù)，交叉概率的初始值為0.5。

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

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

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

2.5 算法實現(xiàn)過程

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

Begin

1. 隨機(jī)初始化種群，并計算目標(biāo)函數(shù)值保存到Fit 數(shù)組中；

2. 初始化協(xié)方差矩陣學(xué)習(xí)概率P，取樣數(shù)量K,G=0；

3. whileG＜Gmax

4. ifrand＜=P

5. 隨機(jī)選取K個個體，根據(jù)式（9）計算種群的協(xié)方差矩陣

6. 計算協(xié)方差矩陣的特征矩陣

7. fori=1 toNPdo

8. 隨機(jī)選取三個不同于i的個體

9. 根據(jù)式（10）將i和3個父個體映射到特征坐標(biāo)系中

10. 根據(jù)式（11）執(zhí)行變異操作

11. 根據(jù)式（12）執(zhí)行交叉操作

12. 根據(jù)式（13）將實驗個體轉(zhuǎn)換到標(biāo)準(zhǔn)坐標(biāo)系

13. 根據(jù)式（16）對超邊界的變量進(jìn)行處理

14. end for

15. else

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

17. 根據(jù)選取的策略執(zhí)行變異操作

18. 根據(jù)式（16）對超邊界的變量進(jìn)行處理

19. 記錄3種變異策略產(chǎn)生優(yōu)秀個體的次數(shù)

20. end

21. fori=1 toNPdo

22. 根據(jù)式（15）更新交叉概率

23. end for

24.end while

End

3 算法收斂性分析

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

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

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

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

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

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

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

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

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

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

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

4 函數(shù)仿真與分析

4.1 CEC2017測試集

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

4.2 參數(shù)設(shè)置

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

4.3 仿真實驗結(jié)果

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

4.4 算法收斂曲線圖

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

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

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

表1 CEC2017標(biāo)準(zhǔn)測試函數(shù)

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

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

圖1 f1 函數(shù)測試結(jié)果(D=30)

圖2 f12 函數(shù)測試結(jié)果(D=30)

圖3 f22 函數(shù)測試結(jié)果(D=30)

圖4 f3 函數(shù)測試結(jié)果(D=100)

圖5 f6 函數(shù)測試結(jié)果(D=100)

表4 預(yù)設(shè)精度VTR

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

圖6 f21 函數(shù)測試結(jié)果(D=100)

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

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

4.6 實驗結(jié)果分析

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

表3是各算法在高維D=100 的情況下實驗數(shù)據(jù)的對比結(jié)果，從表中的數(shù)據(jù)可以看出，在平均值指標(biāo)上，MSCDE算法在f1、f2、f3、f5、f12、f16、f18、f21、f28、f30 測試函數(shù)上最優(yōu)，在f6 測試函數(shù)上與其他算法持平，在f3、f6 測試函數(shù)上得到了實際最優(yōu)值，且在其他測試函數(shù)上同最優(yōu)結(jié)果之間的差距不大；在方差指標(biāo)上，MSCDE算法在f2、f3、f18、f30 測試函數(shù)上為最優(yōu)值?？傮w上可以看出，MSCDE 算法在高維情況下在單峰函數(shù)、混合函數(shù)以及復(fù)合函數(shù)上表現(xiàn)優(yōu)秀。

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

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

4.7 算法復(fù)雜度分析

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

5 結(jié)束語

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