基于控制參數雙峰分布的小種群差分進化算法

苗學良 陳旭

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

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

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

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

0 引言

差分進化（Differential Evolution，DE）算法是一種結構簡單且性能優異的全局優化算法，由Price&Storn提出。由于DE算法具有極好的魯棒性及易實現等特點，所以被廣泛應用于數據挖據、人工神經網絡和核工業等領域。

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

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

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

1.1 雙峰分布參數調節機制

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

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

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

其中，randci（θ，e）為柯西分布;縮放因子F的取值范圍為[0.1，1.5]，交叉概率因子CR取值范圍為[0，1]。通過前期數據仿真實驗，確定F中的。取值分別為0.65和1.5，F中的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）重新生成一個取值范圍內的值;若交叉概率因子CR取值為randci（0.95，0.1）中的值時，若其值超過取值范圍，則用randci（0.95，0.1）重新生成一個取值范圍內的值。

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

1.2 BiMDE算法流程

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

2 仿真實驗結果與分析

2.1 測試函數與實驗參數設置

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

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

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

2.2 算法比較

2.2.1 BiMDE算法與MDEVM算法比較

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

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

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

綜上所述，BiMDE算法與MDEVM算法相比，在不同變異策略、不同維度下均具有明顯優勢，體現了雙峰分布參數調節機制對比均勻分布參數調節機制的有效性。

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

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

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

其中，W表示BiMDE算法有優勢的函數個數，T表示兩種算法效果相似的函數個數，L表示MDEVM算法有優勢的函數個數。

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

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

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

2.3 BiMDE多樣性與收斂性分析

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

如圖2（a）、（c）、（c）、（g）所示，在多峰問題F2和F11上BiMDE與MDEVM相比，BiMDE收斂速度和精度更高。在函數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可快速收斂到最優解附近，因而其多樣性快速下降，而MDEVM/current-to-best/1一直保持相對較高的多樣性，收斂相對較慢。在多峰問題F11、F17和F27上，兩種MDEVM多樣性下降過快，而兩種BiMDE均可保持較好的值，因此在這3種復雜多峰問題上可保持較好的全局搜索能力，在中后期不會陷入局部最優導致的停滯。

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

3 結語

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

（1）BiMDE雙峰分布參數調節機制比MDEVM均勻分布參數調節機制在不同變異策略、不同維度下均具有顯著優勢。

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

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

以上3點表明雙峰參數調節機制在小種群DE上的有效性與BiMDE算法的優異性能。

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