![](https://csdnimg.cn/release/download_crawler_static/9428292/bg5.jpg)
DEB AND JAIN: EMO ALGORITHM USING REFERENCE-POINT-BASED NONDOMINATED SORTING APPROACH, PART I 581
NSGA-II, this is achieved through a computationally efficient,
yet approximate, niche-preservation operator that computes
the crowding distance for every last level member as the
summation of objective-wise normalized distance between two
neighboring solutions. Thereafter, the solutions that have larger
crowding distance values are chosen. In NSGA-III, we replace
the crowding distance operator with the following approaches
(Sections IV-A–IV-E).
A. Classification of Population Into Nondominated Levels
The above procedure of identifying nondominated fronts
using the usual domination principle [17] is also used in
NSGA-III. All population members from the nondominated
front level 1 to level l are first included in S
t
.If|S
t
| = N;
no further operations are needed and the next generation is
started with P
t+1
= S
t
.For|S
t
| >N, members from one to
(l − 1) fronts are already selected, i.e., P
t+1
= ∪
l−1
i=1
F
i
, and the
remaining (K = N −|P
t+1
|) population members are chosen
from the last front F
l
. We describe the remaining selection
process in the following subsections.
B. Determination of Reference Points on a Hyper-Plane
As indicated before, NSGA-III uses a predefined set of
reference points to ensure diversity in obtained solutions.
The chosen reference points can either be predefined in a
structured manner or supplied preferentially by the user. We
will present results of both methods in the results section later.
In the absence of any preference information, any predefined
structured placement of reference points can be adopted,
but, in this paper, we use Das and Dennis’s [48] systematic
approach
1
that places points on a normalized hyper-plane—an
(M − 1)-dimensional unit simplex—which is equally inclined
to all objective axes and has an intercept of one on each axis.
If p divisions are considered along each objective, the total
number of reference points (H )inanM-objective problem is
given by
H =
M + p − 1
p
. (3)
For example, in a three-objective problem (M = 3), the
reference points are created on a triangle with the apex at
(1, 0, 0), (0, 1, 0), and (0, 0, 1). If four divisions (p = 4 ) are
chosen for each objective axis H =
3+4−1
4
or 15 reference
points will be created. For clarity, these reference points are
shown in Fig. 1. In the proposed NSGA-III, in addition to
emphasizing nondominated solutions, we also emphasize pop-
ulation members that are in some sense associated with each
of these reference points. Since the above-created reference
points are widely distributed on the entire normalized hyper-
plane, the obtained solutions are also likely to be widely
distributed on or near the Pareto-optimal front. In the case of a
user-supplied set of preferred reference points, ideally the user
can mark H points on the normalized hyper-plane or indicate
any H, M-dimensional vectors for the purpose. The proposed
algorithm is likely to find near Pareto-optimal solutions cor-
responding to the supplied reference points, thereby allowing
1
Any other structured distribution with or without a biasing on some part
of the Pareto-optimal front can be used as well.
Fig. 1. Fifteen structured reference points are shown on a normalized
reference plane for a three-objective problem with p =4.
Algorithm 1 Generation t of NSGA-III procedure
Input: H structured reference points Z
s
or supplied aspiration
points Z
a
, parent population P
t
Output: P
t+1
1: S
t
= ∅, i =1
2: Q
t
= Recombination+Mutation(P
t
)
3: R
t
= P
t
∪ Q
t
4: (F
1
,F
2
,...) = Non-dominated-sort(R
t
)
5: repeat
6: S
t
= S
t
∪ F
i
and i = i +1
7: until |S
t
|≥N
8: Last front to be included: F
l
= F
i
9: if |S
t
| = N then
10: P
t+1
= S
t
, break
11: else
12:
P
t+1
= ∪
l−1
j=1
F
j
13: Points to be chosen from F
l
: K = N −|P
t+1
|
14:
Normalize objectives and create reference set Z
r
:
Normalize(f
n
,S
t
,Z
r
,Z
s
,Z
a
)
15: Associate each member s of S
t
with a reference point:
[π(s),d(s)] =Associate(S
t
,Z
r
) % π(s): closest
reference point, d: distance between s and π(s)
16:
Compute niche count of reference point j ∈ Z
r
: ρ
j
=
s
∈S
t
/F
l
(
(π(s)=j)?1:0
)
17: Choose K members one at a time from F
l
to construct
P
t+1
: Niching(K, ρ
j
,π,d,Z
r
,F
l
,P
t+1
)
18:
end if
this method to be used more from the point of view of a
combined application of decision-making and many-objective
optimization. The procedure is presented in Algorithm 1.
C. Adaptive Normalization of Population Members
First, the ideal point of the population S
t
is determined
by identifying the minimum value (z
min
i
) for each objective
function i =1, 2,... ,M in ∪
t
τ=0
S
τ
and by constructing the
ideal point ¯z =(z
min
1
,z
min
2
,... ,z
min
M
). Each objective value of
S
t
is then translated by subtracting objective f
i
by z
min
i
so
that the ideal point of translated S
t
becomes a zero vector.
We denote this translated objective as f
i
(x)=f
i
(x) − z
min
i
.
Thereafter, the extreme point (z
i,max
) in each (ith) objective
axis is identified by finding the solution (x ∈ S
t
) that makes the
corresponding achievement scalarizing function (formed with
f
i
(x) and a weight vector close to ith objective axis) minimum.