2.1.2 基于非支配排序的多目标进化算法

目前，大部分多目标进化算法利用帕累托支配关系判断候选解的优劣，其中最具代表性的是改进后的非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ），又被称为快速精英多目标遗传算法。在遗传算法的基础上，NSGA-Ⅱ使用了快速非支配排序方法加速种群选择，基于个体拥挤距离选择算子保留种群多样性，精英策略选择算子帮助种群寻优。快速非支配排序方法通过记录每个候选解 p 被支配的个数（ n _p ）以及每个候选解 p 支配的候选解集合（ S _p ）来辅助快速排序的完成。在 n _p 和 S _p 的帮助下，每个解决方案只需要在每次迭代中与种群中的其他解决方案进行一次比较，确定支配关系即可。

1.NSGA -Ⅱ

NSGA-Ⅱ根据支配关系和个体拥挤距离选择优质父代产生子代，并保留精英个体，主要包括快速非支配排序和拥挤度计算两大步骤，NSGA-Ⅱ流程图如图2-2所示。

1）快速非支配排序 ：首先，快速非支配排序方法为每个个体计算两个变量：支配计数（ n _p ），即支配该个体的数量；该个体支配的集合（ S _p ）。首先，该方法通过循环比较找到所有 n _p =0的个体，并将其放入第一层非支配前沿中。其次，对于第一层非支配前沿中的个体，使用快速非支配排序方法访问其支配集合中的每个个体，并将其支配数减少一个。在此过程中，如果有个体的 n _p =0，则将其放入下一个非支配前沿。然后对下一个非支配前沿中的个体进行上述操作，并确定第三个非支配前沿。重复上述过程直到获得所有前沿。快速非支配排序算法的伪代码如算法2-1所示。

2）拥挤度计算 ：拥挤距离的计算要求根据每个目标函数值的大小以升序方式对种群进行排序，然后，对于每个目标函数，处于边界的个体（函数值最小和最大的个体）被分配一个无限距离值。所有其他中间个体的距离值等于相邻两个个体的目标函数值的绝对归一化差值。其他目标函数的计算也是如此。总体拥挤距离值是根据每个目标对应的单个距离值之和计算得出的。

2.其他非支配排序方法

虽然帕累托支配关系能够帮助种群判断个体的优劣，但当目标个数增加时，这类方法的性能受到了严重的支配阻碍。在一个目标数为 M 的多目标优化问题中，对于两个随机选择的候选解 支配 y 的概率为 。随着目标个数 M 的增加，概率 将呈指数式下降，这种现象称为支配阻碍（dominance resistance）。针对这个问题，学者们提出了多种多目标进化方法来提高区分两个候选解的概率。根据Yaochu Jin团队的归纳，这些方法可以分为以下三类。

1）扩大可支配区域 ：这类方法通过扩大支配区域来减缓选择压力，包括 α -支配法、广义帕累托最优法以及控制支配区域法（Controlling Dominance Area of Solutions，CDAS）。以CDAS为例，它通过改变目标函数的定义控制支配区域的大小，修改如下：

其中， 是修改后的子目标函数， 表示 f （ x ）的L2范数， w _i 表示 x 与第 i 轴的偏角， 是用于控制扩展度的参数。

2）网格划分目标空间 ：第二类方法通过将目标空间划分为网格放宽帕累托支配关系。在该类方法中，候选解 x 的网络坐标 g （ x ）=（ g ₁ （ x ）， g ₂ （ x ），…， g _M （ x ））可以按照下式计算

其中， lb _i 和 d _i 请参考文献[85]进行计算。

3）定义新的支配关系 ：受到模糊逻辑、目标分解的影响，第三类方法通过重新定义标准判断支配关系，常见的算法有模糊支配、（1 -k ）-支配以及 θ -支配。 θ -支配将两个候选解 x 、 y 的支配关系重新定义如下

当且仅当上述公式得到满足时， x θ -支配 y 。其中， λ 是权重向量， θ 是惩罚系数， d ₁ （ x ， λ ）和 d ₂ （ x ， λ ）的计算请参考文献[86]。

为更好地说明上述几类方法，图2-3给出了双目标优化问题候选解可支配区域示意图。