鄒 杰，李 俊

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

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

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

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

文獻(xiàn)[11]利用種群間的協(xié)方差矩陣，為交叉操作建立合適的旋轉(zhuǎn)坐標(biāo)系，實(shí)驗(yàn)證明協(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ù)個(gè)體變異過(guò)程中每種策略產(chǎn)生優(yōu)秀個(gè)體的次數(shù)來(lái)確定每種策略選取的概率，個(gè)體在進(jìn)化的過(guò)程中，根據(jù)每種策略的選取概率來(lái)隨機(jī)選擇，保證產(chǎn)生歷史優(yōu)秀個(gè)體多的策略被選擇的概率更大；然后，通過(guò)一定概率的協(xié)方差矩陣學(xué)習(xí)，為變異和交叉操作建立一個(gè)基于協(xié)方差矩陣的旋轉(zhuǎn)坐標(biāo)系，即特征坐標(biāo)系。不同于文獻(xiàn)[11]中的算法，本文提出的算法將變異和交叉操作均放在了特征坐標(biāo)系中；同時(shí)，使用自適應(yīng)的交叉概率來(lái)平衡算法的全局探索能力和局部探索能力。最后，將算法同近幾年提出的若干優(yōu)秀算法在CEC2017測(cè)試集的30個(gè)測(cè)試函數(shù)上進(jìn)行了比較，根據(jù)算法在低維和高維上的實(shí)驗(yàn)數(shù)據(jù)表明該算法相比其他算法在求解全局最優(yōu)問(wèn)題上優(yōu)勢(shì)明顯。

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

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

1.1 差分變異

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

DE/rand/1：

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

1.2 雜交

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

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

1.3 選擇

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

式中，f(UG i)為實(shí)驗(yàn)個(gè)體UG i的目標(biāo)函數(shù)值，f(XG i)為當(dāng)前個(gè)體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)系中無(wú)法反映各個(gè)變量之間的聯(lián)系，也無(wú)法反映種群的整體情況。因此，本文利用協(xié)方差矩陣構(gòu)建一個(gè)新的具有關(guān)聯(lián)性的坐標(biāo)系，稱為特征坐標(biāo)系，然后將差分進(jìn)化算法的變異和交叉操作在特征坐標(biāo)系中進(jìn)行，具體的計(jì)算公式以及操作如下：

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

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

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

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

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

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

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

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

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

2.2 多策略變異

在差分進(jìn)化算法中，不同的變異策略在收斂性和探索性能上各有優(yōu)勢(shì)，即便是對(duì)于同一個(gè)優(yōu)化問(wèn)題，在不同的進(jìn)化階段，最優(yōu)的變異策略也可能是變化的，因此，本文采用多種變異策略來(lái)平衡算法的收斂能力和探索能力，本文一共選擇了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的收斂能力和探索能力適中。個(gè)體在進(jìn)化的過(guò)程記錄每種變異策略產(chǎn)生優(yōu)秀個(gè)體的次數(shù)，然后根據(jù)下式計(jì)算出每種變異策略的選擇概率：

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

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

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

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

2.4 個(gè)體元素超出邊界處理方式

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

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

2.5 算法實(shí)現(xiàn)過(guò)程

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

Begin

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

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

3. whileG＜Gmax

4. ifrand＜=P

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

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

7. fori=1 toNPdo

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

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

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

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

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

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

14. end for

15. else

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

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

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

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

20. end

21. fori=1 toNPdo

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

23. end for

24.end while

End

3 算法收斂性分析

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

考慮到實(shí)際問(wèn)題中解的精度，為了不失一般性，令S*δ={x||f(x*)-f(x)|＜δ} 表示擴(kuò)大的全局最優(yōu)解集合，δ為求解精度，x*為全局最優(yōu)個(gè)體。下面給出算法依概率收斂的定義以及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)化問(wèn)題時(shí)依概率收斂，若存在單調(diào)遞增序列{tk;k≥1} ?{1,2,…}及非負(fù)序列{ξ(tk);k≥1} 使得算法在tk代目標(biāo)種群中至少存在一個(gè)個(gè)體，通過(guò)繁殖算子產(chǎn)生的實(shí)驗(yàn)個(gè)體Uc滿足P{Uc∈S*δ}≥ξ(tk)＞0 且ξ(tk)發(fā)散。

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

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

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

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

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

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

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

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

4.1 CEC2017測(cè)試集

為了驗(yàn)證MSCDE算法的有效性、適用性、正確性，選擇在CEC2017[21]測(cè)試集中的30 個(gè)測(cè)試函數(shù)上同其他比較算法進(jìn)行低維和高維的對(duì)比。在CEC2017測(cè)試函數(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ù)評(píng)價(jià)次數(shù)FES=300 000 ；在高維D=100 的情況下，種群數(shù)量NP=200，最大演化代數(shù)Gmax=5 000，最大函數(shù)評(píng)價(jià)次數(shù)FES=1 000 000。MSCDE 算法的協(xié)方差矩陣學(xué)習(xí)概率P=0.3，種群采樣數(shù)量K=0.3×NP，縮放因子F=0.5。為了全面客觀地對(duì)MSCDE算法進(jìn)行評(píng)價(jià)，本文將MSCDE 算法與近年來(lái)優(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ī)因素對(duì)算法評(píng)估的影響，各算法均獨(dú)立運(yùn)行20 次。其他比較算法的參數(shù)設(shè)置均與原文一致。實(shí)驗(yàn)環(huán)境為：處理器Intel?Core?i7-7700HQ CPU @ 2.80 GHz，RAM 16 GB，Win10 64位操作系統(tǒng)，MATLAB R2016a。

4.3 仿真實(shí)驗(yàn)結(jié)果

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

4.4 算法收斂曲線圖

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

4.5 不同初始化方式搜索速度對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

表5 給定精度下的搜索時(shí)間s

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

4.6 實(shí)驗(yàn)結(jié)果分析

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

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

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

整體的實(shí)驗(yàn)結(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)確實(shí)能有效的提高算法的性能，進(jìn)一步證明了MSCDE算法的正確性、適用性和有效性。

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

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

5 結(jié)束語(yǔ)

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