角逐和信息素引導的多目標黑寡婦優化算法

傅彥銘，許勵強+，祁康恒，沈煜鳴，屈遲文

1.廣西大學 計算機與電子信息學院，南寧 530004

2.右江民族醫學院 公共衛生與管理學院，廣西 百色 533000

在實際的工程、經濟管理、生命科學等領域的應用中存在大量的優化問題。當優化問題只有單個需要進行優化的目標時，被稱為單目標優化問題。然而，在更多實際場合中存在需要優化多個目標的問題，例如物流調配、工程設計、機場調度[1]等，適用于單目標優化問題的求解方法往往無法滿足多個目標問題的同時求解[2]。因此，研究多目標優化算法就顯得格外重要。

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

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

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

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

1 黑寡婦優化算法

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

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

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

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

2 角逐和信息素引導的多目標黑寡婦優化算法

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

2.1 MBWOA算法總體框架與復雜度分析

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

式中，fix為取整函數，N為種群規模，Va和L為控制N1的參數，t為當前迭代次數，maxgen為最大迭代次數。

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

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

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

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

2.2 兩個體角逐機制

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

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

其中，P是[0,1]內的隨機概率，beta是（-1,1）之間的隨機值，m是（0.4，0.9）之間的隨機值，是從當前種群中隨機選取的一個個體。

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

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

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

最后，對經過調整之后的Ai′和Vi′進行越界處理。算法1描述了兩個體角逐機制。

算法1兩個體角逐機制

2.3 三個體角逐機制

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

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

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

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

算法2三個體角逐機制

2.4 改進信息素機制

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

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

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

算法3改進信息素機制(Ai′,)

2.5 MBWOA的收斂性證明

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

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

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

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

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

定理1MBWOA 算法中，黑寡婦蜘蛛個體狀態Ii一步轉移到另一個狀態Ij的轉移概率為：

其中，個體全局最優解的一步轉移概率為：

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

定理2黑寡婦蜘蛛個體最優狀態集M是一個閉集。

證明設黑寡婦蜘蛛個體狀態為最優狀態，根據算法的執行策略，其下一時刻的狀態，顯然也為最優狀態。依據式（16）、式（17）可知，當因此，黑寡婦蜘蛛個體最優狀態集M是一個閉集。

定理3MBWOA 算法中，最優黑寡婦蜘蛛群體狀態集G是一個閉集。

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

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

定理5當黑寡婦蜘蛛群體內部位置迭代次數趨于無窮時，群體狀態序列必將進入最優狀態集H。

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

定理6MBWOA 收斂于全局最優解。

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

3 實驗與分析

本文的實驗使用一臺Intel Core i5-6300HQ 2.30 GHz CPU 和Windows 10 操作系統的筆記本電腦，算法用MATLAB R2018b編寫。

3.1 多目標性能指標

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

IGD：用于估算每一個真實PF上的參考點P*到最近的解的距離的平均值。對于測試的多目標優化算法，其IGD 值越小，則表明該算法收斂性和多樣性越好。IGD表達式為：

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

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

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

Spread：表示多目標優化算法在非支配區域中的個體分布均勻程度，即測量整個已知的真實PF中向量的分布情況，算法的Spread 值越小，算法的解集多樣性越好，分布越均勻。其表達式為：

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

3.2 對比算法與基準函數

為驗證MBWOA 算法的性能，選取了4 個當前主流的多目標優化算法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 算法進行比較。

這里使用的4 個對比算法的源代碼都可以在PlatEMO[29]中找到。為了實驗的公平性，所有對比算法統一沿用其原始論文的默認參數，如表1所示。基準測試問題包括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 是三目標問題之外都是雙目標問題，決策變量都是30 個。5 個ZDT 問題（ZDT1～ZDT4、ZDT6）都是雙目標問題，ZDT1～ZDT3決策變量是30 個，ZDT4 和ZDT6 決策變量是10 個。由于ZDT5是一個二進制問題，在測試中未被選用。

表1 對比算法參數設置Table 1 Parameter setting of comparison algorithms

3.3 實驗對比分析

本實驗中每個算法在每個測試問題上獨立運行30 次，每次運行對算法所得的解集評估10 000 次。實驗收集了這30 次的平均值和標準差進行比較，標準差數據列在平均值下一行。表中的粗體表示每個問題的最優結果。為了得到統計上可靠的結論，用α=0.05 的顯著性水平進行了Wilcoxon 秩和檢驗，以顯示MBWOA與對比算法之間的統計學差異。

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

表2 各算法HV實驗結果Table 2 HV experimental results of each algorithm

表3 列出了MBWOA 與對比算法在15 個測試問題上的Spread 平均值和標準偏差。其中，MBWOA在11 個測試函數中取得了最優。相比之下，只有LMOCSO 在其他4 個測試函數中取得了最優。其中，在ZDT2 中，MBWOA 所取得的解略遜于LMOCSO。總的來說，在大多數情況MBWOA 在這些測試函數上所產生的解集，相比其他4個對比算法而言，多樣性更好、更穩定、解集分布更均勻。

表3 各算法Spread實驗結果Table 3 Spread experimental results of each algorithm

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

表4 各算法IGD實驗結果Table 4 IGD experimental results of each algorithm

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

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

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

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

結合IGD 統計表可以發現，在RM-MEDA 測試問題中，MBWOA 能夠在F1～F6 中基本能夠完全收斂到真實PF上，在復雜程度更高的F7～F10 問題中，只能部分收斂于真實PF，但相比對比算法而言，更逼近真實PF，收斂速度也更快。對于ZDT 測試問題，MBWOA 也表現出了良好的求解能力。在所有測試中，MBWOA 都能夠收斂到所有問題的真實PF上，且收斂速度相比對比算法而言更快。總的來說，測試表明MBWOA 具有優秀的求解能力，更好的收斂性、多樣性和更高的收斂精度。

3.3.2 收斂速度分析

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

圖3 各測試函數IGD指標變化趨勢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次評估時接近收斂，F2 中LMOCSO 在8 000 次評估時收斂并接近于MBWOA 所取得的最小值。在F8 中，MOEA/D/DU最終取得了最小的IGD 值，其他算法在10 000 次評估完成時尚未收斂。

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

3.3.3 算法耗時

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

表5 獨立實驗30次的平均運行時間Table 5 Average running time of 30 independent experiments單位：s

3.3.4 角逐機制和改進信息素機制及其融合的有效性驗證

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

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

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

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

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

MBWOA-ago 和MBWOA 的區別是使用了改進前的信息素機制，而其他策略相同。圖4 展示了這兩個算法在測試問題F5、F6、ZDT1 和ZDT3 上評估10 000 次所得到的Pareto 前沿。可以清楚地看到，MBWOA-ago 在4 個測試問題中都不能完全收斂到整個真實PF，有些部分沒有解或是與真實PF之間有一定的距離，而MBWOA則收斂到了4個測試問題的整個真實PF上。說明改進信息素機制提升了算法搜索能力，增加了算法的收斂性和多樣性，提高了收斂精度。

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

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

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

最后，在3 種指標的實驗中MBWOA-PH 和MBWOA-COM 均優于BWOA，而融合了兩種策略的MBWOA 優于上述3種算法，說明本文所用的兩種角逐機制和改進信息素機制的有效性，證明了融合兩種策略的合理性。

4 結束語

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