超多目标进化优化研究现状及发展趋势研究

田 野a， 张兴义b

(安徽大学 a.物质科学与信息技术研究院， b.计算机科学与技术学院， 安徽 合肥 230601)

超多目标优化问题指含有多于3个目标函数的优化问题，它广泛存在于许多领域中，例如无人机群路径规划和混合动力汽车控制[1-2].一个超多目标优化问题可以定义为

minf(x)=(f1(x),f2(x),…,fM(x))
x∈Ω

(1)

其中,x=(x1,x2,…,xD)T∈Ω⊂RD是决策向量，f=(f1,f2,…,fM)T∈Λ⊂RM是目标向量，D是决策变量数目，M>3是目标函数数目，Ω是D维的决策空间，Λ是M维的目标空间.由于超多目标优化问题的目标之间往往是互相矛盾的，故一般不存在一个可以在所有目标上均达到最优值的解.因此，求解超多目标优化问题的目的是找到一组在各个目标上折衷的解，而决策者可以从该解集中选择任意一个或多个解作为最终的决策方案[3].所有最优的折衷解构成了该问题的帕累托(Pareto)最优解集，而这些解在目标空间中的图像称为帕累托前沿面.

自VEGA于1985年被提出以来[4]，已有许多采用了不同环境选择策略的进化算法被用于求解多目标优化问题，如基于拥挤距离选择的NSGA-Ⅱ、基于欧氏距离截断的SPEA2和基于网格选择的PESA-Ⅱ[5-7].这些多目标进化算法均采用帕累托支配关系作为基本的解选择策略，上述环境选择策略则用于区分帕累托支配关系无法区分的解.其中帕累托支配关系用于保证选择的解的收敛性，而其它环境选择策略用于保证选择的解的分布性.根据帕累托支配关系，解x支配解y当且仅当

(2)

记作f(x)f(y)，并且认为解x要优于解y.若x不支配y且y不支配x，则称它们是互相非支配的，并认为它们之间无法区分.从以上定义可以看出，对于2个具有M个目标的随机解，其中一个支配另一个的期望概率是0.5M-1.因此，对于M较大的超多目标优化问题来说，进化算法的种群中的解大都互相非支配，即帕累托支配关系无法区分大多数的解.这一现象被称为帕累托支配受阻[8].

在求解超多目标优化问题时，帕累托支配关系的无效，会直接导致选择的解的收敛性无法保证，并使得整个进化算法无法有效收敛.实际上，许多研究指出，NSG-Ⅱ等传统多目标进化算法仅在问题的目标数M≤3时有效，它们无法有效求解超多目标优化问题[8-9].为此，一些采用了特殊环境选择策略的进化算法被相继提出，用于求解超多目标优化问题.这些算法大体可以分为基于帕累托支配关系的算法、基于改进支配关系的算法、基于目标分解的算法和基于性能指标的算法.本文将对以上4类超多目标进化算法进行详细介绍，并对一些具有代表性的算法的性能进行实验对比.此外，本文也对超多目标进化优化的发展趋势给出一些看法.

1 超多目标进化算法介绍

1.1 基于帕累托支配关系的算法

该类型的超多目标进化算法仍采用帕累托支配关系作为基本的解选择策略，用以剔除种群中少量的被支配解.对于剩余的大部分非支配解，该类算法采用特殊的环境选择策略来同时保证选择的解的收敛性与分布性.

KnEA中设计了基于knee point优先选择的策略用于区分非支配解[10].Knee point是位于前沿面上最凸的部分的解，在knee point附近任何一维目标值的稍微减少都会导致其它维目标值的大幅增加[11].因此,在一个非支配解集中，knee point的收敛性要优于其它非支配解.KnEA通过优先选择非支配解中的knee point来保证收敛性，并通过一种自适应的小生境技术来使得选出的knee point具有较好的分布性.

由于高维目标空间中的解的收敛性与分布性存在一定的矛盾，BiGE分别将每个解的收敛性与分布性定义为一个新的目标函数[12].因此，原有的超多目标优化问题被转化为了一个双目标优化问题，即最小化收敛性评价函数与分布性评价函数.之后，该问题便可利用传统基于帕累托支配关系的环境选择策略予以求解.

1by1EA中设计了一种逐一选择策略来应对超多目标优化问题[13].该算法每次从所有非支配解中选出收敛性最好的一个，并将它一定邻域范围内的其它解删除，从而能够在选出收敛性较好的解的同时保证其分布性.实验证实1by1EA可以在超多目标优化问题上获得较好的效果，但如何确定解的收敛性度量标准仍有待研究.

为了更加准确地评价解的收敛性和分布性，GFM-MOEA中提出了一种前沿面建模的方法[14]，它可以根据当前种群估计出前沿面形状的函数表达式.GFM-MOEA将解到前沿面的距离作为其收敛性度量，并将解在前沿面上的投影与其它解的投影的距离作为其分布性度量.GFM-MOEA中的前沿面建模方法不仅提升了在不同形状前沿面上的收敛性度量的准确性，也提供了一种较为准确的前沿面归一化方法.

总而言之，基于帕累托支配关系的算法的研究重点，在于如何评价高维空间中每个解的收敛性与分布性.此外，对于高维空间中的解来说，较好的分布性往往对应着较差的收敛性[9]，因此,如何在选择策略中平衡收敛性与分布性也是设计该类算法的重点.

1.2 基于改进支配关系的算法

由于帕累托支配关系无法区分超多目标优化问题的大部分解，因此，一些工作通过改进帕累托支配关系使其具有区分超多目标优化问题的解的能力.现有用于超多目标优化问题的支配关系可以分为4类，即基于支配区域扩展的支配关系、基于网格的支配关系、基于模糊逻辑的支配关系和基于小生境的支配关系.

根据帕累托支配关系的定义可知，一个具有M维目标的解的支配区域占整个目标空间0.5M.因此，第一类支配关系通过扩大每个解的支配区域来提升其支配其它解的概率，从而达到区分解的目的.例如，CDAS和GPO分别通过修改解的目标函数值和帕累托支配的定义来扩大每个解的支配区域[15-16].

第二类支配关系将目标空间划分为若干网格，并用每个解所在的网格坐标来代替目标值进行帕累托支配关系的判断.由于某个维度上目标值不同的2个解的网格坐标值可能是相同的，它们之间的非支配关系便可能变为支配与被支配的关系.因此，采用网格坐标也可以提升一个解支配其它解的概率.属于该类支配关系的有ε支配和grid支配等[17-18].

第三类支配关系利用模糊逻辑来提升一个解支配其它解的概率.在帕累托支配关系中，解x支配解y的充分条件是x的所有目标值均小于等于y；而在基于模糊逻辑的支配关系中，x的大部分目标值小于等于y即可使得x支配y，因此,一个解支配其它解的概率被大幅提升了.属于该类支配关系的有(1-k)支配和fuzzy支配等[19-20].

第四类支配关系利用小生境技术来判断解之间的支配关系.该类支配关系将每个解划分至一个小生境中，而相同小生境内的收敛性最好的解支配其它所有解.例如，θ支配生成一组均匀分布的权值向量[21]，并将每个解分配至离它最近的权值向量.SDR采用一种自适应小生境技术来自动地确定每个解所在的小生境以及每个小生境的大小[22]，可在不同形状前沿面上获得较好的分布性.

值得注意的是，以上工作均只提出了新型支配关系，并在传统多目标进化算法如NSGA-Ⅱ上验证了性能.因此，将这些支配关系与第一类超多目标进化算法结合来进一步提升性能是非常可行的方案.

1.3 基于目标分解的算法

自MOEA/D被提出以来，基于目标分解的多目标进化算法受到越来越多研究者的关注[23].虽然MOEA/D不是为求解超多目标优化问题而设计的，但由于其没有使用任何支配关系，它也能较好地求解超多目标优化问题.该类算法的核心思想是生成一组均匀分布的权值向量，并根据每个解在每个权值向量上的聚集函数值将解分配至权值向量上.通过在每个权值向量上仅保留一个聚集函数值最好的解可以保证收敛性，而权值向量本身的均匀分布又可以保证分布性.该类算法的研究重点主要在于聚集函数的设计、解到权值向量的分配方法以及权值向量的自适应.

MOEA/D中给出了3种聚集函数，即加权和方法、Tchebycheff方法与PBI方法.实验证实，加权和方法仅适用于具有凸前沿面的多目标优化问题，Tchebycheff方法的综合性能最好，而PBI方法能够获得分布性更好的种群.MOEA/D-AWA中通过将权值向量转换提出了一种改进的Tchebycheff方法，它能获得和PBI方法同样好的分布性[24].RVEA中提出了一种全新的聚集函数APD，它能更好地求解超多目标优化问题[25].

在进化过程中可能会出现一些解在多个权值向量上有最好的聚集函数值的现象，因此，如何将解分配至权值向量也是一个研究重点.MOEA/D中采用较为直接的方法，即将每个解复制多份并分配至它能达到最好的聚集函数值的所有权值向量上.MOEA/D-DE中限制了每个解的复制次数，这使得选择过程不会过于贪心[26].MOEA/D-DU限制每个解仅可被分配至离它最近的若干权值向量上[27]，而RVEA限制每个解仅可被分配至离它最近的一个权值向量上[25].MOEA/D-STM将解到权值向量的分配视为一个线性分配问题，并利用一个匹配方法予以解决[28].

基于目标分解的多目标进化算法得到的种群，一般和权值向量具有相同的分布，因此，当问题的前沿面形状过于复杂而与权值向量的分布不一致时，该类算法得到的种群的分布性往往较差[29].为此，一些算法通过在进化过程中调整权值向量的分布来提升分布性.例如，A-NSGA-Ⅲ和RVEA*根据当前种群的分布来调整权值向量[25，30]，而MOEA/D-AWA和AR-MOEA则在进化过程中维持一个分布性较好的外部文档[24,31]，并依此来更新权值向量的分布.

由于基于目标分解的算法具有较高的运行效率和较好的效果，其已成为求解超多目标优化问题最重要的算法类型之一.得益于基于目标分解的算法的灵活框架，一些工作将目标分解与其它选择策略结合来进一步提升性能.例如，NSGA-Ⅲ和MOEA/DD是结合了帕累托支配关系的基于目标分解的算法[32-33]，而θ支配也借鉴了目标分解的思想[21].

1.4 基于性能指标的算法

为了对比多目标进化算法的性能，一些性能指标被提出用于定量地评价算法得到的种群质量.这些指标也被用于进化算法的环境选择策略中，即选出种群中具有最好指标值的子集.性能指标通常可以同时评价种群的收敛性与分布性，因此，算法无需再考虑收敛性与分布性的平衡.

HypE采用HV指标作为环境选择的准则[34]，它每次从种群中删除一个能使种群HV值下降最少的解，因此，最终剩余的解能有较高的HV值，即较好的收敛性与分布性.由于HV的计算复杂度与问题的目标数呈指数级相关，为了提升算法在超多目标优化问题上的效率，HypE中采用了蒙特卡洛模拟法来近似地估计种群的HV值.

MOMBI-Ⅱ采用基于R2指标的环境选择策略[35].R2指标的思想与基于目标分解的算法类似，即衡量种群相对于一组均匀分布的权值向量的收敛性与分布性.因此，MOMBI-Ⅱ得到的种群也具有和权值向量相同的分布.此外，该算法中采用了一种目标空间归一化策略用于求解非归一化的超多目标优化问题.

AR-MOEA采用一种改进的IGD指标来进行环境选择[31].IGD指标衡量种群与前沿面的接近程度，需要计算种群中每个解与前沿面上一组均匀参考点之间的距离.由于问题的前沿面对于进化算法来说是未知的，AR-MOEA利用一组均匀分布的权值向量作为计算指标的参考点，并在进化过程中不断调整权值向量的分布以更加接近问题的前沿面形状.

MaOEA/IGD也是基于IGD指标的超多目标进化算法[36].它首先采用单目标进化算法估计出问题的前沿面的范围，并根据此范围在目标空间中建立一个超平面.通过在超平面上生成一组均匀分布的参考点，MaOEA/IGD便可以计算种群的IGD值从而进行环境选择.

虽然使用性能指标可以大大简化对解的收敛性和分布性评价，但性能指标的计算本身存在2个难题：①性能指标值一般对选取的参考点极为敏感[37]，因此,如何选取合适的参考点是值得研究的问题；②基于性能指标的算法需要反复计算种群的性能指标值，这使得该类算法的运行效率较低，因此，如何提升性能指标的计算效率也是值得研究的问题.

2 超多目标进化算法性能对比

本节将对8个具有代表性的超多目标进化算法进行实验对比，包括基于帕累托支配关系的算法GFM-MOEA、基于改进支配关系的算法GrEA(采用了grid支配)和NSGA-II/SDR(采用了SDR)，基于目标分解的算法MOEA/D、MOEA/DD和RVEA，以及基于性能指标的算法MOMBI-Ⅱ和AR-MOEA.实验基于进化多目标优化平台PlatEMO完成[38].

2.1 实验设置

(1)测试函数.实验选取常用的超多目标优化测试问题DTLZ1-DTLZ7和WFG1-WFG9[39-40].所有测试问题的目标数M设为5和10.DTLZ1的决策变量数D设为M+4，DTLZ7的决策变量数D设为M+19，其它所有测试问题的决策变量数设为M+9.

(2)种群大小.所有算法在5维问题上的种群大小N设为126，在10维问题上的种群大小N设为275.此外，所有基于目标分解的算法所使用的权值向量的数目等于种群大小.

(3)迭代次数.所有算法在DTLZ1和DTLZ3上的迭代次数设为500，在其它所有测试问题上的迭代次数设为300.

(4)算法参数.GFM-MOEA中的惩罚参数设为0.2，使用建模方法的频率设为0.1，GrEA中的每维网格数设为10，MOEA/D中使用的聚集函数为PBI，MOEA/DD中的邻域范围设为0.1N，RVEA中的惩罚参数设为2,使用参考点自适应的频率设为0.1，MOMBI-Ⅱ中的变化阈值设为0.5,容忍阈值设为0.001,文档大小设为5.

(5)遗传算子.所有算法采用模拟二进制交叉和多项式变异来产生子代[41-42]，其中交叉概率为1、变异概率为1/D、分布指数设为20.

2.2 实验结果与分析

表1给出了8个超多目标进化算法在DTLZ1-DTLZ7和WFG1-WFG9上的IGD指标值[43]，表中显示的平均值是30次独立运行的结果.同时，表1中每行最好的IGD值以深色高亮显示，且与最好的IGD值在Wilcoxon秩和检验(显著性水平为0.05)下无显著差异的结果以浅色高亮显示.由表1中可见，不同算法在超多目标优化问题上的性能差异较大，其中GFM-MOEA获得了15个最好结果，GrEA和MOEA/D分别获得了5个最好结果，MOEA/DD获得了3个最好结果，RVEA获得了2个最好结果，MOMBI-Ⅱ和AR-MOEA分别获得了1个最好结果.

DTLZ1和DTLZ3具有较多的局部最优值，它们能测试算法在超多目标优化问题上的收敛性.可以看出，基于目标分解的MOEA/DD和基于性能指标的AR-MOEA在这2个测试问题上的综合性能最好.DTLZ5和DTLZ6的前沿面始终是一条一维的曲线，它们能测试算法在具有退化的前沿面的问题上的性能.从表中易知，基于PBI方法的MOEA/D能够在这2个测试问题上获得明显好于其它算法的结果.DTLZ7和WFG1-WFG3具有极不规则的前沿面形状，而GFM-MOEA、GrEA和AR-MOEA在求解这3个测试问题时表现出了最好的性能.WFG4-WFG9的前沿面是高维空间中的超球面，但前沿面每维的范围各不相同，它们能测试算法在高维空间上的归一化能力.显然，基于前沿面建模的GFM-MOEA可以获得比其它算法更好的结果.

表1 8个超多目标进化算法在DTLZ1-DTLZ7和WFG1-WFG9上的IGD值

为了更加直观地比较8个算法的性能差异，图1展示了它们在10维DTLZ1、DTLZ3、DTLZ5、DTLZ7、WFG2和WFG4上的结果.图1中以平行坐标图的方式绘制了每个算法得到的最好IGD值所对应的种群[44].在较难收敛的DTLZ1和DTLZ3上，除GFM-MOEA和GrEA外的其它所有算法均能收敛到前沿面上.在具有退化前沿面的DTLZ5上，只有MOEA/D能够收敛到前沿面并保持较好的分布性.在具有不规则前沿面的DTLZ7和WFG2上，GFM-MOEA、GrEA和AR-MOEA得到的种群的分布范围要明显大于其它算法得到的种群.而在具有未归一化前沿面的WFG4上，GFM-MOEA、GrEA和NSGA-Ⅱ/SDR得到的种群的分布范围最广.

图1 8个超多目标进化算法在DTLZ1、DTLZ3、DTLZ5、DTLZ7、WFG2和WFG4上的结果Fig.1 Results of eight many-objective evolutionary algorithms on DTLZ1, DTLZ3, DTLZ5, DTLZ7, WFG2, and WFG4

根据以上实验结果来看，若待解决问题较容易收敛但具有复杂的前沿面形状，可以选择GFM-MOEA来求解，因为它在具有不规则或未归一化的前沿面的问题上的综合性能最好.若待解决的问题较难收敛则可以选择AR-MOEA，因为它有较好的收敛性且在具有不规则前沿面的问题上也有较好的分布性.

3 超多目标进化优化发展趋势

经过了十余年的研究与发展，进化算法可以在超多目标优化测试问题上取得非常理想的结果.除了以上介绍的4类超多目标进化算法之外，超多目标进化优化的研究在近些年也呈现出了一些新的特点.

首先，大多数超多目标进化算法均通过改进选择策略来提升性能，它们大都采用类似的遗传算子如模拟二进制交叉和多项式变异.与此不同的是，近些年还有少数算法通过改进产生子代解的算子来提升进化算法求解超多目标优化问题的性能.例如，NMPSO中设计了一种粒子群算法[45]，MaOEDA-IR中设计了一种分布估计算法[46]，而CSEA中设计了一种代理模型辅助算法[47].

其次，大多数超多目标进化算法仅在测试问题上进行了效果验证，但并没有被用于解决实际中的超多目标优化问题.实际上，目前常用的超多目标优化测试问题的形式太过理想[48]，它们与实际问题的形式有一些差异.因此，一些工作设计了更加多样化的超多目标优化测试问题[49]，而另一些工作着重于分析超多目标进化算法在实际问题上的性能[2].

再者，由于高维目标空间过大，算法很难将得到的数百个解分布于整个高维前沿面.为此，一些工作在求解超多目标优化问题时加入决策者的偏好信息来为决策者提供更符合要求的候选解[50]；此外，一些工作则通过搜索前沿面的knee point来代替搜索覆盖整个前沿面的解集[51]，从而在没有决策者的偏好信息时也能提供更少更好的候选解.

最后，高维目标空间中解的可视化也是一个值得研究的难题.虽然目前有许多高维数据的可视化方法，但仍然没有一种方法能够满足算法设计者和问题决策者的所有要求[52].设计更好的高维数据可视化方法不仅能指导设计者开发更加有效的超多目标进化算法，还能使决策者能够更加直观地进行方案选择.

4 结 论

本文首先简单介绍了超多目标优化问题的定义与研究概况，然后详细地介绍了4类超多目标进化算法的特点及一些代表性算法,并通过实验对比了8个具有代表性的超多目标进化算法的性能.本文实验所对比的算法大都是近5年发表于进化计算领域的顶级期刊《IEEE Transactions on Evolutionary Computation》上的，它们可以代表当前超多目标进化算法的最高水平.实验证实，GFM-MOEA在具有复杂前沿面的超多目标优化问题上能获得更好的效果，而AR-MOEA更加适合于较难收敛的超多目标优化问题.除了算法研究之外，本文也介绍了几个关于超多目标优化的研究热点，包括遗传算子的设计、测试问题的设计、偏好信息的利用和高维可视化方法的设计.