基于反射變異策略的自適應差分進化算法

錢武文，柴軍瑞，張子映，談 然

西北旱區生態水利工程國家重點實驗室培育基地（西安理工大學），西安 710048

1 引言

差分進化算法[1]（DE）于1995年提出，是一種類似遺傳算法、蟻群算法的群優化算法，具有結構簡單易于操作、對求解函數無特殊要求以及參數少的優點。作為一種群體智能優化算法，DE也同樣易于發生算法早熟和進化停滯。缺乏種群多樣性是導致DE發生早熟收斂的主要原因。DE使用貪婪的選擇策略，個體只在生成了具有更好適應值個體的前提下才能發生進化。對于最小值優化問題，從統計上講，個體函數值越小其發生進化的概率也越小。因此，如何更好地維持DE的種群多樣性和增強子代生成策略的魯棒性是改進DE的兩個重要方向。

DE具有縮放因子(F)，交叉因子(CR)和種群規模(NP)三種參數，其中F和CR是子代生成策略直接使用的兩種參數。相比原始DE使用固定的F和CR值，自適應變化的F和CR能改善DE的性能。針對這兩個參數，研究者們提出了多種自動調節參數的方法[2-4]。文獻[5]提出一種遺傳成功個體的參數而失敗個體參數重生成的參數調節方法（jDE）。Zhang等[6]提出一種具有反饋調節的自適應參數調節方法（JADE），該方法能根據成功個體的參數信息反饋調節F和CR的值。Tanabe等[7]在JADE的基礎上，提出了一種帶歷史參數存儲的自適應方法（SHADE），該方法在JADE的基礎上進一步提升了算法的魯棒性。

子代生成策略高度影響著DE的性能。算法的全局探測能力和局部開采能力是相互對立的。國內外學者針對怎樣平衡DE的探測和開采能力方面提出了一些改進的子代生成策略[8-10]。Zhang等[6]基于current-to-best/1提出了一種新型的變異策略current-to-pbest/1，即從 p個最優個體任選一個代替current-to-best/1中的最好個體。Mohamed[11]提出了一種基于三角變異策略的改進DE，其在無約束全局優化問題中取得了不錯的效果。Yi等[12]提出了一種混合的變異策略，該變異策略使用全局探測性能較強的ran/1和局部開采能力較強的currentto-best/1按一定規則混合使用。

NP作為DE的另一大參數，相比其他兩個參數國內外學者對NP的研究較少。主要在于一些學者發現當引入一些自適應策略去控制種群規模后，可能使得算法停滯和早熟收斂變得更糟[13]。當前的自適應控制種群規模的方法[14-15]共同體現出了一個問題，那就是增加種群規模會降低找到正確搜索方向的可能性，而降低種群規模則導致早熟收斂和算法停滯的可能性增加。

Nelder-Mead方法是一種無約束非線性優化的直接搜索方法，使用D+1個點構成的廣義三角形作為單純形進行搜索，有著優秀的局部收斂速度。本文受Nelder-Mead方法啟發，提出了一種類似Nelder-Mead方法中反射操作的變異策略，稱為反射變異策略。該策略使用隨機的4個個體完成一次變異操作，具有明確的變異方向。參與變異操作的個體的選擇隨機性降低了算法早熟的可能性。引入了一種控制參數自適應調節方法，結合本文提出的變異策略使用固定的種群規模組成了RMADE算法以期進一步提升算法的整體性能。大量實驗測試表明反射變異策略的提出的價值。

2 基本差分進化算法

2.1 初始化種群

DE基于實數編碼，首先在問題的可行域上隨機生成初始種群，Xi=(xi,1,xi,2,…,xi,D),i={1,2,…,NP}，其中D為變量的個數，NP為種群規模。具體操作如下：

其中，xmin,j，xmax,j分別為第 j維的最小值和最大值，r為[0，1]之間的均勻隨機數。

2.2 變異操作

與其他進化算法的變異操作不同的是，DE采用父代的差分矢量作為其最基本的變異成分，每個差分矢量是由父代中兩個不同的個體相減得到，對差分矢量進行縮放后，與種群中另外的相異個體進行相加便得到變異矢量。目前，已有幾種主要的變異矢量的生成方法，其相應表達式見表1，其中：g為代數，Xbest,g為第g代群體找到的最優位置；Xa,g,Xb,g,Xc,g,Xd,g,Xe,g為隨機選擇的5個不同個體，F為縮放因子。

表1 基本變異策略的名稱及表達式

2.3 交叉操作

為了提高種群的多樣性，DE引入交叉操作，使得實驗向量至少有一位分量由變異矢量貢獻，具體如下：

其中，CR為交叉算子，r為0～1的均勻隨機數，jrand為[1，D]的隨機整數。

2.4 選擇操作

良好的選擇策略能顯著提高算法的收斂性能，DE采用“貪婪”的選擇策略，通過由經過變異和交叉操作所生成的實驗個體與父代個體進行競爭，擇優選擇進入下一代種群中的個體，具體如下：

（1）最小值問題

（2）最大值問題

為了不失一般性，本文的研究為最小值優化問題。

3 提出的算法

將詳細介紹本文提出的基于反射變異策略的自適應差分進化算法（RMADE），首先介紹提出的反射變異策略。

3.1 反射變異策略

作為一種無約束非線性優化的直接搜索方法，Nelder-Mead方法使用單純形進行搜索（對于D維優化問題，其單純形是D+1個點構成的廣義三角形）。首先，計算單純形各頂點的函數值并對其按從小到大進行排序，得到最好點、次壞點和最壞點。由除最壞點外的其余個體計算單純形中心，然后通過反射、擴張、收縮和壓縮等操作搜索更好的點構成新的單純形，當達到預期的精度或其他終止條件時，方法終止，否則，迭代單純形。Nelder-Mead方法簡單易于實現，且適用于導數未知的非線性最優化問題，有著優秀的局部收斂速度，因此，Nelder-Mead方法廣泛應用于各個領域。

盡管Nelder-Mead方法存在上述優點，但它對初始解有著較強的依賴性，并且當求解多模態問題時，易于陷入局部收斂。因此，除了對于一些特定問題的優化外，Nelder-Mead方法有著很大的局限性。Nelder-Mead方法的反射是最壞點基于中心點的反射，其擴張操作進行的前提是反射點優于最好點。收縮操作是在反射點劣于次壞點的情況下進行的。若反射和收縮操作都不能找到優于次壞點的點時，才進行壓縮操作。壓縮操作的作用是壓縮搜索空間。反射和擴張操作的搜索方向是一致的，都是最壞點到中心點的方向。差分進化算法經過一定的進化代數后，種群個體將呈現出往最優解附近聚集的趨勢[16-17]。因此，差分進化算法的搜索過程實際上是和Nelder-Mead方法的壓縮操作類似。受Nelder-Mead方法啟發，提出一種新型的變異策略，本文稱之為反射變異策略。該變異策略同樣引入一種單純形的概念，即不論求解問題的維數，始終選擇種群中的4個任意個體組成單純形，每完成一次變異操作須引入一個單純形。該策略操作如下：

其中，Vi,g為i個體在g代的試向量；Xo,g是單純形中心；Xa,g和Xd,g分別為單純形中的最好點和最壞點，F為變異縮放因子。

不同于Nelder-Mead方法，本文使用的單純形中心Xo,g是根據單純形頂點的函數值計算的，并且除最壞點外的各個頂點均按其函數值權重分配到中心中。單純形中心Xo,g的計算公式如下：

其中，w1，w2和w3分別為除最壞點外的其余單純形頂點的權重；Xa,g,Xb,g和Xc,g為除最壞點外的剩余單純形頂點。

這種變異策略既類似于Nelder-Mead方法中的反射操作，具有明確的搜索方向，又類似于基本差分進化算法中的rand/1變異操作，其基向量擁有一定的隨機性。采用本文提出的變異操作生成子代個體的過程如圖1所示。

圖1 反射變異策略的變異操作示意圖

3.2 控制參數自適應調整機制

傳統的差分進化算法采用固定的變異因子和交叉因子，而針對不同的優化問題，使用固定的控制參數將嚴重妨礙了算法的性能。參數自適應調整機制允許每一個體使用不同于其他個體的縮放因子F和交叉因子CR去生成子代個體，且能根據算法進化過程中成功個體的經驗反饋調節控制參數。本文采用SHADE[7]算法中的參數自適應調整方法。

F和CR分別由一個柯西分布和一個正態分布隨機產生，這兩個分布的標準差都為0.1。均值則是從兩個大小都為H的用來存儲控制參數均值的數組中隨機抽取。初始這個數組中的元素為0.5。

變異因子F和交叉因子CR分別按式（7）和（8）自適應生成：

其中，randc(MF,ri,0.1)和randn(MCR,ri,0.1)分別為服從均值為MF,ri標準差為0.1的柯西分布和均值為MCR,ri標準差為0.1的正態分布的隨機數。當Fi＞1，則令Fi＞1；若 Fi＜0，則重新使用公式（8）生成 Fi。CRi∈[0，1]，若超出邊界，則使用距其最近的邊界替換。MF,ri為MF中序號為ri的元素，MCR,ri為MCR中序號為ri的元素，ri為一個1～H的隨機整數。MF和MCR內的值影響F和CR的隨機產生，根據每一個優化問題的不同進化階段中成功個體的參數信息反饋調節MF,ri和MCR,ri的值，將改進算法的性能。引入一個位置參數pos用來控制MF和MCR的更新位置，pos初始值為1，當 pos＞H ，則 pos=1，否則 pos每更新完一次則+1。MF,pos和MCR,pos的更新過程如下：

其中，SF和SCR是當前代中所有成功個體的相應控制參數信息。SF和SCR的數組大小等于當前代中成功個體的個數。當試向量Ui,G有一個更低的目標函數值（最小值優化問題）時，其相應的母個體的控制參數將保存在SF和SCR中，即Fi→SF，CRi→SCR。

其中，meanWA(·)是算術平均算子，meanWL(·)是Lehmer平均算子。wk為控制MF,i和MCR,i更新的權值，用于減緩進化過程中SCR和SCR可能偏于較小值的問題[18]。使用Δf來記錄成功個體的減少的函數值Δf(k)=fold(k)-fnew(k)，數組Δf的大小等于當前代中成功個體的數目。

3.3 算法的基本思想和步驟

變異策略DE/rand/1具有很強的全局收斂能力，卻有著較慢的收斂速度。傳統的Nelder-Mead方法具有優秀的局部收斂能力，卻有著很差的全局探測能力。怎樣在全局收斂性和局部搜索速度之間尋求一個平衡是本文的核心。對此，本文受Nelder-Mead方法啟發，提出了一種新型的變異策略。該策略既結合了rand/1的隨機性，又結合了Nelder-Mead方法的搜索方向的明確性，因此能在降低早熟收斂的可能性的同時提高算法的收斂速度。使用自適應參數調節方法進一步提升了算法的整體性能。具體步驟如下：

步驟1初始化H、縮放因子均值MF和交叉因子均值MCR。

步驟2根據公式（1）隨機產生初始種群并計算初始種群。

步驟3判定是否達到終止條件，若是轉步驟8，若否則轉步驟4。

步驟4按公式（7）和（8）隨機生成控制參數。

步驟5對每一靶個體，從當前種群中隨機抽取4個個體，比較它們的函數值，按公式（5）完成變異操作并按公式（2）完成交叉操作。

步驟6計算試向量的函數值并與靶個體比較，若好于靶個體，則替換靶個體。

步驟7根據公式（9）和（10）更新縮放因子均值MF和交叉因子均值MCR；返回步驟3。

步驟8輸出最優個體。

4 測試函數與參數設置

本文使用的算法使用Frotran90編寫，編譯環境為Intel Visual FORTRAN Composer XE 2013 with VS2010，在配置為2.83 GHz Intel?Core?2 Quad CPU和4 GB內存的計算機上運行，運行Windows 7系統。

4.1 測試函數

本文采用和文獻[19]相同的12個測試函數來進行測試算法的性能。 f1～f5為單峰函數，其中 f5為階梯函數，f6為噪音函數，f7～f12為多峰函數。值得注意的是，f4是Rosenbrock函數，當其維數D=2和3時，是單峰函數，但其在高維問題上存在多個極小值點[20]。測試函數的相關特性如表2所示。

表2 測試函數的名稱、維數、搜索空間和最優值

4.2 算法性能比較

為了使本文算法具有可比性，將RMDE與HSDE[12]，jDE[5]和SHADE[7]進行比較。參與比較的算法的參數與原文參數一致。對于上述12個問題，種群規模都設置為100。記錄獨立運行30次的平均值（Mean）和標準差（Std Dev）。為使實驗結果的比較具有統計性，使用Wilcoxon符號秩檢驗對各算法的實驗結果進行檢驗，使用符號“+”、“=”和“－”分別表示本文算法比目標算法在統計學上“顯著更好”、“沒有顯著的更好或更差”和“顯著更差”。為了增加測試結果的可讀性，將性能表現最好的實驗結果加粗顯示。實驗結果如表3所示，表中后3行分別統計了“+”、“=”和“－”的數目。

由表3可知，RMADE在單峰函數和多峰函數上的求解中都表現出了最好的性能。對于單峰函數 f1～f5，RMADE表現在函數 f3和 f4上相比其他算法具有顯著優勢，在噪音函數 f6的優化中，RMADE表現最佳，其次為SHADE、jDE表現最差，說明了本文的算法在求解噪音函數方面具有較好的抗干擾能力，這主要歸功于本文提出的反射變異策略在生成試向量的過程中使用了較多個體的信息。RMADE在多峰函數 f7～f12相比其他算法表現最佳，特別在求解函數 f8～f9中，RMADE相比表中其他算法具有顯著的優勢，說明RMADE具有不錯的全局收斂能力。需要注意的是，RMADE在對函數 f8的優化中在給定的較少函數評價次數的情況下能收斂到全局最優值，而其他算法均未完成收斂，說明RMADE相比參與比較的其他算法具有更快的收斂速度。總的來說，使用反射變異策略并結合3.2節中的參數自適應調整機制的RMADE能較好地平衡算法的探測和開發能力。

表3 RMADE和其他DE變體在12個測試函數上的測試結果

為了更直觀地對比各算法的收斂速度，繪制了各算法求解上述12個測試函數時的收斂過程曲線，如圖2所示。從圖中可以看出，RMADE在單峰函數和多峰函數下都具有最佳的收斂速度。RMADE與SHADE具有可比性，RMADE和SHADE使用相同的參數調整機制但RMADE的收斂速度比SHADE更好，這是由于RMADE采用的反射變異策略利用4個個體的信息去指導試向量的生成，并且將其中的最優個體和最劣個體的差分向量作為變異的方向，從某種程度上講反射變異策略屬于貪婪變異策略。

4.3 變異策略比較

為進一步考察本文提出的變異策略在探測和開發方面的性能，從表2中選取單峰函數 f1和多峰函數 f8作為測試函數，將本文提出的反射變異策略與表1中基本變異策略進行比較。為了保證比較的公平性，所有的變異策略使用二項式交叉策略，并使用3.2節描述的自適應參數方法。繪制兩種函數下的收斂過程曲線如圖3所示。

由圖3可知，對于單峰函數 f1，策略best/1的收斂速度最快、精度最高，其次就是本文提出的反射變異策略，rand/2的收斂速度最慢。對于多峰函數 f8，只有本文提出的反射變異策略在給定的函數評價次數下搜索到了全局最優值0，因此精度最高，其后為rand/1和rand/2。策略best/1、best/2和current-to-best/1在前期收斂速度快，但它們過于強調算法的開采能力而忽略了算法的探測性，因而陷入了早熟收斂。從總體上看，本文提出的反射變異策略既具有不錯的局部收斂速度，又具有良好的全局收斂能力。因此本文提出的反射變異策略相比其他基本的變異策略具有更好的性能，因而其的提出是有意義的。

4.4 自適應參數分析

縮放因子F和交叉因子CR的取值對算法的性能具有很大的影響，為了研究算法RMADE的參數自適應機制，繪制了12個測試函數下的控制參數進化曲線，如圖4所示。從圖4可以看出，兩參數的均值(MF和MCR)隨算法的進化而取不同的值，以滿足不同階段下的參數要求。算法求解的函數類型不同時，較優的參數取值亦不相同。相比縮放因子F，交叉因子CR對算法的收斂性有著更加重要的作用。當求解單峰函數時(f1～f5)，由圖2中可知，交叉因子CR隨著進化的進行變得越來越大。而在多峰函數(f7～f12)時，算法在搜索過程中會先后經歷兩個階段，即探測和開采。在探測階段，算法所需CR相對較小以滿足維持種群多樣性的要求，而當算法搜索到最優解的山谷時，則即將進入開采階段，此時算法所需的CR相對較大，以達到加速開采的目的。從圖2（g）、圖2（h）和圖2（l）中可以明顯地看到 CR 的這一變化過程。對噪音函數 f6的求解中，由于噪音元素為0～1之間的隨機數，因此噪音在搜索初期相對較小，可以看成普通單峰優化問題，隨著進化的進行，噪音干擾將變得越來越明顯，CR變大將更偏于隨機搜索。由圖4可知，本文所使用的參數調節機制能有效地調整算法各個進化階段下控制參數的值。

圖2 各算法收斂過程曲線比較

圖3 各變異策略在函數 f1和 f8下的收斂過程曲線

[3]張春美，陳杰，辛斌.參數適應性分布式差分進化算法[J].控制與決策，2014，29（4）：701-706.

[4]張錦華，宋來鎖，張元華，等.加權變異策略動態差分進化算法[J].計算機工程與應用，2017，53（4）：156-162.

[5]Brest J，Greiner S，Boskovic B，et al.Self-adapting control parameters in differential evolution：A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation，2006，10（6）：646-657.

[6]Zhang J，Sanderson A C.JADE：Adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.

[7]Tanabe R，Fukunaga A.Success-history based parameter adaptation for differential evolution[C]//IEEE Congress on Evolutionary Computation，2013：71-78.

[8]Wang Y，Cai Z，Zhang Q.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：55-66.

[9]Mallipeddi R，Suganthan P N，Pan Q K，et al.Differential evolution algorithm with ensemble of parameters and mutation strategies[J].Applied Soft Computing，2011，11（2）：1679-1696.

[10]Wu G，Mallipeddi R，Suganthan P N，et al.Differential evolution with multi-population based ensemble of mutation strategies[J].Information Sciences，2016，329（C）：329-345.

[11]Mohamed A W.An improved differential evolution algorithm with triangular mutation for global numerical optimization[J].Computers&Industrial Engineering，2015，85（C）：359-375.

[12]Yi W，Gao L，Li X，et al.A new differential evolution algorithm with a hybrid mutation operator and selfadapting control parameters for global optimization problems[J].Applied Intelligence，2015，42（4）：642-660.

[13]Yang M，Li C，Cai Z，et al.Differential evolution with auto-enhanced population diversity[J].IEEE Transactions on Cybernetics，2015，45（2）：302.

[14]Teo J.Differential evolution with self-adaptive populations[M]//Knowledge-Based Intelligent Information and Engineering Systems.Berlin Heidelberg：Springer，2005：1284-1290.

[15]Brest J，Mau?ec M S.Population size reduction for the differential evolution algorithm[J].Applied Intelligence，2008，29（3）：228-247.

[16]Tasoulis D K，Plagianakos V P，Vrahatis M N.Clustering in evolutionary algorithms to efficiently compute simultaneously local and global minima[C]//IEEE Congress on Evolutionary Computation，2005：1847-1854.

[17]Epitropakis M G，Plagianakos V P，Vrahatis M N.Balancing the exploration and exploitation capabilities of the differential evolution algorithm[C]//IEEE Congress on Evolutionary Computation，2008：2686-2693.

[18]Peng F，Tang K，Chen G，et al.Multi-start JADE with knowledge transfer for numerical optimization[C]//IEEE Congress on Evolutionary Computation，2009：1889-1895.

[19]李牧東，趙輝，翁興偉，等.基于最優高斯隨機游走和個體篩選策略的差分進化算法[J].控制與決策，2016，31（8）：1379-1386.

[20]Yao Xin，Lin Guangming，Liu Yong.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation，1999，3（2）：82-102.