多模态多目标进化算法研究综述

张佳星，褚晓凯，屈俊峰

（1.湖北文理学院计算机工程学院，襄阳 441053；2.河北地质大学信息工程学院，石家庄 050031；3.河北地质大学人工智能与机器学习研究室，石家庄 050031）

0 引言

在现实工程和科学研究中，许多优化问题需要同时满足多个目标，这类问题被称为多目标优化 问 题（multi-objective optimization problems，MOPs）［1-2］。近年来，使用进化算法（evolutionary algorithms，EAs）求解MOPs是比较流行且有效的方法。这类方法可以很好地在目标空间搜索到完整且分布均匀的Pareto前沿面，从而为决策者提供更合适的选择。然而，随着研究的深入和问题的复杂化，不仅目标空间的维度越来越高，而且Pareto最优解集（pareto optimal set，PS）和Pareto前沿面之间的映射关系变得越来越复杂，PS在决策空间的分布呈多模态性，即两个或多个不同的Pareto最优解对应同一Pareto前沿位置，这样的问题被称为“多模态多目标优化问题（multi-modal multi-objective optimization problems，MMOPs）”［3］。虽然找到Pareto前沿面就可以满足优化要求，但是获得更多PS可以为决策者提供更多的备选方案，以便做出更好的选择。在实际应用和科学研究中存在着许多MMOPs，例如流水车间调度问题［4］中存在多种优化方案同时满足调度要求、游戏地图生成问题［5］中存在多个候选映射空间都符合设计师的需求、选址优化问题［6］中有多个区域同时满足选址要求、特征选择问题［7］中相同的特征个数同时对应多个特征组合，等。因此，研究如何结合EAs的思想求解MMOPs具有很重要的现实意义。

近年来，研究者们提出了不同的多模态多目标进化算法（multi-modal multi-objective evolution⁃ary algorithms，MMOEAs）来求解 MMOPs。根据其算法特征，大致可以将其分为基于Pareto支配、基于目标分解、基于新型进化范例三大类。

1 多模态多目标优化概述

1.1 相关概念

MMOPs属于MOPs，因此用到了MOPs中的一些相关定义。在一般情况下，最小化多目标问题可以定义为：

其中X=(x1,x2,…,xD)T为D维决策向量，Ω∈RD是可行的D维决策空间，F()X定义了m个目标函数(f1(X),f2(X),…,fm(X))。F(X)的所有可能值构成的空间为m维的目标空间。

在多目标优化问题中通常通过Pareto支配关系来比较不同解的优劣，定义如下：

在MMOPs中，通常决策空间中会存在两个或多个相似的PS对应目标空间中PF的相同区域。本文采用Rudolph和Preuss［8］提出的松弛等价来定义MMOPs：

定义1一个MMOPs需要找到所有等价于Pareto最优解的解。

定义2两个解X′1和X′2是等价的，如果表示a的任意范数，μ是决策者给出的一个很小的非负阈值，如果μ=0，MMOPs应找出所有等价的Pareto最优解。若设定μ>0，则MMOPs还应找出其他质量可被接受的解。

1.2 求解要求

求解MMOPs的主流方法依然是进化算法，但与传统的MOEAs有所不同，这主要是因为与MOPs相比MMOPs具有一定的特殊性。求解MOPs的目的是找到一组收敛性好且分布均匀的Pareto前沿，并不会关注决策空间的情况。但是在实际生活中，决策者在选择解决方案时往往需要参考决策向量，因为决策向量代表了最终解决方案的各项实际参数，所以关注决策空间的分布性同样是很有必要的。因此，MMOPs的求解重点是如何提高解集在决策空间的多样性。

根据MMOPs的相关定义可知，其主要特点是决策空间中有两个或多个Pareto最优解集，并且经常会出现不同解集上的两个点在决策空间距离很远但在目标空间距离相近的情况。因此在求解这类MMOPs时通常会遇到两个挑战。①如何平衡算法的搜索能力，设计有效的搜索策略，使算法可以搜索到多个PS的位置，并使每个PS都尽可能完整。②如何设计有效的个体选择机制，将同一PF位置上的不同解同时保留下来，同时还要尽可能使决策空间距离很远但在目标空间距离相近的解不被淘汰。为便于理解，下面结合图1对这两个挑战进行解释分析。

图1 具有两个等价PS的MMOPs示意图

假设图1是一个双目标双变量的MMOPs，这一问题的PS=PS1∪PS2，其中PS1对应了一个完整的PF，PS2同样对应这个完整的PF，当算法搜索到PS1时，算法已经搜索到了一个完整的PF，继续进化只会提高PS1的质量，而很难在探索到PS2的邻域。更具体的说，当算法搜索到解决方案A后，很难再搜索到与其等价解决方案B，因此需要算法在前期可以同时搜索到多个PS的大概位置，防止陷入某一个PS。其次，设置合理的个体选择机制同样是很困难的，当算法同时搜索到C和D两个解决方案时，由于这两个解在目标空间中距离很近，当非支配解的数量超过预定规模时，为了维持Pareto前沿的多样性，通常会淘汰解D这种比较拥挤的解，但实际上C和D两个解决方案在决策空间中距离很远，也就意味着在实际应用中这代表了结果相近但参数不同的两个方案，将其同时保留下来是很有必要的。因此在设计选择策略时不能仅依靠解在目标空间的拥挤程度，要同时考虑决策空间和目标空间解的分布情况。

1.3 评价指标

使用EA求解MMOPs最终会得到一组折中的可选方案，不能像单目标一样用最优解和真实解的绝对值来进行评价。因此研究者们提出了不同的评价指标来客观展示不同算法之间的性能差距，目前，常见的评价多模态多目标优化算法的指标，一个是在评估多目标优化算法时常用的超体积（hypervolume，HV）［9］，另一个是Yue等［10］提出的针对多模态多目标算法的指标：帕累托近似性（pareto set proximity，PSP）。

HV指标用来评估得到的PF与其参考点构成的超体积大小，主要用来验证解在目标空间的分布性，具体如公式（3）所示,

其中，PF是多目标算法获取的Pareto前沿，z*是多目标测试函数的参考点，v(x,z*)是指PF中的一个解与参考点z*围成的超立体体积。以图2为例，PF={ }

图2 超体积（HV）计算示意图

A,B,C,D，z*为该问题的参考点，则HV(PF,z*)为图中的阴影面积。这一评价指标的优势不需要预先提供真实的PF作为参考，并且可以同时衡量解集的收敛性和多样性。

另一指标PSP反映了多模态多目标算法获取的PS与实际PS之间的相似程度，具体如公式（4）。

式中，CR是算法获取的PS与实际PS之间的覆盖率；IGDX被称为决策空间反世代距离，表示算法获取的PS到实际PS之间的欧式距离。CR的计算方式如下，

D表示决策空间的维数，表示算法求得的PS在第l维决策变量上的最小值，相应的表示最大值，Vminl和Vmaxl分别为真实的PS在第l维上的最小值和最大值。CR越大表示求得的PS越是接近真实PS，当CR=1时表示求得的解集与真实解集完全重合。

IGDX是 Zhou 等［11］在指标IGD［12］上的扩展，即将IGD应用于决策空间，具体公式如下，

其中P*表示在真实PS上选取的一组分布均匀的解，O是求得的真实PS，d(v,O)是P*中的点v到集合O中所有点的欧氏距离的最小值，如果P*在真实PS上的分布足够均匀，IGDX就可以很好的衡量解在决策空间分布情况，其数值越小，则表示求得的解集与参考集P*距离越小。

PSP指标很好的将两者进行了结合，可以同时衡量求得的解在决策空间的收敛性和多样性，从而有效评价MMOEAs的真实性能。

1.4 测试函数

MMOPs的相关研究虽然早在2005年［13-14］就已经开始，但是近几年才被研究者们广泛关注。因此，为MMOPs设计的测试函数并不多，而且经典的多目标测试函数并不符合多模态问题的特征（具有多个PSs），所以它们并不适合用来对MMOEAs进行测试。目前使用最为广泛的是2019CEC竞赛［15］中的测试集。该测试集包含了22个测试函数，表1给出了22个测试函数的一些具体特征，包括函数名称、PS的数目、重叠情况、目标数量、决策空间维度以及本文使用的评价指标HV的参考点。

表1 测试函数的具体特征

其中PS的数目和重叠情况是影响测试函数求解难度的重要信息，一般来说，PS数量越多求解难度越高，如果多个PS存在重叠或者相互连接，同样会增加求解难度。此外，函数MMF10-MMF13、MMF14_a和MMF15_a中同时包含了全局PS和局部PS。

2 多模态多目标进化算法最新研究进展

自2005年以来，学者们就已经开始关注在求解MOPs时决策空间的复杂性［13-14］，但大多都是独立进行的，没有明确使用“多模态多目标优化”一词。Coelho等［16］将其称为多目标多全局优化（multi-objective multi-global optimization），而在Zechman等［17］的相关研究中又被称为多模态多目标棘手问题（multi-modal multi-objective wicked problems），直至2016年Ling等［18］才明确定义了代表MMOPs的术语。

在多模态多目标优化问题中，目标空间的同一个Pareto前沿往往对应决策空间中的多个Pareto最优解集。传统的MOEAs的目的是求得收敛性和分布性好的Pareto前沿，即重点关注解在目标空间的收敛性和分布性，而很少关注解在决策空间的多样性。因此，在求解多模态多目标优化问题时往往不能得到分布性良好的Pareto最优解集。近年来，研究者们提出了不同的多模态多目标进化算法（multi-modal multi-objective evolutionary algorithms，MMEAs）来求解MMOPs。根据其算法特征，大致可以分为基于Pareto支配、基于目标分解、基于新型进化范例三类。

2.1 基于Pareto支配的MMOEAs

这类算法同样采用Pareto支配的方法对个体进行选择，但这种方法在求解MMOPs时往往无法保证解在决策空间的分布性。为此，研究者们在传统Pareto支配方法的基础上又加入了不同的选择策略作为算法的第二选择标准，以保持种群的多样性。

Deb 等［14］提出了 Omni-Optimizer，该算法是在NSGAII基础上的一个扩展。为增强算法的稳定性，该算法在初始化种群时采用了拉丁超立方体采样的方法。在进化过程中首次引入了决策空间拥挤距离的概念，并结合非支配排序作为种群进化时的选择策略，与传统MOEAs相比，决策空间的多样性得到了很大的提升。

Ling等［18］提出了 DN-NSGA-II，该算法同样是在NSGAII上的改进。提出了一种基于决策空间的小生境方法，同时对二选竞赛方式进行了改进，增大了决策空间距离远的解进入交配池的概率，从而使算法能在同一个Pareto前沿上找到多个全局Pareto最优解集。

Kim等提出了SPEA2+［19］，该算法是在SPEA2的基础上进行的扩展，添加了新的交叉机制和存档机制，采用两个档案库来保持解的收敛性。分别在目标空间和决策空间根据解的密度进行更新以进行环境选择，以此来同时维持解在目标空间和决策空间的多样性。

Liu等［20］提出了一种双峰小生境进化算法，种群在非支配排序后，在目标空间和决策空间中同时采用生态位共享方法进行种群多样性维护，从而使求解MMOP的解多样化。

Pareto支配的方法在求解MMOPs时应用依然广泛，其主要优势在于该方法适用性强、操作简单、收敛速度快等。除此之外，这类算法具有很强的可扩展性，可以针对MMOPs的特性对算法本身的选择策略、进化范式等方面进行设计和改进，从而提高算法的收敛性和多样性。

2.2 基于目标分解的MMOEAs

目标分解的核心思想是将多目标问题分解为多个简单的单目标问题进行求解，这一方法在求解MOPs时表现良好，因此，研究者们针对MMOPs的特性对此进行改进，使算法能够同时维持解集在决策空间和目标空间的多样性。

Hu等［21］在MOEA/D中引入了决策空间多样性维护机制，环境选择是基于目标空间中的PBI函数值和决策空间中的拥挤距离值相结合来进行的。通过这种方式，可以将多个不同的解决方案关联到一个子问题，这有助于扩展解决MMOPs问题的多样性。

Tanabe等［22］提出了 MMOEA/D-AD，该算法在其决策空间中设置一个了相对邻域，根据子问题在目标空间的位置，将子问题与其决策空间中的相邻子问题进行比较，在搜索过程中自动调整种群的大小，每个子代只更新决策空间邻域内的个体中与同一子问题相关的原始解。因此，可以为每个子问题保留多个Pareto最优解集。

Tanabe等［23］针对这类分解的方法提出了一种基于三个操作的框架：分配、删除和添加操作，给同一子问题分配多个解，以处理多个等效的解决方案。这类方法可以在一定程度上同时兼顾解在目标空间和决策空间的多样性，但也增加了算法的计算成本，而且，这类算法一般使用均匀分布的权重向量来维持多样性，过于依赖参数的设置和搜索空间的复杂程度。因此，合理的划分子问题，以及设计更简便的资源分配方式是目前这类算法的主要研究方向。

2.3 基于新型进化范例的MMOEAs

许多新型进化范例在求解MOEAs时可以取得很好的表现，因此，研究者们将适用于多目标优化问题求解的进化算法移植到多模态多目标优化问题的求解中，用性能优越的新型进化算法来求解MMOPs。代表性算法简述如下。

Yue等［10］提出了MO_Ring_PSO_SCD，这是基于环形拓扑结构的粒子群进化算法。粒子群进化算法在MOPs和MMOPs中应用都非常广泛。在MO_Ring_PSO_SCD中，作者提出了一种结合非支配排序和特殊拥挤距离的选解方式，同时考虑了帕累托解集在目标空间和决策空间的拥挤距离，有效维护了解集的多样性。同时还提出了多模态多目标优化问题测试函数和新的评价指标。

Zhang等［24］在MO_Ring_PSO_SCD的基础上提出了MMOCLRPSO，该算法同样采用了环形拓扑结构，以非支配排序和特殊拥挤距离相结合的方式进行选解。并且在此基础上设计了一种基于欧几里德距离的聚类方法对决策空间进行聚类，以此增强算法在决策空间的搜索能力。

Liang等［25］提出了MMODE，采用差分进化算法求解MMOPs。该算法采用非支配排序进行进化种群的第一选择，引入决策空间拥挤距离进行第二选择，通过个体预选择机制和改进的变异算子来增加解的多样性。同时对解的越界处理方式进行了改进。

Hu等［26］提出了MMOPIO，采用了基于合并参数的改进鸽群优化算法（PIO）求解MMOPs。该算法提出了一种自组织映射（self-organizing map，SOM）来控制决策空间，从而为PIO建立良好的邻域关系。利用精英学习策略和特殊的拥挤距离计算机制获得均匀分布的解集。

Jza等［27］提出了CNMM，该算法采用粒子群优化算法来得到下一代进化群体，采用改进的差分进化策略来扩大搜索范围，并用近邻移动策略让粒子向最优解逼近，在局部范围内进化，从而达到优化的目的。

这类基于新型进化范例的优化算法具有较强的搜索能力，可以探索到更多的Pareto最优解集，在处理多模态多目标问题时取得了很好的效果。并且这类算法同样具有很强的可扩展性，为研究者们提供了许多新的思路。

2.4 其他

此外，还有一些其他研究很难归为上述几类，Liu等［28］提出了TriMOEA-TA＆R，该算法是一种使用双存档和重组策略的新型MOEAs。通过分析决策变量之间的关系来指导搜索，采用双重档案的通用框架协同维护种群，使用聚类思想保证目标空间的多样性，使用小生境的清除策略来促进决策空间的多样性。Fan等［29］还提出了一种基于分区搜索的框架，将决策空间划分为多个子空间，从而实现对种群的划分。但其在一定程度上限制了种群初期的全局搜索能力。Li等［30］提出了DE-RLFR，该算法是一种基于适应度排序强化学习的进化算法，基于Q-Learning框架自适应的选择变异策略产生下一代。

3 结语

尽管目前的MMOEAs在求解MMOPs时取得了一定的成果，但仍然存在一些挑战。目前，MMOEAs存在如下三个典型问题及研究方向。首先，现有的大多数MMOEAs虽然在决策空间取得了很好的分布，但同时牺牲了一部分目标空间的性能，因此，如何同时维持目标空间和决策空间的多样性依旧是研究的重点。然后，大多数算法采用小生境技术来维持种群多样性，但在算法初期没有任何先验知识的情况下，很难准确地对种群进行划分，特别是在MMOPs问题中，使用小生境方法在算法前期无法同时准确的捕获到多个PS，若强行对种群进行划分则有可能会影响算法在前期的全局搜索能力，从而对最终结果产生不好影响。因此，如何平衡算法搜索能力可以作为未来的研究方向。其次，用于测试函数的评价指标仅能单独评价决策空间或者目标空间的性能，而多模态多目标优化问题注重的是同时维护决策空间和目标空间的多样性，因此设计一些针对问题特性的综合评价指标同样是很有意义的研究方向。最后，目前有关多模态多目标问题的实际应用相对较少，因此将多模态多目标优化算法应用于更多的实际优化问题中，使算法研究更有意义同样是未来的目标。