傅彥銘，許勵強(qiáng)+，祁康恒，沈煜鳴，屈遲文

1.廣西大學(xué) 計算機(jī)與電子信息學(xué)院，南寧 530004

2.右江民族醫(yī)學(xué)院 公共衛(wèi)生與管理學(xué)院，廣西 百色 533000

在實(shí)際的工程、經(jīng)濟(jì)管理、生命科學(xué)等領(lǐng)域的應(yīng)用中存在大量的優(yōu)化問題。當(dāng)優(yōu)化問題只有單個需要進(jìn)行優(yōu)化的目標(biāo)時，被稱為單目標(biāo)優(yōu)化問題。然而，在更多實(shí)際場合中存在需要優(yōu)化多個目標(biāo)的問題，例如物流調(diào)配、工程設(shè)計、機(jī)場調(diào)度[1]等，適用于單目標(biāo)優(yōu)化問題的求解方法往往無法滿足多個目標(biāo)問題的同時求解[2]。因此，研究多目標(biāo)優(yōu)化算法就顯得格外重要。

智能優(yōu)化算法不受問題的數(shù)學(xué)性質(zhì)限制，具有良好的全局優(yōu)化能力，被廣泛用于求解優(yōu)化問題，一般可以被分為以下四個不同的類別：進(jìn)化算法、仿自然優(yōu)化算法、仿植物優(yōu)化算法和群體智能優(yōu)化算法[3]。群體智能優(yōu)化算法在這些算法中有著重要的作用和地位。群體智能優(yōu)化算法最初起源于一些具有社會性行為特征的生物群體行為規(guī)律的研究，如螞蟻、蜜蜂、鳥群等[4]。目前，對于群體智能優(yōu)化算法的研究，已經(jīng)有一套比較成熟的方法：首先從一種由小及大的、從大量個體到整個群體行為作為研究的起點(diǎn)，再為它們的不同行為建立模型，并為這些模型樹立配套的規(guī)則，以保證其正確運(yùn)轉(zhuǎn)，最終得到完整的群體智能優(yōu)化算法，用于解決待優(yōu)化問題。群體智能優(yōu)化算法在神經(jīng)網(wǎng)絡(luò)[5]、圖像處理[6]、路徑規(guī)劃[7-8]、入侵檢測[9]等場景中與其他方法交叉融合，取得了很好的效果。例如，量子計算[10]由于其與生俱來的并行性和在一些問題上具有能夠?qū)崿F(xiàn)指數(shù)加速的潛力，與群體智能優(yōu)化算法結(jié)合，在許多問題求解中獲得了優(yōu)異的性能。蔡雨希等[11]提出一種將篩選法和粒子群算法相結(jié)合的LCL 濾波器參數(shù)的設(shè)計方法，解決了濾波器體積大或高頻濾波性能存在的一些問題。李曉巖等[12]將蟻群算法與神經(jīng)網(wǎng)絡(luò)相糅合，提出一種對新型船舶圖像壓縮的方法。

黑寡婦優(yōu)化算法（black widow optimization algorithm，BWOA）[13]是一種群體智能優(yōu)化算法，已經(jīng)應(yīng)用于多個領(lǐng)域解決了各種工程優(yōu)化問題。例如，Mukilan 等[14]引入BWOA 優(yōu)化深度卷積神經(jīng)網(wǎng)絡(luò)的參數(shù)，并將經(jīng)過優(yōu)化的深度卷積神經(jīng)網(wǎng)絡(luò)用于從視頻幀中檢測出人和物體，實(shí)驗(yàn)證明所提出的方法優(yōu)于卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural networks，CNN）、CNN-帝企鵝優(yōu)化（emperor penguin optimizer，EPO）和CNN-粒子群優(yōu)化（particle swarm optimization，PSO）等方法。Wilson 等[15]提出了一種結(jié)合BWOA 的高效節(jié)能集成聚類方法（energy efficient ensemble clustering method-black widow optimization algorithm，EECM-BWO），實(shí)現(xiàn)洪水災(zāi)害實(shí)時監(jiān)測無線傳感器網(wǎng)絡(luò)的有效數(shù)據(jù)傳輸，實(shí)驗(yàn)顯示該方法優(yōu)于當(dāng)前一些主流的方法，例如布谷鳥優(yōu)化算法（energy efficient ensemble clustering method-cuckoo optimization algorithm，EECM-COA）、被動多跳聚類算法（energy efficient ensemble clustering method-passive multihop clustering algorithm，EECM-PMC）等。Premkumar等[16]使用BWOA 優(yōu)化了風(fēng)力渦輪機(jī)（wind turbine，WT）仿真器的比例積分（proportional integral，PI）控制器的參數(shù)，即PI 控制器的比例和積分增益，該方法的仿真結(jié)果與硬件結(jié)果吻合良好。

在實(shí)際應(yīng)用中有許多優(yōu)化問題屬于多目標(biāo)優(yōu)化問題，而黑寡婦算法是為求解單目標(biāo)優(yōu)化問題而提出的，無法直接應(yīng)用于求解多目標(biāo)優(yōu)化問題。此外，雖然BWOA 具有能夠快速收斂并且精度高的優(yōu)點(diǎn)，但其所采用的更新策略過于簡單，容易陷入局部最優(yōu)解；其次，在多維空間中缺乏搜索能力；BWOA 種群結(jié)構(gòu)單一，算法的收斂性和多樣性有待改善。

為解決上述問題，提高算法的綜合能力，本文提出一種基于角逐和改進(jìn)信息素機(jī)制的多目標(biāo)黑寡婦優(yōu)化算法（multi-objective black widow optimization algorithm，MBWOA）。MBWOA 采用一種動態(tài)分配種群的方法，在迭代過程中將種群一分為二，分別使用不同的角逐機(jī)制，其中第一部分負(fù)責(zé)種群的收斂性，第二部分則負(fù)責(zé)種群多樣性。此外，隨著迭代次數(shù)的增加，算法對于收斂性與多樣性的需求也會逐漸變化，動態(tài)分配種群讓算法在收斂性和多樣性之間取得更好的平衡。同時，使用一種改進(jìn)的信息素更新機(jī)制，該機(jī)制根據(jù)種群總體的信息素水平，引導(dǎo)待優(yōu)化個體向種群間隙方向進(jìn)行優(yōu)化，改善種群的多樣性，增強(qiáng)算法的收斂能力。

1 黑寡婦優(yōu)化算法

黑寡婦優(yōu)化算法是由Pe?a-Delgado、Peraza-Vázquez等通過模擬黑寡婦蜘蛛群體的行為于2020年提出的一種群體智能優(yōu)化算法。算法主要模擬了黑寡婦的兩種行為。

（1）黑寡婦在蜘蛛網(wǎng)上的運(yùn)動分為螺旋前進(jìn)和直行，這兩種運(yùn)動方式以不同的概率發(fā)生。第t代黑寡婦種群的第i個個體通過式（1）螺旋前進(jìn)或直行的方式來更新，得到第t+1代個體。

其中，Amin表示第t代種群中適應(yīng)度最小的個體，P是[0,1]內(nèi)的隨機(jī)概率，beta是（-1,1）之間的隨機(jī)值，m是（0.4,0.9）之間的隨機(jī)值，是第t代種群中隨機(jī)選擇的個體。

可以看出，黑寡婦優(yōu)化算法（BWOA）更新策略過于簡單，導(dǎo)致在解空間內(nèi)的搜索能力不足，缺乏種群的多樣性和容易陷入局部最優(yōu)解。同時，運(yùn)動策略所選取的、用以指導(dǎo)子代更新的個體的選取方式隨機(jī)性強(qiáng)，而作為指導(dǎo)子代更新的個體在種群應(yīng)該具有一定的指向性，否則將導(dǎo)致算法收斂能力不足的問題。此外，信息素的計算僅考慮種群中適應(yīng)度最大和最小的個體，不能反映種群總體水平，在根據(jù)信息素值進(jìn)行更新過程中，也存在選擇指導(dǎo)子代更新的個體隨機(jī)性強(qiáng)等問題。

2 角逐和信息素引導(dǎo)的多目標(biāo)黑寡婦優(yōu)化算法

本文在黑寡婦優(yōu)化算法的基礎(chǔ)上引入了帕累托最優(yōu)[17]和非支配解排序[18]，使得BWOA能夠用于解決多目標(biāo)優(yōu)化問題。與此同時，采用兩種策略進(jìn)一步改善算法的收斂性和多樣性。（1）引入兩種不同的角逐機(jī)制更新種群，使得算法在迭代過程中能夠兼顧收斂性和多樣性。（2）使用兩種角逐機(jī)制所得的結(jié)果和非支配解排序的信息改進(jìn)了信息素的計算方法，通過這些方式可以改善算法的收斂性和多樣性。綜合以上的工作，本文提出了一種角逐和改進(jìn)信息素引導(dǎo)的多目標(biāo)黑寡婦優(yōu)化算法。

2.1 MBWOA算法總體框架與復(fù)雜度分析

MBWOA 算法首先對種群初始化，計算個體的非支配排序等級，然后初始化信息素數(shù)組，得到初始非支配解集AS。為了使算法兼顧多樣性和收斂性，MBWOA 在每次迭代的種群中隨機(jī)選擇N1個個體構(gòu)成子種群Part1，剩余部分構(gòu)成子種群Part2，兩個子種群的規(guī)模相差不會太大，以保證算法在每一個階段對收斂性和多樣性的需求都有基礎(chǔ)的保證而不會完全傾向于任一個方面。此外，為了符合算法前期需要更強(qiáng)的搜索能力的要求，負(fù)責(zé)算法多樣性的子種群規(guī)模在一開始被設(shè)定為它的最大值，隨著迭代次數(shù)的增加而遞減。與此同時，隨著迭代次數(shù)的增加，算法將愈加注重收斂性，因此負(fù)責(zé)算法收斂性的子種群將逐漸擴(kuò)大其規(guī)模。其中負(fù)責(zé)收斂性的子種群規(guī)模N1根據(jù)式（4）計算：

式中，fix為取整函數(shù)，N為種群規(guī)模，Va和L為控制N1的參數(shù)，t為當(dāng)前迭代次數(shù)，maxgen為最大迭代次數(shù)。

種群的Part1 和Part2 分別對應(yīng)算法的收斂性、多樣性，二者分別采用兩個體角逐機(jī)制和三個體角逐機(jī)制方式更新個體，通過采用不同的更新策略，可以在保證種群多樣性的同時，讓算法盡可能避免局部最優(yōu)，增強(qiáng)算法收斂性。

兩個子種群中的個體更新后，將兩個子種群融合。由于算法的多樣性和收斂性是不可分割、互為補(bǔ)充的兩個性質(zhì)，任一個的缺失將導(dǎo)致算法的效果大打折扣，二者融合是必要且必須的。與此同時，由于采用的是兩個子種群沒有交叉重合的部分的分配方式，即在一次迭代中不存在一個個體同時屬于兩個子種群，這就保證了二者融合不會產(chǎn)生沖突。兩個子種群融合后對每個個體計算其信息素值，在得到個體信息素值的大小和根據(jù)擁擠度選出兩個當(dāng)前種群中的個體之后，通過更新得到子代個體。第t次迭代結(jié)束后，根據(jù)非支配等級更新種群各個體的非支配排序等級，用第i+1 代種群與當(dāng)前的AS通過非支配解排序更新AS[19]。最終，maxgen次迭代結(jié)束后，輸出最優(yōu)解集AS。圖1 描述了MBWOA算法的總體流程。

圖1 MBWOA算法流程Fig.1 Flowchat of MBWOA

MBWOA 的時間復(fù)雜度主要由初始化和主循環(huán)兩部分主導(dǎo)。假設(shè)種群個體數(shù)量為N，決策向量維數(shù)為D，最大迭代次數(shù)為T，目標(biāo)數(shù)為M。初始化種群的復(fù)雜度為O(DN)，初始化信息素矩陣的復(fù)雜度為O(N)，非支配排序的復(fù)雜度為O(MN2)。在主循環(huán)中，兩個體角逐機(jī)制復(fù)雜度為O(1)，三個體角逐機(jī)制在最壞情況下復(fù)雜度為O(N2/4)，更新外部存檔集的主要時間復(fù)雜度來自非支配排序，為O(MN2)。則總O(DN+N)+O(MN2)+O(T+TN2/4+TMN2)，算法的時間復(fù)雜度為max{O(DN)，O(TN2)}。

2.2 兩個體角逐機(jī)制

兩個體角逐機(jī)制用于更新種群Part1 中個體和速度。首先從當(dāng)前AS中隨機(jī)選出兩個非支配解Po1、Po2，根據(jù)式（5）計算兩個解與當(dāng)前解的余弦相似度大小，并從這兩個解中選出與相似程度更高的解作為本次角逐的優(yōu)勝解，則另外一個解為。兩個n維個體X(x1,x2,…,xn)、Y(y1,y2,…,yn)的余弦相似度取決于兩個個體夾角的余弦值，其余弦值越接近1，就表明其夾角越接近于0°，兩個個體就越相似。

黑寡婦在蜘蛛網(wǎng)上時而直行，時而螺旋前進(jìn)。與此相匹配，Ai′的計算根據(jù)P的取值有兩種不同的計算方式，式（7）分別對應(yīng)黑寡婦的螺旋前進(jìn)與直行。

其中，P是[0,1]內(nèi)的隨機(jī)概率，beta是（-1,1）之間的隨機(jī)值，m是（0.4，0.9）之間的隨機(jī)值，是從當(dāng)前種群中隨機(jī)選取的一個個體。

式（7）中的δ由式（8）計算，其中是待調(diào)整的個體Ai′的非支配排序等級。非支配排序方法簡單來說，先從種群中選出第一組不能被其他解所支配的解，其等級為1，在剩余部分中再次選出所有非支配解，其等級為2，以此類推，MaxFNo是當(dāng)前種群中非支配排序等級數(shù)值的最大值。

式（8）中的μ由式（9）計算：

其中，ub是個體各維度數(shù)值上界數(shù)組，lb是個體各維度數(shù)值下界數(shù)組，t為迭代數(shù)。

最后，對經(jīng)過調(diào)整之后的Ai′和Vi′進(jìn)行越界處理。算法1描述了兩個體角逐機(jī)制。

算法1兩個體角逐機(jī)制

2.3 三個體角逐機(jī)制

不同于兩個體角逐機(jī)制，三個體角逐機(jī)制在迭代中的作用是盡量挖掘出角逐中非優(yōu)勝解和所蘊(yùn)含的隱藏信息，并用于更新種群Part2 中的個體和速度。在三個體角逐機(jī)制中，首先從當(dāng)前AS中隨機(jī)選出三個不同的非支配解Po1、Po2、Po3 進(jìn)行角逐，再根據(jù)式（5）分別計算三個不同的非支配解與當(dāng)前解的余弦值，并以所得余弦最小的解作為優(yōu)勝解，其次為中間解和失敗解。角逐結(jié)束后，根據(jù)式（10）得到調(diào)整后的速度Vi′：

兩個n維解X(x1,x2,…,xn)、Y(y1,y2,…,yn)的歐幾里德距離用式（11）計算：

Ai′的更新基于速度Vi′更新，如式（12）所示：

最后對Ai′、Vi′進(jìn)行越界處理。比起兩個體角逐機(jī)制，三個體角逐機(jī)制更注重于算法的多樣性。這樣是為了避免算法陷入局部最優(yōu)解，從而增強(qiáng)算法的全局搜索能力。算法2描述了三個體角逐機(jī)制。

算法2三個體角逐機(jī)制

2.4 改進(jìn)信息素機(jī)制

在MBWOA 算法中，使用改進(jìn)的信息素機(jī)制，每次迭代都會用式（13）對當(dāng)前個體Ai′的信息素值phi進(jìn)行評估。

當(dāng)前個體Ai′的信息素phi低于時，則該個體Ai′往往非支配等級數(shù)值較大并且離真實(shí)PF距離較遠(yuǎn)，因此需要對其進(jìn)行調(diào)整和優(yōu)化。優(yōu)化之前需要從當(dāng)前種群中依照擁擠度的大小對應(yīng)的概率找出另外兩個不同的個體，種群中每一個個體的被選中的概率是根據(jù)其擁擠度的大小決定的，擁擠度越大，被選中的概率就越小，這是為了盡量避免在解空間中選出兩個位置鄰近的個體從而導(dǎo)致的優(yōu)化效果不明顯的問題。選出個體之后根據(jù)式（15）更新。

其中，b是隨機(jī)自然數(shù)。該式意在對那些非支配排序等級數(shù)值較大、離真實(shí)Pareto前沿距離較遠(yuǎn)的個體進(jìn)行更新。以優(yōu)勝解為基準(zhǔn)，更新的方向根據(jù)b取值的不同隨機(jī)指向之間的間隙或兩側(cè)一定程度內(nèi)的方向，引導(dǎo)個體向種群間隙方向進(jìn)行優(yōu)化，以改善種群的分布，增強(qiáng)算法的收斂能力。真實(shí)前沿（Pareto front，PF）是測試問題對應(yīng)的最優(yōu)解集映射到目標(biāo)函數(shù)空間的曲面。更新后，對At+1i進(jìn)行越界處理。算法3 描述了改進(jìn)信息素機(jī)制。改進(jìn)后的信息素機(jī)制彌補(bǔ)了BWOA 信息素機(jī)制的缺陷，增強(qiáng)了子代更新的指向性，強(qiáng)化了搜索能力，提升了算法的收斂性和收斂速度，3.3.4 小節(jié)展示了改進(jìn)前后的效果對比圖。

算法3改進(jìn)信息素機(jī)制(Ai′,)

2.5 MBWOA的收斂性證明

對于隨機(jī)算法是否收斂性問題，著名學(xué)者Solis等[20]提出了兩條判定標(biāo)準(zhǔn)。MBWOA 算法作為一種隨機(jī)算法，因此可以利用該判定標(biāo)準(zhǔn)來驗(yàn)證該算法的收斂性。其具體描述如下：

若以最小化為目標(biāo)的優(yōu)化問題（B為所求解問題的可行解空間，f為目標(biāo)函數(shù)）,隨機(jī)算法D通過t次迭代后的解為xt，則其t+1次迭代所產(chǎn)生的新解為xt+1=D(xt,ε)，ε為算法D迭代過程中所獲得的解。

準(zhǔn)則 1若f(D(x,ξ)) ≤f(x),ξ∈B，則f(D(x,ξ)) ≤f(ξ)。

準(zhǔn)則 2若對 ?a∈B,s.t.v(a) >0，則

其中，ut(a)為算法D迭代t次后在集合a上的概率測度，v(a)為集合x上Lebesgue測度。

定理1MBWOA 算法中，黑寡婦蜘蛛個體狀態(tài)Ii一步轉(zhuǎn)移到另一個狀態(tài)Ij的轉(zhuǎn)移概率為：

其中，個體全局最優(yōu)解的一步轉(zhuǎn)移概率為：

黑寡婦蜘蛛個體位置Ai一步轉(zhuǎn)化為Aj的概率為：

定理2黑寡婦蜘蛛個體最優(yōu)狀態(tài)集M是一個閉集。

證明設(shè)黑寡婦蜘蛛個體狀態(tài)為最優(yōu)狀態(tài)，根據(jù)算法的執(zhí)行策略，其下一時刻的狀態(tài)，顯然也為最優(yōu)狀態(tài)。依據(jù)式（16）、式（17）可知，當(dāng)因此，黑寡婦蜘蛛個體最優(yōu)狀態(tài)集M是一個閉集。

定理3MBWOA 算法中，最優(yōu)黑寡婦蜘蛛群體狀態(tài)集G是一個閉集。

證明?si∈G,?sj?G,sj∈S，對任意步長l,l≥1，由Ckapman-Kolmogorov方程可得：

定理4[21]設(shè)Markov 鏈有一集合D非空，且非空集D為不屬于Markov 鏈的閉集，C?D=?，則當(dāng)j∈C時，且j?C時，

定理5當(dāng)黑寡婦蜘蛛群體內(nèi)部位置迭代次數(shù)趨于無窮時，群體狀態(tài)序列必將進(jìn)入最優(yōu)狀態(tài)集H。

證明由定理2～定理4可證。

定理6MBWOA 收斂于全局最優(yōu)解。

證明在MBWOA算法的每次迭代次數(shù)都保存群體的最優(yōu)黑寡婦蜘蛛位置，即滿足f(D(x,ξ)) ≤f(ξ)，符合準(zhǔn)則1 條件；其次，依據(jù)定理6 可知，MBWOA 算法經(jīng)過無窮次迭代后，黑寡婦蜘蛛群體位置序列必將進(jìn)入最優(yōu)狀態(tài)，滿足收斂準(zhǔn)則的條件2。因此，MBWOA 收斂于全局最優(yōu)解。

3 實(shí)驗(yàn)與分析

本文的實(shí)驗(yàn)使用一臺Intel Core i5-6300HQ 2.30 GHz CPU 和Windows 10 操作系統(tǒng)的筆記本電腦，算法用MATLAB R2018b編寫。

3.1 多目標(biāo)性能指標(biāo)

為了評估算法的多目標(biāo)性能，選用反向迭代距離（inverted generational distance，IGD）[22]、超體積指標(biāo)（hypervolume，HV）[23]和擴(kuò)散程度（Spread）[24]這3個指標(biāo)進(jìn)行評價。

IGD：用于估算每一個真實(shí)PF上的參考點(diǎn)P*到最近的解的距離的平均值。對于測試的多目標(biāo)優(yōu)化算法，其IGD 值越小，則表明該算法收斂性和多樣性越好。IGD表達(dá)式為：

P是多目標(biāo)算法所求得的解集，P*為從Pareto 真實(shí)前沿PF上采樣的一組均勻分布的參考點(diǎn)，dis(x,y)表示參考解集P*中的點(diǎn)x到解集P中的點(diǎn)y的歐氏距離。

HV：指多目標(biāo)優(yōu)化算法的非支配解集X與參考點(diǎn)P圍成的目標(biāo)空間區(qū)域的體積v(x,P)，多目標(biāo)優(yōu)化算法所取得的HV 值越大，該算法的多樣性和收斂性就越好。其表達(dá)式為：

其中，X是一組多目標(biāo)優(yōu)化算法的Pareto 最優(yōu)解集，P為參考點(diǎn)，x表示X中的一個解，v(x,P)表示參考點(diǎn)P與x的超體積。

Spread：表示多目標(biāo)優(yōu)化算法在非支配區(qū)域中的個體分布均勻程度，即測量整個已知的真實(shí)PF中向量的分布情況，算法的Spread 值越小，算法的解集多樣性越好，分布越均勻。其表達(dá)式為：

其中，N是目前非支配解集中解的個數(shù)，參數(shù)di是求得的非支配解集里相鄰最近的解之間的歐氏距離，dˉ代表解集中所有di的平均值。df以及dl分別表示所取得的非支配解集邊界解以及極值解之間的歐氏距離。

3.2 對比算法與基準(zhǔn)函數(shù)

為驗(yàn)證MBWOA 算法的性能，選取了4 個當(dāng)前主流的多目標(biāo)優(yōu)化算法SMPSO（speed-constrained multi-objective PSO）[25]、MOEA/D/DU（multi-objective optimization evolutionary algorithm based on decomposition with a distance based updating strategy）[26]、NSGA-II/SDR（non-dominated sorting genetic algorithm II with strengthened dominance relation）[27]、LMOCSO（large-scale multi-objective competitive swarm optimization algorithm）[28]與本文提出的MBWOA 算法進(jìn)行比較。

這里使用的4 個對比算法的源代碼都可以在PlatEMO[29]中找到。為了實(shí)驗(yàn)的公平性，所有對比算法統(tǒng)一沿用其原始論文的默認(rèn)參數(shù)，如表1所示?；鶞?zhǔn)測試問題包括10 個RM-MEDA（benchmark MOP for a regularity model-based multiobjective estimation of distribution algorithm）[30]問題（以下簡稱F1～F10）和5 個ZDT（benchmark MOP proposed by Zitzler，Deb and Thiele）[31]問題。除F4、F8 是三目標(biāo)問題之外都是雙目標(biāo)問題，決策變量都是30 個。5 個ZDT 問題（ZDT1～ZDT4、ZDT6）都是雙目標(biāo)問題，ZDT1～ZDT3決策變量是30 個，ZDT4 和ZDT6 決策變量是10 個。由于ZDT5是一個二進(jìn)制問題，在測試中未被選用。

表1 對比算法參數(shù)設(shè)置Table 1 Parameter setting of comparison algorithms

3.3 實(shí)驗(yàn)對比分析

本實(shí)驗(yàn)中每個算法在每個測試問題上獨(dú)立運(yùn)行30 次，每次運(yùn)行對算法所得的解集評估10 000 次。實(shí)驗(yàn)收集了這30 次的平均值和標(biāo)準(zhǔn)差進(jìn)行比較，標(biāo)準(zhǔn)差數(shù)據(jù)列在平均值下一行。表中的粗體表示每個問題的最優(yōu)結(jié)果。為了得到統(tǒng)計上可靠的結(jié)論，用α=0.05 的顯著性水平進(jìn)行了Wilcoxon 秩和檢驗(yàn)，以顯示MBWOA與對比算法之間的統(tǒng)計學(xué)差異。

表中的符號+、?和=分別表示使用此統(tǒng)計檢驗(yàn)的對比算法明顯好于、差于、接近于MBWOA。表2 總結(jié)了MBWOA 與4 個對比算法在15 個測試問題上的HV 平均值和標(biāo)準(zhǔn)偏差。MBWOA 在除了ZDT6的包括ZDT 和RM-MEDA 系列的所有14 個測試問題函數(shù)中都取得了最優(yōu)。同時，MBWOA 與SMPSO 在唯一沒有取得最優(yōu)的ZDT6 測試問題中，算法運(yùn)行結(jié)果與LMOCSO 所取得的最優(yōu)解的HV 指標(biāo)值的差距非常小。這表明MBWOA 在這些測試函數(shù)上表現(xiàn)出了最好的多樣性、穩(wěn)定性和收斂性。

表2 各算法HV實(shí)驗(yàn)結(jié)果Table 2 HV experimental results of each algorithm

表3 列出了MBWOA 與對比算法在15 個測試問題上的Spread 平均值和標(biāo)準(zhǔn)偏差。其中，MBWOA在11 個測試函數(shù)中取得了最優(yōu)。相比之下，只有LMOCSO 在其他4 個測試函數(shù)中取得了最優(yōu)。其中，在ZDT2 中，MBWOA 所取得的解略遜于LMOCSO?？偟膩碚f，在大多數(shù)情況MBWOA 在這些測試函數(shù)上所產(chǎn)生的解集，相比其他4個對比算法而言，多樣性更好、更穩(wěn)定、解集分布更均勻。

表3 各算法Spread實(shí)驗(yàn)結(jié)果Table 3 Spread experimental results of each algorithm

表4 展示了MBWOA 與對比算法在測試問題上的IGD 平均值和標(biāo)準(zhǔn)偏差。MBWOA 在15個基準(zhǔn)問題中取得了13個IGD 的最優(yōu)值。在RM-MEDA 測試問題中，只有MOEA/D/DU 在F8 問題上取得最優(yōu)，MBWOA 則在其他RM-MEDA 測試問題有著顯著的優(yōu)勢。在ZDT系列測試問題中，MBWOA 在除ZDT6之外的所有測試問題上都取得了最小的IGD 值。而在ZDT6 測試問題上，MBWOA 的運(yùn)行結(jié)果略遜色于LMOCSO所取得的最優(yōu)解。這說明MBWOA具有更好的穩(wěn)定性、收斂性和多樣性。

表4 各算法IGD實(shí)驗(yàn)結(jié)果Table 4 IGD experimental results of each algorithm

3.3.1 收斂精度及前沿分布情況分析

圖2 展示了MBWOA 和對比算法的運(yùn)行結(jié)果。黑點(diǎn)是對應(yīng)問題的真實(shí)PF，藍(lán)點(diǎn)則是算法的解集?？梢钥吹?，對于圖中列出的測試問題，MBWOA 都可以完全收斂到真實(shí)PF上，而4 個對比算法則不能收斂到真實(shí)PF，或不能完全收斂到所有問題的整個真實(shí)PF上。F1 是一個線性、PF為凸的函數(shù)。圖2（a）～（e）展示了10 000 次評估完成時MBWOA 和所有對比算法的運(yùn)行結(jié)果。其中，SMPSO 和LMOCSO 最終能夠收斂到真實(shí)PF上，但二者在第一個目標(biāo)值接近0 的部分有部分缺失，MOEA/D/DU 和NSGA-II/SDR則存在很大部分的缺失，在ZDT1 中的情況也與此類似。而在F3 和ZDT3 中，對比算法都未能收斂或是未完全收斂。

圖2 部分測試函數(shù)求解近似前沿Fig.2 Pareto optimal front of some test functions

圖2（k）～（o）展示了對比算法和MBWOA 在難度更大的F4 問題上的運(yùn)行結(jié)果。SMPSO 的解只在靠中心的部分能夠達(dá)到真實(shí)PF，其解集與真實(shí)PF的距離較大。MOEA/D/DU 的解分布在真實(shí)PF的周圍，但是離真實(shí)PF還有一段距離。LMOCSO 的解均勻散布在真實(shí)PF周圍以及略遠(yuǎn)的空間。說明這些算法的收斂性能需要進(jìn)一步加強(qiáng)。而NSGA-II/SDR 的解則聚集在真實(shí)PF的頂部上空的區(qū)域，而其他部分則幾乎沒有解，其多樣性有待加強(qiáng)。相比之下，MBWOA 所產(chǎn)生的解幾乎都在真實(shí)PF上，或是離真實(shí)PF非常接近，與此同時，解基本覆蓋了整個真實(shí)PF，且分布相對較為均勻。

結(jié)合IGD 統(tǒng)計表可以發(fā)現(xiàn)，在RM-MEDA 測試問題中，MBWOA 能夠在F1～F6 中基本能夠完全收斂到真實(shí)PF上，在復(fù)雜程度更高的F7～F10 問題中，只能部分收斂于真實(shí)PF，但相比對比算法而言，更逼近真實(shí)PF，收斂速度也更快。對于ZDT 測試問題，MBWOA 也表現(xiàn)出了良好的求解能力。在所有測試中，MBWOA 都能夠收斂到所有問題的真實(shí)PF上，且收斂速度相比對比算法而言更快?？偟膩碚f，測試表明MBWOA 具有優(yōu)秀的求解能力，更好的收斂性、多樣性和更高的收斂精度。

3.3.2 收斂速度分析

圖3 給出了MBWOA 和對比算法在15 個測試問題上的IGD 變化趨勢。圖中的橫坐標(biāo)代表評價次數(shù)，縱坐標(biāo)代表IGD 的值，紅色線條代表MBWOA 的解集隨著迭代次數(shù)的增加所取得的IGD 值的變化情況，每次迭代評估100次。

圖3 各測試函數(shù)IGD指標(biāo)變化趨勢Fig.3 Change trend of IGD indicators of each test function

對于RM-MEDA 系列測試問題，MBWOA 能夠在RM-MEDA_F1～F4、F7中的第2 000次評估之前收斂并且取得最小的IGD 值，在F5～F6 中，MBWOA 也能夠在接近2 000次評估時收斂并取得最小值；在F8中雖能夠較快收斂，但未能取得最小的IGD 值；在F9中最終取得最小值。相比之下，SMPSO 在9 000 次評估時收斂，LMOCSO 在10 000次評估時接近收斂，F(xiàn)2 中LMOCSO 在8 000 次評估時收斂并接近于MBWOA 所取得的最小值。在F8 中，MOEA/D/DU最終取得了最小的IGD 值，其他算法在10 000 次評估完成時尚未收斂。

在ZDT 系列測試問題中，MBWOA 在ZDT1～ZDT3 中都能在2 000 多次評估之內(nèi)收斂并最終取得IGD最小值，ZDT4中大約5 000次評估時收斂并取得最小的IGD，ZDT6 在2 000 次評估之內(nèi)收斂，最終取得的IGD 值雖不是最小，但與在此問題中取得最優(yōu)的LMOCSO差距非常小。而對比算法雖然在某些問題上能夠收斂，但從總體上來說，MBWOA 在兼顧收斂速度的同時取得更好的解集的能力相比對比算法而言更強(qiáng)，表現(xiàn)更好。

3.3.3 算法耗時

表5 列出了算法在4 個測試問題上獨(dú)立運(yùn)行30次得到的平均運(yùn)行時間。可以看出MBWOA 的總耗時會比其他算法更長一些，這是由于其每次循環(huán)過程中都需要進(jìn)行非支配排序并維護(hù)種群，因此MBWOA 為了增加種群多樣性，提高算法的收斂精度，是以犧牲算法的運(yùn)行時間為代價的。

表5 獨(dú)立實(shí)驗(yàn)30次的平均運(yùn)行時間Table 5 Average running time of 30 independent experiments單位：s

3.3.4 角逐機(jī)制和改進(jìn)信息素機(jī)制及其融合的有效性驗(yàn)證

為驗(yàn)證本文所用策略的有效性以及融合兩種策略的合理性，分別使用不包含角逐機(jī)制和改進(jìn)信息素機(jī)制的黑寡婦優(yōu)化算法BWOA、單獨(dú)使用改進(jìn)信息素更新機(jī)制的黑寡婦優(yōu)化算法MBWOA-PH、單獨(dú)使用兩種角逐機(jī)制的黑寡婦優(yōu)化算法MBWOACOM 與本文提出的融合兩種方法的MBWOA 算法在IGD、Spread 和HV 指標(biāo)上進(jìn)行實(shí)驗(yàn)，表6 為實(shí)驗(yàn)結(jié)果。除開前兩列，表格中每四列構(gòu)成一組實(shí)驗(yàn)，共計3 組。3 組實(shí)驗(yàn)中分別使用BWOA、MBWOA-PH、MBWOA-COM 和MBWOA 在15 個不同的測試函數(shù)上對于IGD、Spread、HV指標(biāo)進(jìn)行對比。

表6 MBWOA與對比算法在IGD、Spread和HV上的對比結(jié)果Table 6 Comparison results of MBWOA and comparison algorithms on IGD,Spread and HV

在測試IGD 的實(shí)驗(yàn)中，BOWA、MBWOA-PH、MBWOA-COM 和MBWOA 所取得最優(yōu)解的數(shù)量分別為0、1、0、14。同時，MBWOA-PH和MBWOA-COM在15個測試問題上優(yōu)于BWOA 的數(shù)量分別為9個和14 個，這說明兩種策略都能夠增強(qiáng)算法的收斂性和多樣性。

在測試Spread 的實(shí)驗(yàn)中，BOWA、MBWOA-PH、MBWOA-COM 和MBWOA 所取得最優(yōu)解的數(shù)量分別為0、2、1、12，MBWOA-PH 和MBWOA-COM 在15個測試問題中分別有13 個不同的測試函數(shù)優(yōu)于BWOA，說明所用的兩種策略都能加強(qiáng)算法的多樣性并且改善種群的分布。

在測試HV 的實(shí)驗(yàn)中，BOWA、MBWOA-PH、MBWOA-COM 和MBWOA 所取得最優(yōu)解的數(shù)量分別為1、1、3、10，MBWOA-PH 和MBWOA-COM 在15個測試問題上優(yōu)于BWOA 的數(shù)量分別為9 個和12個，表明本文所用的兩種策略都能增強(qiáng)算法的多樣性和收斂性。

MBWOA-ago 和MBWOA 的區(qū)別是使用了改進(jìn)前的信息素機(jī)制，而其他策略相同。圖4 展示了這兩個算法在測試問題F5、F6、ZDT1 和ZDT3 上評估10 000 次所得到的Pareto 前沿?？梢郧宄乜吹剑琈BWOA-ago 在4 個測試問題中都不能完全收斂到整個真實(shí)PF，有些部分沒有解或是與真實(shí)PF之間有一定的距離，而MBWOA則收斂到了4個測試問題的整個真實(shí)PF上。說明改進(jìn)信息素機(jī)制提升了算法搜索能力，增加了算法的收斂性和多樣性，提高了收斂精度。

圖4 信息素機(jī)制改進(jìn)前后的Pareto前沿Fig.4 Pareto frontiers before and after improvement of pheromone mechanism

圖5 展示了MBWOA-ago 和MBWOA 在4 個 測試函數(shù)上的IGD 變化趨勢。在4 個測試問題上，MBWOA 都能在2 000 次評估時就完成收斂，而MBWOA-ago 則需要運(yùn)行更多次才能慢慢收斂。這表明改進(jìn)信息素機(jī)制能夠提升算法的收斂速度。

圖5 信息素機(jī)制改進(jìn)前后的IGD變化趨勢Fig.5 Trends in IGD before and after improvement of pheromone mechanism

最后，在3 種指標(biāo)的實(shí)驗(yàn)中MBWOA-PH 和MBWOA-COM 均優(yōu)于BWOA，而融合了兩種策略的MBWOA 優(yōu)于上述3種算法，說明本文所用的兩種角逐機(jī)制和改進(jìn)信息素機(jī)制的有效性，證明了融合兩種策略的合理性。

4 結(jié)束語

本文提出了一種基于角逐機(jī)制和改進(jìn)信息素機(jī)制引導(dǎo)的多目標(biāo)黑寡婦優(yōu)化算法，引入了兩種角逐機(jī)制和改進(jìn)信息素機(jī)制來提高算法的性能。在算法每次迭代過程中將種群分為兩部分，兩部分在每次迭代中的規(guī)模不同，每部分使用不同的角逐機(jī)制更新個體，種群沿不同方向更新，使算法能夠兼顧收斂性和多樣性。接著，使用改進(jìn)信息素機(jī)制對經(jīng)過不同角逐機(jī)制調(diào)整的、信息素值較低的個體進(jìn)行更新，引導(dǎo)個體向種群間隙方向進(jìn)行優(yōu)化，改善種群的分布，增強(qiáng)算法的收斂能力。MBWOA 與主流的多目標(biāo)優(yōu)化算法SMPSO、MOEA/D/DU、NSGA-II/SDR 和LMOCSO 在RM-MEDA、ZDT 測試問題上測試，得到IGD、HV 和Spread 值。最終實(shí)驗(yàn)證明MBWOA 的收斂性、多樣性、穩(wěn)定性、解的均勻性均優(yōu)于對比算法，是一種有競爭力的多目標(biāo)優(yōu)化算法。最后，驗(yàn)證了算法所用策略的有效性及融合的合理性。此外，未來進(jìn)一步的研究點(diǎn)是將MBWOA 用于解決一些實(shí)際工程問題。