基于控制參數(shù)雙峰分布的小種群差分進(jìn)化算法

苗學(xué)良 陳旭

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

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

DOI：10.11907/rjdk.192142 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）006-0074-05

0 引言

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

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

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

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

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

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

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

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

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

縮放因子F的雙峰分布具體取值方法為：當(dāng)縮放因子F取值為randci（0.65，0.1）中的值時(shí)，若其值小于0.1，則將值截?cái)酁?.1;若其值大于1時(shí)，則將值截?cái)酁閘。當(dāng)縮放因子F取值為randci（1.5，0.1）中的值時(shí)，若其值小于l，則截?cái)酁?;若其值大于1.5時(shí)，將值截?cái)酁?.5。

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

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

1.2 BiMDE算法流程

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

2 仿真實(shí)驗(yàn)結(jié)果與分析

2.1 測試函數(shù)與實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

2.2 算法比較

2.2.1 BiMDE算法與MDEVM算法比較

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

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

此外，BiMDE與MDEVM相比，在不同維度下均更有優(yōu)勢。例如，當(dāng)D=10時(shí)，BiMDE/rand/1與MDEVM/rand/1相比在21組函數(shù)上有優(yōu)勢，僅在3組上有劣勢;當(dāng)D=30時(shí)，BiMDE/rand/1與MDEVM/rand/1相比，在21組函數(shù)上有優(yōu)勢，僅在2組上有劣勢;當(dāng)D=50時(shí)，BiMDE/rand/1與MDEVM/rand/1相比在2l組函數(shù)上有優(yōu)勢，僅在3組上有劣勢;當(dāng)D=100時(shí)，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)勢。維度越高代表問題的復(fù)雜程度越高，算法在不同維度的分析有助于檢驗(yàn)算法維度擴(kuò)展性，所以BiMDE算法具有很好的維度擴(kuò)展性。

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

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

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

首先，將BiMDE與DESP、EMDE和OEMDE進(jìn)行比較。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ù)個(gè)數(shù)，T表示兩種算法效果相似的函數(shù)個(gè)數(shù)，L表示MDEVM算法有優(yōu)勢的函數(shù)個(gè)數(shù)。

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

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

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

2.3 BiMDE多樣性與收斂性分析

選取D=30時(shí)BiMDE系列算法中的BiMDE/rand/1和BiMDE/current-to-best/1，分別與MDEVM系列算法中MDEVM/rand/1和MDEVM/current-to-best/1在收斂性、多樣性上進(jìn)行對比。收斂速度通過最優(yōu)值下降速度體現(xiàn)，多樣性評價(jià)指標(biāo)如式（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收斂慢，但在中期時(shí)收斂速度加快且精度也有所提高;而BiMDE/current-to-best/1比MDEVM/current-to-best/1擁有更好的收斂速度與精度。

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

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

3 結(jié)語

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

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

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

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

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

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