搜索

NSGA3算法及其MATLAB版本实现

gecimao 发表于 2019-06-07 00:51 | 查看: | 回复:

  看懂NSGA3之前,了解的NSGA2的话更有帮助,这个博士写的带约束的NSGA2的matlab版本很不错(9个非约束的测试问题和5个带约束的测试问题),大家想了解NSGA3的最好先看看。

  再来介绍一下Deb大神的实验室公开发布的代码链接,里面有大神实验室的nsga2各种版本的代码(主要是c语言实现的)

  谢谢已经有大神们公布了他们所理解的nsga3的代码,至今为止(2018.1.2),我能找到的NSGA3算法的代码有两个版本(Deb团队尚未公布NSGA3标准版本的代码),有读者能找到其他版本的话,希望可以共享链接(谢谢):

  1- Yarpiz团队的matlab版本(归一化有一点问题,后面会讲到),有和一个同学讨论了一下,这个版本问题挺大的,建议大家直接看MOEA-dev,这个版本先归一化再非支配排序,其实应该先非支配排序然后再归一化的,感谢这个同学的指出,我贴出来是因为这个版本代码风格很好,MOEA可能不适合第一次接触遗传算法的 同学:

  好了,进入正题,我们直接开始介绍一下NSGA3(读到这里我希望大家对NSGA2已经很了解了,加油~),NSGA3与NSGA2的算法框架大致相同,只是在选择机制有所不同。NSGA2用拥挤距离对同一非支配等级的个体进行选择(拥挤距离越大越好),而NSGA3用的是基于参考点的方法对个体进行选择。NSGA3采用基于参考点的方法就是为了解决在面对三个及其以上目标的多目标优化问题时,如果继续采用拥挤距离的话,算法的收敛性和多样性不好的问题(就是得到的解在非支配层上分布不均匀,这样会导致算法陷入局部最优)。

  NSGA-III 首先定义一组参考点。然后随机生成含有 N 个(原文献说最好与参考点个数相同)个体的初始种群,其中 N 是种群大小。接下来,算法进行迭代直至终止条件满足。在第 t 代,算法在当前种群 Pt的基础上,通过随机选择,模拟两点交叉(Simulated Binary Crossover,SBX)和多项式变异 产生子代种群 Qt。Pt和 Qt的大小均为 N。因此,两个种群 Pt和 Qt合并会形成种群大小为 2N 的新的种群 Rt=Pt∪Qt。

  为了从种群 Rt中选择最好的 N 个解进入下一代,首先利用基于Pareto支配的非支配排序将 Rt分为若干不同的非支配层(F1,F2等等)。然后,算法构建一个新的种群St,构建方法是从 F1开始,逐次将各非支配层的解加入到 St,直至 St的大小等于 N,或首次大于 N。假设最后可以接受的非支配层是 L层,那么在 L+ 1 层以及之后的那些解就被丢弃掉了,且 St\ FL中的解已经确定被选择作为 Pt+1中的解。Pt+1中余下的个体需要从 FL中选取,选择的依据是要使种群在目标空间中具有理想的多样性。

  这一段我举个例子说明一下,比如你的N设置为100,那么Pt大小为100,Qt是Pt交叉和变异后的个体,Qt的数目也是100,那么Rt=Pt∪Qt,Rt数目是两百,现在只要从这两百中选100个个体进行下一轮迭代。

  那么怎么从这两百个选一百个呢?NSGA的思想首先是把所有解进行分非支配排序,这里目标值越小越好,甲三个目标值是(2,3,5),乙的三个目标是(4,3,5),丙的三个目标是(3,3,4),那么给甲和丙在F1层即等级为1,F2层是乙,等级为2,以此类推。假如一共有8层非支配层(F1,F2,。。。,F8),你选到F1+F2+F3+…+F7时候已经有90个个体了,而F8层有20个个体,那么怎么在F8选这10个个体,即怎么在F8里的20个选十个,NSGA2用的是基于拥挤距离的方法,而NSGA3用的是基于参考点的方法。( St\ FL里面,St就是这里的F1到F7的所有个体的总和,F8就是FL,St\ FL这个符号意思就是已经被选择的F1到F7所有个体)

  在原始NSGA-II中,FL中具有较大拥挤距离的解会优先被选择。然而,拥挤距离度量并不适合求解 MaOPs(三个及更多目标的多目标优化问题)。因此 NSGA-III 不再采用拥挤距离,而是采用了新的选择机制(这个机制就是NSGA3与2之间的最大区别之处),该机制会通过所提供的参考点,对 St中的个体进行更加系统地分析,以选择 FL中的部分解进入 Pt+1。

  步骤2:Compute ideal point(计算理想点):即求解这一代种群所有目标的最小值。比如甲三个目标值是(2,3,5),乙的三个目标是(4,3,5),丙的三个目标是(3,3,4),那么 ideal point为(2,3,4)。

  步骤3: Translate objectives(把所有个体的目标值减去 ideal point): 即甲三个目标值是(0,0,1),乙的三个目标是(2,0,1),丙的三个目标是(1,0,0)。

  它的意思就是使得这个这方程最小的向量就是我们要找的极值点,这点比较难理解,我慢慢解释,拿三个目标的例子来说明,我们先看下图,这所谓的极值点指的啥?

  我们把三个目标值范围不一样的问题称为非归一化类的问题,这个大家可以参考这篇博士论文:袁源. 基于分解的多目标进化算法及其应用[D]. 清华大学, 2015. 这个大神在里面提出另一个归一化的思路,有兴趣可以了解。

  归一化这个步骤本身很好理解。难理解的地方是怎么找到这个极值点。我们还是举三个目标的问题作为例子,我们初始化种群后,会得到很多个体,他们的目标值可能是(1,3,0.3),(2,6,0.3),(0.1,0.2,3)等等,如果有一些点如果在一个目标上的值很大,在另外两个目标上的值很小,这些点就更靠近这个坐标轴,这个就是所谓的 extreme points,目标就是找到在一个方向上值很大,另外两个目标值很小的点,三个目标的问题话对应我们可以找到三个这样的 extreme points。比如在ASF方程中,固定第一个坐标轴,(1,0.2,0.3)/(1,10e-6, 10e-6),这个时候最大的肯定是0.3这个方向,在固定第一个坐标轴时。我们在群体中找到另外两个目标中小的那个。比如(1,0.6,0.3)在ASF后变为0.6*10e6,(1,0.2,0.3)在ASF后变为0.3*10e6,(1,0.1,0.2)在ASF后变为0.2*10e6,这三个点那个作为extreme points最为合适,我想现在你肯定知道了,0.2*10e6是最小的,对应(1,0.1,0.2)是最合适的。这就是原文Thereafter, the extreme point in each objective axis is identified by finding the solution (x ∈ St) that makes the following

  6: Compute intercepts aj for j = 1, … , M,得到了极值点,就可以构建超平面计算截距了,怎么求?台湾师范大学教授那个C版本的NSGA3有详细说明,我直接复制了

  这步还要注意的是,万一这个超平面构建不起来咋办?袁源. 基于分解的多目标进化算法及其应用里有提示在4.2.4章节里,我截个图:

  Normalize objectives目标归一化部分很关键,基于参考点的选择部分一样重要,这部分也难理解最好的还是NSGA3原文献里algorithm4那个选择过程的伪代码最好理解,反而前面E.Niche-preservation operation 里写复杂了,还是老样子直接放伪代码,难理解的地方主要有两个。

  其实我在github上找到了NSGA3 matlab实现的一个非常好的版本,大家可以我的主页去下载,MOEAs,希望对大家有所帮助,这个博客排版什么的我太粗糙了,大家体谅,其实就是归一化和选择这个两个步骤最难理解,我写详细了,研究过NSGA3的基本都能自己实现了,欢迎评论交流,祝好运!!

  多目标优化算法(四)NSGA3(NSGAIII)论文复现以及matlab和python的代码前沿:最近太忙,这个系列已经很久没有更新了,本次就更新一个Deb大神的NSGA2的“升级版”算法NSGA3。...博文来自:晓风

  最近学习蚁群算法,单单学习算法还是不够深入了解,得实际编程实现了,理解才能更加透彻,本文根据这篇博文贴出来的代码进行扩充解释,主要就是做个记录,其中阴影部分是本人自己加注释,或许能给刚开始学蚁群算法和...博文来自:wayjj的博客

  NSGA3与NSGA2的算法框架大致相同,只是在选择机制有所不同。NSGA2用拥挤距离对同非支配等级的个体进行选择(拥挤距离越大越好),而NSGA3用的是基于参考点的方法对个体进行选择。NSGA3采用论坛

  NSGA(非支配排序遗传算法)、NSGAII(带精英策略的非支配排序的遗传算法),都是基于遗传算法的多目标优化算法,都是基于pareto最优解讨论的多目标优化,遗传算法已经做过笔记,下面介绍paret...博文来自:weixin_34217711的博客

  加密算法介绍一. 密码学简介据记载,公元前400年,古希腊人发明了置换密码。1881年世界上的第一个电话保密专利出现。在第二次世界大战期间,德国军方启用“恩尼格玛”密码机,密码学在战争中起着非常重要的...博文来自:leolewin的博客

  前言本篇博客出于学习交流目的,主要是用来记录自己学习多目标优化中遇到的问题和心路历程,方便之后回顾。过程中可能引用其他大牛的博客,文末会给出相应链接,侵删!REMARK:本人纯小白一枚,如有理解错误还...博文来自:Erpim的博客

  最近在做作业遇到一个Dejong’sfifthfunction的multimodal的问题,用传统的GA方法尝试了很多次,的确没办法搞定,随机很多次也不一定在globaloptimum的地方得到一次解...博文来自:silence1214的专栏

  以优化SVR算法的参数c和g为例,对DE(差分进化)算法MATLAB源码进行了详细中文注解。...博文来自:Genlovy Hoo的博客

  前言   粒子群算法实现起来并不是很难,算法思想可以参加我上一篇博文,不多说了。好了,Matlab版的粒子群走起。1定义变量   粒子群算法有很多参数,做实验的时候会纠结在参数问题上,这里就随机设定了...博文来自:谷震平的专栏

  首先NSGA-III算法沿用了NSGA-II的框架,要弄懂NSGA-III,先要简略地了解NSGA-II,两种算法都是多目标进化算法,大致可以分为两步:第一步是非支配分层,第二步是从最后一个非支配层级中挑选个体进入子代。

  多目标遗传发算法NSGA-III(基于参考点的非支配排序算法),在NSGA-II基础进行改进的,提高了算法的收敛性

  本博文是在之前两次多目标优化算法的学习成果上再次实验得到的结果,只是之前使用的编程语言为matlab和python,此次结果是用c语言编程得到的,图是用matlab画的,具体的算法解析请看我前面的两篇...博文来自:晓风

  为了能随时了解Matlab主要操作及思想。故本文贴上NSGA-Ⅱ算法Matlab实现(测试函数为ZDT1)。更多内容访问SGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而...博文来自:徐奕的专栏

  NSGA-II的选择算法。主要包含三个部分: 1.快速非支配排序 要先讲一下支配的概念,对于解X1和X2,如果X1对应的所有目标函数都不比X2大(最小问题),且存在一个目标值比X2小,则X2被X1支配...博文来自:allonok888的博客

  最近为了找一些如何搞referencepoint,老板让我去看下NSGAIII的paper。老板说上课的时候讲过的,搞得我很惭愧,我当时没好好听。并且看了老板的PPT和论文上说的差别有点大啊。才拿到这...博文来自:silence1214的专栏

  设置(Profile)一个设置是一个ASF的配置(configuration)的描述数据集合。一个设置必须至少包含一个流的配置设置。流信息设置中的流信息包含流的比特率(bitrate),缓冲窗口和媒体...博文来自:ITBUG的专栏

  测试可以跑,根据自己情况修改下函数即可. NSGA-III 首先定义一组参考点。然后随机生成含有 N 个(原文献说最好与参考点个数相同)个体的初始种群,其中 N 是种群大小。接下来,算法进行迭代直至终止条件满足。在第 t 代,算法在当前种...

  aravind seshadri文章的算法程序,已做修改验证,运行成功

  算法描述       EP是L.J.Fogel于20世纪60年代在人工智能研究中提出的一种有限状态机进化模型,在此模型中机器的状态基于分布的规律进行编译。       D.B.Fogel在90年代拓广...博文来自:coutamg的博客

  在many-objective的优化算法中,目前很多都是基于referencepoint的,而这些referencepoint大部分都是使用的Das的那个方法,也就是在一个单位截距的超平面内生成这些点...博文来自:silence1214的专栏

  继续上面的说,接下来按照NSGAIII的paper所说,就是Nchepreservation操作了,也就是当FlF_l中个体加入到当前pool中的话,个体过多的时候的选择了,可以说上面的子算法都是为这...博文来自:silence1214的专栏

  将父代和子代作为待选种群进行非支配排序时,会出现解丢失的问题。情况严重,会使待选种群的规模,小于原始尺寸。此种情况下,子代选择会报错。出现解丢失的原因为待选种群目标值里有NaN,此时根据自己目标函数将...博文来自:YoungHaus的博客

  前两篇博客演示了广播式的websocket 推送。 广播式有自己的应用场景,但是广播式不能解决我门一个常见的场景,即消息由谁发送、由谁接收的问题。本例中演示了一个简单的聊天室程序。例子中只有两个用户...博文来自:哎幽的成长

  4、图纸统计工具 软件介绍:该工具可以统计已打开AutoCAD图纸模型空间中符合预订要求的实体的数量,进而可用于统计各项目的数量。...博文来自:jellymiki的博客

  深度卷积网络   涉及问题: 1.每个图如何卷积:   (1)一个图如何变成几个?   (2)卷积核如何选择? 2.节点之间如何连接? 3.S2-C3如何进行分配? 4.16-...博文来自:江南研习社

  tensorflow在ubuntu系统上按照官方文档安装起来相对容易,在centos上由于没有apt-get( yum)相对困难一些,本文会提到一些安装过程中遇到的一些坑及解放方案。...博文来自:zhangweijiqn的专栏

  以下流程是根据博客;并根据自己的实际经验而成,亲测可用。 以下路径多是绝对路径,需要...博文来自:xll_bit的博客

  上一篇文章说了python如何解析excel文件博文来自:waylyn_wu的专栏

  mnist数据集介绍、读取、保存成图片 1、mnist数据集介绍: MNIST数据集是一个手写体数据集,简单说就是一堆这样东西  MNIST的官网地址是 MNIST; 通过阅读官网我们可以知...博文来自:YF_Li123的博客

  一、信道的定义与调制信道的数学模型 1.信道的定义与分类         信道(Channel)是指以传输媒质为基础的信号通道。根据新到的定义,如果信道仅是指信号的传输媒质,这种信道称为狭义信道;如果...博文来自:Seth的博客

  前段时间看了一些关于LSTM方面的论文,一直准备记录一下学习过程的,因为其他事儿,一直拖到了现在,记忆又快模糊了。现在赶紧补上,本文的组织安排是这样的:先介绍rnn的BPTT所存在的问题,然后介绍最初...博文来自:天道酬勤,做一个务实的理想主义者

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  command窗口是命令窗口,即为sqplus窗口,有命令提示符,识别sqlplus命令,基本的命令都可以执行 sql仅可执行DDL、select、DML等...博文来自:Ape55的博客

  题目点评 数据类型是所有程序都会涉及到的,是计算机语言比较基础知识,这种问题被问到的可能性其实并不大,这样的题目只要花点时间把它记下来就好了,难易程度一般。  两大类: 栈:原始数据类型(Und...博文来自:雄领IT的专栏

  4  软件设计   软件设计部分主要包括uboot移植、内核编译、系统移植、设备驱动编程、应用程序编程(QT编程、mysql数据库编程、控制系统编程)、各个模块的功能函数(部分是在windows下面的...博文来自:求是07的专栏

  上一篇文章讲解了SNMP的基本架构,本篇文章将重点分析SNMP报文,并对不同版本(SNMPv1、v2c、v3)进行区别! 四、SNMP协议数据单元 在SNMP管理中,管理站(NMS)和代理(Age...博文来自:假装在纽约

  一、概述最近在springboot项目引入thymeleaf模板时,使用非严格标签时,运行会报错。默认thymeleaf模板对html5标签是严格检查的。二、在项目中加NekoHTML库在Maven中...博文来自:Luck_ZZ的博客

本文链接:http://kingstonflowers.net/dingshiyueshu/468.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部