知识卡片

普通读书笔记卡 · 3734.b

非支配排序兼顾多样性

理解等级:中级

在多目标最小化中,若解 A 各目标都不差于 B、且至少一项更好,就说 A 支配 B。NSGA-Ⅱ用三项机制比较候选:

  1. 快速非支配排序:不被任何解支配的解为第 1 层;暂时去掉它们,剩余解中不被支配的为第 2 层,依此分级,层号越小越优先。
  2. 拥挤距离:同一层内无法分优劣,就优先保留周围同层解较稀疏的个体,使解在 Pareto 前沿(互不支配的解在目标空间形成的边界)上分布较均匀。
  3. 精英保留:子代与父代共同竞争下一代名额,好解不会因繁殖而丢失。

示例(补充):两目标都要小,A=(1,4)、B=(2,2)、C=(4,1) 互不支配,同属第 1 层;D=(3,3) 被 B 支配,属第 2 层。

层级负责目标权衡,拥挤距离和精英保留分别应对解集扎堆与好解丢失。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 . 5 基 于 遗 传 算 法 的 社 区 检 测 · 查看原书依据

      相对于NSGA而言,NSGA-Ⅱ具有以下优点:①提出了新的基于分级的快速非支配解排序方法,降低了计算复杂度;②为了标定快速非支配排序后同级中不同元素的适应度值,同时使当前Pareto前沿面中的个体能扩展到整个Pareto前沿面,并尽可能均匀分布,该算法提出了拥挤距离的概念,采用拥挤距离比较算子代替NSGA中的适值度共享方法;③引入了精英保留机制,经选择后参加繁殖的个体所产生的后代同其父代个体共同竞争,产生下一代种群,因此有利于保持优良的个体,提高种群的整体进化水平。

    参考来源

    - 位置:《智能算法导论》第 1 章 1.5.1 节“多目标遗传算法”(`EPUB/xhtml/chapter1_0013.xhtml`)。 - 结论依据:原文列出 NSGA-Ⅱ 的快速非支配排序、拥挤距离与父子代竞争三项改进,并描述 NSGA 逐批确定非支配个体的分级思路。“支配”的判定写法与 A–D 四点分层为依据原书思路补充的教学示例,非书中数据。 - 原始内容:该算法提出了拥挤距离的概念,采用拥挤距离比较算子代替NSGA中的适值度共享方法;③引入了精英保留机制,经选择后参加繁殖的个体所产生的后代同其父代个体共同竞争