多目标演化算法 | 从参考点出发，求解高维多目标优化问题！

图文已经华南理工大学智能算法实验室授权。

实验室负责人：黄翰教授

联系邮箱：hhan@scut.edu.cn

从社会生活的角度出发，最优化问题普遍存在于我们的日常生活中。例如，人们往往追求利润的最大化、投资风险的最小化等。随着科学技术和生产生活的日益发展，人们面临的优化问题也日渐复杂。其中，多目标优化问题是一类典型的代表。顾名思义，多目标优化问题即人们需同时优化多个目标，且各目标之间往往存在冲突。例如，生产经营者往往希望用最小的代价获得最大的收益；人们购买汽车时，除了考虑价格外，还会考虑汽车的性能、舒适度等（见图一）。而演化算法（见图二）是模拟生物界自然选择和自然进化的随机启发式算法，现已成为当前解决复杂多目标优化问题的有效工具之一。其中，中国香港城市大学张青富教授提出的MOEA/D目前已成为求解多目标优化问题最流行的算法框架[1-2]。

图一 生活中的多目标优化问题

图二 演化算法示意图

近年来，高维多目标优化问题已成为演化计算研究领域的热点难题之一。在高维多目标优化问题中，待优化的目标个数至少是4个。随着目标个数的增加，问题的求解难度会逐步加大。现阶段，国内外学者已提出众多高维多目标优化算法。然而，绝大多数的工作主要采用理想点（Ideal point）计算衡量个体收敛性和多样性的指标。实践表明，针对不同形状的Pareto前沿（PF），选择合适的参考点，比如理想点或天底点（Nadir point），对提高算法性能具有重要意义。此外，在基于Pareto支配关系的算法中，支配抵抗解（Dominance resistant solutions，DRSs）易于出现，但难以及时发现并剔除，进而降低算法的收敛速度。

针对上述问题，华南理工大学软件学院智能算法实验室与中山大学周育人教授团队合作提出一种基于自适应参考点策略的高维多目标演化算法（PaRP/EA）[3]，该算法运用一个欧式距离比估计PF的大致形状，进而自适应地选择参考点。此外，我们还设计了一种检测和删除支配抵抗解的有效方法。该研究成果现已被国际知名杂志IEEE Transactions on Evolutionary Computation录用。下面让我们一起回顾关于本研究工作的发展进程与相关成果。

图三 算法PaRP/EA的基本框架

图四 算法PaRP/EA中的环境选择部分

PaRP/EA 算法的主要流程如图三，四所示，图三描述了PaRP/EA 的基本流程，与通常的多目标优化算法类似，其主要特色在于环境选择部分（见图四）。在该算法中，我们首先采用与NSGA-III算法类似的方法，对种群进行归一化处理；其次，根据Pareto支配关系找出非支配解集和被支配解集；接着，运用非支配解集估计PF的形状，形状类型主要包括凹状，凸状或线性等，其中主要通过找出非支配解集中与m维向量V=（1,1,...,1）夹角最小的m个解（其中m为目标个数），并采用距离比值q估计PF的大致形状。

图五 估计PF形状的示意图 （a）

以及参考点示意图（b）

我们尝试估计PF形状的一个示意图以及参考点（见图五），根据计算出的距离比值q，可估计PF的大致形状，并且根据不同的情况可分为三类，当q小于0.9时，PF被判定为凸状，当q在0.9至1.1时，PF是线性的，若q大于1.1时，PF则为凹状。其次，根据PF的形状选择参考点，若PF是凸状的，则将参考点设置为如图五（b）中的Znad，否则将参考点设置为Z*。此外，我们还会对非支配解集进行进一步的分类，主要是通过集合中个体在超立方体位置的不同进行标记，位于超立方体内部的个体记为一类，位于外部的个体记为另一类。如图五（b）所示，位于外部的个体包含两个个体，即c和d；而位于内部的个体包含剩下的10个个体。事实上，我们会优先考虑超立方体内部的个体，因为这样有利于识别及剔除支配抵抗解。例如，若c和d至少有一个目标值很大(另一个目标值很小)，则可认为它们是支配抵抗解，此时采用超立方体的分类方法可对二者进行有效剔除。最后，在对超立方体内部个体的进行selection操作时，我们用到了最大夹角优先准则和逐个删除这两个策略对解集中的目标个体进行处理(见[4-5])。

在实验部分，我们通过将PaRP/EA算法与NSGA-III, VaEA,MOEA/D, θ-DEA,1by1EA, GWASFGA 和MOEA/D-IPBI等算法进行全面比较，以得到PaRP/EA算法在处理高维多目标优化问题的能力优劣对比结果。所选测试问题共29个，性能指标选择了广泛使用的IGD和HV。最后实验结果如表I-III所示，由结果知，相比其他算法，PaRP/EA算法在更多情况下可获得更优的性能。

图六 PaRP/EA算法与其它算法对比实验结果

图七则是在15目标WFG7和WFG7-1测试问题上各算法的最终解集分布图。其中需要了解的是，WFG7测试问题的PF凹状的，而WFG7-1测试问题的PF则是凸状的。根据结果可以看出，仅PaRP/EA和VaEA能同时在WFG7和WFG7-1两个问题上均有较好的性能表现（并且在WFG7-1问题上，PaRP/EA优于VaEA），而其它算法仅在其中之一表现较好，或者在两个问题上表现均不好。从上述实验结果不难得知，PaRP/EA算法能有效地处理不同形状的PF。

图七 在15目标WFG7（红色线条）和WFG7-1（黑色线条）测试问题上，各算法的最终解集

事实上，多目标优化问题广泛存在于科学研究和工程实践，所以研究这类问题的有效解法具有重要的科学价值及实际意义。针对目标个数超过3个的多目标优化问题，本文设计了一种有效的新算法。具体地，算法通过估计PF的大致形状，自适应地选择参考点。此外，算法还采用了一种识别和剔除支配抵抗解的方法。实验结果表明，新算法具有较好的性能表现，尤其是能够较为有效地处理具有不同PF形状的多目标优化问题。并且，新算法具有无需设置权向量、时间复杂度不高等优点，可能比较适合于求解一些工程实际问题，如软件工程、深度学习等领域的优化问题。值得说明的是，实际优化问题的PF形状可能较为复杂，既有凸状部分也有凹状部分。当前，估计PF形状所采用的方法还可进一步改进，以更好地解决这类复杂的实际优化问题。

参考文献

[1] Zhang Q., Li H., MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition, IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

[2] Li H, Zhang Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE transactions on evolutionary computation, 2009, 13(2): 284-302.

[3]Yi Xiang, Yuren Zhou, Xiaowei Yang and Han Huang, A Many-objective Evolutionary Algorithm With Pareto-adaptive Reference Points, IEEE Transactions on Evolutionary Computation, Accepted, DOI: 10.1109/TEVC.2019.2909636

[4] Y. Xiang, Y. Zhou, M. Li, and Z. Chen, “A vector angle based evolutionary algorithm for unconstrained many-objective problems,” IEEE Transactions on Evolutionary Computation, vol. 21, no. 1, pp. 131–152, Feb. 2017.

[5] Y. Zhou, Y. Xiang, Z. Chen, J. He, and J. Wang, “A scalar projection and angle based evolutionary algorithm for many-objective optimization problems,” IEEE Transactions on Cybernetics, vol. 49, no. 6, pp. 2073–2084, June 2019.