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

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

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

https://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:https://www.omegaxyz.com/2017/04/19/nsga2fastsort/

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

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

  1. 拥挤度计算有问题,应该是根据每个目标函数值进行排序完成之后,再将首尾的两个目标函数的拥挤度赋值为无穷大。

      • 大佬,您有没有研究过NSGA_II的收敛速度问题,我最近复现的NSGA_ii算法,我基本600generations才能大致收敛到真实PF,但是我看论文里都是250代,这让我很是困惑,反复检查了很久都没有找到问题所在。

        • 看一下变异率是否过高或过低,初始化的时候看看能不能初步筛选,不要随机初始化。具体应该有很多策略可以提高收敛速度。

  2. 请问交叉变异操作是在快速非支配排序法中体现的吗?还是没有进行这些操作

  3. 博主,您的产生种群Q的函数里b=pow(2*u,1.0/21);这个代码的1/21是什么意思啊?不太理解怎么选择变异的。

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

评论