多目标进化算法研究综述

张丹丽，曹 锦，高彦杰

（上海电力大学 电子与信息工程学院，上海 200090）

多目标优化问题（Multi-objective Optimization Problem，MOP），又称多能性问题[1]。现实生活中大量的工程问题都属于MOPs，如柔性作业车间调度决策、城市运输、工期成本问题等。由于多目标优化问题需要平衡多个目标来达到总目标最优，具有高纬度、大尺度的特点，优化十分困难。针对这一问题，很多研究者提出了解决多目标优化问题的进化算法。根据选择机制的不同，大部分多目标进化算法（Multi-objective Evolutionary Algorithms，MOEAs）可分为三大类[2]，即基于Pareto支配的MOEAs、基于分解的MOEAs和基于指标的MOEAs。

现有的多目标进化算法的综述类文章侧重于对经典多目标进化算法的介绍与分析，而没有涉及解决高维多目标优化问题（Many-objective Optimization Problems，MaOPs）的研究。对于超过三个以上的高维多目标优化问题（MaOPs）、结构复杂的多目标优化问题以及针对各种不同形状的Pareto集的具有通用性的MOEAs的研究仍然存在缺陷。

因此，本文的重点侧重于高维多目标进化算法的研究。针对这些目前仍未很好解决的问题，归纳总结了近些年提出的最先进的MOEAs，分别从基于Pareto支配的MOEAs、基于分解的MOEAs和基于指标函数的MOEAs进行归纳总结。最后，就MOEAs目前仍然存在的问题进行分析，并对今后的研究方向进行了展望，可对相关领域学者开展自己新的研究方向提供参考。

1 多目标优化的相关理论

多目标优化问题（MOPs）可以描述为[3]：

minxf（x）=minx[f1（x），f2（x），...fm（x）]，x∈Ω，

其中，决策向量X=（x1，x2，...xn）属于非空决策空间Ω，目标函数向量f：Ω→Λ由m（m≥2）个目标组成，Λ是目标空间。下面简单地介绍几个相关定义：

定义1（可行解）：满足约束条件的决策空间中的解x∈Ω，即称为可行解。

定义2（Pareto支配）：给定两个解x，y∈Ω，以及它们对应的目标向量f（x），f（y）∈Rm，当且仅当∀i∈{1，2，...m}，fi（x）≤fi（y）且∃j∈{1，2，...m}，fj（x）＜fj（y）时，则x支配y（表示x＜y）。

定义3（Pareto最优解）：如果一个解不被任何其他解所支配，则它被定义为帕累托最优解（Pareto Optimal Solution）。

定义4（Pareto最优解集）：一个多目标优化问题的所有Pareto解构成的集合称为Pareto最优解集（Pareto Set，PS）。

定义5（Pareto前沿）：Pareto最优解集中的解所对应的目标向量称为Pareto前沿（Pareto Front，PF）。

2 多目标进化算法最新进展

针对目前仍未很好解决的多目标优化问题，下面将研究基于Pareto支配的MOEAs、基于分解的MOEAs和基于指标函数的MOEAs三类算法的最新进展。

2.1 基于Pareto支配的MOEAs

基于Pareto支配的MOEAs可以成功地解决具有两个或三个目标的MOPs问题。然而，对于MaOPs时，许多基于Pareto支配的MOEAs可能会遇到朝向真正Pareto前沿的选择压力的问题。因为在早期迭代过程中，非支配解的数量随着目标的数量呈指数增长。基于Pareto优势的收敛保持机制（如NSGA-III）失去了驱动种群向Pareto前沿移动的选择压力。因此，基于帕累托优势度的准则不能区分个体的收敛程度。

为了提高解的收敛性，K.Praditwong等人[4]率先提出了具有代表性的双存档算法，使用两个独立的档案来保留有前途的候选解。当两个存档文件的总大小溢出时，仅对DA执行停止操作，并删除拥挤候选解。然而，在处理MaOPs时，CA和DA中的数量可能会显著增加。接着，B.Li等人[5]在此基础上提出改进的双存档算法（ITAA）为CA的大小设置了一个阈值。然而，由于DA的大小是没有限制的，ITAA的最终输出解的多样性不足。为了解决这个问题，W.Hangding等人[6]提出了改进的双存档算法（TwoArch2），利用IBEA的更新策略对CA进行更新，当种群溢出时，DA迭代选择具有极值目标值的边界解。最后，DA被输出为TwoArch2的最终解。L.Cai等人[7]使用了两种基于聚合框架的更新策略来更新CA和DA。然而，对于投影不完全覆盖单位超平面的部分帕累托前沿的MaOPs，DA的大小可能小于给定的大小，这是因为某些权向量可能具有相同的最优解。显然，上述算法均未能设计一个平衡收敛性和多样性的机制来解决MaOPs。

针对上述算法存在的缺陷，C.Dai[8]提出了一种改进的基于多搜索策略的双存档进化算法（TwoArchM）。TwoArchM的主要组成部分是对两个文档采用两种更新策略来平衡收敛性和多样性，提出了一种多搜索策略来增强收敛性，平衡探索和开发。实验表明，在大多数问题上，TwoArchM得到的解的质量比其他算法得到的解要好。

不同于上述双存档算法，P.Wang等人[9]提出了一种基于维数收敛的多目标进化算法DC-MaOEA。在该算法中，提出了基于个体与虚拟理想点距离关系的维数收敛函数DC。当候选的选择过程具有相同的Pareto支配等级，DC值可以进一步衡量它们的收敛性。另外，还发展了交配机制，以提高交配群体的收敛性能。为了平衡种群的收敛性和多样性，还设计了环境选择，对种群进行综合评价。实验结果表明了所提出的DC-MaOEA算法具有优越性。

2.2 基于分解的MOEAs

对于MaOPs，其高维目标是造成其高复杂程度的原因之一。然而，现实生活中一些特殊的MaOPs中的目标可能彼此高度相关，因此有些目标是冗余的。这些MaOPs的PFs具有很低的维数，可以称之为退化MaOPs。然而，现有的MOEA/D框架中的自适应策略不能处理退化问题，其中每个子问题考虑一个单一尺度的目标函数。

针对退化MOPs，H.Liu等人[10]提出了MOEA/D的一个最新变体MOEA/D-M2M。每个子问题的可行域由目标空间中的方向向量（或参考向量）定义。因此，不同的目标具有同等的重要性。显然，MaEA/D-M2M未能有效处理退化MOP。针对文献[10]存在的问题，L.Hui等人[11]在其基础上提出了一种新的MOEA/D算法，称为MOEA/DAM2M。该算法利用搜索过程中收集的信息自适应地调整每个子问题的可行域。仿真实验表明该算法具有良好的鲁棒性。

在基于分解的多目标进化算法中，由于进化算子对问题的性质非常敏感，在不同的搜索阶段往往具有不同的特性。然而，在现有的集成方法中所有的子问题/子空间使用的进化算子是相同的。但是，对于复杂的MOPs，其子问题/子空间的特性是不同的。

基于现有的集成方法忽略了以上这一点，X.Hong等人[2]提出了一种细粒度集成方法（FGEA），用于在一代中为不同的子空间选择合适的进化算子。定义了每个进化算子在每个子问题/子空间中的局部贡献和全局贡献，并且设计了一种自适应策略来鼓励进化算子做出更多的贡献，以获得更多的机会来生成更多的后代解。在为子空间选择进化算子时，该自适应策略同时考虑了进化算子的局部贡献和全局贡献。为了验证所提出的细粒度集成方法的性能，挑选了多目标优化中最广泛使用的基准作为多目标优化问题，这些MOPs的决策变量之间的复杂联系给MOEAs带来了挑战，这使它们比其他MOPs更难解决。实验结果验证了该算法的有效性，揭示了FGEA具有一定的竞争性。

2.3 基于指标函数的MOEAs

一些研究所指出，MOEAs的性能很大程度上取决于问题的Pareto前沿形状，而大多数现有的MOEAs在Pareto前沿形状不同问题上表现出了较差的通用性。基于指标的MOEAs为了计算各种性能指标，需要在帕累托前沿取样一组参考点。在实践中真实的帕累托前沿是未知的，一组参考点只能从近似帕累托前沿抽样获得。目前，大多数现有的参考点适应方法在具有不规则帕累托前沿的MOPs上取得了显著的性能。但相比之下，当应用于具有规则帕累托前沿的MOPs时，它们的性能会显著恶化。

针对这一问题，文献[12]提出了一种增强型IGD指标，称为无贡献解检测（IGD-NS）。通过区分对指标没有任何贡献的无贡献解，IGD-NS能够对非支配解提供更全面的衡量。与传统的IGD指标相比，IGD-NS给定的候选解提供了更全面的评估。接着，在IGD-NS算法的基础上，还提出了一种MOEA/IGD-NS算法，将储存在外部档案中的非支配解作为计算IGD-NS的参考点。实验结果表明，虽然MOEA/IGD-NS算法在某些具有两个或三个目标的MOP问题上的性能优于现有的MOEAs算法，但在对不同类型的Pareto前沿问题的通用性较差。

为了解决这一问题，文献[13]提出了一种新的基于IGD-NS的MOEA方法，称为AR-MOEA，该方法采用参考点自适应的方法来调整参考点，以便在每一代计算IGD-NS。为了评估AR-MOEA算法的有效性，将拟议的AR-MOEA与用于解决MOPs的4个MOEA进行比较，以及用于处理MAOP的4个MOEAs。然后，通过与两种最先进的参考点自适应方法比较。实证结果表明，所提出的AR-MOEA在具有不同类型帕累托前沿的MOPs和MaOPs上均优于8个具有代表性的MOEA，显示出良好的通用性。通过将参考点自适应方法嵌入到NSGA-III中，进一步评估了该方法的性能。与另外两种最新的自适应方法相比，该方法在规则和不规则Pareto前沿问题上仍然表现出最好的性能。

3 结束语

尽管现有的MOEA在解决多目标问题方面取得了巨大的成功，但仍存在一些挑战。下面提出一些多目标进化算法研究中存在的问题以及今后研究方向的一些展望。

首先，现有的MOEAs大多是针对没有约束的MOPs问题，但是现实生活中的多目标优化问题多是存在一定的约束，研究带有约束的多目标优化问题的成为进化算法下一步需要重点研究的方向。然后，大多数现有MOEAs的性能在大规模多目标优化问题上急剧退化。迄今为止，对于具有不规则Pareto前沿的大规模多目标优化问题的研究还很少，解决这些问题将更具挑战性，因为许多现有的参考向量调整方法可能会受到维数灾难的影响。其次，求解具有不规则Pareto前沿的昂贵多目标优化问题是一个极具挑战性的课题，因为只能提供对目标函数的少量评估。在这种情况下，需要更有效的适应方法，能够在有限的计算预算下正确地识别帕累托前沿的分布，代理辅助进化算法。最后，如果Pareto前沿随时间变化，即如果多目标优化问题是动态的，则具有不规则Pareto前沿的多目标优化问题将变得更难求解。在这种情况下，帕累托前沿在位置、形状以及不规则性方面可能随时间而改变。