#Attention Please
#网上看了很多关于NSGA2的讲解,但是总觉得少了点意思,为此经过多出选择裁剪给出了最通俗易懂的讲解,如果错误欢迎批评指正。
#以下部分内容来源于网上公开的讲解。
1、原理
了解NSGA2的前提是学会NSGA,而对于NSGA算法,我们需要了解非支配排序和遗传算法,进一步地就过渡到NSGA2;
NSGA2也就是用到了所谓的快速非支配排序算法,以及采用精英策略对新产生的父代和子代解进行选择;
这里精英策略作为一个主循环,在主循环里嵌套选择策略,对新生成的解进行快速非支配排序。
2、过程
随机初始化产生一组解--->非支配排序进行选择--->交叉--->变异--->将旧解【父代解】和新解【子代解】合并--->对合并后的解进行精英策略选择生成父代--->循环以上过程直到达到终止条件。
3、关键步骤
适应度:可以通俗理解就是你定义的所谓目标函数,当然几个目标【多目标】就可以算出几个适应度的数值。
如上式中的可以作为其中一个适应度函数。
更形象的,我们可以建立一个二维坐标系,这里的两个维度代表的是2个目标的适应度函数。
非支配排序:以上图为例,我们可以看到4个小人分别位于不同的层,并且在两个坐标轴都有对应的数值:Salary和Height,现在要做的就是:A、B、C、D这四个人的综合评价指标,谁的更好呢?我们到底是更多的考虑身高还是更多的考虑薪资水平呢?由此,我们引出非支配排序的概念。
拥挤距离:以下定义来源于原论文,《A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II》
中文版本的解释如下:
为了获得对种群中某一特定解附近的密度估计, 我们沿着对应目标计算这个解两侧的两点间的平均距离。 这个值是对用最近的邻居作为顶点形成的长方体的周长的估计称之为拥挤距离)。在图 1 中, 第i 个解在其前沿的拥挤距离(用实心圆标记)是长方体的平均边长(用虚线框表示。(用实心圆标记的点是同一非支配前沿的解)
非支配排序:
快速非支配排序:NSGA2
精英策略:
首先有一群具有多个目标的个体做为父代,在每个迭代中,在GA操作之后合并父代和子代。通过非支配排序,我们将所有个体分类到不同的帕累托最优前沿层次。然后按照不同层次的顺序从帕累托最优前沿选择个体作为下一个种群。对于多样性保护,还计算了“拥挤距离”。拥挤距离比较将算法各阶段的选择过程引向一致展开的帕累托最优前沿。
4、引用
[8]A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
5、附赠一张很精辟的图
如果你觉得不错,佛系随缘打赏,感谢,你的支持是我继续耕耘的动力。