基于改进灰狼算法的多任务优化算法

史光伟，王启任

（天津工业大学电子与信息工程学院，天津 300387）

近年来，多任务优化（multi-task optimization，MTO）[1-6]已经成为智能优化领域的新兴研究方向，MTO 关注如何同时解决多个优化问题并提高独立解决各问题的性能，在图像处理[7]、路径规划[8]和互联网[9]等领域MTO 技术已经展现出优势。进化多任务方法[10]和多因素优化方法[11]是多任务优化的两类重要分支。由Ong 等[5]提出的感知多任务算法（cognitive multitasking algorithm，CMA）是进化多任务的典型代表，其能够在统一的基因型空间中进行跨域多任务优化。由Gupta 等[4]提出的多因素进化算法（multi-factorial evolutionary algorithm，MFEA）是多因素优化的典型代表，该算法利用遗传算法来实现了不同任务之间的信息交互以及个体的更新。相比于CMA 算法，MFEA 通过发挥任务之间潜在的互补性来实现知识共享，具有更好的寻优性能。

2017 年，深圳大学Chen 等[12]提出了一种基于协同进化模因算法的进化多任务单目标优化算法。该算法提出了一种基于准牛顿的局部搜索方法，显著提高了收敛速度。2018 年，华南理工Chen 等[13]提出了一种基于模因多目标差分进化的多任务优化方法。该算法的关键思想是使用多个子种群来解决多个任务，每个子种群专注于解决单个任务。2020 年，南方科技大学LYU 等[14]提出了一种基于头脑风暴的多任务优化算法，该算法通过所提出的头脑风暴操作实现各组成任务的优化和不同任务之间的知识转移。以上所提到的算法都是基于MFEA 进行改进的，大都存在寻优精度受限、计算耗时长的问题。

基于上述问题，本文提出一种基于改进灰狼算法的多任务优化算法（improved grey wolf algorithm based multi-task optimization algorithm，IGWMTO）。该算法采用灰狼算法（GWO）取代MFEA 中的遗传算法（GA），并引入抗扰因子和动态权重参数来对狼群个体进行更新，以期进一步提高多任务优化算法的优化性能。

1 基本原理

1.1 多任务优化

在多任务场景中，通常存在一些有用知识可以用来解决某任务问题，同时也有助于求解其他任务问题[15]。因此，通过将多个任务问题以某种方式进行关联，将有助于改善寻优精度和寻优效率。给定一个具有k个任务的MTO 问题，在不失一般性的情况下，假设所有任务都是单目标、无约束的最小化问题。定义第j个任务为Tj，其目标函数为fj：Xj→R。其中Xj为Dj维度的解决空间，R 为实数域。MTO 的目标是为k个任务找到全局最优值，即

若在特定任务的解决空间上施加了约束条件，则需将约束函数与任务的目标函数一起考虑优化。

1.2 MFEA 算法

MFEA 的核心思想是利用n个个体的种群pop=来同时寻找k个任务的全局最优值，其中pi表示种群中的个体。MFEA 算法主要由3 个部分组成：种群初始化、遗传机制和选择性评价[16]。对于种群初始化，定义第j个任务的维度为Dj，定义维度等于max{Dj}的统一搜索空间Dmultitask。在初始化过程中，每个个体都被赋予一个由Dmultitask随机变量组成的向量[17]。同时，MFEA 提出以下定义用于评估每个个体的特征。

（1）因素代价：每个个体在所有任务上的因素代价Ψ 被定义为

式中：λ 为惩罚因子；δ 和f为当前个体在该任务上的约束违反总数和目标函数值。

（2）因素等级：每个个体在所有任务上的因素等级r是利用Ψ 对所有个体进行从小到大的排序的索引。

（3）技能因子：每个个体的技能因子τ 是个体在所有任务中能力最好的任务的索引，即

（4）标量适应度：每个个体的标量适应度φ 被定义为

（5）多因素最优：如果个体pi是k个任务的全局最优，则称其为多因素最优。

对于遗传机制，MFEA 采用选择性交配和选择性模仿2 种方法实现信息在不同任务之间的转移，并通过随机交配概率来平衡搜索空间的开发和探索。在选择性评估过程中，MFEA 采用一种垂直文化传播方法来对种群个体进行评估，该方法允许后代模仿上一代的技能因子，进而减少了计算成本[18]。

1.3 灰狼算法

灰狼算法[19]对狼的社会等级进行数学建模，将最优个体定义为α 狼，第二优和第三优的个体分别定义为β 狼和γ 狼，其余剩下个体为ω 狼。灰狼算法利用α 狼、β 狼和γ 狼的位置信息对狼群个体进行更新迭代，从而完成最优解的寻找，即针对猎物的包围过程。上述思想可建模为

式中：t为当前迭代次数；A和C为系数向量；Xp为猎物位置向量；X为灰狼位置向量；D为当前位置与猎物之间的距离。系数向量A和C可表示为：

在迭代过程中，向量a由2 线性下降到0，而r1和r2为[0,1]中的随机向量。Dα、Dβ和Dγ分别表示当前候选灰狼与最优3 头狼之间的距离，且有

式中：Xα、Xβ和Xγ分别为α、β 和γ 狼的位置向量；X为灰狼的位置向量。进一步，狩猎过程可建模为

其中

2 基于改进灰狼算法的多任务优化算法

本文所提IGWMTO 算法的工作流程如图1 所示。

图1 IGEMTO 算法流程图Fig.1 Flow diagram of IGWMTO

相比于MFEA 算法，本文IGWMTO 算法的优势主要体现在以下方面：

（1）采用灰狼算法代替MFEA 算法的遗传算法，利用个体在所有任务上的技能因子和因素等级来对狼群进行分类，并利用适应度值动态更新个体隶属任务。

（2）引入狮群优化算法中的抗扰因子[20]，增大了灰狼随机游走初期的范围，加强了全局勘探能力，使α 狼、β 狼和γ 狼的位置更新具有一定的随机性，进而提高种群的多样性，并且有效避免了陷入局部最优的问题，从而得到最优解。

（3）基本GWO 算法通过计算3 个最佳灰狼位置的平均值来更新灰狼位置，这种策略并没有考虑3 头狼在群体狩猎活动中的贡献度问题。由于GWO 算法的α 狼并不一定是全局最优解，这时在不断迭代中，随着其余ω 狼向这3 头狼逼近，容易陷入局部最优。本文算法引入动态权重参数来平衡全局搜索和局部搜索的相互影响，可进一步提高算法收敛速度和精度。

IGWMTO 算法的具体步骤主要包括以下部分。

步骤1：随机生成N个个体，并对所有个体进行初始化处理。

步骤2：计算每个个体在所有任务上的适应度值并构建矩阵，其可以表示为

式中：k为任务数量，矩阵元素为每个个体针对某个任务的适应度值。

步骤3：将矩阵中每一行的元素进行排序，并提取每个个体在任务上的排序索引值构建因素等级向量，其向量n=（n1，n2，…，nk）内部元素为该个体在所有任务上的因素等级，其中最小元素所对应的任务为该个体的技能因子η（η∈[1，2，…，k]）。

步骤4：根据该技能因子对狼群进行分类，将排序前三的索引对应的个体分别记作该任务上的α、β 和γ 狼，可以获得其位置向量Xα、Xβ和Xγ。

步骤5：在对狼群个体进行更新迭代时，考虑到α狼具有很强的局部搜索能力，但容易使得种群陷入局部最优。因此，引入狮群优化算法的扰动因子，使得狼群个体更新保持一定随机性，扩大搜索范围并避免算法过早收敛。进而将式（11）修正为：

式中：ω1为成年狮子比例因子且是（0，1）中的一个随机数，为使算法收敛更快，值一般小于0.5。ω2为母狮扰动因子，其定义为

式中：s表示狮子在活动范围内移动的最大步长；l和h分别表示狮子运动范围空间各维度的最小均值和最大均值；T为最大迭代次数；t为当前迭代次数；ω3为幼狮干扰因子，其可以表示为：

式中：T为最大迭代次数；t为当前迭代次数。在上述公式中，ω2和ω3的步长均设为1。

步骤6：计算当前迭代次数下的狼群个体适应度值。由式（10）可知，典型灰狼算法ω 狼受当前迭代次数占主导地位的灰狼（α、β 和γ 狼）影响。但是，考虑到α、β 和γ 狼的能力存在差异，并且随着迭代次数的增加，ω 狼会受到α、β 和γ 狼的动态影响。因此，为了平衡全局搜索和局部搜索之间的相互影响，本文引入动态权重参数C[21]来更新种群的个体值，其计算公式为

式中：C为一个随机向量，其范围为[0，1]。

步骤7：根据式（17）计算当前迭代次数下个体在所有任务上的适应度值并进行对比。若相较于原始任务，该个体在另一任务上的适应度值更好，则需动态更新该个体所属任务，并围绕该任务的头狼继续更新。

步骤8：对所有任务中的头狼进行更新，重复上述步骤，直到最大迭代次数。

3 实验及结果分析

本文将种群规模与迭代次数都设为100，在Benchmark 测试函数上对所提算法进行测试，表1 为测试函数设置情况，且令各维度的搜索空间相同。选取MFEA 作为参照进行对比，令2 种算法分别在多个不同的优化问题上进行寻优迭代，并将统计结果记录于表2 中，针对所有的优化问题，给出了MFEA 和本文算法运行100 次的最佳适应度值、均值和方差。将每个问题所对应的收敛曲线绘制于图2—图5。

表1 Benchmark 测试函数Tab.1 Benchmark test functions

表2 MFEA 和IGWMTO 在不同问题中的结果Tab.2 Results of MFEA and IGWMTO on different problems

图2 MFEA 和IGWMTO 在问题1 上的收敛趋势Fig.2 Convergence trends for MFEA and IGWMTO on problem 1

图3 MFEA 和IGWMTO 在问题2 上的收敛趋势Fig.3 Convergence trends for MFEA and IGWMTO on problem 2

图4 MFEA 和IGWMTO 在问题3上的收敛趋势Fig.4 Convergence trends for MFEA and IGWMTO on problem 3

图5 MFEA 和IGWMTO 在问题4 上的收敛趋势Fig.5 Convergence trend of MFEA and IGWMTO on problem 4

由表2 可以看出，IGWMTO 在4 个不同的优化问题中的结果均优于MFEA 的寻优结果。上述结果表明，IGWMTO 具有良好的快速寻优能力和深度寻优能力。

算法运行时间如表3 所示。

表3 IGWMTO 与MFEA 的运行时间Tab.3 Running time of IGWMTO and MFEA s

由图2—图5 可知，相比于MFEA，IGWMTO 在所有任务中的曲线下降速度更快，收敛速度和效果更好。由表3 可知，IGWMTO 在运算速度上也存在优势，相较于MFEA 算法，其在4 个不同优化问题中的运行时间分别降低了约80.1%、76.8%、74.8%和76.5%。

4 结束语

本文提出了一种新颖且易于实现的基于改进灰狼算法的多任务优化算法，其通过计算个体的因素等级和技能因子来对狼群进行分类并根据适应度值动态更新个体隶属任务，引入狮群优化算法的抗扰因子和动态权重参数来对原始灰狼算法进行改进。该方法不仅提高了种群的多样性，而且平衡了全局搜索和局部搜索之间的相互影响，大大提高了算法收敛的精度和速度。与MFEA 算法相比，本文IGWMTA 算法在4个不同优化问题中的运行时间分别降低了约80.1%、76.8%、74.8%和76.5%。