![](https://csdnimg.cn/release/download_crawler_static/16114910/bg5.jpg)
698 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 5, OCTOBER 2015
Algorithm 2: Initialization Procedure (INITIALIZATION)
Output: parent population P, weight vector set W,
neighborhood set of weight vectors E
1 Generate an initial parent population P ={x
1
,...,x
N
} by
random sampling from ;
2 if m < 7 then
3 Use Das and Dennis’s method to generate
N =
H+m−1
m−1
weight vectors W ={w
1
,...,w
N
};
4 else
5 Use Das and Dennis’s method to generate
N
1
=
H
1
+m−1
m−1
weight vectors B ={b
1
,...,b
N
1
} and
N
2
=
H
2
+m−1
m−1
weight vectors I ={i
1
,...,i
N
2
},
where N
1
+ N
2
= N;
6 for k ← 1 to N
2
do
7 for j ← 1 to m do
8 i
k
j
=
1−τ
m
+ τ × i
k
j
;
9 end
10 end
11 W
m×N
← B
m×N
1
∪ I
m×N
2
;
12 end
13 for i ← 1 to N do
14 E(i) ={i
1
,...,i
T
} where w
i
1
,...,w
i
T
are the T
closest weight vectors to w
i
;
15 end
16 Use the nondominated sorting method to divide P into
several nondomination levels F
1
, F
2
,...,F
l
;
17 Associate each member in P with a unique subregion;
18 return P, W, E
mating selection procedure chooses some parents for offspring
generation. Then, the offspring is used to update the parent
population according to some elite-preserving mechanism. In
the following paragraphs, the implementation details of each
component in MOEA/DD will be explained step-by-step.
B. Initialization Procedure
The initialization procedure of MOEA/DD (line 1 of
Algorithm 1), whose pseudo-code is given in Algorithm 2,
contains three main aspects: the initialization of parent pop-
ulation P, the identification of nondomination level structure
of P, the generation of weight vectors, and the assignment
of neighborhood. To be specific, the initial parent population
P is randomly sampled from via a uniform distribution.
A set of weight vectors W ={w
1
,...,w
N
} is generated
by a systematic approach developed from Das and Dennis’s
method [59]. In this approach, weight vectors are sampled
from a unit simplex. N =
H+m−1
m−1
points, with a uniform
spacing δ = 1/H, where H > 0 is the number of divisions
considered along each objective coordinate, are sampled on
the simplex for any number of objectives. Fig. 3 gives a sim-
ple example to illustrate the Das and Dennis’s weight vector
generation method.
As discussed in [49], in order to have intermediate weight
vectors within the simplex, we should set H ≥ m. However,
in a high-dimensional objective space, we will have a large
Fig. 3. Structured weight vector w = (w
1
, w
2
, w
3
)
T
generation process with
δ = 0.25, i.e., H = 4 in 3-D space [59].
4+3−1
3−1
= 15 weight vectors are
sampled from an unit simplex.
amount of weight vectors even if H = m (e.g., for an
seven-objective case, H = 7 will results in
7+7−1
7−1
= 1716
weight vectors). This obviously aggravates the computational
burden of an EMO algorithm. On the other hand, if we sim-
ply remedy this issue by lowering H (e.g., set H < m), it will
make all weight vectors sparsely lie along the boundary of the
simplex. This is apparently harmful to the population diversity.
To avoid such situation, we present a two-layer weight vec-
tor generation method. At first, the sets of weight vectors in
the boundary and inside layers (denoted as B ={b
1
,...,b
N
1
}
and I ={i
1
,...,i
N
2
}, respectively, where N
1
+ N
2
= N)are
initialized according to the Das and Dennis’s method, with
different H settings. Then, the coordinates of weight vectors
in the inside layer are shrunk by a coordinate transforma-
tion. Specifically, as for a weight vector in the inside layer
i
k
= (i
k
1
,...,i
k
m
)
T
, k ∈{1,...,N
2
}, its jth component is
reevaluated as
i
k
j
=
1 − τ
m
+ τ × i
k
j
(5)
where j ∈{1,...,m} and τ ∈ [0, 1] is a shrinkage factor (here
we set τ = 0.5 without loss of generality). At last, B and I
are combined to form the final weight vector set W.Fig.4
presents a simple example to illustrate our two-layer weight
vector generation method.
Each weight vector w
i
= (w
i
1
, ···, w
i
m
)
T
, i ∈{1,...,N},
specifies a unique subregion, denoted as
i
, in the objective
space, where
i
is defined as
i
=
F(x) ∈ R
m
|F(x), w
i
≤F(x), w
j
(6)
where j ∈{1,...,N}, x ∈ and F(x), w
j
is the acute angle
between F(x) and w
j
. It is worth noting that a recently pro-
posed EMO algorithm MOEA/D-M2M [40] also employs a
similar method to divide the objective space. However, its
idea is in essence different from our method. To be specific,
in MOEA/DD, the assignment of subregions is to facilitate
the local density estimation which will be illustrated in detail
later; while, in MOEA/D-M2M, different weight vectors are