简介: 此文章是学习进化算法NSGA-II时的学习笔记

NSGA-II 算法学习总结

一. NSGA-II 算法流程


图一

算法流程如图一所示，这里不做赘述.

二. 快速非支配排序

直接用例子来说明:

  1. 对每个个体记录
    (1) $ {N_p} $ (支配个体p的个体数量)
    (2) $ {S_p} $ (被个体p支配的个体数量)
  • 如图二所示，

图二
  1. 找到 \( {N_p}=0 \) 的个体，作为第一非支配等级的个体，即 Rank=1. 如图三所示:

图三

  1. 对于第一非支配等级中的每一个个体p：\(N_p=N_p-1\)
    找到\( N_p=0 \)的个体作为第二非支配等级的个体，即Rank=2,如图四所示:


    图四

  2. 对于第二支配集, 对\(S_p \)中的每一个个体： \( N_p=N_p-1 \)
    找到\( N_p=0 \)的个体作为第三非支配等级的个体，即Rank=3


图五

如此循环下去，直到\( S_p \)为空或者所有的个体都已经遍历。

二. 计算拥挤距离

  • 拥挤距离: 对于每个非支配等级上的个体，计算与该个体相邻的两个个体组成的矩形的长和宽之和.
  • 边界个体的拥挤距离分配为无穷大. 例如，1，2，3，7，5的拥挤距离是无穷大。这样做的原因是为了保证变价在进化过程中保留下来。

图六

如图六所示,拥挤距离如下：
长公式
式中\( f_1^{\max }\)和\(f_1^{\min }\)代表了\(f_1\)方向上的最大值和最小值

三. 拥挤度比较算子与二元锦标赛选择

  • 在NSGA-II 算法中，使用基于拥挤度比较算子的二元锦标赛选择来选择父代个体。
  • 随机选择两个个体
  • 拥有更低排序值的个体获胜。例如图六，个体1和个体4比较，个体1获胜
  • 如果两个个体拥有相同的排序值，则拥有更大拥挤距离的个体获胜。例如，如图六，个体4和个体6比较，个体4获胜
  • 若两个个体拥有相同的排序值和相同的拥挤距离，则随机选择一个获胜

四. 模拟二进制交叉（SBX）

模拟二进制交叉是一种实数编码遗传算法的交叉算子，用于生成二进制交叉的子代。假设两个父代个体分别为\( x{p1} \)和\( x{p2}\) ,则子代个体\( x{01} \)和\( x{o2} \)的产生如下:

  • 首先满足式子:
    $ {x^L} < {x{p1}} < {x{p2}}< {x^U} $

对于\( x{o1}\)的产生如下:


式中，u: [0,1]之间的随机数, \( \eta _c \):交叉分布指数、对于\(x{o2}\)的产生如下:


五. 多项式变异

  1. 多项式变异用于在父代个体 \(x_p\) 附近变异产生一个子代个体 \( x_o \)




${x_o} = {x_p} + {\delta _q} \cdot ({x^U} - {x^L})$

六. 精英保留策略

  • 将父代个体和子代种群合并(保留种群中的精英)
  • 在组合种群中进行非支配排序
  • 计算在相同非支配等级的个体的拥挤度距离
  • 基于非支配等级，以升序方式对个体进行排序
  • 对同一非支配等级，按照拥挤距离进行以降序方式排序
  • 选择排序后的前N个个体，N为种群规模

最后更新： 2020年03月04日 22:58

原始链接： /2019/12/20/2019-12-20-NSGA-II_算法学习/

赏
× 请我吃糖~
打赏二维码