NSGA-II多目标优化算法讲解（附MATLAB代码）

小编今天为大家讲解NSGA-II多目标优化算法，提到多目标优化，大家可能第一个就想到NSGA-II算法，今天小编就带领大家解开NSGA-II的神秘面纱。

NSGA-II全称是快速非支配排序遗传算法，这个算法的精髓体现在“快速非支配排序”这7个字上，那么究竟什么是“快速非支配排序”，NSGA-II是如何实现“快速非支配排序”的呢？各位先别急，且听小编慢慢道来，在基于粒子群算法的多目标搜索算法讲解（附MATLAB代码）中，已经讲到，多目标优化问题没有一个所谓的最优解，而是存在一个最优解集。

为了让大家更深入了解NSGA-II算法，小编查阅网上各种大神讲解的资料，终于在知乎上发现一位大神讲解地特别到位，这位大神在知乎上回答的链接如下：

https://www.zhihu.com/question/26990498/answer/35644566

小编觉得这位大神在讲解NSGA-II时，真的讲得太nice了,因此小编决定做一次大自然的搬运工，把这位大神的回答搬运过来。小编建议各位边看代码边体会下面的步骤，效果会更好。

NSGA-II在常规遗传算法上的改进，关键步骤就3步。
1）快速非支配排序算子的设计
多目标优化问题的设计关键在于求取Pareto最优解集。NSGA-II算法中的快速非支配排序是根据个体的非劣解水平对种群分层，其作用是指引搜索向Pareto最优解集方向进行。它是一个循环的适应值分级过程：首先找出群体中非支配解集，记为第一非支配层F，将其所有个体赋予非支配序值irank=1(其中irank是个体i的非支配排序值)，并从整个种群中除去；然后继续找出余下群体中非支配解集，记为第二非支配排序层F2，个体被赋予非支配序值irank=2；照此进行下去，直到整个种群被分层，同一分层内的个体具有相同的非支配序值irank。
2）个体拥挤距离算子设计
为了能够在具有相同irank的个体内进行选择性排序，NSGA-II提出了个体拥挤距离的概念。个体i的拥挤距离是目标空间上与i相邻的2个个体i+1和i-1之间的距离，其计算步骤为：
a)对同层的个体初始化距离。令L[i]d=0（其中L[i]d表示任意个体i的拥挤距离）；
b)对同层的个体按第m个目标函数值升序排列；
c)使得排序边缘上的个体具有选择优势。给定一个大数M，令L[1]d=L[end]d=M；
d)对排序中间的个体，求拥挤距离：
（其中：L[i+1]m为第i+1个个体的第m目标函数值，和分别为集合中第m目标函数值的最大值和最小值）
e)对不同的目标函数，重复步骤a)~步骤d)操作，得到个体i的拥挤距离L[i]d，通过优先选择拥挤距离较大的个体，可使计算结果在目标空间比较均匀分布，以维持种群的多样性。
3）精英策略选择算子
精英策略即保留父代中的优良个体直接进入子代，以防止获得的Pareto最优解丢失。精英策略选择算子按3个指标对由父代Ci和子代Di合成的种群Ri进行优选，以组成新的父代种群Ci+1。首先淘汰父代中方案校验标志为不可行的方案；其次按照非支配序值irank从低到高排序，将整层种群依次放入Ci+1，直到放入某一层Fj时出现Ci+1大小超过种群规模限制N的情况；最后，依据Fj中的个体拥挤距离由大到小的顺序继续填充Ci+1直到种群数量达到N时终止。

下面这个图片能很好的说明NSGA-II的实现过程

最后附上用NSGA-II求解ZDT1函数的MATLAB代码，ZDT1函数如下：

更多相关文章

随机推荐