专栏首页图灵技术域NSGA-II多目标遗传算法概述

NSGA-II多目标遗传算法概述

什么是NSGA-II

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

算法目的:针对当前M个个体,选取N个个体(M>N)。 NSGA-II关键算法(步骤) 1.先对M个个体求pareto解。然后得到F1,F2……等这些pareto的集合。 2.把F1的所有个体全部放入N,若N没满,继续放F2,直到有Fk不能全部放入已经放入F1、F2、…、F(k-1)的N(空间)。此时对Fk进行求解。 3.对于Fk中的个体,求出Fk中的每个个体的拥挤距离Lk[i](crowding distance),在fk中按照Lk[i]递减排序,放入N中,直到N满。

NSGA-II关键子程序算法

1. 快速非支配排序算法 多目标优化问题的关键在于求取Pareto最优解集。NSGA-II快速非支配排序是依据个体的非劣解水平对种群M进行分层得到Fi,作用是使得解靠近pareto最优解。这是一个循环的适应值分级过程,首先找出群体中的非支配解集,记为F1,将其所有个体赋予非支配序irank=1(其中irank是个体i的非支配序值),并从整个群体M中除去,然后继续找出余下群体中的非支配解集,记为F2,F2中的个体被赋予irank=2,如此进行下去,知道整个种群被分层,Fi层中的非支配序值相同。

2.个体拥挤距离 在同一层Fk中需要进行选择性排序,按照个体拥挤距离(crowding distance)大小排序。个体拥挤距离是Fk上与i相邻的个体i+1和i-1之间的距离,其计算步骤为: ①对同层的个体距离初始化,令L[i]d=0(表示任意个体i的拥挤距离)。 ②对同层的个体按照第m个目标函数值升序排列。 ③对于处在排序边缘上的个体要给予其选择优势。 ④对于排序中间的个体,求拥挤距离:

(其中:L[i+1]m为第i+1个体的第m目标函数值fmax,fmin分别为集合中第m目标函数的最大和最小值。) ⑤对于不同的目标函数,重复②到④的步骤,得到个体i的拥挤距离L[i]d,有限选择拥挤距离较大的个体,可以是计算结果在目标空间均匀地分布,维持群体的多样性。

3.精英策略选择算法 保持父代中优良个体直接进入子代,防止Pareto最优解丢失。 选择指标对父代Ci和子代Di合成的种群Ri进行优选,组成新父代Ci+1. 先淘汰父代中方案检验标志不可行的方案,接着按照非支配序值irank从低到高将整层种群依次放入Ci+1,直到放入某一层Fk超过N的限制,最后,依据拥挤距离大小填充Ci+1直到种群数量为N。

注释: 多目标规划中,由于存在目标之间的冲突和无法比较的现象,一个解在某个目标上是最好的,在其他的目标上可能比较差。Pareto 在1986 年提出多目标的解不受支配解(Non-dominated set)的概念。其定义为:假设任何二解S1 及S2 对所有目标而言,S1均优于S2,则我们称S1 支配S2,若S1 的解没有被其他解所支配,则S1 称为非支配解(不受支配解),也称Pareto解。这些非支配解的集合即所谓的Pareto Front。所有坐落在Pareto front 中的所有解皆不受Pareto Front 之外的解(以及Pareto Front 曲线以内的其它解)所支配,因此这些非支配解较其他解而言拥有最少的目标冲突,可提供决策者一个较佳的选择空间。在某个非支配解的基础上改进任何目标函数的同时,必然会削弱至少一个其他目标函数。

原创文章非商业转载请注明出处,商业转载请联系。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NSGA-Ⅱ算法Matlab实现(测试函数为ZDT1)

    NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其改进主要是针对如上所述的三个方面: ①提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方...

    里克贝斯
  • 遗传算法系列之五:多目标遗传算法和遗传编程

    在遗传算法深入研究的阶段,人们提出将各种将遗传算法应用到更广泛领域,从而产生了一些有趣的后续工作。这些后续工作中,多目标遗传算法和遗传编程由于它们重要...

    AlgorithmDog
  • Jmetal 4+ 使用指南三使用Jmetal进行试验

    演化计算与人工智能
  • NSGA-II入门

    在遗传算法在解决多目标优化遇到瓶颈时,许多学者花费了不少时间和精力在多目标优化的遗传算法上,Goldberg首先将Pareto最优解的概念与适应度值概念相关联,...

    演化计算与人工智能
  • 基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模

    今天跟大家分享一篇之前发表的文章,《基于稀疏化鲁棒LS-SVR与多目标优化的铁水硅含量软测量建模 》。 摘要: 针对高炉炼铁过程的关键工艺指标——铁水硅含量[...

    昱良
  • Jmetal 4+ 使用指南一以NSGA-II为例

    演化计算与人工智能
  • Jmetal 4+ 使用指南四使用Jmetal进行试验-NSGAIIStudy(一)

    演化计算与人工智能
  • 论文研读-多目标自适应memetic算法

    演化计算与人工智能
  • matlab多目标优化算法之NSGA-Ⅱ【含源代码】

    当优化问题的目标函数为两个或两个以上时,该优化问题就是多目标优化。不同于单目标优化问题,多目标问题没有单独的解能够同时优化所有目标,也就是目标函数之间存在着冲...

    matlab爱好者
  • Jmetal 4+ 使用指南二

    并且生成四个文件,分别是目标函数值,决策变量值,log日志文件 这种方式指定的问题是写在main方法中的problem = new ZDT3("ArrayRea...

    演化计算与人工智能
  • NSGA-Ⅱ算法C++实现(测试函数为ZDT1)

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

    里克贝斯
  • 多目标进化算法应用于提高医药数据领域学习器的性能(CS AI)

    原文标题完整翻译:多目标进化算法应用于提高在医药数据领域使用整体特征选择和离散化模型的学习器的性能

    Donuts_choco
  • Math-Model(一)算法综述

    美赛马上来了,总结一下这些年参赛的算法(我打编程位),数学建模主要模型不单独写,参考数学模型第四版教材即可,只给出编程中一些重要的算法目录,如果有方法漏写,请评...

    Pulsar-V
  • 多目标P系统进化算法中文期刊研读第一期

    杨世品,陆小华,薄翠梅,等. 多目标P系统仿生优化算法[J]. 北京工业大学学报,2016,42(10):35-41. DOI:10.11936/bjutxb2...

    演化计算与人工智能
  • 基于多目标优化模型的不完全数据集机器学习(CS LG)

    机器学习技术已经发展到从完整的数据中学习。当数据集中存在缺失值时,应通过删除具有缺失值或插补的数据点来分别对不完整的数据进行预处理。在本文中,我们提出了一种在线...

    毛艺漩8078803
  • Jmetal 4+ 使用指南七-并行算法

    演化计算与人工智能
  • Jmetal 4+ 使用指南五 使用Jmetal进行试验-Running the experiments

    这是因为相对地址在我目前的环境下win10+R下读不出来,因此此处换成绝对地址。在java环境中这种写法是正确的的,但是在R语言的环境中,这是有错误的 有两个地...

    演化计算与人工智能
  • 动态多目标优化研究综述

    转载自http://cjc.ict.ac.cn/online/onlinepaper/lrc-20207694828.pdf

    演化计算与人工智能
  • Jmetal 4+ 使用指南六 Experimentation example: StandardStudy

    演化计算与人工智能

扫码关注云+社区

领取腾讯云代金券