帕累托前沿（Pareto Front）

  • 由所有的非支配解构成的解集在目标空间的映射称为Pareto前沿（PF）。
  • 当多目标问题中多个目标存在冲突的时候，我们可以用“支配”的概念来决定解的好坏。
    • 非支配解：假设任何二解S1 及S2 对所有目标而言，S1均优于S2，则我们称S1 支配S2，若S1 的解没有被其他解所支配，则S1 称为非支配解（不受支配解），也称Pareto解（帕雷托解）。
    • 支配解：若解S2的所有目标均劣于S1，则称S1优于S2，也称S1支配S2，S2为受支配解。
    • Pareto前沿面：找到所有Pareto解之后，这些解组成的平面叫做Pareto前沿面（Non-dominated front）。在目标函数较多时，前沿面通常为超曲面。。

举个例子：

image-20220910195634707

若Height和Salary均为Maximize问题，则本例中A、B、C均支配D；A、B可支配C、D；A与B为非支配关系(两者各有一个指标大于对方，一个指标小于对方)。在多目标优化问题中，如果能找到一组不互相支配也不受其他解支配的解集，即称之为”帕累托最优”解。该解集映射到目标空间中即构成Pareto Front。本例中，解A和解B均在帕累托前沿上。

NSGA-Ⅱ

image-20220910200601638

每一行的末尾都显示了np和Sp。np的意思是“有多少人支配你?”Sp的意思是“你在控制谁?”因为A和B不受任何解的支配，也不互相支配，所以它们的np = 0, Sp包含C和d。C受A和B的支配，它的np = 1。C也支配D，所以Sp包含D。