约束多目标优化问题（Constrained multi-objective optimization problems，CMOPs）普遍存在于现实生活中，在推荐系统、物流配送、路径规划等领域有广泛应用。CMOPs求解的难点主要在于如何在约束和目标之间实现有效平衡。事实上，大多数现有的约束处理技术（Constrained handling technique, CHT）都是为了实现这种平衡而设计的。
最近，有研究团队通过比较CDP[1]、SR[2]等几种具有代表性的CHT，发现CHT的性能与CMOPs的类型相关[3]。受此启发，智能算法研究中心的研究人员提出了一种新的CHT——考虑约束多目标优化问题类型的权衡模型（Trade-off Model，ToM）[4]。目前，该工作的相关论文成果已被智能优化领域的国际学术期刊IEEE Transactions on Cybernetics（JCR一区，影响因子11.448）录用。下面将对ToM进行详细介绍。
根据约束帕累托前沿（Constrained Pareto Front, CPF）和非约束帕累托前沿（Unconstrained Pareto Front, UPF）之间的关系，可将CMOPs分为三种类型[3]。如图1所示，Type I的CPF和UPF完全重合，Type II的CPF与UPF有部分交集，而Type III的CPF与UPF则无交集。
图1 三类CMOPs的示意图
一般而言，求解不同类型的CMOPs时，应当根据问题情形赋予约束和目标不同的重要性。对于Type I，仅通过优化目标即可实现问题的求解，即优化目标比满足约束更重要；对于Type III，一般认为满足约束比优化目标更加重要；而对于Type II，则对动态地平衡目标与约束提出了更高的要求。遗憾的是，实际问题的类型往往是事先未知的。根据问题的类型设计约束处理策略的思路似乎行不通。但是，无论问题的真实类型是什么，它必然属于上述三种类型之一。因此，在设计约束处理策略时，可针对这三种问题类型分别设计特定的机制来处理目标和约束之间的关系。ToM正是基于这种思路而设计的一种约束处理策略。
具体来说，ToM自动地将优化过程分为两个阶段：第一阶段优先考虑目标（Objective priority），第二阶段则优先考虑约束（Constraint priority）。两个阶段之间的切换是通过一种智能策略来自动实现的。第一和第二阶段分别是针对Type-I和Type-III问题而设计的，而两个阶段的自动切换对Type-II问题的求解是有益的。值得说明的是，ToM与Fan等人提出的PPS搜索策略[6]存在一些相似之处，但二者在设计初衷和具体实现等方面具有显著不同（详细讨论见文献[4]）。
图2 ToM算法总体框架图
算法1给出了ToM的总体框架，见图2。作为一种约束处理机制，ToM可集成在MOEA/D和NSGA-II算法框架内，它们分别是分解型和非分解型多目标演化算法的典型代表。这种集成非常容易实现，仅需将算法1中的第11行替换成MOEA/D或NSGA-II的程序即可。例如，图3给出了MOEA/D-ToM的伪代码，仅对原始MOEA/D的源程序作了少量修改。
图3 MOEA/D-ToM算法框架图
为验证ToM的有效性，我们做了大量的仿真实验：在MOEA/D[5]和NSGA-II[1]框架内，将ToM与几种主流CHT进行全面比较。表1给出了在MOEA/D框架内，不同CHT在各测试集的各类问题上得到的最优和次优HV指标值的百分比。结果显示，ToM在大多数情况下获得了最佳性能。
表1 在MOEA/D框架内各CHT获得的最优和次优HV结果的百分比
（最优和次优百分比分别用深灰色和浅灰色背景标注）
表2则给出了各个CHT在MOEA/D框架内的平均排序。可以看出，ToM几乎在所有情形下均取得最好排序。
表2 在MOEA/D框架内各CHT的平均排序
表3给出了各个CHT在NSGA-II框架内的平均排序。同样地，ToM几乎在所有情形下均取得最佳排序。以上实验结果表明，与其他CHT相比，ToM无论是在MOEA/D还是NSGA-II框架内都具有显著优势，是一种有效的约束处理机制。
表3 在NSGA-II框架内各CHT的平均排序
进一步地，我们将基于ToM的算法与主流的约束多目标演化算法进行比较。实验结果如表4所示，MOEA/-D-ToM取得了最佳排序。
表4 基于ToM的算法与主流算法在测试集上的排序
以上实验所采用的测试问题的类型是已知的，而实际问题的类型往往是未知的。鉴于此，我们采用了具有真实应用背景的软件产品线配置问题[7]来检验我们的方法在实际应用中是否真的有效。表5给出了各个算法在软件产品线配置问题上的平均排序。结果表明，基于ToM的算法同样表现优异。特别地，MOEA/D-ToM取得了最佳排序。
表5 软件产品线配置问题上的实验结果
综上，我们首先将ToM与其他约束处理策略分别在MOEA/D和NSGA-II框架内进行比较，以说明ToM是一种新的、有效的约束处理策略；然后，我们运用类型已知的测试问题来全面比较基于ToM的算法与其他主流约束多目标演化算法在求解CMOPs时的性能表现。实验结果表明，基于ToM的算法更具优势。最后，我们采用软件产品线配置这个实际应用问题，进一步验证了本文方法的有效性。总结来说，本文提出的ToM策略为处理约束多目标优化问题提供了一种行之有效的新方法。
华南理工大学智能算法研究中心长期致力于将人工智能算法应用在解决复杂优化问题上，并取得了一些初步成效。未来，我们将继续在这个主题进行探索，以期为软件工程、人工智能与算法设计等研究领域做出积极的学术贡献。
参考文献
[1] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II, " IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
[2] T. P. Runarsson and X. Yao, "Stochastic ranking for constrained evolutionary optimization, " IEEE Transactions on Evolutionary Computation, vol. 4, no. 3, pp. 284-294, 2000.
[3] Z. Ma and Y. Wang, "Evolutionary constrained multiobjective optimization: Test suite construction and performance comparisons, " IEEE Transactions on Evolutionary Computation, vol. 23, no. 6, pp. 972-986, 2019.
[4] Y. Xiang, X. Yang, H. Huang, and J. Wang, "Balancing constraints and objectives by considering problem types in constrained multiobjective optimization," IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2021.3089633.
[5]Q. Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based on decomposition, " IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, 2007.
[6] Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, and E. Goodman, "Push and pull search for solving constrained multi-objective optimization problems, " Swarm and Evolutionary Computation, vol. 44, pp. 665-679, 2019.
[7] Y. Xiang, X. Yang, Y. Zhou, and H. Huang, "Enhancing decomposition-based algorithms by estimation of distribution for constrained optimal software product selection," IEEE Transactions on Evolutionary Computation, vol. 24, no. 2, pp. 245-259, 2020.
[8] X. Li, S. Fu, and H. Huang, "A constraint partitioning method based on minimax strategy for constrained multiobjective optimization problems," in Shi Y. et al. (eds) Simulated Evolution and Learning. SEAL 2017. Lecture Notes in Computer Science, vol. 10593, Springer, Cham, 2017, pp. 248-259.
总编：黄翰
责任编辑：袁中锦
文字：向毅、梁靖欣
图片：梁靖欣
校稿：何莉怡
时间：2021年9月1日
