NSGA-Ⅱ算法C++实现(测试函数为ZDT1)

本文共1420个字,预计阅读时间需要4分钟。

在看C++实现之前,请先看一下NSGA-II算法概述

http://www.omegaxyz.com/2017/04/14/nsga-iiintro/

NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其改进主要是针对如上所述的三个方面:
①提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方面它将父代种群跟子代种群进行合并,使得下一代的种群从双倍的空间中进行选取,从而保留了最为优秀的所有个体;
②引进精英策略,保证某些优良的种群个体在进化过程中不会被丢弃,从而提高了优化结果的精度;
③采用拥挤度和拥挤度比较算子,不但克服了NSGA中需要人为指定共享参数的缺陷,而且将其作为种群中个体间的比较标准,使得准Pareto域中的个体能均匀地扩展到整个Pareto域,保证了种群的多样性。

头文件:

个体的类声明:

群体的类声明:

全局变量及部分函数声明:

关于排序函数qsort

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )
利用qsort对F[i]数组按照cmp3排序

群的初始化:

个体初始化:

利用二进制锦标赛产生子代:

1、随机产生一个初始父代Po,在此基础上采用二元锦标赛选择、交叉和变异操作产生子代Qo, Po 和Qo群体规模均为N
2、将Pt和Qt并入到Rt中(初始时t=0),对Rt进行快速非支配解排序,构造其所有不同等级的非支配解集F1、F2……..
3、按照需要计算Fi中所有个体的拥挤距离,并根据拥挤比较运算符构造Pt+1,直至Pt+1规模为N,图中的Fi为F3

ZDT1问题函数值的计算:

判断目标函数值是否被支配:

快速非支配排序法:重点!!!

计算拥挤距离:重点!!!具体解释见其他文章!!!

采集多样性的选择:

主要操作函数:

主函数:

ZDT1问题图像及前沿面。

测试结果:

 

快速支配排序具体解释见多目标算法NSGA-II:http://www.omegaxyz.com/2017/04/19/nsga2fastsort/

多目标问题解释:http://www.omegaxyz.com/2017/04/16/theexpofpareto/

读者评分
[评分人数: 6 平均分: 3.8]

10 位极客在 “NSGA-Ⅱ算法C++实现(测试函数为ZDT1)” 留下足迹

  1. 为什么结果波动比较大呢,感觉每次得到的结果差别有些大,然后一开始的make_new_pop函数对初始种群选择Q的时候choice函数里的选择方法没有用,因为一开始没有拥挤距离和rank 有影响吗?

评论

OmegaXYZ