苗學良 陳旭

摘要：當前差分進化算法研究主要集中在常規(guī)種群上，對小種群差分進化（DE）算法的研究較少。小種群差分進化算法因種群規(guī)模小，存在多樣性降低過快的問題。因此提出一種基于控制參數(shù)雙峰分布的小種群差分進化算法（BiMDE）。該算法采用基于柯西雙峰分布的參數(shù)調(diào)節(jié)機制處理變異縮放因子F和交叉概率因子CR，并對縮放因子F進行矢量化設定。將BiMDE算法在函數(shù)集CEC2014上進行測試，并與5種最新的小種群差分進化算法進行比較。結(jié)果表明，BiMDE算法在求解精度、收斂速度以及多樣性保持上具有較大優(yōu)勢。

關鍵詞：差分進化;小種群;控制參數(shù);雙峰分布;多樣性

DOI：10.11907/rjdk.192142 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）006-0074-05

0 引言

差分進化（Differential Evolution，DE）算法是一種結(jié)構(gòu)簡單且性能優(yōu)異的全局優(yōu)化算法，由Price&Storn提出。由于DE算法具有極好的魯棒性及易實現(xiàn)等特點，所以被廣泛應用于數(shù)據(jù)挖據(jù)、人工神經(jīng)網(wǎng)絡和核工業(yè)等領域。

種群數(shù)目對DE算法的最終優(yōu)化效果影響很大。種群數(shù)目多時，DE算法具有更好的種群多樣性，從而為算法提供更好的全局搜索能力，且可減少陷入停滯和局部極值的可能性。但同時單次迭代需更多的評估，占用大量內(nèi)存，因此不適用于內(nèi)存小且實時性要求高的應用場景。近年來小種群DE（Micro-DE）算法引起研究者關注。Micro-DE算法種群大小取值一般小于10，因而具有硬件需求較低和內(nèi)存需求較小的優(yōu)勢，在嵌入式系統(tǒng)有更好的應用前景。但是種群數(shù)目少也帶來問題，如使種群易于收斂到局部最優(yōu)解附近，從而導致過早收斂與停滯;此外，還會使種群多樣性降低過快，子代個體會因為跳不出局部最優(yōu)解而不能獲取更好的優(yōu)化結(jié)果。因此研究者們進行了相應改進。如Xuan等提出一種擁有新型變異策略的小種群DE算法（DESP），該算法在DE/randl/bin的基礎上增加一個擾動策略，同時提出一種判斷機制以調(diào)節(jié)擾動幅度，有效解決了小種群DE算法過早收斂停滯的問題;Brown等在JADE的基礎上提出了一種自適應小種群DE算法（uJADE），該算法通過改進變異策略、引進重啟和擾動機制，使優(yōu)化效果得到明顯提高;Salehinejad等提出矢量化的小種群DE算法（MDEVM），該算法將縮放因子F矢量化應用到小種群DE算法中，解決了小種群DE多樣性降低過快問題，并引入并行機制以增強算法運行效率;一年后，Salehineiad等又提出了一種多種變異策略自適應的小種群DE算法（EMDE），該算法在MDEVM的基礎上將5種典型的差分變異策略用隨機選擇的方式加入到算法差分變異中;隨后再次進行改進，提出了一種新的逆向?qū)W習的多策略自適應小種群DE算法（OEMDE），該算法在EMDE的基礎引入了逆向?qū)W習機制，逆向?qū)W習機制中的逆向群體初始化和逆向群體跳轉(zhuǎn)可有效利用群體和逆向群體中的信息。還有研究者發(fā)現(xiàn)可通過調(diào)節(jié)參數(shù)、增強種群多樣性緩解Micro-DE算法因種群個體數(shù)目少引起的過早收斂和停滯等問題。

綜上所述，本文設計一種基于雙峰矢量分布的縮放因子F與雙峰分布的交叉概率因子CR的參數(shù)自調(diào)節(jié)機制，使小種群DE算法在快速收斂的同時保持較好的多樣性，從而獲得更好的優(yōu)化結(jié)果。

1 控制參數(shù)雙峰分布的小種群DE算法

1.1 雙峰分布參數(shù)調(diào)節(jié)機制

雙峰分布調(diào)節(jié)機制最早由Wang等在常規(guī)種群DE算法研究中提出，該機制特點是運用雙峰分布的縮放因子F和交叉概率因子CR，使算法可平衡全局搜索與局部搜索能力。

為解決小種群DE算法多樣性降低過快的問題，本文將雙峰分布參數(shù)調(diào)節(jié)機制引入到小種群DE算法中，將縮放因子F矢量化，從而增強小種群DE算法多樣性。

在BiMDE算法中對縮放因子F和對交叉概率因子CR的具體設置為：

其中，randci（θ，e）為柯西分布;縮放因子F的取值范圍為[0.1，1.5]，交叉概率因子CR取值范圍為[0，1]。通過前期數(shù)據(jù)仿真實驗，確定F中的。取值分別為0.65和1.5，F(xiàn)中的e取值為0.1;CR中的θ取值分別為0.1和0.95，CR中的e取值為0.1。

縮放因子F的雙峰分布具體取值方法為：當縮放因子F取值為randci（0.65，0.1）中的值時，若其值小于0.1，則將值截斷為0.1;若其值大于1時，則將值截斷為l。當縮放因子F取值為randci（1.5，0.1）中的值時，若其值小于l，則截斷為1;若其值大于1.5時，將值截斷為1.5。

交叉概率因子CR雙峰分布具體取值方法為：當交叉概率因子CR取值為randci（0.1，0.1）中的值時，若其值超過取值范圍，則采用randci（0.1，0.1）重新生成一個取值范圍內(nèi)的值;若交叉概率因子CR取值為randci（0.95，0.1）中的值時，若其值超過取值范圍，則用randci（0.95，0.1）重新生成一個取值范圍內(nèi)的值。

在DE算法參數(shù)中，縮放因子F和交叉概率因子CR對優(yōu)化結(jié)果影響較大，縮放因子F越大，全局優(yōu)化效果越好，縮放因子F越小，局部優(yōu)化效果越好;交叉概率因子CR越大，種群多樣性越好，交叉概率因子CR越小，種群多樣性越差。在設計雙峰分布矢量化縮放因子F時充分考慮全局搜索和局部搜索能力的平衡，所以選用柯西分布及對超過取值范圍的值采用截斷操作，使其取值主要集中在兩個值附近，在保證全局搜索的同時兼顧局部搜索，從而使優(yōu)化效果更好，如式（2）所示。小種群DE算法種群多樣性丟失過快是影響優(yōu)化效果的主要原因，雖然較大的交叉概率因子CR會增強種群個體多樣性，但一直使用較大的交叉概率因子CR會使子代個體從父代個體中繼承的信息少，含有較多父代信息的子代個體將被丟失，從而影響最終優(yōu)化結(jié)果。因此在對交叉概率因子CR進行設計時需充分考慮該情況，設定一種雙峰柯西分布設計，如式（3）所示。

1.2 BiMDE算法流程

將雙峰分布參數(shù)調(diào)節(jié)機制引入Micro-DE算法，可得到基于控制參數(shù)雙峰分布的Micro-DE算法（Micro DEBased on Bimodal Distribution of Control Parameters.BiMDE）。采用變異策略a/b的BiMDE記為BiMDE/a/b。

2 仿真實驗結(jié)果與分析

2.1 測試函數(shù)與實驗參數(shù)設置

實驗采用CEC2014測試函數(shù)集。在CEC2014中共有30個測試函數(shù)，分別為C1：3個單峰函數(shù)F1-F3、G2：13個簡單多峰函數(shù)F4-F16、G3：6個混合函數(shù)F17～F22和G4：8個組合函數(shù)F23～F30。根據(jù)CEC2014的要求，每個測試函數(shù)運行51次并記錄統(tǒng)計結(jié)果。

根據(jù)文獻，本文所有小種群DE算法的種群個數(shù)Np全部設為8;DE算法中的縮放因子F和交叉概率因子CR全部按照文獻中算法的值設定;將最大計算代價（maxFES）按文獻設為2000xD。為了更好地了解算法運行狀態(tài)及檢驗算法是否適用于不同維度，在D=10、D=30、D=50、D=100四個維度對算法進行測試和數(shù)據(jù)分析。

本文仿真實驗中的各種DE算法采用MATLAB語言實現(xiàn)，軟件為MATLAB2014a。運行環(huán)境為：Windows 7，雙核3.9GHz CPU，4GB內(nèi)存。

2.2 算法比較

2.2.1 BiMDE算法與MDEVM算法比較

選取DE算法中5種典型變異策略，分別采用BiMDE與MDEVM方法在CEC2014的4類函數(shù)上進行Wilcoxon秩和檢驗對比，然后從各維度分析兩類算法優(yōu)缺點。選用DE/a/b策略的MDEVM算法，記為MDEVM/a/b。

如表1所示，BiMDE與MDEVM在相同維度時相比，在5種不同變異策略下BiMDE均有明顯優(yōu)勢。例如，當D=10時，BiMDE/rand/1與MDEVM/rand/1相比，在2l組函數(shù)上有優(yōu)勢，僅在3組上有劣勢;當D=10時，BiMDE/rand/2與MDEVM/rand/2相比，在25組函數(shù)上有優(yōu)勢，僅在1組上有劣勢;同樣當D=10時，在best/1、best/2和current-to-best/1這3種變異策略下，與MDEVM算法相比，BiMDE算法有絕對優(yōu)勢。

此外，BiMDE與MDEVM相比，在不同維度下均更有優(yōu)勢。例如，當D=10時，BiMDE/rand/1與MDEVM/rand/1相比在21組函數(shù)上有優(yōu)勢，僅在3組上有劣勢;當D=30時，BiMDE/rand/1與MDEVM/rand/1相比，在21組函數(shù)上有優(yōu)勢，僅在2組上有劣勢;當D=50時，BiMDE/rand/1與MDEVM/rand/1相比在2l組函數(shù)上有優(yōu)勢，僅在3組上有劣勢;當D=100時，BiMDE/rand/1與MDEVM/rand/1相比，在2l組函數(shù)上有優(yōu)勢，僅在4組上有劣勢。在不同維度下，均利用另外4種變異策略rand/2、best/1、best/2和current-to-best/1，與MDEVM算法相比，BiMDE算法有絕對優(yōu)勢。維度越高代表問題的復雜程度越高，算法在不同維度的分析有助于檢驗算法維度擴展性，所以BiMDE算法具有很好的維度擴展性。

綜上所述，BiMDE算法與MDEVM算法相比，在不同變異策略、不同維度下均具有明顯優(yōu)勢，體現(xiàn)了雙峰分布參數(shù)調(diào)節(jié)機制對比均勻分布參數(shù)調(diào)節(jié)機制的有效性。

2.2.2 BiMDE算法與其它小種群DE算法比較

將BiMDE系列算法中性能最優(yōu)異的BiMDE/rand/1和BiMDE/current-to-best/1算法分別與另外4種小種群DE算法進行比較，包括：EMDE、OEMDE、DESP和uJADE。在CEC2014的30組測試函數(shù)上進行Wilcoxon秩和檢驗，對比結(jié)果如表2所示。

首先，將BiMDE與DESP、EMDE和OEMDE進行比較。BiMDE與DESP相比，在不同維度下，至少在24組函數(shù)上有顯著優(yōu)勢;BiMDE與EMDE相比，在不同維度下，至少在17組函數(shù)上有顯著優(yōu)勢;BiMDE與OEMDE相比，在不同維度下，至少在24組函數(shù)上有明顯優(yōu)勢。綜合可知，BiMDE算法相較于DESP、EMDE、OEMDE算法，在不同維度均表現(xiàn)出絕對優(yōu)勢。

其中，W表示BiMDE算法有優(yōu)勢的函數(shù)個數(shù)，T表示兩種算法效果相似的函數(shù)個數(shù)，L表示MDEVM算法有優(yōu)勢的函數(shù)個數(shù)。

“w”表示BiMDE算法有優(yōu)勢的函數(shù)個數(shù)，“T”表示兩種算法效果相似的函數(shù)個數(shù)，“L”表示其它小種群DE算法有優(yōu)勢的函數(shù)個數(shù)。

其次，將BiMDE與uJADE進行比較。uJADE加入位置擾動、個體重啟策略和帶有存檔功能的變異策略，是一種性能非常優(yōu)異的小種群DE算法。由表2可以看出，在低維度下BiMDE劣于uJADE。然而，隨著維度的上升，BiMDE比uJADE表現(xiàn)更好。例如，當D=10時，BiMDE/current-to-best/1與uJADE相比，在13組函數(shù)中占有優(yōu)勢，在15組函數(shù)中處于劣勢;當D=30時，BiMDE/current-to-best/1與uJADE相比，在13組函數(shù)中占有優(yōu)勢，但劣勢函數(shù)下降到了組;當D=50時，BiMDE/current-to-best/1與uJADE相比，有優(yōu)勢的函數(shù)組數(shù)上升到15組;當D=100時，BiMD E/current-to-best/1與uJADE相比，有優(yōu)勢的函數(shù)組數(shù)達到了18組。值得注意的是，uJADE在低維度下的優(yōu)勢是由于其采用的位置擾動、個體重啟與新式變異等策略，這些策略的引人大幅增加了uJADE復雜度。BiMDE簡潔性好，并且隨著維度的上升更有優(yōu)勢，因而對復雜問題更有潛力。

由以上分析可知，BiMDE與DESP、EMDE和OEMDE在不同維度上進行對比，均表現(xiàn)出明顯優(yōu)勢。與uJADE相比，BiMDE在高維度下更簡潔、優(yōu)勢更明顯。

2.3 BiMDE多樣性與收斂性分析

選取D=30時BiMDE系列算法中的BiMDE/rand/1和BiMDE/current-to-best/1，分別與MDEVM系列算法中MDEVM/rand/1和MDEVM/current-to-best/1在收斂性、多樣性上進行對比。收斂速度通過最優(yōu)值下降速度體現(xiàn)，多樣性評價指標如式（4）所示。圖2（a）、（c）、（e）、（g）分別為單峰測試函數(shù)F2、簡單多峰測試函數(shù)F11、混合測試函數(shù)F17、合成測試函數(shù)F27的收斂狀態(tài);（b）、（d）、（f）、（h）分別展示這4組測試函數(shù)多樣性。

如圖2（a）、（c）、（c）、（g）所示，在多峰問題F2和F11上BiMDE與MDEVM相比，BiMDE收斂速度和精度更高。在函數(shù)F17和F27上，BiMDE/rand/1在前期比MDEVM/rand/1收斂慢，但在中期時收斂速度加快且精度也有所提高;而BiMDE/current-to-best/1比MDEVM/current-to-best/1擁有更好的收斂速度與精度。

如圖2（b）、（d）、（f）、（h）所示，在單峰問題F2上，前期兩種BiMDE與兩種MDEVM多樣性相似，在中后期時BiMDE/current-to-best/1可快速收斂到最優(yōu)解附近，因而其多樣性快速下降，而MDEVM/current-to-best/1一直保持相對較高的多樣性，收斂相對較慢。在多峰問題F11、F17和F27上，兩種MDEVM多樣性下降過快，而兩種BiMDE均可保持較好的值，因此在這3種復雜多峰問題上可保持較好的全局搜索能力，在中后期不會陷入局部最優(yōu)導致的停滯。

綜上分析可知，與MDEVM算法相比，BiMDE算法在處理不同類型問題時均擁有較好的收斂速度與精度：在單峰問題上可快速找到近似最優(yōu)解，多樣性下降較快;在多峰問題上可保持較高的多樣性以加強全局搜索能力。

3 結(jié)語

本文設計了一種雙峰柯西分布的參數(shù)調(diào)節(jié)機制以解決小種群DE算法多樣性降低過快問題，并提出了BiMDE算法。將BiMDE算法與MDEVM、DESP、EMDE、OEMDE、uJADE算法在計算代價較小的情況下進行比較，得到如下結(jié)論：

（1）BiMDE雙峰分布參數(shù)調(diào)節(jié)機制比MDEVM均勻分布參數(shù)調(diào)節(jié)機制在不同變異策略、不同維度下均具有顯著優(yōu)勢。

（2）BiMDE算法與DESP、EMDE、OEMDE、uJADE等小種群DE算法相比，未引入過多策略，簡潔性更好。在所有維度下BiMDE均優(yōu)于DESP、EMDE和OEMDE。在高維度下BiMDE算法優(yōu)于uJADE。

（3）在不同類型問題上BiMDE均擁有較好的收斂性和多樣性。

以上3點表明雙峰參數(shù)調(diào)節(jié)機制在小種群DE上的有效性與BiMDE算法的優(yōu)異性能。

盡管BiMDE算法比已有的小種群差分進化算法優(yōu)勢更大，但不同變異策略的BiMDE算法對不同類型的問題優(yōu)化效果不同。下一步可通過分析不同變異策略的BiMDE算法優(yōu)缺點，設計變異策略自適應的小種群DE算法。此外，還可將BiMDE算法應用于實際工程問題，以期進一步改進算法。