-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathNDSort.m
166 lines (162 loc) · 6.4 KB
/
NDSort.m
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
function [FrontNo,MaxFNo] = NDSort(varargin)
%NDSort - Do non-dominated sorting by efficient non-dominated sort.
%
% FrontNo = NDSort(F,s) does non-dominated sorting on F, where F is the
% matrix of objective values of a set of individuals, and s is the number
% of individuals to be sorted at least. FrontNo(i) denotes the front
% number of the i-th individual. The individuals have not been sorted are
% assigned a front number of inf.
%
% FrontNo = NDSort(F,C,s) does non-dominated sorting based on constrained
% domination, where C is the matrix of constraint values of the
% individuals. In this case, feasible solutions always dominate
% infeasible solutions, and one infeasible solution dominates another
% infeasible solution if the former has a smaller overall constraint
% violation than the latter.
%
% In particular, s = 1 indicates finding only the first non-dominated
% front, s = size(F,1)/2 indicates sorting only half the population
% (which is often used in the algorithm), and s = inf indicates sorting
% the whole population.
%
% [FrontNo,K] = NDSort(...) also returns the maximum front number besides
% inf.
%
% Example:
% [FrontNo,MaxFNo] = NDSort(PopObj,1)
% [FrontNo,MaxFNo] = NDSort(PopObj,PopCon,inf)
%------------------------------- Reference --------------------------------
% [1] X. Zhang, Y. Tian, R. Cheng, and Y. Jin, An efficient approach to
% nondominated sorting for evolutionary multiobjective optimization, IEEE
% Transactions on Evolutionary Computation, 2015, 19(2): 201-213.
% [2] X. Zhang, Y. Tian, R. Cheng, and Y. Jin, A decision variable
% clustering based evolutionary algorithm for large-scale many-objective
% optimization, IEEE Transactions on Evolutionary Computation, 2018, 22(1):
% 97-112.
%------------------------------- Copyright --------------------------------
% Copyright (c) 2018-2019 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 [educational forum], IEEE
% Computational Intelligence Magazine, 2017, 12(4): 73-87".
%--------------------------------------------------------------------------
PopObj = varargin{1};
[N,M] = size(PopObj);
if nargin == 2
nSort = varargin{2};
else
PopCon = varargin{2};
nSort = varargin{3};
Infeasible = any(PopCon>0,2);
PopObj(Infeasible,:) = repmat(max(PopObj,[],1),sum(Infeasible),1) + repmat(sum(max(0,PopCon(Infeasible,:)),2),1,M);
end
if M < 3 || N < 500
% Use efficient non-dominated sort with sequential search (ENS-SS)
[FrontNo,MaxFNo] = ENS_SS(PopObj,nSort);
else
% Use tree-based efficient non-dominated sort (T-ENS)
[FrontNo,MaxFNo] = T_ENS(PopObj,nSort);
end
end
function [FrontNo,MaxFNo] = ENS_SS(PopObj,nSort)
[PopObj,~,Loc] = unique(PopObj,'rows');
Table = hist(Loc,1:max(Loc));
[N,M] = size(PopObj);
FrontNo = inf(1,N);
MaxFNo = 0;
while sum(Table(FrontNo<inf)) < min(nSort,length(Loc))
MaxFNo = MaxFNo + 1;
for i = 1 : N
if FrontNo(i) == inf
Dominated = false;
for j = i-1 : -1 : 1
if FrontNo(j) == MaxFNo
m = 2;
while m <= M && PopObj(i,m) >= PopObj(j,m)
m = m + 1;
end
Dominated = m > M;
if Dominated || M == 2
break;
end
end
end
if ~Dominated
FrontNo(i) = MaxFNo;
end
end
end
end
FrontNo = FrontNo(:,Loc);
end
function [FrontNo,MaxFNo] = T_ENS(PopObj,nSort)
[PopObj,~,Loc] = unique(PopObj,'rows');
Table = hist(Loc,1:max(Loc));
[N,M] = size(PopObj);
FrontNo = inf(1,N);
MaxFNo = 0;
Forest = zeros(1,N);
Children = zeros(N,M-1);
LeftChild = zeros(1,N) + M;
Father = zeros(1,N);
Brother = zeros(1,N) + M;
[~,ORank] = sort(PopObj(:,2:M),2,'descend');
ORank = ORank + 1;
while sum(Table(FrontNo<inf)) < min(nSort,length(Loc))
MaxFNo = MaxFNo + 1;
root = find(FrontNo==inf,1);
Forest(MaxFNo) = root;
FrontNo(root) = MaxFNo;
for p = 1 : N
if FrontNo(p) == inf
Pruning = zeros(1,N);
q = Forest(MaxFNo);
while true
m = 1;
while m < M && PopObj(p,ORank(q,m)) >= PopObj(q,ORank(q,m))
m = m + 1;
end
if m == M
break;
else
Pruning(q) = m;
if LeftChild(q) <= Pruning(q)
q = Children(q,LeftChild(q));
else
while Father(q) && Brother(q) > Pruning(Father(q))
q = Father(q);
end
if Father(q)
q = Children(Father(q),Brother(q));
else
break;
end
end
end
end
if m < M
FrontNo(p) = MaxFNo;
q = Forest(MaxFNo);
while Children(q,Pruning(q))
q = Children(q,Pruning(q));
end
Children(q,Pruning(q)) = p;
Father(p) = q;
if LeftChild(q) > Pruning(q)
Brother(p) = LeftChild(q);
LeftChild(q) = Pruning(q);
else
bro = Children(q,LeftChild(q));
while Brother(bro) < Pruning(q)
bro = Children(q,Brother(bro));
end
Brother(p) = Brother(bro);
Brother(bro) = Pruning(q);
end
end
end
end
end
FrontNo = FrontNo(:,Loc);
end