进化算法（EA）是一种模拟自然进化过程的随机优化方法。它模拟由个体组成的群体的集体学习过程，其中每个个体表示给定问题搜索空间中的一点，从随机生成的初始种群出发，通过随机选择、变异和交叉过程，使群体进化到搜索空间中越来越好的解个体所在区域。多目标进化算法及其变种在实际多目标优化问题中得到成功的应用，下面对多目标进化算法进行介绍。

多目标进化算法以随机初始化种群为起点对种群进行演化操作，依据四个主要步骤逐渐地改善种群质量，使种群朝着最优解方向不断地逼近。这四个步骤操作如下［1］：

Step 1：配偶选择。基于个体在种群中的排序和秩的大小，选择出两个个体作为交配对象（父本）以便产生优秀的子代。尽管某些多目标进化算法中的父本数目可能超过两个，如MOEA/D［2］的父本就是三个个体，但大多数多目标进化算法依然是通过选择策略选出两个个体来作为父本。这些选择策略以统计概率的方式选出优良的个体。

Step 2：繁殖。通过一些进化操作算子（如交叉和变异）来重组选择的交配个体。Sivanandam和Deepa［3］就相关的进化操作算子给出了一个较全面的总结。

Step 3：环境选择（精英策略）。产生子代后，需要采用新的选择机制从子代和父代种群中选出新的种群。环境选择就是从子代和父代中分别选出λ个和μ个个体，为此设计了两种不同的环境选择机制：在第一种机制中，从组成的种群（由μ个父本和λ个子代个体构成）中选择出最佳μ个个体。而在第二种机制中，仅从λ个子代中选出最佳μ个个体。（μ+λ）-ES机制采用了精英策略来确保较好的父本幸存于新种群中。

Step 4：如果不满足停止条件，则执行Step 2。

随着研究的不断深入，多目标进化算法不断涌现。根据不同的要求，可以对多目标进化算法进行分类。本节基于不同的选择机制与决策方法对多目标进化算法进行分类［5］。

1.按不同的选择机制分类

根据不同的选择机制，多目标进化算法可分为如下几类：聚集函数方法；指标选择方法；基于Pareto的方法；基于超体积的方法。图2-3展示了这些分类以及相关算法或方法。

图2-3　基于不同选择机制的多目标进化算法分类

1）聚集函数方法

在求解多目标优化问题时，最简单的方法就是将全部的子目标函数组合或者聚集成一个单目标函数，从而将多目标优化问题转化为单目标优化问题。假设将一个多目标优化问题转化成一个单目标优化问题，其公式如下所示：

式中：wi表示第i个子目标的权重，且表示第i个子目标函数；m为多目标优化问题的目标函数总数。

该方法的运行机制就是运用聚集操作算子将m个目标函数整合成一个单目标函数。这种方法非常实用，但是需要获取足够多且有效的权重系数，而这是很困难的。Saaty［6］在1986年提出了一种层次分析方法，用于产生反映目标重要性的权重向量。层次分析方法通过非常简单的计算将数值置于因素及选择之前。同时，根据优化问题的一些特点，聚集函数运算往往会导致过早收敛。此外，这种权重分类方法包含了固定权重、自适应权重以及随机权重［7］。根据权重分类，基于聚集函数的多目标进化算法被相继提出。Ishibuchi和Murata［8］提出了一种随机权重遗传算法，在该算法中，分配给各子目标函数的权重会随着进化而发生随机变化。这种方法有助于算法朝着最优解的方向发展，但不能保证找到的Pareto前端是均匀分布的，尤其是在包含大量Pareto前端点的多目标优化问题上，很难找到分布均匀的Pareto前端。Gen和Cheng［9］提出了一种利用当前种群的变化信息来调整权重的方法，即自适应权重遗传算法（adaptive weight genetic algorithm，AWGA），这种自适应权重可协助算法的搜索方向朝着理想解不断地逼近。然而在非连续目标空间的多目标优化问题上，该算法却不能展示出良好的性能。最新出现的一种特殊的多目标进化算法是由Zhang和Li［2］开发的基于分解的多目标进化算法（MOEA/D）。该算法首先将随机权重向量分配给种群中的个体，每个个体都有一个邻居，该邻居是通过所分配的权重系数的最短欧氏距离来定义得到的。将每个个体的邻居视作为一个子问题，所有的子问题将独立地进行更新操作并产生子代。由于每个子问题中的个体仅与邻居中的个体进行比较，因此，这种分解式算法降低了每代的计算复杂度。但是邻居需要重新定义且权重也要不断变化。(www.daowen.com)

2）指标选择的方法

基于群体的方法主要依靠群智能的进化来实施更新搜索，向量评价遗传算法（VEGA）［10］是这类方法的典型代表。在每次迭代过程中，将种群划分为m个子种群，即每个子种群大小为N/m，其中N为种群规模，m为目标函数总数。每个子种群进行独立搜索，再将m个子种群合并为一个种群，并实施搜索操作。整个搜索过程就是不停地迭代各子群体和合并群体的搜索操作。VEGA的选择机制存在着一个较突出的问题：一个优良的折中解通常会顾及所有的子目标，但是对于VEGA来说，优良的折中解未必就是最优解，这样的解在VEGA的选择过程中会被淘汰掉，也就是说，VEGA在选择操作时，只考虑一个目标的同时通常会忽略其他目标。

3）基于Pareto的方法

该方法的主要特征是在选择机制中考虑了Pareto占优的思想。NSGA-Ⅱ［11］是该类方法的典型代表，根据支配关系将种群划分为若干等级，第一等级表示当前群体的非支配解集合，第二等级表示在群体中去掉第一等级后所求得的非支配解集合，直到不能再划分出更多的等级为止。选择过程中会优先选择第一等级非支配解集中的个体，然后再考虑其他等级的个体，以此类推，直到满足新种群的大小要求。近几年来的研究主要集中在这类方法，其中具有代表性的包括NSGA-Ⅱ［11］、强度Pareto进化算法（strength Pareto evolutionary algorithmⅡ，SPEA2）［12］及Pareto存档进化策略（Pareto archived evolution strategy，PAES）［13］等。

4）基于超体积（hypervolume，HV）的方法

HV是一个衡量多目标优化问题解集质量的指标，它是指由解集与一组特定的点（参考点）在目标空间中围成的区域的体积（在二维空间中，该区域是一个面）。为了说明HV的计算过程，图2-4给出了一个含有4个解的二维目标空间超体积实例。超体积由这些解与一组特定的参考点围成的区域所构成。尽管解A、B、C均能产生这样的区域（由于解B支配解D，所以解D不能产生这样的区域），但是相比其他解，解B能够产生更大区域的超体积。在以前，HV作为一个很受欢迎的衡量指标，可测试算法的性能，由于每个解对超体积的贡献不一，因此HV也可以用来衡量解的优劣。Huband等［14］提出了一种改进的SPEA2版本，该算法采用了基于环境选择的超体积来截断优化过程，因此，对超体积贡献大的个体将幸存下来，以保持外部文档的多样性。Zitzler和Künzli［15］提出了一种基于指标的进化算法（indicator-based evolutionary algorithm，IBEA），该算法采用一种二元超体积指标（binary hypervolume indicator）来比较解的优劣，并给每个解分配一个对应的适应度值。Bader和Zitzler［16］提出了一种基于超体积的多目标进化算法，称为HypE。由于超体积的计算过程十分耗时，因此基于超体积的多目标进化算法的运行速度也十分缓慢［17］。

图2-4　超体积实例

2.按不同的决策方法分类

求解多目标优化问题可分为两个过程：第一个是优化过程，即寻找Pareto最优解的过程；第二个是选择解的过程，通常也被称为决策过程。在决策过程中，决策者要清晰地表达其对目标的偏好。根据决策方式的不同，多目标进化算法可分为如下三大类。

1）先验方法（priori method）

这是一个先决定然后搜索的策略。决策者通常将多目标转化为一个标量函数。先验方法要求决策者有大量的先验知识来指导决策过程。此外，每一次目标的重要性发生变化时，都有一个新的优化过程产生。先验方法主要包含词典法（lexicographic）、线性适应度组合（linear fitness combination）及非线性组合（nonlinear combination）。词典法首先会根据指标优先级进行排序，然后对目标进行优化。线性适应度组合方法通过线性组合并给予各目标合适的权重值，将其转化成一个单目标问题。非线性组合方法又包含多适应度组合（multiplicative fitness combination）方法、目标向量适应度（target vector fitness）方法及极大极小适应度组合（minimax fitness combination）方法。先验方法的优点在于简单、易于操作及效率高；不足之处在于搜索空间有限，从而不能发掘出所有可能的解。

2）后验方法（posteriori method）

这是一个基于搜索然后决定的策略。这种策略就是尽可能多地找到非支配解，并从中选择一个解。后验方法主要包含独立样本（independent sampling）、指标选择（criteria selection）、聚合选择（aggregation selection）和Pareto样本（Pareto sampling）等技术。独立样本技术利用单目标搜索方法实现多目标优化策略，每个子目标都有不同的权重值，每次执行操作时需要调整权重值。它的优点在于简单高效；不足之处是当目标维数较大时，运行的难度随之提高。指标选择技术的典型代表算法是VEGA，它是指将种群平均划分为目标数大小的子种群，同时对子目标赋予权重值，然后这些子种群进行独立搜索优化，最后合并直到满足终止条件。它的优点是简单、易于实现；缺点在于会失去某些Pareto解。聚合选择技术是一类线性或非线性组合方法，对选择的个体进行操作，每次运行均产生一组解。其不足之处在于由于引入了权重组合求解个体适应度，所以将会损失一些最优边界的解。Pareto样本技术是基于Pareto支配的一种方法。由于它一次运行能产生满意的非支配解，同时不需要提前为各子目标分配权重，因此它是当前多目标进化算法采用较多的一种决策技术。

3）交互决策方法（progressive method）

它是先验方法与后验方法的交互过程，在此过程中既可采用先验决策方法，也可以采用后验决策技术。它的弱点在于难以选取决策偏好，且决策效率较低。