多目标进化算法综述

梅志伟

摘要：基于种群的进化算法在一次运行中能够产生一组近似的 Pareto 最优解集，因此多目标进化算法成为处理多目标优化问题中的主流方法。介绍了多目标优化问题中的数学模型以及相关定义，根据多目标进化算法的特点，将现有算法分为4类并分别进行阐述，同时分析了它们的优缺点。

关键词：多目标优化；进化算法；支配；分解

DOIDOI：10.11907/rjdk.171169

中图分类号：TP301

文献标识码：A 文章编号：1672-7800（2017）006-0204-04

0 引言

在人们的实际生活中，大多数优化问题都是多目标优化问题，广泛存在于经济管理、工程实践和科学研究等领域中。当前，多目标优化在理论和应用方面均取得了不少进展，但是由于多目标优化问题的复杂性，因此仍存在大量挑战。

多目标优化问题中往往存在多个彼此相互冲突的目标。与单目标优化不同，在多目标优化中，提高一个目标的性能会引起其它一个或多个目标性能的下降。因此，多目标优化问题中不存在一个单独的最优解，而是存在一组表示各个目标间权衡和折中关系的解集，称该解集为Pareto最优解集。Pareto最优解集在目标域的投影被称为Pareto前沿。

由于很多现实工程问题中的优化问题是NP难，传统的数学规划方法将会变得异常困难。而具有自然界规律启发式特征的求解方法往往适合近似求解这些困难问题，这些方法被称为进化计算[1]。进化算法基于种群的特性使其十分适合多目标优化问题的求解。同时，进化算法还具有鲁棒性强的特点。因此，进化算法被广泛应用在多目标优化问题的求解上。

1 多目标进化问题概述

多目标优化问题同时优化多个目标，这些待优化的目标包含最大化、最小化或者两者都有的问题。在实际处理时，为了简化问题，可以将最大化或最小化问题取反，使所有优化目标全部转化成最小化或最大化问题。本文中将讨论最小化问题。

2 多目标进化算法一般流程

生物进化是一个不断优化的过程，在不断的变化过程中增加自身的适应性。进化计算以生物进化为启发，对一个解进行抽象编码，模拟生物进化中的基因。进化算法以种群为基础，是一个黑盒的搜索、优化方法，进化算法不需要优化问题具备一定的前提条件，例如连续性、可微性等，且一次运行能够产生一组解。因此，进化算法特别适合处理多目标优化问题。

生物的进化过程主要包括繁殖、变异、竞争和选择。与之类似，一个典型的进化算法主要包含以下步骤：①初始化：生成一个初始化种群，记为P，其中包含N个个体（解），并记当前代数t=0；②适应度评价：计算每个个体x∈P的适应度值F（x）；③繁殖：从父代种群P繁殖出后代种群Q，具体包括交叉和变异过程；④选择：使用选择算子从P∪Q中选择出N个精英个体，作为下一代的父代种群P；⑤下一代进化：增加进化代数t=t+1，如果满足终止条件，则停止算法并输出P，否则进入下一代迭代过程，即转入第2步。

一个典型的进化算法流程如图1所示。

3 多目标进化算法分类

从进化算法诞生之初，由于其在多目标优化问题上的优异表现，众多研究人员提出了多种多目标进化算法。根据算法特性不同，具体可分为以下几类：

3.1 基于Pareto支配关系的多目标进化算法

通过Pareto支配关系，可以对两个解进行对比，从而利用支配信息指导解集的选择。基于Pareto支配关系的多目标进化算法一直以来都是一个热门研究方向，研究人员提出了许多算法，例如SPEA[2]、SPEA2[3]、PESA[4]、PESA-II[5]、NSGA-II[6]等。

基于Pareto支配的多目标进化算法取得了令人瞩目的成就，然而在处理超多目标优化问题时却面临许多挑战。由于Pareto支配的特性，超多目标空间中的大部分解均为非支配关系，从而失去了选择压力。研究人员通过改进Pareto支配关系，提出了一系列方法。

Laummans等[7]定义了一种ε支配关系，增加了一个解的支配空间；Deb等[8]根据ε支配关系，提出了ε-MOEA算法，在超多目标优化问题中取得了较好效果。ε-MOEA算法将目标空间划分成網格，不同网格中的解使用ε支配关系进行比较，相同网格中的解则使用传统的Pareto支配关系。

2001年，Ikeda等[9]也提出了一种新的支配关系，称为α支配。在α支配关系中，比较一个目标的同时会考虑其它目标函数值。通过一个线性平衡函数重新计算对比时的目标值，若一个解在一个目标上显著优于另一个解，而在另一个目标上则略微处于弱势，则前者仍然能α支配后者，这样的支配关系有利于选择更好的解。

除此之外，还有多种算法建立在改进的Pareto支配关系之上，例如基于网格支配的GrEA算法[10]、基于ε排序策略的εR-EMO算法[11]等。

3.2 基于分解的多目标进化算法

将一个多目标优化问题分解为一组单目标的子问题进行求解也是一个常见的解决方法。常见的分解方法包括加权和法、切比雪夫法以及基于惩罚值的边界交叉法[12]。

2007年，Zhang等[13]结合了上述几种分解方法提出了一种基于分解的多目标进化算法（MOEA/D），这是近年来的一个热门算法框架。在MOEA/D算法中，通过传统的分解方法将一个多目标优化问题分解为一组单目标的子问题，然后使用进化算法同时求解这些子问题。MOEA/D还通过权重向量之间的距离关系定义了子问题间的邻居关系。在优化一个子问题时，通过相邻子问题间交叉变异的进化过程生成新解，并使用新解来更新当前子问题的解。MOEA/D中还引入了一种邻居子问题间的信息共享方法，即一个新解在更新对应子问题的同时还会更新其邻居子问题。实验表明，MOEA/D算法相较于以往的一些基于分解的算法，效果更为突出。Li等[14]将差分进化的思想引入到MOEA/D的进化过程中，同时还限制了邻居子问题的最大更新数目，进一步提高了算法性能。

与基于Pareto支配关系的算法在超多目标优化问题中的局限不同，基于分解的算法能够直接适用于超多目标优化问题中。针对超多目标优化问题的特性，研究人员也提出了许多改进方法。Asafuddoula等[15]将系统抽样和自适应的ε控制技术引入到基于分解的进化算法中，在超多目标空间中生成均匀的权重向量，平衡解集的收敛性与多样性；為了解决超多目标空间选择压力过大导致的多样性丢失问题，Fabre等[16]提出了一种并行的遗传算法，将每个子问题都关联到一个子种群，通过子种群的进化实现整个种群的进化，实验结果也验证了其在多样性保持方面的优势。

3.3 基于指标的多目标进化算法

多目标进化算法求得的解集可以通过许多评价指标来衡量，基于指标的多目标进化算法通过评价指标来指引算法的搜索方向，指导进化过程中新种群的选择。

Zitzler等[17]首先将评价指标引入到进化算法的选择策略中，提出一种基于评价指标的进化算法（IBEA），可以通过任意一种评价指标来对比候选解。在IBEA中，不需要使用例如适应值共享等多样性保持策略，也不需要对整个近似Pareto最优解集进行计算，只需对比其中的部分解即可。

IH指标可以衡量一个解集的质量，IH指标值越大，表示解集质量越好。为了能够最大化一个解集的IH指标值，Emmerich等[18]提出了一种基于S-度量选择的多目标进化算法（SMS-EMOA）。SMS-EMOA通过IH指标的梯度信息来指导种群进化过程。在处理低维的多目标优化问题时，SMS-EMOA求得的解集具有很好的收敛性和多样性。但是，在面对超多目标优化问题时，SMS-EMOA的计算复杂度成指数上升，算法效果急剧下降。其每一代进化的计算复杂度为O（Nm/2+1），其中N为种群大小，m为问题的目标个数。

Brockhoff等[19]将目标空间缩小技术与基于IH指标的方法结合起来，提出一种新的算法，通过使用不同的目标空间缩小方法提高基于IH指标的算法性能。

IH指标的计算是一个非常耗时的过程，对基于IH指标的算法有很大影响。为了克服计算过于复杂的弊端，Bader等[20]提出了一种快速的近似计算方法，使用蒙特卡罗模拟近似计算解集的IH值，并提出了一种基于IH指标近似的多目标进化算法，在处理超多目标优化问题上取得了令人满意的成果。

通过将非支配排序和R2指标结合起来，Manriquez等[21]提出了R2-MOGA和R2-MODE算法，在处理超多目标优化问题时有显著优势；Gomez等[22]也提出了一种基于R2指标的优化算法MOMBI，同样也取得了不错的优化效果。

3.4 混合算法

在多目标进化算法中，研究人员提出了众多优化技术，不同技术均有其独特优势，例如基于Pareto支配关系的算法能够适应各种形状的Pareto前沿，但在处理超多目标优化问题时却显得不尽如人意；基于分解的算法通用性较好，但是常规的分解方法却容易导致解集多样性的丢失。其它的优化技术也各有优缺点。将这些技术混合起来，结合各种方法的优点来处理复杂的优化问题，也是一种非常有效的方法。

一种方法是将全局搜索与局部搜索结合起来，即多目标模因算法。例如，在Adra等[23]的算法中，对每一代进化中求得的最优解使用局部搜索策略在目标空间进一步优化，随后将优化后的解映射到对应的决策空间并预测其具体的决策向量；在Wang等[24]的算法中，则使用局部搜索来生成子代解。

另一种广泛使用的方法是将不同方法中的搜索策略结合起来，例如将粒子群优化和进化算法结合起来[25]，在每一代中，由粒子群优化产生的解再使用进化算法进行优化。

另一方面，还可以根据进化过程的不同特性将整个进化过程划分为多个阶段，在不同阶段使用不同的搜索策略。例如在Yang等[26]的算法中，进化过程包含3个阶段，分别侧重于被支配的解、平衡支配解和非支配解，以及着重于非支配解3个部分，结合NSGA-II算法的思想和局部增强搜索策略来实现各个阶段的进化过程。

4 结语

多目标进化算法由于其基于种群的特性而成为处理多目标优化问题的一种热门方法。本文进行了多目标优化问题的相关数学描述，简要介绍了相关理论定义。根据多目标进化算法的特性，本文还将近年来的主流进化算法分为4类进行阐述，并分析了它们的优缺点，以更好地应用于多目标优化问题的求解。

参考文献：

[1]POOLE D，MACKWORTH A，GOEBEL R.Computational intelligence：a logical approach[M].Oxford University Press，1997.

[2]ZITZLER E，THIELE L.Multiobjective evolutionary algorithms：a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.

[3]ZITZLER E，LAUMANNS M，THIELE L.SPEA2：improving the strength Pareto evolutionary algorithm[C].Eurogen，2001，3242（103）：95-100.

[4]CORNE D W，KNOWLES J D，OATES M J.The Pareto envelope-based selection algorithm for multiobjective optimization[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2000：839-848.

[5]CORNE D W，JERRAM N R，KNOWLES J D，et al.PESA-II：region-based selection in evolutionary multiobjective optimization[C].Proceedings of the Genetic And Evolutionary Computation Conference （GECCO2001），2001.

[6]DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[7]LAUMANNS M，THIELE L，DEB K，et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation，2002，10（3）：263-282.

[8]DEB K，MOHAN M，MISHRA S.Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[J].Evolutionary Computation，2005，13（4）：501-525.

[9]IKEDA K，KITA H，KOBAYASHI S.Failure of pareto-based MOEAs：does non-dominated really mean near to optimal？[C].Evolutionary Computation，Proceedings of the 2001 Congress on.IEEE，2001：957-962.

[10]YANG S，LI M，LIU X，et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2013，17（5）：721-736.

[11]AGUIRRE H，TANAKA K.Space partitioning with adaptive ε-ranking and substitute distance assignments：a comparative study on many-objective mnk-landscapes[C].Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation.ACM，2009：547-554.

[12]MIETTINEN K.Nonlinear multiobjective optimization[M].Springer Science & Business Media，2012.

[13]ZHANG Q，LI H.MOEA/D：A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

[14]LI H，ZHANG Q.Multiobjective optimization problems with complicated Pareto sets，MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation，2009，13（2）：284-302.

[15]ASAFUDDOULA M，RAY T，SARKER R.A decomposition-based evolutionary algorithm for many objective optimization[J].IEEE Transactions on Evolutionary Computation，2015，19（3）：445-460.

[16]GARZA-FABRE M，TOSCANO-PULIDO G，COELLO C A C，et al.Effective ranking+ speciation= many-objective optimization[C].2011 IEEE Congress of Evolutionary Computation （CEC）.IEEE，2011：2115-2122.

[17]ZITZLER E，KNZLI S.Indicator-based selection in multiobjective search[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2004：832-842.

[18]EMMERICH M，BEUME N，NAUJOKS B.An EMO algorithm using the hypervolume measure as selection criterion[C].International Conference on Evolutionary Multi-Criterion Optimization.Springer Berlin Heidelberg，2005：62-76.

[19]BROCKHOFF D，ZITZLER E.Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods[C].2007 IEEE Congress on Evolutionary Computation.IEEE，2007：2086-2093.

[20]BADER J，ZITZLER E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19（1）：45-76.

[21]DAZ-MANRQUEZ A，TOSCANO-PULIDO G，COELLO C A C，et al.A ranking method based on the R2 indicator for many-objective optimization[C].2013 IEEE Congress on Evolutionary Computation.IEEE，2013：1523-1530.

[22]GMEZ R H，COELLO C A C.MOMBI：a new metaheuristic for many-objective optimization based on the R2 indicator[C].2013 IEEE Congress on Evolutionary Computation，2013：2488-2495.

[23]ADRA S F，DODD T J，GRIFFIN I A，et al.Convergence acceleration operator for multiobjective optimization[J].IEEE Transactions on Evolutionary Computation，2009，13（4）：825-847.

[24]WANG Y，CAI Z，GUO G，et al.Multiobjective optimization and hybrid evolutionary algorithm to solve constrained optimization problems[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B （Cybernetics），2007，37（3）：560-575.

[25]ELHOSSINI A，AREIBI S，DONY R.Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization[J].Evolutionary Computation，2010，18（1）：127-156.

[26]YANG D，JIAO L，GONG M.Adaptive multi-objective optimization based on nondominated solutions[J].Computational Intelligence，2009，25（2）：84-108.

（責任编辑：黄 健）