NSGA-III_nsga3参考点

NSGA-III 非支配排序遗传算法III（Matlab）

在使用进化优化方法开发多目标优化算法并展示其在大多数涉及两个和三个目标的各种实际问题上的优势后，现在越来越需要开发进化多目标优化( EMO )算法来处理高维多目标(有4个及以上目标)优化问题。在本文中，我们总结了最近的一些努力，并讨论了一些可行的方向，以开发用于解决高维目标优化问题的潜在EMO算法。然后，我们提出了一个基于参考点的多目标进化算法，该算法遵循NSGA - II框架(我们称之为NSGA-III)，它强调非支配的种群成员，但靠近一组提供的参考点。将提出的NSGA-III应用于多个3 ~ 15个目标的高维多目标测试问题，并与最近提出的EMO算法( MOEA/D )的两个版本进行比较。虽然这两种MOEA/D方法在不同类型的问题上都有很好的效果，但所提出的NSGA-III在本文所考虑的所有问题上都能产生令人满意的结果。本文给出了无约束问题的结果，后面的文章在处理高维目标优化问题时考虑了约束和其他特殊情况。

主要创新

1. 特殊支配原则的使用：针对很大部分种群是非支配的，可以通过使用特殊支配原则来缓解，该原则将自适应地离散Pareto最优前沿，并找到一个均匀分布的点集。 例如，利用 $ϵ$-支配原则会使得距离一组Pareto最优点距离内的所有点都是$ϵ$-支配的，因此，该过程会产生有限个Pareto最优点作为目标。这样的考虑也将缓解多样性保护的第二个困难。 这些研究都是在低维问题的背景下进行的，它们在解决高维目标优化方面的成功尚待建立。

2. 使用预定义的多目标搜索：越来越清楚的是，期望单个基于种群的优化算法在帕累托最优前沿附近收敛，同时在一个大维问题中均匀分布在整个前沿的期望太大了。处理这类高维多目标优化问题的一种方法是通过一些外部手段来辅助多样性维护问题。这一原则可以直接解决上述第二个难题。可以通过算法设定多个预定义的目标搜索，而不是搜索整个搜索空间以获得Pareto最优解。由于找到了与每个目标搜索任务相对应的最优点，处理一个大的非支配集的第一个困难也得到了缓解。 重组问题可以通过使用一个匹配限制方案来解决，其中来自相邻目标的两个解参与重组操作。我们提出的算法( NSGA -Ⅲ)就是基于这一原理提出的；因此，我们对这一方面进行了较为详细的讨论。我们提出了两种不同的方法来实现预定义的多目标搜索原则。
   a)可以事先指定一组跨越整个Pareto最优前沿的预定义搜索方向，并沿着每个方向进行多次搜索。由于搜索方向分布广泛，在大多数问题中，得到的最优点也很可能广泛分布在Pareto最优前沿上。

   b)代替多个搜索方向，可以为此指定多个预定义的参考点。此后，可以强调每个参考点对应的点，以找到一组分布广泛的Pareto最优点集。

NSGA-III算法

1. 算法整体框架
   

2. 参考点生成

   如前所述，NSGA - III使用一组预定义的参考点来保证获得解的多样性。所选择的参考点既可以以结构化的方式预定义，也可以由用户优先提供。我们将在后面的结果部分给出两种方法的结果。在没有任何偏好信息的情况下，参考点的任何预定义的结构化放置都可以被采用，但是，在本文中，我们使用Das和Dennis 的系统方法，将点放置在一个标准化的超平面- -一个( M-1)维的单位单纯形上，该单纯形同样倾向于所有的目标轴，并且在每个轴上的截距为1。如果沿每个目标考虑p个分割，则M-目标问题的参考点总数(H)为：

   $$H=\left(\genfrac{}{}{0ex}{}{M+p-1}{p}\right)$$
   

   图显示了对于一个p=4的三目标问题，在归一化参考平面上给出了15个结构化的参考点。

3. 关联操作

   在根据St在目标空间中的成员范围对每个目标进行自适应归一化后，我们需要将每个种群成员与一个参考点相关联。为此，我们通过将参考点与原点连接起来，定义超平面上每个参考点对应的参考线。然后，我们计算St的每个种群成员与每条参考线的垂直距离。在标准化后的目标空间中，参考线最接近某个种群成员的参考点被认为与该种群成员相关。如下图所示。
   
   该过程在算法3中给出。
   

4. 小生境保存操作（Niche-Preservation Operation）

   值得注意的是，一个参考点可能有一个或多个与其相关联的人口成员，也可能不需要任何人口成员。我们统计了$P_{t+1}=S_t/F_l$中与每个参考点相关的种群成员的数量。我们将第$j$个参考点的生态位数记为${\rho }_j$ 。我们现在设计一个新的小生境保持操作如下：
   首先，我们确定了具有最小${\rho }_j$ 的参考点集$J_{min}=j：argmi{n}_j{\rho }_j$ .在多个这样的参考点的情况下，随机选择一个($\bar{j}\in J_{\min }$) 。

   若${\rho }_j=0$ (意味着在参考点$\bar{j}$ 上没有关联的$P_{t+1}$成员)，则在集合$F_l$ 中存在$\bar{j}$ 的两种情形. 首先，$F_l$前面存在一个或多个与参考点$\bar{j}$ 相关的成员。在这种情况下，与参考线有最短垂直距离的那个加入$P_{t+1}$。然后对参考点$\bar{j}$ 的计数${\rho }_{\bar{j}}$增加一个。其次，前沿$F_l$没有与参考点$\bar{j}$相关联的成员。在这种情况下，参考点被排除在对当前生成的进一步考虑之外。

   若${\rho }_{\bar{j}}\ge 1$ (这意味着在$S_t/F_l$ 中已经存在一个与参考点相关的成员)，则在$P_{t+1}$中加入与参考点$\bar{j}$相关联的前$F_l$ 中任意2个被选中的成员(如果存在)。则计数${\rho }_{\bar{j}}$ 递增1。更新小生境计数后，重复该过程共K次，以填补$P_{t+1}$的所有空缺种群。

   [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YZh6UMy7-1691846747966)(attachments/5RRSNSSP.png)]
   

5. 一代Nsga- III的计算复杂度

   O ( $N^{2}M$)。

结论

在本文中，我们提出了一种基于参考点的方法来解决早期提出的用于解决高维目标优化问题的NSGA - II框架。所提出的NSGA -Ⅲ方法已应用于三目标到15目标的现有和新的测试问题以及三目标和九目标的实际问题。测试问题涉及具有凸、凹、不相交、不同尺度、有偏密度的前沿，以及涉及多个局部前沿的多峰性，优化算法可能会陷入其中。在所有这些问题中，所提出的NSGA - III方法已经能够成功地在多次运行中反复地找到一个融合良好和多样化的点集。性能缩放到15个目标主要是由于通过提供一组均匀分布的参考点来帮助多样性保护。在高维问题中，EMO算法面临着越来越困难的保持多样性的任务。通过提供一组参考点和NSGA-III有效的小生境方法来寻找与每个参考点相关的Pareto最优解，使得在多达15个目标中获得的解的多样性保持成为可能。

NSGA - III的性能已经与最近提出的MOEA/D程序的几个版本进行了比较。尽管不同的MOEA / D已经展示了它们在不同问题上的工作，但是没有一个单一的版本能够高效地解决所有的问题。本文提出的NSGA-III程序很好地解决了所有问题，其另一个优点在此值得一提。与MOEA/D版本不同，NSGA-III程序不需要设置任何额外的参数。

此外，NSGA-III已被测试其解决多种不同类型的高维多目标问题的能力。事实证明，NSGA - III能够使用少量用户提供的结构化或随机分配的参考点，从而使该方法适用于基于偏好的高维多目标优化决策方法。也有研究表明，与前面提出的另一种基于EMO的方法相比，NSGA - III程序可以用于快速估计高维目标优化问题中的最低点。在实际应用中，多目标和多目标优化问题的决策只需要少数折衷点即可。研究表明，NSGA - III可以在种群规模较小的情况下，只找到少数几个点( 5个目标20个, 10个目标65个)，从而减少计算量。

本文提出的基于参考点集的NSGA - III方法与基于超网格的归档技术具有类似的隐式原理，如自适应网格算法和MOEA。基于网格的方法随着目标的增加，需要考虑的网格数量成倍增加，而$ϵ$ -支配概念虽然在一定程度上减轻了寻找适当多样性解的负担，但在为大维问题寻找分布均匀的Pareto最优解方面仍然存在足够的困难。然而，比较NSGA - III 和基于$ϵ$ -支配的算法在高维多目标优化问题上的表现，仍是一个有趣的未来研究。在本文的高维多目标问题中，NSGA - III的性能远远优于经典的生成方法。然而，同时使用多个搜索方向的基于种群的聚合方法的更深入的研究值得追求。

参考文献

Deb, Kalyanmoy, 和Himanshu Jain. 《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 18, 期 4 (2014年8月): 577–601. https://doi.org/10.1109/TEVC.2013.2281535.

代码

clc;
clear;
close all;

%% Problem Definition

CostFunction = @(x) MOP2(x);  % Cost Function

nVar = 5;    % Number of Decision Variables

VarSize = [1 nVar]; % Size of Decision Variables Matrix

VarMin = -1;   % Lower Bound of Variables
VarMax = 1;   % Upper Bound of Variables

% Number of Objective Functions
nObj = numel(CostFunction(unifrnd(VarMin, VarMax, VarSize)));


%% NSGA-II Parameters

% Generating Reference Points
nDivision = 10;
Zr = GenerateReferencePoints(nObj, nDivision);

MaxIt = 50;  % Maximum Number of Iterations

nPop = 80;  % Population Size

pCrossover = 0.5;       % Crossover Percentage
nCrossover = 2*round(pCrossover*nPop/2); % Number of Parnets (Offsprings)

pMutation = 0.5;       % Mutation Percentage
nMutation = round(pMutation*nPop);  % Number of Mutants

mu = 0.02;     % Mutation Rate

sigma = 0.1*(VarMax-VarMin); % Mutation Step Size


%% Colect Parameters

params.nPop = nPop;
params.Zr = Zr;
params.nZr = size(Zr, 2);
params.zmin = [];
params.zmax = [];
params.smin = [];

%% Initialization

disp('Staring NSGA-III ...');

empty_individual.Position = [];
empty_individual.Cost = [];
empty_individual.Rank = [];
empty_individual.DominationSet = [];
empty_individual.DominatedCount = [];
empty_individual.NormalizedCost = [];
empty_individual.AssociatedRef = [];
empty_individual.DistanceToAssociatedRef = [];

pop = repmat(empty_individual, nPop, 1);
for i = 1:nPop
    pop(i).Position = unifrnd(VarMin, VarMax, VarSize);
    pop(i).Cost = CostFunction(pop(i).Position);
end

% Sort Population and Perform Selection
[pop, F, params] = SortAndSelectPopulation(pop, params);


%% NSGA-II Main Loop

for it = 1:MaxIt
 
    % Crossover
    popc = repmat(empty_individual, nCrossover/2, 2);
    for k = 1:nCrossover/2

        i1 = randi([1 nPop]);
        p1 = pop(i1);

        i2 = randi([1 nPop]);
        p2 = pop(i2);

        [popc(k, 1).Position, popc(k, 2).Position] = Crossover(p1.Position, p2.Position);

        popc(k, 1).Cost = CostFunction(popc(k, 1).Position);
        popc(k, 2).Cost = CostFunction(popc(k, 2).Position);

    end
    popc = popc(:);

    % Mutation
    popm = repmat(empty_individual, nMutation, 1);
    for k = 1:nMutation

        i = randi([1 nPop]);
        p = pop(i);

        popm(k).Position = Mutate(p.Position, mu, sigma);

        popm(k).Cost = CostFunction(popm(k).Position);

    end

    % Merge
    pop = [pop
           popc
           popm]; %#ok
    
    % Sort Population and Perform Selection
    [pop, F, params] = SortAndSelectPopulation(pop, params);
    
    % Store F1
    F1 = pop(F{1});

    % Show Iteration Information
    disp(['Iteration ' num2str(it) ': Number of F1 Members = ' num2str(numel(F1))]);

    % Plot F1 Costs
    figure(1);
    PlotCosts(F1);
    pause(0.01);
 
end

%% Results

disp(['Final Iteration: Number of F1 Members = ' num2str(numel(F1))]);
disp('Optimization Terminated.');
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

扫码关注公众号获取更多代码