陳丹妮，趙劍冬，高 靜

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

1 引言

多模態(tài)優(yōu)化問題[1]是指優(yōu)化的問題存在多個(gè)局部或者全局最優(yōu)解，它普遍存在于我們的生活中，例如圖像分割、機(jī)械設(shè)計(jì)和電力系統(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ī)律或者生物種群的社會(huì)生活而提出的。Salcedo-Sanz[11]通過對(duì)大量群智能優(yōu)化算法的研究，發(fā)現(xiàn)優(yōu)化算法想要取得良好表現(xiàn)的基礎(chǔ)是在勘探和探索之間取得平衡。而上述算法在優(yōu)化過程中較少關(guān)注勘探和探索兩者間的平衡，這可能限制了它們?cè)诙嗄B(tài)問題上的尋優(yōu)能力。為了彌補(bǔ)上述不足，學(xué)者們提出了不少改進(jìn)方法[12 - 16]，包括混合算法、環(huán)拓?fù)?、局部信息和小生境技術(shù)等。

Pierezan等[17]受郊狼對(duì)生存環(huán)境的適應(yīng)性及其社會(huì)結(jié)構(gòu)的啟發(fā)，在2018年提出了郊狼優(yōu)化算法COA (Coyote Optimization Algorithm)，該算法為在優(yōu)化過程中平衡探索和勘探提供了新的機(jī)制。郊狼優(yōu)化算法能有效地處理具有邊界約束的連續(xù)變量全局優(yōu)化問題。然而，在現(xiàn)實(shí)世界中很多優(yōu)化問題是多模態(tài)的，為了找到多模態(tài)問題的全局最優(yōu)解，要求算法具有跳出局部最優(yōu)的能力。在多模態(tài)情景下，郊狼優(yōu)化算法的收斂精度和穩(wěn)定性需要進(jìn)一步提高。在此基礎(chǔ)上，受到小生境技術(shù)對(duì)其他群優(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é)詳細(xì)介紹本文提出的基于確定性擁擠的多模態(tài)郊狼優(yōu)化算法；第4節(jié)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行理論分析；第5節(jié)給出結(jié)論和未來的研究工作。

2 相關(guān)工作

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

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

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

2.2 小生境技術(shù)

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

Thomsen[28]在差分算法DE(Differential Evolution)中分別使用了適應(yīng)度共享方法(SharingDE算法)和確定性擁擠方法(CrowdingDE算法),實(shí)驗(yàn)結(jié)果表明，CrowdingDE算法具有更好的穩(wěn)定性和收斂速度。為了解決多模態(tài)問題，Majumdar等[29]在入侵雜草優(yōu)化算法中引入了擁擠技術(shù)，結(jié)果表明該算法比其他標(biāo)準(zhǔn)多模態(tài)優(yōu)化算法具有更優(yōu)的收斂精度。除上述文獻(xiàn)之外，還有許多群智能優(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個(gè)核心的改進(jìn)部分：(1)新的郊狼進(jìn)化機(jī)制；(2)新的郊狼群組文化趨勢(shì)計(jì)算方法；(3)郊狼更新社會(huì)狀況認(rèn)知的新方法。DCCOA算法的流程如圖1所示。

Figure 1 Overall of DCCOA

3.1 新的郊狼進(jìn)化機(jī)制

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

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

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

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

(4)根據(jù)式(1)計(jì)算父代和子代郊狼之間的歐氏距離，記為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)

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

3.2 新的郊狼群組文化趨勢(shì)計(jì)算方法

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

(2)

3.3 郊狼更新社會(huì)狀況認(rèn)知的新方法

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

(3)

(4)

(5)

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

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

(6)

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

4 實(shí)驗(yàn)對(duì)比

4.1 實(shí)驗(yàn)設(shè)置與基準(zhǔn)函數(shù)

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

Table 1 List of benchmark functions used in the experiment

在上述基準(zhǔn)函數(shù)上，8個(gè)算法分別在10維、50維和100維這3個(gè)不同決策變量維數(shù)上各獨(dú)立進(jìn)行50次實(shí)驗(yàn)。其中，當(dāng)決策變量的維數(shù)為10維、50維和100維時(shí)，各算法的迭代次數(shù)分別為1 000次、2 000次和3 000次。實(shí)驗(yàn)的硬件環(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。

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

4.2 性能評(píng)估與理論分析

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

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

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

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

5 結(jié)束語

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

Table 2 Experimental results of eight algorithms on benchmark functions

續(xù)表