多方针优化 | NSGA-Ⅲ（上篇，附MATLAB代码）

ruozhis

今天为各位讲解多方针优化算法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代码如下：

1. function [W,N] = UniformPoint(N,M)
2. %UniformPoint - Generate a set of uniformly distributed points on the unit
3. %hyperplane
4. %
5. %   [W,N] = UniformPoint(N,M) returns approximate N uniformly distributed
6. %   points with M objectives.
7. %
8. %   Example:
9. %       [W,N] = UniformPoint(275,10)
11. %--------------------------------------------------------------------------
12. % Copyright (c) 2016-2017 BIMK Group. You are free to use the PlatEMO for
13. % research purposes. All publications which use this platform or any code
14. % in the platform should acknowledge the use of ”PlatEMO” and reference ”Ye
15. % Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin, PlatEMO: A MATLAB Platform
16. % for Evolutionary Multi-Objective Optimization [Educational Forum], IEEE
17. % Computational Intelligence Magazine, 2017, 12(4): 73-87”.
18. %--------------------------------------------------------------------------
20.     H1 = 1;
21.     while nchoosek(H1+M,M-1) <= N
22.         H1 = H1 + 1;
23.     end
24.     W = nchoosek(1:H1+M-1,M-1) - repmat(0:M-2,nchoosek(H1+M-1,M-1),1) - 1;
25.     W = ([W,zeros(size(W,1),1)+H1]-[zeros(size(W,1),1),W])/H1;
26.     if H1 < M
27.         H2 = 0;
28.         while nchoosek(H1+M-1,M-1)+nchoosek(H2+M,M-1) <= N
29.             H2 = H2 + 1;
30.         end
31.         if H2 > 0
32.             W2 = nchoosek(1:H2+M-1,M-1) - repmat(0:M-2,nchoosek(H2+M-1,M-1),1) - 1;
33.             W2 = ([W2,zeros(size(W2,1),1)+H2]-[zeros(size(W2,1),1),W2])/H2;
34.             W  = [W;W2/2+1/(2*M)];
35.         end
36.     end
37.     W = max(W,1e-6);
38.     N = size(W,1);
39. end

复制代码

NSGA-Ⅲ代码获取方式

https://yarpiz.com/456/ypea126-nsga3
参考文献

• Katoch S, Chauhan S S, Kumar V. A review on genetic algorithm: past, present, and future[J]. 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[J]. 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[J]. 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 [educational forum][J]. 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[J]. 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