角逐和信息素引导的多目标黑寡妇优化算法

傅彦铭，许励强+，祁康恒，沈煜鸣，屈迟文

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 用于解决一些实际工程问题。