《NSGA算法大量测试函数实验结果展示》由会员分享，可在线阅读，更多相关《NSGA算法大量测试函数实验结果展示（37页珍藏版）》请在金锄头文库上搜索。
1、NSGA-NSGA-算法大量测试算法大量测试函数实验结果展示函数实验结果展示Pareto最优解最优解图片来源：基于双极偏好的多目标粒子群算法及应用研究图片来源：基于双极偏好的多目标粒子群算法及应用研究1、pareto最优解又称非支配解、非占优解，pareto最优解集又称非劣解、非支配解集、非占优解集2、左图为最小化的两目标优化问题的最终pareto前沿分布示意图，则f1和f2目标值均为越小越优，实线和虚线组成部分为可行域，实线表示pareto前沿面，也就是所有pareto最优解对应的目标矢量组成的曲面，一个多目标优化问题对应一个pareto前沿面。3、A、B、C三点位于pareto前沿面上，该
2、三点的解为pareto最优解，他们三者之间不存在支配或是占优关系。D、E、F三点的解为可行解，非pareto最优解。4、A点的解支配F点的解，或是相比F点的解，A点的解是pareto占优。同样B和C点与D、E、F点之间存在支配关系或是占优关系多目标进化优化领域的一些主要算法多目标进化优化领域的一些主要算法 Coello Coello总结方式总结方式第一代多目标进化优化算法：（1）MOGA（多目标优化遗传算法）（2）NSGA（非支配排序多目标优化遗传算法）（3）NPGA（小生境pareto多目标优化遗传算法）主要特点：基于非支配排序选择、小生境（共享函数）多样性保持主要特点：基于非支配排序选择、
3、小生境（共享函数）多样性保持 主要问题：如何将进化算法与多目标优化问题有机地结合主要问题：如何将进化算法与多目标优化问题有机地结合第二代多目标进化优化算法：（1）SPEA（Pareto强度多目标进化算法）和SPEA2、（2）PAES（精英保留进化策略）、PESA和PESA-、（3）NSGA-（是迄今为止最优秀的多目标进化优化算法之一） 主要特点：精英保留机制、以及基于聚类、拥挤距离、空间超格等方主要特点：精英保留机制、以及基于聚类、拥挤距离、空间超格等方法多样性保持法多样性保持 主要问题：算法的效率问题，如何处理高维多目标优化问题主要问题：算法的效率问题，如何处理高维多目标优化问题参考文献：进
4、化多目标优化算法研究参考文献：进化多目标优化算法研究多目标进化优化算法一般流程多目标进化优化算法一般流程随机产生初始种群P P用EA进化算法得到G 构造PG的非支配解集NDset调整非支配解集NDset规模并使之满足分布性要求是否满足终止条件P=NDset输出结果，结束是否如何构造非支配集如何构造非支配集1、采用何种策略来调整非支采用何种策略来调整非支配集的配集的规模规模2、如何保持非支配集的多样、如何保持非支配集的多样性和分布性性和分布性终止条件：终止条件：多人为设定，迭代次数限定或是迭代多次，最优值没有变化。迭代多次的原因，无法判断迭代次数较少时，出现的最优解是否为真正的最优解。NSGA-
5、算法算法NSGANSGA主要问题：主要问题：1、构造pareto最优解集计算复杂度太高，为O( ),m为目标个数，N为种群大小2、需预先设定共享参数3、没有采取外部种群策略（即精英保留机制）NSGA-NSGA-改进情况：改进情况：1、快速非支配解排序2、基于拥挤距离保持解集多样性3、引入精英保留机制保持优良个体改进改进NSGA-算法算法快速非支配解排序非支配解排序：非支配解排序：首先是每个个体跟种群里面的其它个个体进行支配关系比较，是否支配其它全部个体，复杂度为O（mN）；循环进行直到等级1中非支配个体全部搜索到，复杂度为O（ ）；最坏的情况下，有N个等级，每个等级只存在一个解，复杂度为O(
6、)快速非支配解排序：快速非支配解排序：左图为排序思路，前半段红框是个体之间支配关系的比较，引入Sp存放和np记录，循环得到等级1；后半段红框循环得到等级2、等级3.复杂度为O（ ）NSGA-算法算法基于拥挤距离保持解集多样性一个个体的拥挤一个个体的拥挤距离：距离：是通过计算与其相邻的两个个体在每个子目标函数上的距离差之和来求取。图中图中所示为两个子目标情况下：个体i的拥挤距离即图中虚线四边形的长与宽之和拥挤比较运算符（Crowed-Comparison Operator)：IF 两个个体属于不同等级的非支配解集，优先考虑等级序号较小的OR 若两个个体属于同一等级的非支配解集，优先考虑拥挤距离较
7、大的NSGA- procedure：1、随机产生一个初始父代Po，在此基础上采用二元锦标赛选择、交叉和变异操作产生子代Qo， Po 和Qo群体规模均为N2、将Pt和Qt并入到Rt中（初始时t=0），对Rt进行快速非支配解排序，构造其所有不同等级的非支配解集F1、F2.3、按照需要计算Fi中所有个体的拥挤距离，并根据拥挤比较运算符构造Pt+1，直至Pt+1规模为N，图中的Fi为F3NSGA-算法算法应用篇MATLAB -nsga_2.m 无约束问题无约束问题 (unconstrained)Copyright (c) 2009, Aravind SeshadriC -nsga2.c 无约束无约束&
8、约束问题约束问题 (unconstrained&constrained)Copyright (c) 2003, Kalyanmoy Debnsga_2.m（主函数）（主函数）initialize_variables.m（初始化种群）（初始化种群）non_domination_sort_mod.m（初始种群排序）（初始种群排序）tournament_selection.m（锦标赛选择）（锦标赛选择） genetic_operator.m（遗传操作）（遗传操作）non_domination_sort_mod.m（非支配解集排序）（非支配解集排序）replace_chromosome.m（替代种群）
9、（替代种群）开始进化过程开始进化过程如上图所示，蓝色曲线是经典测试函数如上图所示，蓝色曲线是经典测试函数ZDT1用用NSGA-算法得到的算法得到的pareto前前沿面，主要参数沿面，主要参数pop=500，gen=500，n=30，var-domain=0,1,fun=2；红色；红色曲线是经典测试函数曲线是经典测试函数ZDT1的理想的理想pareto前沿面，前沿面，pop=500个个理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/如上图所示，蓝色曲线是经典测试函数如上图所示，蓝色曲线是经典测试函数ZDT2用用NSGA-算
10、法得到的算法得到的pareto前沿面，主要参数前沿面，主要参数pop=500，gen=500，n=30，var-domain=0,1，fun=2；红色曲线是经典测试函数；红色曲线是经典测试函数ZDT2的理想的理想pareto前沿面，前沿面，pop=500个个理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/如上图所示，蓝色曲线是经典测试函数如上图所示，蓝色曲线是经典测试函数ZDT3用用NSGA-算法得到的算法得到的pareto前沿面，主要参数前沿面，主要参数pop=500，gen=500，n=30，var-domain=0
11、,1，fun=2；红色曲线是经典测试函数；红色曲线是经典测试函数ZDT3的理想的理想pareto前沿面，前沿面，pop=136个个理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/如上图所示，蓝色曲线是经典测试函数如上图所示，蓝色曲线是经典测试函数ZDT4用用NSGA-算法得到的算法得到的pareto前沿面，前沿面，主要参数主要参数pop=200，n=10，fun=2；红色曲线是经典测试函数；红色曲线是经典测试函数ZDT4的理想的理想pareto前沿面，前沿面，pop=200个。个。变量个数超过变量个数超过3个的时候，个的
12、时候，f2对应的值比上图显示的值更大。对应的值比上图显示的值更大。ZDT4区别于区别于ZDT1-3的是变量范围不同，的是变量范围不同，ZDT1-3的变量范围都为的变量范围都为xi=0,1，而而ZDT4的变量范围为的变量范围为x1=0,1,xi=-5,5，所以需要修改代码，修改，所以需要修改代码，修改m文件为文件为initialize_variables.m和和genetic_operator.m，将区间范围改为，将区间范围改为-5,5，从，从第二个变量开始循环，第一个变量复制循环代码中的语句，另外设置区间范第二个变量开始循环，第一个变量复制循环代码中的语句，另外设置区间范围大小。围大小。n=3
13、,gen=500n=3,gen=200理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/参考文献：参考文献：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-ZDT4问题有问题有 个不同的局部个不同的局部pareto最优前沿，其中只有一个对应全局最优前沿，其中只有一个对应全局pareto最优前沿。最优前沿。该文献作者一开始也有对该文献作者一开始也有对NSGA-算法下各个测试函数收敛度的讨论算法下各个测试函数收敛度的讨论收敛性度量值计算过程收敛性度量值计算过
14、程首先从理想首先从理想paretopareto最优前沿最优前沿取取H=500H=500的解集合。然后计的解集合。然后计算由某个算法得到的每一个算由某个算法得到的每一个解与解与H H集合中解的最小欧几集合中解的最小欧几里德距离。这些距离的平均里德距离。这些距离的平均值用来表示收敛性度量，文值用来表示收敛性度量，文献给出献给出MeanMean和和VarianceVariance两个两个距离评价指标。距离评价指标。收敛性度量值越小，越好收收敛性度量值越小，越好收敛于理想敛于理想paretopareto最优前沿。最优前沿。如果某个算法得到的解几乎如果某个算法得到的解几乎全部位于全部位于H H集合中，那
15、么收集合中，那么收敛度量值为敛度量值为0 0参考文献：参考文献：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-按照上述收敛性度量判断规则可以看出，按照上述收敛性度量判断规则可以看出，ZDT4在在NSGA-（二进制编码）算法下（二进制编码）算法下收敛性不是很好，很难收敛到理想的收敛性不是很好，很难收敛到理想的pareto最优前沿。最优前沿。问题：问题：NSGA-（实数编码）仿真效果（实数编码）仿真效果V=10 gen=500 pop=500V=10 gen=250 pop=100参考文献：参考文献：A Fast and El
16、itist Multiobjective Genetic Algorithm : NSGA- =0.0027 =0.000017733 如上图所示，蓝色曲线是经典测试函数如上图所示，蓝色曲线是经典测试函数ZDT6用用NSGA-算法得到的算法得到的pareto前沿面，主要参数前沿面，主要参数pop=500，gen=500，n=10，var-domain=0,1，fun=2；红色曲线是经典测试函数；红色曲线是经典测试函数ZDT6的理想的理想pareto前沿面，前沿面，pop=2992个个理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoo
17、book/pop=2500 pop=4106参考文献：进化多目标优化算法研究参考文献：进化多目标优化算法研究如上图所示，蓝色如上图所示，蓝色+是经典测试函数是经典测试函数DTLZ1和和DTLZ3用用NSGA-算法得到算法得到的的pareto前沿面，主要参数前沿面，主要参数pop=500，gen=500，n=12，var-domain=0,1，fun=3；红色部分是经典测试函数；红色部分是经典测试函数DTLZ1和和DTLZ3的的pareto前沿。可以看出这两个测试函数用前沿。可以看出这两个测试函数用NSGA-算法没办法收敛到理想算法没办法收敛到理想pareto前沿面。前沿面。NSGA-（实数编码
18、）（实数编码）gen=500 ， pop=500 ，n=12，var-domain=0,1，fun=3；Convergence metric?gen=500 pop=100 刚好为50000次评价次数内收敛指标：收敛指标：公茂果 等 使用的是最小归一化欧式距离的平均值Mean1 Deb 等使用的是最小欧式距离的平均值Mean2评价准则：评价准则：指标值越低，表明算法得到的解收敛性越好，越接近 理想pareto前沿面备注：备注：收敛性指标是用来比较各种EA算法得到解的收敛性情况如上图所示，蓝色如上图所示，蓝色+/.是经典测试函数是经典测试函数DTLZ2用用NSGA-算法得到的算法得到的paret
19、o前沿前沿面，红色曲面是经典测试函数面，红色曲面是经典测试函数DTLZ2的理想的理想pareto前沿面，前沿面，pop=40000个个理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/gen=1000,pop=500 gen=500,pop=500n=12，var-domain=0,1，fun=3gen=200 gen=500 如上图所示，蓝色如上图所示，蓝色+是经典测试函数是经典测试函数DTLZ4用用NSGA-算法得到的算法得到的pareto前沿前沿面，主要参数面，主要参数pop=500，n=12，var-domain=
20、0,1，fun=3；红色曲面是经典；红色曲面是经典测试函数测试函数DTLZ4的理想的理想pareto前沿面，前沿面，pop=4106个个备注：备注：DTLZ4当迭代参数调整为当迭代参数调整为500代时，仿真效果不是很好，代时，仿真效果不是很好，pareto前沿分前沿分布不够均匀。布不够均匀。理想理想pareto前沿面数据来源：前沿面数据来源：http:/www.cs.cinvestav.mx/emoobook/NSGA-（实数编码）（实数编码）gen=500 pop=500n=12，var-domain=0,1，fun=3nsga2code源代码由源代码由17个头文件和个头文件和1个源文件组成
21、个源文件组成random.h /*Random Number Generator*/input.h /*File Takes Input from user*/realinit.h /*Random Initialization of the populaiton*/init.h /*Random Initialization of the population*/ decode.h /*File decoding the binary dtrings*/ranking.h /*File Creating the Pareto Fronts*/rancon.h /*File Creating
22、the Pareto Fronts when Constraints are specified*/func-con.h /*File Having the Function*/select.h /*File for Tournament Selection*/roullette.h /*the roulette wheel selection*/crossover.h /*Binary Cross-over*/uniformxr.h /*Uniform Cross-over*/realcross2.h /*Real Cross-over*/mut.h /*Binary Mutation*/r
23、ealmut1.h /*Real Mutation*/keepaliven.h /*File For Elitism and Sharing Scheme*/report.h /*Printing the report*/代码来源：代码来源：http:/www.iitk.ac.in/kangal/codes.shtml参考文献：参考文献：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-nsga2-v1.1源代码由源代码由2个头文件和个头文件和19个源文件组成个源文件组成函数修改文件：problemdef.c参数修改文件：ns
24、ga2r.c修正版修正版1.1实际操作更加简便实际操作更加简便参考文献：参考文献：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-约束测试函数如下表约束测试函数如下表nobj=2 ncon=2 nreal=2gen=500 popsize=100左图来源：左图来源：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-gen=500 popsize=100左图来源：左图来源：A Fast and Elitist Multiobjective Genetic Al
25、gorithm : NSGA-gen=500 popsize=100左图来源：左图来源：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-参考文献：参考文献：A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-nobj=5 ncon=7 nreal=3NormalizedNSGA-2对于高维多目标优化问题求解效果对于高维多目标优化问题求解效果一般指目标个数大于一般指目标个数大于5的多目标优化问题的多目标优化问题参考文献：参考文献：A Fast and Eliti
26、st Multiobjective Genetic Algorithm : NSGA-参考文献：进化多目标优化算法研究参考文献：进化多目标优化算法研究 DTLZ DTLZ问题能够扩展到任意多个目标，从而能够很好地扩展问题能够扩展到任意多个目标，从而能够很好地扩展为高维多目标优化问题，是目前采用得最多的测试问题之一。为高维多目标优化问题，是目前采用得最多的测试问题之一。 这里主要选择这里主要选择DTLZ1DTLZ1和和DTLZ2DTLZ2进行讨论进行讨论NSGA-2NSGA-2对高维多目标对高维多目标问题求解效果。将维数扩展到问题求解效果。将维数扩展到4 4维和维和5 5维进行比较和讨论。维进行
27、比较和讨论。NSGA-2对于高维多目标优化问题求解效果对于高维多目标优化问题求解效果参考书本：郑金华多目标进化算法及其应用参考书本：郑金华多目标进化算法及其应用P190-191DTLZ1DTLZ1测试问题取得测试问题取得ParetoPareto最优边界时，对应着属于最优边界时，对应着属于XmXm的所有的所有xixi的值都为的值都为0.50.5，目标函数的值处于满足，目标函数的值处于满足 的线性超平面。该问题难以收敛到的线性超平面。该问题难以收敛到ParetoPareto最优边界。最优边界。DTLZ2DTLZ2测试问题的测试问题的ParetoPareto最优边界对应着最优边界对应着XmXm中所有的中所有的xixi都取都取0.50.5，且目标函，且目标函数值满足数值满足 ，该问题能用来测试一个，该问题能用来测试一个MOEAMOEA在增加目标个数时的运算在增加目标个数时的运算能力。能力。Xm表示决策变量后的变量集合，个数表示决策变量后的变量集合，个数k=n-M+1gen=500,pop=5003 3维情况下的收敛度：维情况下的收敛度：3 3维情况下的收敛度：维情况下的收敛度：4、5维函数维函数gx循环开始数未更改循环开始数未更改结束结束
