大家好,又见面了,我是你们的朋友全栈君。
看懂NSGA3之前,了解的NSGA2的话更有帮助,这个博士写的带约束的NSGA2的matlab版本很不错(9个非约束的测试问题和5个带约束的测试问题),大家想了解NSGA3的最好先看看。 1. Constrained NSGA2:
https://cn.mathworks.com/matlabcentral/fileexchange/49806-matlab-code-for-constrained-nsga-ii-dr-s-baskar–s-tamilselvi-and-p-r-varshini
再来介绍一下Deb大神的实验室公开发布的代码链接,里面有大神实验室的nsga2各种版本的代码(主要是c语言实现的)
http://www.egr.msu.edu/~kdeb/codes.shtml
鉴于初学者都需要一个能跑限起来的程序,不受打击,又很烦某CS某DN上无耻的要shoufei下载,我发一个网址,大家自行去下吧,这个代码比较简单,当然也有逻辑上的瑕疵,但是对于初学者够用了(天天996,实在没空更新和回复,大家见谅,估计有很多用这个解决多目标柔性作业车间调度这种问题的,建议学完了去看我后面贴的清华博士(袁源)的博士论文吧,这个不会给源码的,首先自己觉得代码洗的很烂,懒得回去改了,发出来献丑,其次,开源不是这么开源的,真花功夫投入的理解源码的,其实我发的这些东西够用了):
https://yarpiz.com/
谢谢已经有大神们公布了他们所理解的nsga3的代码,至今为止(2018.1.2),我能找到的NSGA3算法的代码有两个版本(Deb团队尚未公布NSGA3标准版本的代码),有读者能找到其他版本的话,希望可以共享链接(谢谢): 1- Yarpiz团队的matlab版本(归一化有一点问题,后面会讲到),有和一个同学讨论了一下,这个版本问题挺大的,建议大家直接看MOEA-dev,这个版本先归一化再非支配排序,其实应该先非支配排序然后再归一化的,感谢这个同学的指出,我贴出来是因为这个版本代码风格很好,MOEA可能不适合第一次接触遗传算法的 同学: http://cn.mathworks.com/matlabcentral/fileexchange/60678-nsga-iii-in-matlab 2- 台湾师范大学教授写的一个C语言版本: http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
对了这是NSGA3两篇论文下载链接: 1.An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach,Part I: Solving Problems with Box Constraints. http://www.egr.msu.edu/~kdeb/papers/k2012009.pdf 2.An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach. http://www.egr.msu.edu/~kdeb/papers/k2012010.pdf
好了,进入正题,我们直接开始介绍一下NSGA3(读到这里我希望大家对NSGA2已经很了解了,加油~),NSGA3与NSGA2的算法框架大致相同,只是在选择机制有所不同。NSGA2用拥挤距离对同一非支配等级的个体进行选择(拥挤距离越大越好),而NSGA3用的是基于参考点的方法对个体进行选择。NSGA3采用基于参考点的方法就是为了解决在面对三个及其以上目标的多目标优化问题时,如果继续采用拥挤距离的话,算法的收敛性和多样性不好的问题(就是得到的解在非支配层上分布不均匀,这样会导致算法陷入局部最优)。
以下讲解需要注意的地方: 步骤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)。 步骤4: Compute extreme points(计算极值点): 这是最难理解的一步。
它的意思就是使得这个这方程最小的向量就是我们要找的极值点,这点比较难理解,我慢慢解释,拿三个目标的例子来说明,我们先看下图,这所谓的极值点指的啥?
其实就是图中的z1,max z2,max he z3,max三个点,它们各自和原点(即 ideal point)组成的三条线,这三条线就可以组成一个面,这个面和三个坐标轴的交点就是我们最终要求解的截距a1,a2和a3。找到截距后我们,用截距来按照下面的方程进行归一化:
我们把三个目标值范围不一样的问题称为非归一化类的问题,这个大家可以参考这篇博士论文:袁源. 基于分解的多目标进化算法及其应用[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.610e6,(1,0.2,0.3)在ASF后变为0.310e6,(1,0.1,0.2)在ASF后变为0.210e6,这三个点那个作为extreme points最为合适,我想现在你肯定知道了,0.210e6是最小的,对应(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 achievement scalarizing function minimum with weight vector w being the axis direction这句话的意思,也是NSGA3算法最难理解的一步。 6: Compute intercepts aj for j = 1, . . . , M,得到了极值点,就可以构建超平面计算截距了,怎么求?台湾师范大学教授那个C版本的NSGA3有详细说明,我直接复制了
// Given a NxN matrix A and a Nx1 vector b, generate a Nx1 vector x
// such that Ax = b.
//
// Use this to get a hyperplane for a given set of points.
// Example.
// Given three points (-1, 1, 2), (2, 0, -3), and (5, 1, -2).(这里就是我们的extreme point)
// The equation of the hyperplane is ax+by+cz=d, or a'x +b'y + c'z = 1.
// So we have
//
// (-1)a' + b' + 2c' = 1.
// 2a' - 3c' = 1.
// 5a' + b' -2c' = 1.
//
// Let A be { {-1, 1, 2}, {2, 0, -3}, {5, 1, -2} } and b be {1, 1, 1}.
// This function will generate x as {-0.4, 1.8, -0.6},
// which means the equation is (-0.4)x + 1.8y - 0.6z = 1, or 2x-9y+3z+5=0.
//
// The intercepts are {1/-0.4, 0, 0}, {0, 1/1.8, 0}, and {0, 0, 1/-0.6}.
这步还要注意的是,万一这个超平面构建不起来咋办?袁源. 基于分解的多目标进化算法及其应用里有提示在4.2.4章节里,我截个图:
7: Normalize objectives (fn) using Equation 5
第一点是:
其实和这个
其实完全等同,指的是一个意思。 所以
指的是
层中,即
层之前的所有非支配层中和参考点 j 关联的个体数。
第二点: 原文明确告诉你:
这个意思就是在
层中和参考点
关联的个体数,即小生镜数。
第三点: 理解上面之后就简单了许多:先看看
中有没和
关联的个体,没有的话换一个
如果
中有至少一个与
关联的个体,那么还要分两种情况
如果
,即
中没有与
关联的个体,那么选距离最短的那个到
中,否则,随机选取一个个体到
中。当然上诉两种情况都是在
层中选。直到
大小也等于原本种群的大小。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/144254.html原文链接:https://javaforall.cn