多方针优化 | NSGA-Ⅲ（上篇，附MATLAB代码）
今天为各位讲解多方针优化算法NSGA-Ⅲ，实际上我们分袂在NSGA-II多方针优化算法讲解（附MATLAB代码）、多方针优化 | 基于NSGA-II的多方针0-1背包问题求解（附matlab代码）、多方针优化 | NSGA-II进阶教程（全网首个三方针优化教程）这几篇推文中对NSGA-Ⅱ做了详细讲解。那今天讲解的NSGA-Ⅲ实际上和NSGA-Ⅱ只是在选择机制上有区别，其他法式完全不异。因此，需要各位先回顾一下NSGA-Ⅱ的基本法式。
在这里，还有一个基本问题需要各位注意一下，NSGA-Ⅱ是multi-objective优化，即多方针优化，而NSGA-Ⅲ的many-objective优化，即超多方针优化。此中，multi-objective（多方针）指的是2或3个优化方针，many-objective（超多方针）指的是至少4个优化方针。
因此，NSGA-Ⅲ的优势是求解超多方针优化问题，即4个及以上的多方针优化问题。
※注：由于NSGA-Ⅲ内容较多，所以将这部门内容讲解分成三篇推文讲解。
目录
[*]NSGA-Ⅱ求解法式回顾
[*]NSGA-Ⅲ算法设计思路
[*]NSGA-Ⅲ代码获取方式
[*]参考文献
NSGA-Ⅱ求解法式回顾
遗传算法GA伪代码
无论是NSGA-Ⅱ，还是NSGA-Ⅲ，它们的基础都是遗传算法GA。GA的伪代码如下：
GA的基本思路为，种群初始化→进入主循环→选择操作→交叉操作→变异操作→种群更新操作→输出全局最优解。
NSGA-Ⅱ整体伪代码
在了解了GA的基本思路后，再来看一下NSGA-Ⅱ的基本思路：
NSGA-Ⅱ与GA的一大差异在于个体的选择机制。
GA是通过轮盘赌选择或锦标赛选择等选择方式，从父代种群（种群数目为N）中选择若干个个体组成子代种群，一般来说**子代种群数目N_1小于父代种群数目N**。
而NSGA-Ⅱ先将父代种群P_{t}（种群数目为N）与子代种群Q_{t}（种群数目为N）合并R_{t}=P_{t}\cup Q_{t}（种群数目为2N），其次对合并后的种群（种群数目为2N）进行快速非支配排序\mathcal{F}=\text { fast-non-dominated-sort }\left(R_{t}\right)，然后按照非支配排序成果以及拥挤度距离计算成果\text { crowding-distance-assignment }\left(\mathcal{F}_{i}\right)，从合并种群（种群数目为2N）中选择出N个个体。
NSGA-Ⅱ快速非支配排序伪代码
此中，快速非支配排序\mathcal{F}=\text { fast-non-dominated-sort }\left(R_{t}\right)的伪代码如下：
NSGA-Ⅱ拥挤度距离计算伪代码
拥挤度距离计算\text { crowding-distance-assignment }\left(\mathcal{F}_{i}\right)伪代码如下：
NSGA-Ⅱ示意图
NSGA-Ⅱ核心法式示意图如下图所示：
NSGA-Ⅲ算法设计思路
在回顾完NSGA-Ⅱ之后，我们开始今天的主题——NSGA-Ⅲ。实际上，在文章的开篇我们已经提到过，NSGA-Ⅲ与NSGA-Ⅱ的独一分歧在于选择机制。再严格一点，可以说是摒弃拥挤度距离排序机制，而采用一种基于参考点排序的新机制。
NSGA-Ⅲ整体伪代码
我们先给出NSGA-Ⅲ伪代码：
细心的同学已经发现，NSGA-Ⅲ的伪代码实际上和NSGA-Ⅱ的伪代码基本一致，下面我们将这两个伪代码进行对比：
左侧NSGA-Ⅲ标红的处所和右侧NSGA-Ⅱ标红的处所就是两者的差异，即两者的选择机制分歧。其它法式则完全不异。
从选择机制的伪代码行数可以看出，NSGA-Ⅲ的选择机制更为复杂，接下来则重点分解一下NSGA-Ⅲ的选择机制。
首先需要明确一个问题，如果在进行快速非支配排序后，前l层个体数目之和恰好为N，那就不需要后面基于参考点排序的操作了。
因此，后续基于参考点排序是成立在一个前提之上，即前l-1层个体数目之和小于N，前l层个体数目之和大于N。也就是说需要在第l层个体F_{l}中选择出K=N-\left|P_{t+1}\right|个个体。
参考点生成方式
既然，NSGA-Ⅲ采用一种基于参考点的排序机制，那么就有3个很直接的问题：
[*]这些参考点究竟是什么？
[*]采用这种基于参考点的排序机制优势在哪里？
[*]如何生成这些参考点？
首先回答第一个问题——这些参考点究竟是什么。
以一个三方针问题为例，这些参考点实际上等间距均匀分布在一个等边三角形平面上，此中这个等边三角形的三个顶点坐标分袂为(1,0,0),(0,1,0),(0,0,1)，则这些参考点的示意图如下图所示，此中下图中的15个小黑点就是参考点：
接下来回答第二个问题——采用这种基于参考点的排序机制优势在哪里。 我们都但愿多方针优化最终获得的帕列托解能够尽可能均匀分布，而不是这里一堆解，那里一堆解。
因为，均匀分布的帕列托解可以为用户提供多个平衡的解决方案，这些解都保留各自的优势。而分块密集的帕列托解很明显不利于用户做决策，很明显只有这几块的解是能够支撑用户决策的，而缺少其它位置的平衡解，显示不是我们多方针优化的初衷。
因此，为了使最终获得的帕列托解能够均匀分布，NSGA-Ⅲ采用基于参考点排序的方式，在解与参考点之间成立联系，因为构造的参考点是均匀分布的，所以我们但愿最终生成的帕列托解也可以保持均匀分布的这一特性。
最后回到第三个问题——如何生成这些参考点。
我们先回到第一个问题的那张图，各位要注意一点，这些参考点是等间距分布的。
示意图中的参考点是4等分分布的，这些参考点的几何生成方式如下：
[*]先将3个顶点（即(1,0,0)，(0,1,0)，(0,0,1)）进行连线，形成等边三角形。
[*]在每条边长进行4等分操作，即每条边各有5个等分点，这些等分点为部门参考点。
[*]将与各边平行的各对等分点连线，连线发生的交点为另一部门参考点。
[*]上述交点全集即为生成的参考点。
上述参考点生成方式是以3方针为例，4方针及以上的参考点生成方式可以此类推。3方针4等分所生成的参考点示意图如下图所示。
各位可以发现，如果方针数目为M，等分数目为p，则生成的参考点数目H=C_{M+p-1}^{p}。
还是以上述3方针4等分为例，参考点的代数生成方式如下图所示：
4方针5等分的代数生成方式如下图所示：
参考点生成MATLAB代码如下：
function = UniformPoint(N,M)
%UniformPoint - Generate a set of uniformly distributed points on the unit
%hyperplane
%
% = UniformPoint(N,M) returns approximate N uniformly distributed
% points with M objectives.
%
% Example:
% = UniformPoint(275,10)
%--------------------------------------------------------------------------
% Copyright (c) 2016-2017 BIMK Group. You are free to use the PlatEMO for
% research purposes. All publications which use this platform or any code
% in the platform should acknowledge the use of ”PlatEMO” and reference ”Ye
% Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin, PlatEMO: A MATLAB Platform
% for Evolutionary Multi-Objective Optimization , IEEE
% Computational Intelligence Magazine, 2017, 12(4): 73-87”.
%--------------------------------------------------------------------------
H1 = 1;
while nchoosek(H1+M,M-1) <= N
H1 = H1 + 1;
end
W = nchoosek(1:H1+M-1,M-1) - repmat(0:M-2,nchoosek(H1+M-1,M-1),1) - 1;
W = (-)/H1;
if H1 < M
H2 = 0;
while nchoosek(H1+M-1,M-1)+nchoosek(H2+M,M-1) <= N
H2 = H2 + 1;
end
if H2 > 0
W2 = nchoosek(1:H2+M-1,M-1) - repmat(0:M-2,nchoosek(H2+M-1,M-1),1) - 1;
W2 = (-)/H2;
W= ;
end
end
W = max(W,1e-6);
N = size(W,1);
endNSGA-Ⅲ代码获取方式
https://yarpiz.com/456/ypea126-nsga3
参考文献
[*]Katoch S, Chauhan S S, Kumar V. A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 2021, 80: 8091-8126.
[*]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 2002, 6(2): 182-197.
[*]Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE transactions on evolutionary computation, 2013, 18(4): 577-601.
[*]Tian Y, Cheng R, Zhang X, et al. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization . IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
[*]Mostapha Kalami Heris, NSGA-III: Non-dominated Sorting Genetic Algorithm, the Third Version — MATLAB Implementation (URL: https://yarpiz.com/456/ypea126-nsga3), Yarpiz, 2016.
[*]Das I, Dennis J E. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM journal on optimization, 1998, 8(3): 631-657.
<hr/>想快速入门智能优化算法的小伙伴可以阅读我们的册本，本书对算法的讲解详细易懂，对代码的注释也十分完备。
3.6-3.12日京东当当购书5折优惠，想要入手此书的小伙伴可可以抓紧入手哦！
京东自营采办链接：
https://item.jd.com/13422442.html
当当自营采办链接
http://product.dangdang.com/29301483.html
<hr/>咱们下期再见
近期你可能错过了的好文章
新书上架 | 《MATLAB智能优化算法：从写代码到算法思想》
优化算法 | 灰狼优化算法（文末有福利）
优化算法 | 鲸鱼优化算法
遗传算法（GA）求解带时间窗的车辆路径（VRPTW）问题MATLAB代码
粒子群优化算法（PSO）求解带时间窗的车辆路径问题（VRPTW）MATLAB代码
知乎 | bilibili | CSDN：随心390
页:
[1]