NSGA-Ⅱ

Non-dominated Sorting Genetic Algorithm-II（NSGA-Ⅱ）： 非支配排序遗传算法。基于遗传算法，引入快速非支配排序方法、拥挤度计算和精英策略的多目标优化计算方法。

NSGA-Ⅱ

• Non-dominated Sorting Genetic Algorithm-II（NSGA-Ⅱ）： 非支配排序遗传算法。基于遗传算法，引入快速非支配排序方法、拥挤度计算和精英策略的多目标优化计算方法。

  

快速非支配排序方法

• 快速非支配排序是在 Pareto 支配基础上提出的概念。计算每个个体的非支配等级(Pareto等级)，在种群 P 中，当前Pareto最优解的个体的非支配等级为 1，然后除去这些等级为 1 的个体，组成的新种群 P’，在新种群 P’ 中最优解的非支配等级为 2，以此类推计算出种群 P 中的所有个体的非支配等级。
• 种群中的每个个体都有两个参数和，为种群中支配个体 i 的个体数量，是被个体 i 支配的个体的集合，快速非支配排序的步骤如下：
  1. 通过循环比较找到种群中所有的个体，赋予其非支配等级为 1，并将这些个体存入非支配集合中。
  2. 对集合中的每一个个体，将其所支配的个体集合中的每个个体的都减去 1，若则将个体 j 存入集合中，并赋予其中的个体非支配等级 2。
  3. 之后对中的个体重复上述操作，直至所有个体都被赋予了非支配等级。

拥挤度计算

• 拥挤度计算是用于表现同一非支配等级个体之间的距离，在算法中使用是为了保证种群个体的多样性，避免陷入局部最优解。

  1. 令参数， n ∈ 1 … N 。

  2. for 每个目标函数：

     ​ ① 根据该目标函数对该等级的个体进行排序，记为个体目标函数值的最大值，为个体目标函数值的最小值；

     ​ ② 对于排序后两个边界的拥挤度和置为 ∞；

     ​ ③ 计算，其中是该个体排序后后一位的目标函数值。

     end

选择策略

• 模拟生物进化过程中的优胜劣汰，采用的二进制竞标赛选择策略，首先随机选择两个个体进行比较，胜的留下来。比较规则是：首先比较非支配等级，等级小的胜即留下来，其次如果非支配等级相同，比较拥挤度，拥挤度大的留下来，如果拥挤度也相同，随机留下一个。

交叉和变异

• 交叉和变异是模拟生物产生新子代个体的过程。交叉是两个父代按照一定公式利用父代个体每一个元素生成新的子代，而变异是个体是否自己发生一些变化，即产生变异。本次交叉采用的二进制交叉策略，变异采用多项式变异策略。

精英保留策略

• 是将父代种群和生成子代种群一起进行比较，比较策略与选择策略时相同，从而将最优的个体保留到子代种群中去，可以加快优化算法的迭代，避免陷入局部最优解。

• 首先将第 t 代产生的新种群与父代合并组成，种群大小为 2N。

  然后进行非支配排序，产生一系列非支配集并计算拥挤度。由于子代和父代个体都包含在中，则经过非支配排序以后的非支配集中包含的个体是中最好的，所以先将放入新的父代种群中。如果的大小小于 N ，则继续向中填充下一级非支配集，直到添加时，种群的大小超出 N ，对中的个体使用拥挤度比较算子，使个体数量达到 N 。然后通过遗传算子（选择、交叉、变异）产生新的子代种群。

  

多目标优化算法之NSGA-Ⅱ