NSGA算法

大家好，欢迎来到IT知识分享网。

先给自己叠甲，记录自己的学习过程，如有内容错误欢迎指正!!!。

1. NSGA算法简介（Nondominated Sorting Genetic Algorithm）

根据标题，NSGA算法分为两个要点，Nondominated Sorting（非支配排序）和Genetic Algorithm（遗传算法）遗传算法讲解文章。

因此本文主要介绍非支配排序和算法本身的内容，对遗传算法仅作简要提及。

1.1 基本概念

要明白非支配的含义，自然要知道支配（dominated）的含义。

从字面意思上看来看，A “能力” 大于

B，A就能够支配B。
在多目标优化问题中，涉及到多个目标。
如果一个解在所有目标上都不比另一个解差，并且在至少一个目标上更好，那么这个解被称为支配另一个解。
具体来说，假设有两个解$A$和$B$，如果对于所有的目标函数$F(X)$都有$F(A)\le F(B)$，并且至少存在一个目标函数$f_i$使得$f_i(A)<f_i(B)$，那么我们就说解A支配解B。

俗话来讲，就是“我哪哪都与你一样，但有一项能力比你强，我就能支配你。（当然，方方面面比你强，当然也能支配你）”
下面用一个草图简单表述这个意思。

$该问题是minF(X),即最小化优化问题。目标函数F内有两个子函数f_1和f_2。$
对于A和B而言，$F(A)\le F(B),且f_1(A)<f_1(B);f_2(A)<f_2(B)$
满足$当解A在所有目标上都不比解B差，并且在至少一个目标上优于解B。$
所以说，解A 支配 解B。

对于A和C而言，$F(A)\le F(C),且f_1(A)<f_1(C);f_2(A)=f_2(C)$
满足$当解A在所有目标上都不比解C差，并且在至少一个目标上优于解C。$
所以说，解A 支配 解C。

注意！！！

解A 支配 解B时，解A称之为支配解（Dominating Solution），那解B呢? 非支配解？

千万注意！！！解B 不是 非支配解，解B称之为被支配解（Dominated Solution）。

那何为非支配解（Non-dominating Solution）？？？
非支配解是指在解集合中没有任何其他解可以支配它的解。
解集合中有A、B和C三个解。B和C都不能支配A。
此时解A成为非支配解。

注意！！！
帕累托解和非支配解的定义是基于解之间的比较，因此它们都是相对于问题中的解集合而言的。帕累托前沿是针对目标空间的。

总结来说，非支配解和帕累托解在多目标优化中是等价的概念，它们都描述了在多个目标之间达到最佳权衡的解。在实际应用中，寻找帕累托最优解通常意味着寻找非支配解，因为这些解代表了在多个相互冲突的目标之间无法进一步改进的解决方案。

1.2 非支配排序

NSGA与传统的遗传算法的主要区别在于：该算法在选择“基因”执行之前根据解之间的支配关系进行了分层。其选择“基因”、交叉“基因”和变异“基因”与传统的遗传算法没有区别。