大规模多目标进化优化算法研究进展*

谢承旺，龙广林，程文旗，郭 华

(南宁师范大学计算机与信息工程学院，广西南宁 530000)

0 引言

现实中存在大量需要同时优化多个目标的问题，它们通常被称为多目标优化问题 (Multi-objective Optimization Problem,MOP)。 MOP中各目标之间通常是相互冲突的，因此MOP一般不存在能同时优化多个目标的唯一最优解，而往往是一组折中的解，即Pareto解集[1]。因为MOP模型的复杂性使得经典的数学解析方法无法有效地求解，所以研究者尝试采用一些元启发方法求解MOP。进化算法(Evolutionary Algorithm，EA)是一类基于群体搜索的随机优化方法，EA运行一次可以获得一组解，而且对待解问题的数学性质不做严格假设，因而被广泛地应用于求解各种类型的MOP，并因此产生了许多经典的多目标进化算法(Multi-objective Evolutionary Algorithm，MOEA)。

近年来随着社会经济的高速发展，一些更为复杂的MOP不断涌现，这些MOP通常从两个方面进行扩展：一方面，MOP的目标数目越来越大，这使得MOP扩展成高维多目标优化问题(Many-objective Optimization Problem，MaOP，一般指目标数目大于等于4)；另一方面，MOP的决策变量数目越来越多，这使得MOP扩展成大规模多目标优化问题(Large-scale Multi-objective Optimization Problem，LSMOP，一般指决策变数的数目超过100)。需要指出的是，国内外学者对高维多目标进化算法(Many-objective Evolutionary Algorithm,MaOEA)及其研究综述已不少见[2]，但对于大规模多目标进化优化算法(Large-scale Multi-objective Optimization Evolutionary Algorithm，LSMOEA)的研究较少，特别是关于LSMOEA研究综述的论文更是少见，这种状况显然不利于研究者对LSMOP开展深入研究。基于此，本文系统整理了已有关于LSMOP的文献，对求解LSMOP的多种方法进行分门别类，概括各类方法的主要思想和技术特点，指出当前研究LSMOP存在的不足，并对今后LSMOP的研究方向给出建议。

1 大规模多目标优化问题相关概念

不失一般性，以最小化问题为例，一个具有n个决策变量和m个目标的MOP可形式化定义如下：

(1)

其中，x=(x1,x2,…,xn)∈Ω⊆n是n维的决策向量，xi∈[xi,min,xi,max]，i∈(1,2,…,n)，而xi,min和xi,max分别为决策变量xi的下界和上界。对于LSMOP而言，决策向量的维度n通常大于100。F(x) 包含m个相互冲突的目标，且F(x)=(y1,y2,…,ym)∈Λ⊆m。gi(x)是MOP的第i个不等式约束，q为不等式约束的数目。hj(x)是MOP的第j个等式约束，p为等式约束的数目。

以下在式(1)的基础上给出与LSMOP密切相关的若干定义：

定义1(Pareto支配) 假设x和y是MOP的可行解，称xPareto支配y(记作xy)，当且仅当∀i∈[1∶m]∶fi(x)≤fi(y)∧∃j∈[1∶m]∶fj(x)

定义2(Pareto最优解) 对于决策空间Ω中的任一点x*，若在Ω中不存在Pareto支配x*的解向量，则称x*为Pareto最优解，即∃x∈Ω:

xx*。

定义3(Pareto最优解集) 决策空间Ω中所有Pareto最优解构成的集合称为Pareto最优解集(PS)，即PS={x*∈Ω|∃x∈Ω:xx*}。

定义4(Pareto前沿) Pareto最优解集PS对应的目标向量的集合称为Pareto前沿(PF)，即PF={F(x*)|x*∈PS}。

定义5(可分离函数[3]) 如果f(x)被称为可分离函数，当且仅当x中每一个决策变量xi(i=1,…,n)均可独立优化，即

(2)

否则，f(x)被称为不可分离函数。

定义6(变量依赖[4]) 设决策变量xi和xj是相互依赖的变量，则存在决策向量x、a1、a2、b1和b2满足：

f(x)|xi=a2,xj=b1

f(x)|xi=a2,xj=b2>f(x)|xi=a1,xj=b2，

(3)

这里f(x)|xi=a2,xj=b1≜f(x1,…,xi-1,a2,…,xj-1,b1,…,xn)。

2 大规模多目标进化优化算法分类

现实中存在大量的LSMOP，例如投资组合优化问题[5]、车辆路径问题[6]、资源分配问题[7]等，这些应用问题通常具有大量的决策变量，而且决策变量之间尚存在依赖性，这些特征对MOEA的解题能力提出了巨大的挑战，而有关LSMOP的研究也已成为当前多目标优化领域研究的热点之一。

迄今为止，研究者根据LSMOP的特征，基于不同的视角和背景提出了若干解决LSMOP的LSMOEA。以下根据LSMOEA的主要思想和技术特点将它们粗略地分成4种类型：1)基于协同进化(Cooperative Coevolution，CC)的方法；2)基于决策变量分析的方法；3)基于问题重构的方法；4)其他方法。

2.1 基于协同进化的LSMOEA

自然界中，协同进化是指不同的物种在进化过程中相互作用、互相适应、共同进化的过程。Potter等[8]首先提出将进化算法与CC相结合的方法，该方法采用固定的分组策略将决策变量分为较小的子种群，然后利用进化算法实施优化。在LSMOP中，由于决策变量的数目众多，如何对决策变量进行适当分组，将每个组视为一个独立的种群参与协同进化过程，是这类算法的核心思想。

不难发现，关于决策变量的分组方法是该类算法的重要技术特点。目前经典的变量分组策略主要有如下4种类型：

1)随机分组(Random Grouping)[9]：将n个决策变量随机分配到S个规模相等的组中。

2)线性分组(Linear Grouping)[10]：将n个决策变量按自然顺序分成S个规模相同的组，即第一组为{x1,x2,…,xn/S}，第二组为{xn/S+1，…,x2n/S}，以此类推。

3)有序分组(Ordered Grouping)[11]：对于一个选定的解，将决策变量按绝对值升序排序，将绝对值最小的n/S个决策变量分成一组，以此类推。

4)差分分组(Differential Grouping)[12]：在执行分组时先检测决策变量之间的相互作用，将具有相互作用的决策变量分到同一组。

其中，前3种分组机制未使用任何关于目标函数的信息，而差分分组则包含一个基于问题分析的机制。

Antonio等[13]于2013年提出一种基于协同进化策略的大规模多目标优化进化算法CCGDE3，该算法采用随机分组策略，将决策变量随机地划分成多个子种群，利用快速非支配排序方法获得每个子种群的最优非支配解，由此获得最终解集。CCGDE3将协同进化方法和广义差分进化相结合，有效地解决了具有200—500个决策变量的LSMOP。但需指出的是，由于决策变量之间并非都是相互独立的关系，CCGDE3的分组策略没有对决策变量进行分析，利用该算法解决一些具有复杂关系变量的LSMOP时，可能无法获得较好的性能。

2016年，Antonio等[14]提出一种新颖的基于分解的方法解决LSMOP的算法，即MOEA/D2，该算法在CCGDE3的基础上利用随机分组和协同进化方法改善MOEA/D在求解LSMOP时的性能。MOEA/D2对LSMOP的目标空间和决策空间进行分解，实验结果表明，该算法在求解决策变量数目在200—1 200的DTLZ测试问题上具有较好的性能，其效果优于MOEA/D和GDE3。但是这种方法需要进一步考虑如何以较低的计算开销获得一组均匀分布的权重向量，以及发展更高效的决策空间分解技术。

Li等[15]利用一种快速识别变量相互依赖关系的方法对决策变量进行分组，提出一种新的基于协同进化的大规模多目标进化优化方法CCLSM，用以解决LSMOP。CCLSM中快速识别相互依赖关系的方法首先识别可分离变量和不可分离变量，其次识别不可分离变量之间的相互依赖信息。CCLSM将协同进化机制和变量分组方法相结合，并且使用交互的分组策略。必须指出，尽管很多算法都利用了协同进化机制和分组策略来解决LSMOP，但一些高效的变量分组策略和协同进化机制等亟待发展。

2019年，Basu等[16]针对LSMOP中决策变量之间具有可分离和不可分离的特点，提出MOEA/D(s&ns)，该算法将协同进化方法和MOEA/D-DE相结合，利用协同进化方法将决策变量划分成较小规模的子种群，然后利用MOEA/D-DE对各子种群进行优化。

上述LSMOEA的共同特点是利用协同进化的机制，而它们采用的变量分组策略则不尽相同。值得一提的是，CCLSM中利用大规模单目标优化中的快速依赖识别方法，显著增强了算法的性能。

2.2 基于决策变量分析的LSMOEA

为应对决策空间维度不断增大带来的“维数灾难”问题，研究者通过对决策变量进行分析，挖掘决策变量与优化问题之间的相关性，即通常意义上的收敛性相关、多样性相关和收敛性-多样性相关，然后选择合适的策略对决策变量进行优化。

Ma等[17]在2016年提出一种基于决策变量分析的大规模多目标进化优化算法MOEA/DVA,该算法进一步研究决策变量的关系以及决策变量对目标函数的影响。在MOEA/DVA中，对决策变量的分析包括控制变量分析和变量关联性分析。在控制变量分析中，算法将决策变量划分为位置变量、距离变量和混合变量(即与收敛性和多样性均相关的变量)；变量关联性分析则每次通过分析随机的两个决策变量之间的相关性，从而进行分组。MOEA/DVA根据决策变量的相关性，以及它们对优化问题的收敛性和多样性方面的影响对决策变量进行分组，使得该算法在解决某些LSMOP上具有较好的性能。但不可忽视的是，MOEA/DVA需要进行大量的适应度评价，增加了计算开销，而且该算法在混合变量较多的LSMOP上性能较差，因此如何更好地处理混合变量，以及更有效地分配计算资源是这种算法尚待解决的问题。

Song 等[18]发展了一种随机的动态分组策略(Random-based Dynamic Grouping,RDG),他们将RDG与MOEA/D框架相结合，提出新算法MOEA/D-RDG。该算法在求解具有800—1 000个决策变量的UF和WFG系列测试问题上表现出较好的性能。RDG方法的主要特点有3个：1)将变量依赖作为局部信息，而非全局信息；2)动态地确定每个分组的变量，而且分组的大小也是根据分解池动态确定；3)利用C-metric计算相对性能改善，并设置一个性能改进表记录各分组大小引起的性能变化。相比于MOEA/DVA，MOEA/D-RDG采用RDG方法处理LSMOP，而且分组不需要额外的函数评估，所以可以将更多的计算资源用于种群的进化优化，改进算法的性能。值得注意的是，采用动态分组策略是未来设计LSMOEA值得参考的思路。

Zhang等[19]在2016年提出一种大规模高维多目标进化优化算法LMEA，该算法与MOEA/DVA的思想有类似之处，即二者都根据决策变量的控制属性将它们分成收敛性相关变量和多样性相关变量，而且都需要大量的函数评估。不同的是，LMEA利用基于角度的聚类分析方法对决策变量的属性进行分析，并且分别用收敛性优化策略和多样性优化策略对两类变量进行优化。虽然LMEA较之MOEA/DVA在决策变量分析上的计算代价有所降低，但它所需的计算资源仍随决策变量数目的增多而急剧增加，而且对决策变量分类以及变量之间的交互分析亦成为影响该算法时间复杂性的重要因素。

Cao等[20]在2020年提出一种基于图的多目标带偏移的差分分组方法，即mogDG-shift，该方法通过分析决策变量的属性并检测决策变量之间的相互作用，从而根据变量的属性和相互作用对决策变量进行分组。与MOEA/DVA的DVA方法相比，mogDG-shift对决策变量分析和分组的方法更为优越，它的分组精度要远优于DVA。未来mogDG-shift可结合协同进化框架进一步提高算法的优化性能。

2018年，Chen等[21]在协方差矩阵自适应进化策略CMA-ES的基础上，提出一种可扩展小种群的协方差矩阵自适应进化策略求解LSMOP的新算法，即S3-CMA-ES。与MOEA/DVA类似，S3-CMA-ES将决策变量分为收敛性相关变量和多样性相关变量，并基于变量的相互作用，进一步将收敛性相关变量分成多个子组。S3-CMA-ES中每个子种群只收敛到一个解，多个子种群同时进化才收敛到一组近似Pareto最优解。与MOEA/DVA和LMEA类似，S3-CMA-ES也依赖于决策变量分析，从而使得计算开销急剧增加。

在云计算启发下，Cao等[22]于2017年提出一种基于消息传递接口(Message Passing Interface，MPI)的分布式并行协同进化的多目标优化算法DPCCMOEA，该算法利用改进的变量分析方法将决策变量分成若干组，每组由一个子种群进行优化，然后再将每个子种群进一步分成若干组。DPCCMOEA在MPI机制的基础上，构造了两层MPI并行结构，相比于CCGDE3和MOEA/DVA，DPCCMOEA减少了时间消耗并获得较优的解题效果。受DPCCMOEA的启发，未来可利用分布式方法解决LSMOP，以减少计算开销。

2018年，Chen等[23]提出一种并行进化算法(Parallel Evolutionary Algorithm，PEA)用于求解LSMOP。PEA设计了一个并行框架，较好地消除进化过程中各个子进程之间的依赖关系，增强算法的并行性。PEA分离收敛性和多样性，其中当多样性保持固定时，每个子种群仅优化收敛性相关变量，从而达到在不通信情况下实现收敛。基于并行进化算法的框架，如何利用“云”的思想自适应地分配计算资源将是一个颇具吸引力的研究课题。

2.3 基于问题重构的LSMOEA

除上述利用协同进化方法和决策变量分析方法处理LSMOP外，近来利用问题重构(Problem Transformation，PT)的方法处理LSMOP成为新的研究热点。

Zille等[24]在2017年提出一种加权优化框架(Weighted Optimization Framework，WOF)，通过变量分组和加权实施对原始优化问题的转化(问题重构)。其核心思想在于利用分组策略将变量分成若干组，每一组变量关联一个权重，即同组内的决策变量具有相同的权重，从而把对大规模决策变量的优化转换为对较低维度权重向量的优化，实现对搜索空间的降维。基于WOF的问题重构虽然有效降低了决策空间的维度，但其在考虑权重变量相关性方面存在不足，而且在重构策略上比较依赖分组技术。在利用重构方法处理LSMOP中，发展更有效的决策变量分组方法和问题转换策略需要进一步研究。

由于随机嵌入(Random Embedding，RE)技术[25,26]在大规模单目标优化问题中的有效性，Qian等[27]提出一种基于随机嵌入的大规模多目标进化优化算法ReMO，该算法对那些只有少数决策变量对目标函数有贡献的问题(即低有效维度问题)较为有效，它可以将任意无梯度的多目标优化算法进行扩展，用于求解具有低有效维度的大规模非凸多目标优化问题。值得注意的是，ReMO在保持Pareto前沿、降低时间复杂性和旋转扰动不变性(即旋转扰动的鲁棒性)等方面具有良好的性质。因为ReMO无需对决策变量进行分析，大幅减少了函数评估的时间开销，所以该算法成为一种颇具前景的LSMOEA。但需要指出的是，ReMO仅在ZDT测试问题上进行实验，尚需在更多、更困难的LSMOP上检验该算法的性能。

受WOF中转换策略的启发，He等[28]在2019年提出一种利用问题重构加速大规模多目标优化的框架LSMOF，其主要思想是利用问题重构直接跟踪Pareto最优解。LSMOF利用权重向量降低原始问题决策空间的维度，采用指标函数对目标空间进行缩减。具体地，LSMOF首先将候选参考解与一组决策向量相关联，实现对决策空间的重构，从而确定Pareto最优解集的位置；其次，LSMOF将LSMOP转化成低维单目标优化问题，并且利用基于性能指标的适应度赋值策略对单目标优化问题进行优化。对比一些代表性LSMOEA，如MOEA/DVA和WOF，LSMOF收敛速度更快，消耗计算资源更少。需要指出的是，将LSMOF与云计算相结合以提高算法的效率亦是一个值得关注的问题。

2.4 其他方法

受SMS-EMOA[29]的启发，Hong等[30]在2018年提出一种基于双重局部搜索(Dual Local Search)的多目标进化算法DLS-MOEA。该算法利用局部搜索增加种群多样性，利用指标方法增强算法的收敛性，该算法在决策变量数目高达8 192个的WFG测试问题上取得显著较优的性能。一方面，DLS-MOEA并未使用变量分组机制，减少了用于获取变量交互信息的计算开销；另一方面，DLS-MOEA比较依赖性能评估指标的选择。但DLS-MOEA并没有在较多的LSMOP上进行实验，其求解更复杂LSMOP的能力尚待进一步验证。

2016年，Zille等[31]研究变异算子在分组变量中的作用及其对大规模多目标优化的影响，他们在多项式变异的基础上引入3种新的变异方法，即联结多项式变异(Linked Polynomial Mutation)、分组多项式变异(Grouped Polynomial Mutation)、分组和联结多项式变异(Grouped and Linked Polynomial Mutation),实验结果表明，新的变异算子在大规模WFG测试问题上表现出较好的性能。

Tian等[32]在2019年提出一种用于求解大规模稀疏多目标优化问题的进化算法SparseEA，该算法考虑了LSMOP的Pareto最优解的稀疏性(即最优解的大部分决策变量为0)，设计了一种新的种群初始化方法和新的进化算子，用于保证生成解的稀疏性。需要指出的是，该文献中精心设计了一组测试问题集SMOP1-8,用于评估算法的性能，实验表明SparseEA在求解大规模稀疏多目标优化问题时较之其他的算法具有显著的性能优势。

鉴于LSMOEA在求解大规模稀疏多目标优化问题时尚有较大的改进空间，Tian等[33]在2020年提出一种通过学习Pareto最优子空间来求解大规模稀疏多目标优化问题的算法，即MOEA/PSL。该算法通过使用受限玻尔兹曼机(Restricted Boltzmann Machine，RBM)和去噪自动编码器(Denoising Autoencoder，DEA)对Pareto子空间进行学习，其原理在于通过表示RBM和DEA的隐藏层减少决策变量的数目; MOEA/PSL还采用一种参数自适应策略确定在Pareto最佳子空间中生成子代个体的比例和隐藏层的大小。实验结果表明，在求解大规模稀疏多目标优化问题时学习Pareto最优子空间非常重要[33]。

Liang等[34]在2020年提出一种基于RVEA框架的算法，即MOEA-CSOD,该算法将RVEA与分布式对抗网络(Distribution Adversarial Networks，DAN)相结合，利用RVEA中的参考向量引导种群进化，利用DAN的分布式神经网络对抗性训练框架快速生成收敛性较好的解个体。实验表明MOEA-CSOD在LSMOP测试上具有较好的性能[34],但该算法在部分测试问题上表现出个体较少以及DAN过拟合的问题，因此MOEA-CSOD尚需进一步完善。

表1列出了近年来具有代表性的LSMOEA类型、提出年份、LSMOP决策变量的数目、LSMOP目标数目以及算法所使用的测试函数等信息。

表1 代表性大规模多目标进化算法

3 展望

LSMOP在现实中广泛存在，例如电力系统设计问题[35]、投资组合优化问题[5]、车辆路径问题[6]、资源分配问题[7]、距离最小化问题[36]和软件项目调度问题[37]等，这些实际应用问题的决策变量数目一般较多，有的甚至高达1 000维以上；另外，决策变量之间通常还存在复杂的依赖关系。由此可见，设计能有效求解LSMOP的算法在理论和应用上具有重要意义。

迄今为止，虽然研究者基于不同的视角提出了多种LSMOEA，且在一些LSMOP测试上进行实验并取得较好的结果，但有关LSMOEA的研究仍处于起步阶段，未来可以从以下6个方面进一步开展深入的研究：

1)设计更加有效的决策变量分组机制。变量分组是LSMOEA中重要的部件，已有决策变量分组的方法有的是从大规模单目标优化中沿用过来，有的是新发展的变量分组方法，但这些分组方法大多需要大量的函数评估用于发现决策变量之间的依赖信息，增加了算法的时间开销。未来需要进一步发展更加高效的分组策略以提升LSMOEA的性能。

2)LSMOP同时具有高维决策空间和高维目标空间，探索两个高维空间之间的关联性以及问题依赖性可能是设计新的LSMOEA的着力点之一。

3)目前用于测试和验证LSMOEA性能的主要有ZDT[38]、DTLZ[39]、WFG[40]、UF[41]和LSMOP[42]等系列的测试函数，这些测试函数原来大多数是用于测试多目标/高维多目标优化算法的性能，鉴于LSMOP复杂的决策空间，需要精心设计出一系列具有各种类型并且贴合实际应用问题特征的LSMOP基准测试集，以更好地验证LSMOEA的性能。另外，可以建立LSMOP的实际应用案例库，用现实问题检验LSMOEA的效率与效果。

4)目前研究较多的是静态LSMOP，而现实中一些复杂的LSMOP搜索空间可能是动态变化的。对于动态LSMOP的研究将是一个有意义且颇具挑战性的课题。

5)设计出适于评价LSMOEA性能的指标亦是未来需要进一步研究的工作。

6)新的计算模型和学习范式不断涌现，如云计算和深度学习等，如何在LSMOEA中结合这些新型的计算范式亦是未来值得研究的课题。