基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法*

陳丹妮，趙劍冬，高 靜

(1.廣東技術(shù)師范大學(xué)計算機科學(xué)學(xué)院，廣東 廣州 510665；2.廣東恒電信息科技股份有限公司，廣東 廣州 510630)

1 引言

多模態(tài)優(yōu)化問題[1]是指優(yōu)化的問題存在多個局部或者全局最優(yōu)解，它普遍存在于我們的生活中，例如圖像分割、機械設(shè)計和電力系統(tǒng)規(guī)劃等。目前，群智能優(yōu)化算法是解決多模態(tài)優(yōu)化問題較為流行的一類方法。遺傳算法GA (Genetic Algorithm)[2]、模擬退火SA (Simulated Annealing)算法[3]、粒子群優(yōu)化PSO (Partical Swarm Optimization) 算法[4]、蟻群優(yōu)化ACO (Ant Colony Optimization) 算法[5]、螢火蟲算法FA (Firefly Algorithm)[6]、布谷鳥搜索CS (Cuckoo Search) 算法[7]、蝙蝠算法BA (Bat Algorithm)[8]、灰狼優(yōu)化GWO (Grey Wolf Optimizer) 算法[9]、多元宇宙優(yōu)化MVO (Multi-Verse Optimizer)算法[10]等群智能優(yōu)化算法均是模擬自然界的現(xiàn)象規(guī)律或者生物種群的社會生活而提出的。Salcedo-Sanz[11]通過對大量群智能優(yōu)化算法的研究，發(fā)現(xiàn)優(yōu)化算法想要取得良好表現(xiàn)的基礎(chǔ)是在勘探和探索之間取得平衡。而上述算法在優(yōu)化過程中較少關(guān)注勘探和探索兩者間的平衡，這可能限制了它們在多模態(tài)問題上的尋優(yōu)能力。為了彌補上述不足，學(xué)者們提出了不少改進方法[12 - 16]，包括混合算法、環(huán)拓撲、局部信息和小生境技術(shù)等。

Pierezan等[17]受郊狼對生存環(huán)境的適應(yīng)性及其社會結(jié)構(gòu)的啟發(fā)，在2018年提出了郊狼優(yōu)化算法COA (Coyote Optimization Algorithm)，該算法為在優(yōu)化過程中平衡探索和勘探提供了新的機制。郊狼優(yōu)化算法能有效地處理具有邊界約束的連續(xù)變量全局優(yōu)化問題。然而，在現(xiàn)實世界中很多優(yōu)化問題是多模態(tài)的，為了找到多模態(tài)問題的全局最優(yōu)解，要求算法具有跳出局部最優(yōu)的能力。在多模態(tài)情景下，郊狼優(yōu)化算法的收斂精度和穩(wěn)定性需要進一步提高。在此基礎(chǔ)上，受到小生境技術(shù)對其他群優(yōu)化算法的應(yīng)用效果啟發(fā)，本文提出了一種基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法DCCOA(Deterministic Crowding Coyote Optimization Algorithm)，旨在提高算法的收斂精度和穩(wěn)定性。

本文的其余部分組織如下：第2節(jié)主要介紹郊狼優(yōu)化算法和小生境技術(shù)的相關(guān)工作； 第3節(jié)詳細介紹本文提出的基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法；第4節(jié)對實驗結(jié)果進行理論分析；第5節(jié)給出結(jié)論和未來的研究工作。

2 相關(guān)工作

2.1 郊狼優(yōu)化算法

COA算法將郊狼的生存環(huán)境狀況視為優(yōu)化問題的變量，將郊狼對環(huán)境的適應(yīng)能力作為優(yōu)化目標。郊狼根據(jù)郊狼群組內(nèi)的信息共享和不同郊狼群組間的信息交流更新自身對社會狀況的認知，各個郊狼群組經(jīng)過多代郊狼的出生、交流、成長和死亡的更新迭代之后，整個郊狼群中環(huán)境適應(yīng)能力最強的郊狼將被作為優(yōu)化問題的最優(yōu)解。COA算法與GWO算法不同的是：GWO算法關(guān)注狼群的社會等級和捕獵過程，而COA算法則將關(guān)注點聚焦在郊狼之間的交流和社會結(jié)構(gòu)方面。

在國外，Güven?等[18]將COA算法應(yīng)用于風(fēng)力發(fā)電的經(jīng)濟調(diào)度問題上，結(jié)果表明郊狼優(yōu)化算法比遺傳算法和粒子群優(yōu)化算法具有更低的燃料消耗和更好的性能。此外，Qais等[19]使用COA算法建立了高精度的三極管光伏模型。與此同時，Pierezan等[20]將文化算法的一些概念引入COA中，提出了文化郊狼優(yōu)化算法，并將該算法應(yīng)用于重型燃氣輪機的運行。上述研究都將COA算法應(yīng)用于各種不同的實際問題。在國內(nèi)，張新明等[21]提出嵌入全局引導(dǎo)和相互作用的郊狼優(yōu)化算法，提升了COA算法的全局搜索能力，并應(yīng)用于醫(yī)學(xué)圖像增強中的參數(shù)優(yōu)化問題。此外，張新明等[22]還提出強化最優(yōu)和最差狼的郊狼優(yōu)化算法，通過引入全局最優(yōu)郊狼引導(dǎo)操作，并且在最優(yōu)郊狼的成長過程中嵌入一種隨機擾動，提升了算法的全局尋優(yōu)能力。與現(xiàn)有的群智能優(yōu)化算法相比，COA算法具有過程簡單、需要設(shè)定的參數(shù)較少等優(yōu)點。但是，面對多模態(tài)優(yōu)化問題時，COA算法的全局尋優(yōu)能力不足，收斂精度和穩(wěn)定性還有待提高。

2.2 小生境技術(shù)

1995年，Mahfoud[23]首次提出小生境技術(shù)，旨在促進遺傳算法形成并維持穩(wěn)定的亞群體。目前，小生境技術(shù)[24 - 26]主要包括適應(yīng)度共享、物種形成、擁擠和清除等方法。其中，適應(yīng)度共享、物種形成和清除方法都需要設(shè)置小生境參數(shù)，而且這些參數(shù)的設(shè)置需要先驗知識。 擁擠方法是最早也是最簡單的小生境技術(shù)之一，包括原始擁擠OC (Original Crowding)方法[24]、確定性擁擠DC (Deterministic Crowding)方法[23]和概率擁擠PC (Probabilistic Crowding)方法[27]。 其中，確定性擁擠方法因為不需要任何小生境參數(shù)，而更受歡迎。確定性擁擠DC方法隨機選擇2個個體作為父代(P1和P2)，隨后生成2個新生子代(C1和C2)。在子代替換父代之前，DC方法綜合考慮子代與父代彼此之間的距離和適應(yīng)度。因此，本文將確定性擁擠方法引入COA算法中。

Thomsen[28]在差分算法DE(Differential Evolution)中分別使用了適應(yīng)度共享方法(SharingDE算法)和確定性擁擠方法(CrowdingDE算法),實驗結(jié)果表明，CrowdingDE算法具有更好的穩(wěn)定性和收斂速度。為了解決多模態(tài)問題，Majumdar等[29]在入侵雜草優(yōu)化算法中引入了擁擠技術(shù)，結(jié)果表明該算法比其他標準多模態(tài)優(yōu)化算法具有更優(yōu)的收斂精度。除上述文獻之外，還有許多群智能優(yōu)化算法[30 - 33]使用DC方法來提高算法的收斂精度，跳出局部最優(yōu)，保持多樣性等。郊狼優(yōu)化算法也屬于群智能優(yōu)化算法。為此，本文提出了一種基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法(DCCOA)，旨在提升算法在多模態(tài)問題中的全局尋優(yōu)能力。

3 多模態(tài)郊狼優(yōu)化算法

基于COA算法，DCCOA算法有3個核心的改進部分：(1)新的郊狼進化機制；(2)新的郊狼群組文化趨勢計算方法；(3)郊狼更新社會狀況認知的新方法。DCCOA算法的流程如圖1所示。

Figure 1 Overall of DCCOA

3.1 新的郊狼進化機制

在COA算法中，每代中每個郊狼群組只產(chǎn)生一只新生郊狼，而且這只新生郊狼能否存活取決于該郊狼群組中其他郊狼對環(huán)境的適應(yīng)能力是否低于該新生郊狼。 然而，DCCOA算法采用確定性擁擠方法改進郊狼的進化機制。具體的步驟如下所示：

(1)從每個郊狼群組隨機選擇2只郊狼作為父代，記為P1和P2。

(2)在P1和P2郊狼和生活環(huán)境的影響下，產(chǎn)生2只新生郊狼作為子代，記為C1和C2。

(3)計算P1、P2、C1和C2郊狼對環(huán)境的適應(yīng)能力，記為f(P1)、f(P2)、f(C1)和f(C2)。

(4)根據(jù)式(1)計算父代和子代郊狼之間的歐氏距離，記為EdP1C1、EdP1C2、EdP2C1和EdP2C2。

(5)根據(jù)父代郊狼和子代郊狼的適應(yīng)能力和歐氏距離，采用確定性擁擠方法更新郊狼群組。

D維空間中，第b只郊狼的位置是Xb=(xb1，xb2，…,xbD)T，第d只郊狼的位置是Xd=(xd1，xd2，…,xdD)T，那么第b只郊狼和第d只郊狼之間的歐氏距離[34]為：

Edbd=‖Xb-Xd‖,b,d∈N

(1)

在新的郊狼進化機制內(nèi)，只有在競爭的子代郊狼具有更好的環(huán)境適應(yīng)能力情況下，它才能代替父代郊狼。 確定性擁擠方法是郊狼進化機制中的一個重要過程，它不僅保證了適應(yīng)環(huán)境能力較強的新生郊狼得到存活，還確保了距離更接近的父代郊狼被存活的新生郊狼取代，以此來提升算法在多模態(tài)問題中的全局尋優(yōu)能力。

3.2 新的郊狼群組文化趨勢計算方法

除了提出新的郊狼進化機制，DCCOA算法還改進了郊狼群組文化趨勢的計算方法。COA算法把每個郊狼群組中所有郊狼對環(huán)境適應(yīng)能力的中位數(shù)作為該郊狼群組的文化趨勢。 雖然中位數(shù)有著不容易受到極端值影響的優(yōu)點，但它并不能全面地反映總體情況。算術(shù)平均值是由總體數(shù)據(jù)計算得出的，它具有優(yōu)良的數(shù)學(xué)性質(zhì)，是實際應(yīng)用中使用最廣泛的趨勢測量方法。本文考慮到在郊狼群體生活中，每只郊狼都會對其群組的文化趨勢有所影響，因此定義郊狼群的文化趨勢計算方法如式(2)所示：

(2)

3.3 郊狼更新社會狀況認知的新方法

對于郊狼這個物種而言，每個郊狼群組中通常有2只阿爾法郊狼(α)，然而COA算法在每個郊狼群中只定義了1只阿爾法郊狼。為了更真實地模擬郊狼物種的社會生活，DCCOA算法在每個郊狼群組中定義了2只阿爾法郊狼(α1和α2)，它們是在每個郊狼群組中對環(huán)境適應(yīng)能力最強的2只郊狼?？紤]到最小化問題，在t時刻第p個郊狼群的α1和α2定義如式(3)和式(4)所示：

(3)

(4)

(5)

其中，ω1和ω2分別表示阿爾法郊狼α1和α2在其郊狼群組中對δ1的影響權(quán)重。經(jīng)過多次調(diào)參實驗測試，ω1和ω2的值設(shè)為0.8和0.2時效果最優(yōu)。

此外，COA算法在更新郊狼對社會狀況的認知時，設(shè)定阿爾法郊狼的影響(δ1)和郊狼群組文化趨勢的影響(δ2)是隨機的。然而，在郊狼種群的社會生活中，這兩者的影響權(quán)重并非隨機數(shù)。一般來說，阿爾法郊狼是每個郊狼群組中的強者，它們在郊狼更新對社會狀況的認知過程中有著較大的影響，而郊狼群組的文化趨勢影響則是潛移默化的，因此，在本文算法中，郊狼更新社會狀況認知的方式如式(6)所示：

(6)

其中，λ1和λ2分別表示δ1和δ2的影響權(quán)重。經(jīng)過多次實驗測試，λ1和λ2的值設(shè)置為0.7和0.05時效果最佳。這也意味著在郊狼更新對社會狀況認知時，相比郊狼群組的文化趨勢影響，阿爾法狼有著更大的影響權(quán)重。

4 實驗對比

4.1 實驗設(shè)置與基準函數(shù)

為了評估本文提出的DCCOA算法的性能，將其與COA、PSO、GA、FA、CS、BA和MVO算法進行不同決策變量維數(shù)的多次實驗對比。其中根據(jù)文獻[17]將DCCOA和COA的參數(shù)Np和Nc分別設(shè)置為20和5，即郊狼總數(shù)為100。其他算法直接使用相應(yīng)文獻設(shè)定的參數(shù)。實驗選擇了8個典型的基準函數(shù)，具體如表1所示。為了驗證算法在多模態(tài)問題中的全局尋優(yōu)能力，8個基準函數(shù)包含2個單峰函數(shù)(F1和F2)和6個多峰函數(shù)(F3～F8),其中函數(shù)表達式中的n表示決策變量維數(shù)。

Table 1 List of benchmark functions used in the experiment

在上述基準函數(shù)上，8個算法分別在10維、50維和100維這3個不同決策變量維數(shù)上各獨立進行50次實驗。其中，當決策變量的維數(shù)為10維、50維和100維時，各算法的迭代次數(shù)分別為1 000次、2 000次和3 000次。實驗的硬件環(huán)境為：Intel(R) Core(TM) i5-4210U CPU @ 1.70 GHz,4 GB內(nèi)存。軟件環(huán)境為：64位的Windows 10，Python 3.7.0。

實驗采用最小值、最大值、均值和方差這4個指標來衡量算法的性能。其中最小值和最大值分別代表在50次實驗中各算法能夠找到函數(shù)全局最優(yōu)解的最好表現(xiàn)和最差表現(xiàn)；均值代表50次實驗中各算法的平均表現(xiàn)；方差代表各算法在實驗中的穩(wěn)定性。

4.2 性能評估與理論分析

表2匯總了在不同決策變量維數(shù)下，8個算法在基準函數(shù)上的收斂精度和穩(wěn)定性的統(tǒng)計結(jié)果，其中，對最佳結(jié)果進行加粗顯示。實驗結(jié)果表明，在3個不同的決策變量維數(shù)上，DCCOA算法在多個基準函數(shù)上的性能均優(yōu)于COA算法的。DCCOA算法表現(xiàn)出更好的收斂精度和更強的穩(wěn)定性，最優(yōu)表現(xiàn)時將收斂精度和穩(wěn)定性提高了4個數(shù)量級。

從收斂精度的角度來看，總體上，在多模態(tài)函數(shù)上DCCOA算法的表現(xiàn)更佳，在單模態(tài)函數(shù)上FA、CS和PSO算法的表現(xiàn)較優(yōu)。對于F1函數(shù)，當決策變量維數(shù)為10時，DCCOA算法的收斂效果是最好的，這是因為在較低維數(shù)下，將平均值作為文化趨勢更有效地體現(xiàn)了每個郊狼群組中所有郊狼對社會狀況的認知對該郊狼群組的文化趨勢都有所貢獻。但是，隨著維數(shù)的上升，它的性能有所下降，此時，F(xiàn)A算法和CS算法的表現(xiàn)更勝一籌。這是由于布谷鳥搜索算法采用了隨機游走的萊維飛行操作和螢火蟲采用了相對亮度的引領(lǐng)操作，這讓它們在高維數(shù)的連續(xù)單模態(tài)曲面有更好的收斂精度。對于F2函數(shù)，PSO算法的表現(xiàn)較佳，這是因為粒子群體在尋優(yōu)過程中會將歷史最優(yōu)位置進行記憶并傳達給其他粒子，這讓其在單模態(tài)函數(shù)上具有較大的優(yōu)勢。這一優(yōu)勢也讓PSO算法在低維數(shù)的多模態(tài)F6函數(shù)上具有良好的表現(xiàn)。對于F3～F8函數(shù)，DCCOA算法展示出了很好的收斂效果，尤其在高度多模態(tài)F5和F7函數(shù)上以及搜索難度較大的F8函數(shù)上，它的收斂精度優(yōu)于其他幾個算法。這是因為小生境技術(shù)的引入，進一步促進算法在尋優(yōu)過程中平衡勘探和探索，從而提升算法跳出局部最優(yōu)的能力。同時，更新郊狼對社會狀況認知的新方法更真實地模擬了郊狼的種群生活，也有利于更好地尋找全局最優(yōu)解。

從穩(wěn)定性的角度來看，CS算法在單模態(tài)F1函數(shù)上展示出了較強的穩(wěn)定性。這是因為布谷鳥算法在光滑曲面上通過不斷隨機行走可以逐步接近全局最優(yōu)解。在單模態(tài)F2函數(shù)上PSO算法具有較佳的穩(wěn)定性。這是因為粒子在優(yōu)化過程中充分利用自身信息和群體信息，在求解單模態(tài)問題時具有優(yōu)異特性。對于多模態(tài)F3～F8函數(shù)，DCCOA算法表現(xiàn)出較強的穩(wěn)定性，這是由于新的郊狼進化機制采用了確定性擁擠方法，它不僅保證了適應(yīng)環(huán)境能力較強的新生郊狼的存活，而且還確保離新生郊狼較近的父代郊狼被替代，有利于維持郊狼的多樣性，提升算法在多模態(tài)問題上的穩(wěn)定性。同時，新的更新郊狼對社會狀況認知的方法采用權(quán)重法和定義2只阿爾法郊狼，這都更符合郊狼的真實種群生活，對算法穩(wěn)定性的提升有所貢獻。此外，F(xiàn)A算法在F4函數(shù)上也展現(xiàn)了較好的穩(wěn)定性，這是由于在更新螢火蟲時同時考慮了確定性因素和隨機因素。

從收斂曲線的角度來看，整體上，BA算法和PSO算法最容易陷入問題的局部最優(yōu)解，與此同時，BA有著更快的收斂速度；DCCOA算法和COA算法的表現(xiàn)相對穩(wěn)定。在單模態(tài)函數(shù)上，8個算法在較低決策變量維數(shù)的表現(xiàn)沒有太大的差異，但是隨著維數(shù)的上升，PSO算法的性能有明顯下降。在多模態(tài)函數(shù)上，PSO算法跳出局部最優(yōu)的能力較差，這是因為它在尋優(yōu)過程的勘探和探索之間沒有取得平衡。BA算法雖然展示出了較快的收斂速度，但是它同樣容易陷入問題的局部最優(yōu)解。相比COA算法，DCCOA算法在大多數(shù)情況下展示出稍快的收斂趨勢和較優(yōu)的收斂精度。這是因為新的郊狼進化機制采用了確定性擁擠方法，它有利于進一步促進算法在勘探和探索之間的平衡，從而提升算法在多模態(tài)問題中的全局尋優(yōu)性能。

5 結(jié)束語

為了解決多模態(tài)優(yōu)化問題，本文提出了一種基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法(DCCOA)。該算法對COA算法做了3方面的改進，具體包括新的郊狼進化機制、新的郊狼群組文化趨勢計算方法和郊狼更新對社會狀況認知的新方法。為了評價DCCOA的性能，將其與COA、PSO、GA、FA、CS、BA和MVO算法在多個基準函數(shù)上進行實驗。實驗結(jié)果表明，相比COA算法，本文算法展示出更高的收斂精度、更快的收斂速度和更強的穩(wěn)定性。本文證明了將確定性擁擠方法應(yīng)用到郊狼優(yōu)化算法上可進一步提升算法在勘探和探索之間的平衡能力，從而提升算法在多模態(tài)情況下的全局尋優(yōu)能力。這是因為在更新郊狼群時，距離相近并且對環(huán)境適應(yīng)能力較差的郊狼被淘汰。然而，本文還存在許多局限性，其中之一就是算法的計算時間相對較長。因此，在之后的工作中，將打算用平行策略進行搜索，以縮短算法尋優(yōu)時間。

Table 2 Experimental results of eight algorithms on benchmark functions

續(xù)表