「工业人工智能」论文分享：一种面向约束多解多目标优化的多任务辅助进化算法

研 究 背 景

约束多解多目标优化问题（CMMOPs）是指具有多个等价约束Pareto最优解集映射至目标空间同一个约束Pareto前沿的优化问题。该类问题在现实生活中广泛存在，例如选址问题[1]，即距离最小化问题。如图1所示，有三个目标需要优化：1)从选定地点到学校的距离；2)选定地点到医院的距离；3)所选地点到便利店的距离。图1显示了四个与这些目标位置具有相同最小距离的非支配选项，分别标记为选项1、选项2、选项3和选项4。然而，选项1和选项4位于河流中，是不可行解。选项2、选项3是两个满足约束条件的Pareto最优解，如果算法能找到满足约束条件的所有Pareto最优解，则能为不同租户提供更多的备选方案。

图1：约束多解多目标选址问题示意图

根据目标空间中约束Pareto前沿（CPF）和无约束Pareto前沿（UPF）之间的关系，CMMOPs 可以分为四类（如图2所示）：

图2：目标空间中CPF与UPF的关系

然而，决策空间中多个等效Pareto最优解集（PS）的存在给问题增加了复杂性，导致图2所示的每类又包含四种不同的情景。以图2(a)为例， 约束PS（CPS）与相应的可行域（FR）之间的关系导致以下四类情况的产生（如图3所示）：

不同大小形状的CPS和FR会导致算法搜索的不平衡。不同的CPS拥有不同大小的吸引区域，当CPS间的吸引区域的规模相差较大时，算法倾向于搜索吸引区域规模较大的CPS，从而忽略吸引区域规模较小的CPS。与之相似，算法更倾向于搜索FR较大的CPS而忽略FR较小的CPS。

图3：决策空间中CPS和FR的分布

解决CMMOPs的难点在于同时实现以下三种平衡：

本文提出CMMO-MTA方法

为解决CMMOPs中的挑战问题，本文提出了一个多任务辅助的优化求解框架（CMMO-MTA）。如图4所示，CMMO-MTA算法主要包括三个任务：一个主任务（T_M）和两个辅助任务（T_A1和T_A2）：

T_M为原始优化问题：

T_A1为约束条件被放缩的优化问题：

T_A2为无约束条件的优化问题：

在初始化阶段，为三个任务分别生成一个随机种群，其中T_M包含N个候选解，T_A1和T_A2包含N/2个候选解；然后更新T_A1中的松弛参数。在优化阶段，每个种群根据具体任务特征进行选择、交配和评估。随后，在父代种群和子代种群结合的阶段，算法进行知识迁移操作。T_A1和T_A2的子代种群被视作有价值的知识迁移给T_M。这种单向的知识迁移确保了T_A1和T_A2始终专注于各自的优化任务，不受T_M的影响，从而保证T_A1和T_A2可以给T_M提供更有效用价值的专业知识。此外，针对不同任务采用不同的环境选择策略，选择有潜力的候选解进入下一代。最后，CMMO-MTA算法将执行基于空间平衡的选择机制，选择在决策空间和目标空间都表现出色的精英候选解作为最终输出。

在CMMO-MTA算法中，T_A2的优化与T_M保持一致。其优化思路参考SPEA2[2]算法。具体来说，使用适应度值F_obj作为选择标准来构建亲本交配池，其中R代表了对收敛性的量化，而D_obj包含了对目标空间多样性的考量。

F_obj(x)=R(x)+D_obj(x)

由于T_M和T_A2在交配池构建中考虑了目标空间多样性，故使用决策空间优先环境选择方法（DPES）决定存活到下一代的个体。具体来说，DPES采用截断方法来控制种群大小，而截断方法所使用的距离是在决策空间中进行计算的，从而避免在决策空间中移除边界解。

由于T_A1的约束条件处于放缩状态，T_A1以一种渐进的方式向T_M收敛。采用不同于T_M的优化方法，不仅有效地增加优化方法的多样性，且为T_M探索到更多有价值的知识。首先在构建亲本交配池时，采用适应度值F_two作为构建标准，其中D_two综合考虑了目标空间和决策空间的多样性。

F_two(x)=R(x)+D_two(x)

因此，采用基于生态位平衡的环境选择方法（NBES）以显式小生境的思想来保护决策空间的多样性。首先，执行SPEA2进行预选。然后，针对优化问题的多模态特性将种群划分为位于各个PS周围的多个小生境，并以每个小生境为最小单位，独立地选择优秀个体存活至下一代。

为了实现决策空间和目标空间中的搜索平衡，SBSM首先选择所有的非支配解作为精英解，若精英解总数超过N，则依次移除最拥挤的个体，直到精英解总数等于N（如图5所示）。其中，在计算最拥挤个体的过程中，综合考量决策空间和目标空间的个体拥挤度，如下式所示，

分别在决策空间和目标空间中选择距离当前个体最近的三个个体，计算距离并求和。拥有最小距离的个体被视作最拥挤的个体，依次从精英集合中删除。该方法不仅考虑了决策空间个体拥挤度，同时也考虑了目标空间的个体拥挤度，这样的综合考量使决策空间和目标空间的搜索平衡得以实现。

图5：基于空间平衡的选择机制（SBSM）流程图

仿 真 实 验

本文的仿真实验分别采用两组基准函数集（CMMF[1]和CMMOP[3]）共31个测试问题 以及一个实际应用问题，评估本文提出的CMMO-MTA在CMMOPs上的求解性能。

CMMO-MTA 与七种先进的优化算法进行了比较，即C-TAEA[4]、CMOEA-ES[5]、PPS[6]、DN-NSGA-II[7]、MO_ Ring_PSO_SCD[8]、CMMODE[1]和CMMOCEA[3]。具体实验结果排名如表1所示。结果表明，CMMO-MTA在决策空间和目标空间都表现出较强的竞争力。

表1：算法的指标排名

为了验证CMMO-MTA的关键部件的有效性，设计了四个变体：

图6所示为CMMO-MTA及其变体在四个测试问题上的结果。通过与VARIANT1，VARIANT2和VARIANT3的对比结果可得CMMO-MTA 中的每个任务都发挥了关键作用。通过利用多任务优化框架，CMMO-MTA 实现了约束条件与目标函数之间，探索与开发之间的平衡。与VARIANT4的对比结果证明了所提出的 SBSM在提高目标空间性能方面的有效性，使得决策空间和目标空间之间关注度得到有效平衡。

图6：CMMO-MTA和变体在四个测试问题上的比较结果

为评估 CMMO-MTA 在实际应用中的有效性，本文利用选址问题进行了仿真测试。该问题包含三个相互冲突的最小化目标，即找到与三类基本生活设施（即学校、医院和便利店）距离最小的可行位置。为确保公平比较，每种方法都独立运行了 31 次。图7以箱型图的形式给出了比较结果（IGDX 和 IGD）。结果表明，采用了多模态处理技术的算法，如 CDP_DN-NSGA-II、CDP_MO_Ring_PSO_SCD、CMMOCEA、CMMODE和CMMO-MTA）都在决策空间（IGDX）表现优异。当考虑目标空间（IGD）时，与其他七种算法相比，CMMO-MTA始终表现出稳健而有前途的结果。这意味着CMMO-MTA在解决实际问题方面的潜力。

图7：选址问题的比较结果

总 结

本文提出了一种多任务辅助进化算法CMMO-MTA用于约束多解多目标优化问题的求解。CMMO-MTA 利用多任务优化框架，将CMMOPs转化成一个主任务与两个辅助任务，辅助任务专注于自身问题，独立优化，并向主任务传输有效用价值的知识。此外，还设计了两种环境选择策略，从不同角度增强了算法的探索能力。实验结果表明，CMMO-MTA算法在各种CMMOPs上都展现了优越的性能。

目前CMMOPs的研究仍处于早期阶段，因此，还具有许多值得深入研究的问题，例如，约束条件或目标函数随时间变化的CMMOPs。针对这类复杂的优化问题，未来，将CMMO-MTA的多任务框架与其他先进的机器学习方法（如图神经网络）相结合的研究思路也是是值得进一步研究的课题。

初稿：郑恬子

复审：颜学明

终审：金耀初