基于自适应迁移知识来源的约束多因子进化算法

A Constrained Multifactorial Evolutionary Algorithm Based on Adaptive Transferred Knowledge Sources

摘要: 在约束多任务优化中，如何在任务之间迁移知识是一个复杂的问题。现有的方法是从源任务的种群中随机选择个体进行迁移，忽略了源任务中一些目标函数值好的个体对目标任务的积极影响。本文针对约束多任务优化问题，提出基于自适应迁移知识来源的约束多因子进化算法。首先，利用一个归档集来存储每个任务中目标函数值最好的个体，用于产生高质量子代。然后，提出一个自适应迁移知识来源策略，通过一个自适应概率来确定被迁移的个体是来自于种群还是归档集。实验结果表明，与其他现有的约束多任务进化算法相比，所提算法可以产生更好的或至少相当的性能。

Abstract: In constrained multitask optimization, transferring knowledge between tasks is a complex problem. Existing methods randomly select individuals from the source task’s population for transfer, disregarding the positive impact of individuals with good objective function value on the target task. This paper proposes a constrained multifactorial evolutionary algorithm based on adaptive transferred knowledge sources. Firstly, an archive is used to store individuals with the best objective function value in each task to generate high-quality offspring. Then, an adaptive transfer knowledge source strategy determines whether the transferred individuals are from the population or the archive through adaptive probability. The experimental results demonstrate that the proposed algorithm can achieve better or at least comparable performance.

1. 引言

多任务优化(MTO) [1] 旨在利用任务间的知识迁移，同时求解多个优化任务。在这些优化任务中，任务之间是存在相关性的。通过利用任务之间的知识迁移，可以帮助整个MTO问题获得更好的性能 [2] [3] [4] 。近几年来，MTO在无约束多任务优化领域取得了显著的进展，并成功应用于求解一些现实问题，如车辆路径问题 [5] 、铁路旅客舒适度评价问题 [6] 、光伏模型的参数提取 [7] 。然而，在现实生活中，许多优化问题都包含特定的约束。以多辆车的路径规划为例，这些路径规划问题存在许多的约束条件(如货物需求量、交货时间、车辆容量限制等)。因此如何高效求解带约束的MTO问题具有重要的研究意义。

目前关于约束多任务优化(CMTO) [8] 的研究比较少。在现有的CMTO研究中，研究人员在 [8] 中设计了一组CMTO基准问题，并将可行性优先约束处理技术 [9] 结合到多任务进化算法中，用于求解CMTO问题。后来，Xing等人提出了一个基于自适应归档集的约束多因子进化算法(A-CMFEA) [10] 。A-CMFEA使用归档集策略和变异策略来防止种群陷入局部最优，使用一个自适应的随机配对概率策略来调整知识迁移的频率。

相比于直接剔除违反约束的个体 [8] ，利用归档集保留部分目标函数值好的个体能够帮助种群跳出局部最优，从而收敛到全局最优。然而，在先前的基于归档集的约束多任务优化算法中，归档集中的个体只是简单地参与环境选择，一些目标函数值好的个体并没有得到充分的利用。另外，在当前的约束多任务优化中，被迁移的个体主要是从种群中获取的，然而当目标任务的约束最优解与源任务的无约束最优解更靠近时，从归档集中选择目标值小的个体进行迁移更有利于加快目标任务的进化。

因此，为了充分利用种群中目标函数值好的个体中的有用信息，本文提出了一个基于自适应迁移知识来源的约束多因子进化算法。在所提算法中，将可行性优先约束处理技术结合到AT-MFEA中，并增加了归档集策略和自适应迁移知识来源策略。本文的主要贡献如下：

1) 提出了一个新的归档集策略用于保留部分目标函数值最好的个体，以充分利用目标函数的有用信息以产生更多高质量子代，从而帮助种群跳出局部最优。

2) 提出自适应迁移知识来源策略。通过计算从归档集中获取的迁移个体和从种群中获取的迁移个体的成功率，比较两者的大小，自适应确定被迁移个体的种群来源。

3) 广泛的实验验证了所提算法的有效性。

本文的其余部分如下。第二节介绍了所提出的算法。第三节介绍了实验和结果，并对其进行了分析。第四节为本文进行了总结。

2. 所提算法

2.1. 相关知识

2.1.1. 约束多任务优化

CMTO是指在进化过程中同时优化两个或两个以上的约束任务，并为每个任务找到最优解 [8] 。具体地，对于一个有K个任务的CMTO问题，令 $X_i\left(i=1,2,\cdots ,K\right)$ 为第i个任务的搜索空间， $f_i:X_i\to ℝ$ 为目标函数，并假设所有任务都是最小化问题。每个任务有m个约束， $g:X_i\to ℝ$ 表示不等式约束， $h:X_i\to ℝ$ 表示等式约束，CMTO的目标是找到一组可行解集 $\left\{x_1^{*},x_2^{*},\cdots ,x_K^{*}\right\}$ ，使其满足：

$\begin{array}{c}{x}_i^{*}=\arg \min f_i\left(x\right)i=1,2,\cdots ,K\\ g_{i,j}\left(x\right)\le 0\text{j=}1,2,\cdots ,p\\ h_{i,\text{k}}\left(x\right)=0\text{k=}p\text{+}1,\cdots ,m\end{array}$ (1)

一般地，等式约束可以通过一个趋向于0的正数 $\epsilon$ 松弛为一个不等式约束：

$\left|h_{i,k}\left(x\right)\right|-\epsilon \le 0$ (2)

如果一个解 $x_i^{*}$ 满足 $g_{i,j}\left(x_i^{*}\right)\le 0$ 且 $\left|h_{i,k}\left(x_i^{*}\right)\right|-\epsilon \le 0$ ，则称 $x_i^{*}$ 为可行解。另外，为了在多因子优化环境比较不同个体的质量，每个个体都具备一组属性 [1] ，其定义如下：

定义1 (因子代价)：个体 $p_i$ 在任务 $T_j$ 上的因子代价定义为 ${\psi }_j^i=\lambda \cdot {\delta }_j^i+f_j^i$ ，其中 $j\in \left\{1,2,\cdots ,K\right\}$ ， $\lambda$ 为惩罚系数， $f_j^i$ 和 ${\delta }_j^i$ 分别为个体 $p_i$ 在任务 $T_j$ 上的目标函数和总体约束违反程度。如果个体 $p_i$ 在任务 $T_j$ 上是可行的，则其约束违反程度为0， ${\psi }_j^i=f_j^i$ 。

定义2 (因子排序)：个体 $p_i$ 在任务 $T_j$ 上的因子排序 $r_j^i$ 定义为个体在种群中的索引，而这个索引是由种群中所有个体的因子代价 ${\psi }_j^i$ 从小到大的排序来确定。

定义3 (适应值标量)：个体 $p_i$ 的适应值标量定义为 ${\phi }_i=1/\min \left\{r_j^i\right\}$ ， $j\in \left\{1,2,\cdots ,k\right\}$ 。

定义4 (技能因子)：个体 $p_i$ 的技能因子定义为 ${\tau }_i=\arg {\min }_j\left\{r_j^i\right\}$ ， $j\in \left\{1,2,\cdots ,k\right\}$ 。

定义5 (多因子最优)：当且仅当 $p^{*}$ 是所有K个组成任务的全局最优时，它被称为多因子最优。

2.1.2. 仿射增强多因子进化算法(AT-MFEA)

为了求解异构CMTO问题，即不同任务的决策空间或适应度空间不相似的CMTO问题，Xue等人在 [11] 中提出了仿射增强多因子进化算法(AT-MFEA)。在AT-MFEA中，作者设计了一个比较容易计算的秩损失函数，用于减少源任务和目标任务之间由于排序的场景不匹配导致的问题。该秩损失函数计算公式如下：

${\varphi }^{*}=\underset{\varphi \in \Phi }{{\displaystyle \min }}{\displaystyle {\int }_x\Vert \mathcal{R}\left[p^s\left(x\right)\right]-\mathcal{R}{\left[p^t\left(\varphi \left(x\right)\right)\right]}^2\Vert }$ (3)

其中， ${\varphi }^{*}$ 表示从源任务到目标任务的映射解， $\Phi$ 表示完全映射空间， $\mathcal{R}$ 是排序操作， $p^s\left(x\right)$ 和 $p^t\left(\varphi \left(x\right)\right)$ 分别表示源任务和目标任务的高斯渐进分布模型。

在AT-MFEA中，仿射变换可以表示为：

$\tilde{x}={\varphi }_a\left(x;\theta \right)=xA+b$ (4)

其中 ${\tilde{x}}_{1\times n}$ 是迁移解， ${\varphi }_a(\cdot )$ 是仿射变换操作， $x_{1\times n}$ 是源任务中的解， $\theta =\left[A,b\right]$ 是仿射变换的参数集， $A_{n\times n}$ 和 $b_{1\times n}$ 分别是收缩变换和平移变换。在以上的变换中，通过多元高斯分布的数学推导可得到矩阵A和b，并通过(4)得到迁移解。

算法1给出AT-MFEA基于映射的任务间交叉的具体操作。首先输入来自不同任务的两个个体 $x_i$ 和 $x_j$ 及其相应的进化路径 $E^i$ 和 $E^j$ 。其中，被评估的个体从初始种群到当前种群被称为其进化路径。然后，根据进化路径，生成渐进表达式 $\left[p^i\left(x\right),p^j\left(x\right)\right]$ 。然后，通过源实例与目标实例的仿射变换，可得到参数矩阵 $\left[A_{ij},b_{ij}\right]$ 。通过式(4)，可以得到的转换解 ${x^{\prime }}_i$ 和 ${x^{\prime }}_j$ 。最后 $x_i$ 和 $x_j$ 与转化后的解杂交产生子代。

2.2. 归档集策略

在本文中归档集用于保存每个任务的前arc_maxsize个目标函数值最好的个体。用于参与子代的产生和迁移知识的选择，其更新过程由算法2给出。

首先，由归档集(archive)和子代种群(offspring)组成混合种群。然后在混合种群中根据技能因子，找到每个任务对应的子种群，将这些子种群中的个体的目标值进行排序，找到前arc_maxsize个目标函数值最小的个体放入到归档集中，这里的arc_maxsize表示每个任务的归档集的种群规模。

2.3. 自适应迁移知识来源策略

由于在没有先验知识的情况下很难知道源任务最优解和目标任务最优解之间的关系，一个简单有效的方式是通过比较两种迁移方式的成功率。具体地，一开始，先以初始概率atp0迁移归档集中的个体，然后在进化过程中，通过比较从归档集中迁移的个体的成功率和从种群中迁移的个体的成功概率，如果前者的概率大于后者，则增加其迁移概率，否则减少其迁移概率。算法3给出更新归档集个体的迁移概率的伪代码。

首先，输入6个参数，其中kt_num和akt_num分别表示来自种群和归档集的迁移个体的数量，skt和sakt，分别表示来自种群的迁移个体成功的数量和来自归档集的迁移个体成功的数量，其初始值均为0。在本文中，将在种群中存活的迁移个体称为成功个体。atp(gen-1)为上一代的atp，c为用于调整atp的常数。行1~2计算个体的成功率，行3~7更新atp。

2.4. 所提算法框架

本文将所提的归档集策略和自适应迁移知识来源策略嵌入到基于可行性优先约束处理技术的AT-MFEA中，其细节由算法4给出。

一开始，我们初始化种群并为每个个体分配技能因子，接着我们初始化归档集和所有参数，然后判断是否满足终止条件，如果不满足则进入主循环，否则退出主循环。

在主循环中，首先，我们先从种群和归档集的混合种群中选择两个个体 $x_i$ 和 $x_j$ ，如果它们的技能因子相同，则执行任务内的SBX交叉操作产生两个子代 $c_1$ 和 $c_2$ ，并分配技能因子。如果它们的技能因子不同且随机数rand1小于迁移概率rmp，则执行任务间知识迁移操作。当执行任务间知识迁移操作时，随机生成一个随机数rand，若rand小于 $\text{atp}\left({\tau }_i\right)$ ，则从源任务的归档集中选择个体与当前个体进行任务间映射交叉产生子代，此时 $\text{akt\_num}\left({\tau }_i\right)+1$ 。否则，则从源任务的种群中选择个体与当前个体进行任务间映射交叉产生子代，此时 $\text{kt\_num}\left({\tau }_i\right)+1$ 。并令子代继承当前个体的技能因子。如果 $x_i$ 和 $x_j$ 的技能因子不同且 $rand1\ge rmp$ 时，我们从混合种群中随机选择两个分别与 $x_i$ 和 $x_j$ 有相同技能因子的 $x_1$ 和 $x_2$ ，通过SBX交叉操作产生子代 $c_1$ 和 $c_2$ 。接着，我们合并当前种群、子代和归档集，利用可行优先约束处理技术更新种群 $\text{P}\left(t+1\right)$ ，利用算法2更新归档集 $\text{archive}\left(t+1\right)$ 。然后，在31~33行，分别计算每个任务对应的子种群中来自源任务归档集的迁移个体的数量 $\text{sakt}\left({\tau }_i\right)$ 和来自源任务种群的迁移个体的数量 $\text{skt}\left({\tau }_i\right)$ ，最后，根据算法3更新atp。

3. 实验设计和分析

3.1. 参数设置

对比实验的参数设置为：

1) 目标函数维度：50

2) 种群规模：100 * K，K为测试问题的任务数量

3) 最大函数评估次数：100,000

4) 独立运行次数：30

5) 所提算法的其他参数设计

a) SBX交叉算子： $p_c=1,{\eta }_c=2$

b) 多项式变异： $p_m=1/D_{\dim },{\eta }_m=5$

c) 迁移概率rmp：rmp = 0.3，初始atp0：atp0 = 0.3，常数c：c = 0.01

d) 归档集种群规模arc_maxsize：arc_maxsize = 0.1 * 100 * K

6) 对比算法的其他参数设置与其原文献相同。

3.2. 基准函数和对比算法

本文选用CMT [8] 系列作为约束多任务优化问题的基准测试函数。另外，本文将可行性优先约束处理技术嵌入到MFDE [12] 、MFEA [1] 、MFEA-II [13] 、MFMP [14] 、MTEA-AD [15] 、AT-MFEA [11] 中构建了6个约束多任务优化算法进行性能比较。分别记为PF-MFDE、PF-MFEA、PF-MFEA-II、PF-MFMP、PF-MTEA-AD、PF-AT-MFEA。

3.3. 所提算法在基准函数上的表现

本节将所提算法与6个对比算法在基准测试问题上进行性能比较，表1给出了各算法在测试问题上

Table 1. Average objective function values from 30 independent runs of 7 algorithms on the test instances

表1. 7个算法在测试实例上独立运行30次的平均目标函数值

Figure 1. The average objective function value convergence trends of 7 algorithms over 30 independent runs on test instances

图1. 7个算法在测试实例上独立运行30次的平均目标函数收敛趋势

独立运行30次获得的平均目标值。所有算法均在MATLAB R2021a上运行。在表1中用黑色粗体突出最好的结果。为了验证算法的性能，我们利用Wilcoxon秩和检验在0.05的显著性水平下分析算法的显著性。记号“+”，“−”和“=”分别表示比较算法优于、差于和近似于所提算法。需要注意的是，当目标函数值为“NaN”时，表明该算法在30次运行中都没有找到当前任务的可行解。

从表1可以看出，所提算法在9个问题18个任务中，有14个任务优于PF-AT-MFEA，这说明了本文所提的归档集策略和自适应迁移知识来源策略能够有效地提高算法的性能。可行性优先约束处理技术虽然能快速找到可行域，但对于可行区域小且不连续的任务，该方法容易导致算法早熟。而归档集保留部分目标函数值好的个体并参与子代的产生，有利于产生更多目标函数值更好的高质量子代，从而帮助种群穿越不可行区域到达离全局最优解更近的可行区域。另外，当目标任务的约束最优解与源任务的无约束最优解更靠近时，从源任务的归档集中选择迁移个体能够加快种群收敛。反之，当目标任务的约束最优解与源任务的约束最优解更靠近时，从源任务的种群中选择迁移知识能够加快种群收敛。而自适应迁移知识来源策略能够自适应地调整这两种迁移方式的频率。

表1最后一行的显著性分析结果表明，所提算法在9个问题18个任务中，分别有18、17、15、16、13个任务优于F-MFDE、PF-MFEA、PF-MFEA-II、PF-MFMP、PF-MTEA-AD。所提算法保留了PF-AT-MFEA的优势，同时增加的两个策略提高了算法的有效性。

另外，为了更加直观地比较这些算法的性能，我们在图1给出7个算法在CMT测试问题上独立运行30次后的平均目标趋势图。由于篇幅的限制，这里给出了CMT2-8的趋势图。从图1可以看出，在绝大数实验中，所提算法都获得了更快地收敛速度，这表明与其他约束多任务算法相比，所提算法有更好的收敛性。即使在进化的早期，所提算法也展现出了更显著的收敛性，这进一步验证了所提算法的性能优于其他算法。

4. 总结

考虑到基于可行优先的约束多任务算法容易使种群陷入局部最优，本文提出了一个新的归档集策略用于保存部分目标值好的个体，并让这些个体参与子代的产生。另外，考虑到目标任务的约束最优解与源任务的无约束最优解和约束最优解之间的位置关系，本文提出了自适应迁移知识来源策略，用于确定迁移知识是来自于源任务的归档集还是种群。本文将所提的两个策略应用于一个基于可行性优先约束处理技术的约束多任务算法上。数据实验结果表明所提算法获得了更好的性能，能够有效地求解约束多任务优化问题。