MOEA/D with Angle-based Constrained Dominance
Principle for Constrained Multi-objective Optimization
Problems

arXiv:1802.03608v1 [] 10 Feb 2018

Zhun Fana , Yi Fanga , Wenji Lia , Xinye Caib,∗, Caimin Weic , Erik Goodmand
a Department

of Electronic Engineering, Shantou University, Guangdong, 515063, China
of Computer Science and Technology, Nanjing University of Aeronautics and
Astronautics, Jiangsu, 210016, China
c Department of Mathematics, Shantou University, Guangdong, 515063, China
d BEACON Center for the Study of Evolution in Action, Michigan State University. East
Lansing, Michigan, USA
b College

Abstract
This paper proposes a novel constraint-handling mechanism named angle-based
constrained dominance principle (ACDP) embedded in a decomposition-based
multi-objective evolutionary algorithm (MOEA/D) to solve constrained multiobjective optimization problems (CMOPs). To maintain the diversity of the
working population, ACDP utilizes the information of the angle of solutions
to adjust the dominance relation of solutions during the evolutionary process.
This paper uses 14 benchmark instances to evaluate the performance of the
MOEA/D with ACDP (MOEA/D-ACDP). Additionally, an engineering optimization problem (which is I-beam optimization problem) is optimized. The
proposed MOEA/D-ACDP, and four other decomposition-based CMOEAs, including C-MOEA/D, MOEA/D-CDP, MOEA/D-Epsilon and MOEA/D-SR are
tested by the above benchmarks and the engineering application. The experimental results manifest that MOEA/D-ACDP is significantly better than the
other four CMOEAs on these test instances and the real-world case, which indicates that ACDP is more effective for solving CMOPs.
Keywords: Constraint-handling Mechanism, Angle-based Constrained
Dominance Principle (ACDP), Decomposition based Multi-objective
Algorithm (MOEA/D)

1. Introduction
Multi-objective optimization problems (MOPs) involve the optimization of
more than one objective function. In the real world, many optimization prob∗ Corresponding

author
Email address: xinye@nuaa.edu.cn (Xinye Cai)

Preprint submitted to Elsevier

February 13, 2018

lems invariably involve a number of constraints and a multiple conflicting objectives. In general, a CMOP can mathematically be described as follows:

T

minimize F(x) = (f1 (x), . . . , fm (x))

subject to g (x) ≥ 0, i = 1, . . . , q
i
(1)

h
j (x) = 0, j = 1, . . . , p



x ∈ Rn
where F (x) = (f1 (x), f2 (x), . . . , fm (x))T ∈ Rm is an m-dimensional objective
vector, gi (x) ≥ 0 is the ith inequality constraint, and hj (x) = 0 is the j th
equality constraint. x ∈ Rn is an n-dimensional decision vector. The feasible
region S is defined as the set {x|gi (x) ≥ 0, i = 1, . . . , q and hj (x) = 0, j =
1, . . . , p}.
In CMOPs, there are usually more than one constraint. To demonstrate the
degree of constraint violation, these constraints are commonly summarized into
a scalar value as follows:
φ(x) =

q
X

| min(gi (x), 0)| +

i=1

p
X

|hj (x)|

(2)

j=1

when φ(x) = 0, the solution x is feasible, otherwise it is infeasible.
For any two feasible solutions xa ∈ S and xb ∈ S of a CMOP, it can be said
that xa dominates xb if the following condition is met:
∀i fi (xa ) ≤ fi (xb ) and ∃j fj (xa ) < fj (xb )

(3)

where i, j ∈ {1, 2, ..., m}. If there exists a solution x∗ ∈ S, which dominates
any other solutions in S, x∗ can be said as a Pareto optimal solution. The set
of all Pareto optimal solution belonging to S is called as Pareto set (PS). The
set of the mapping vectors of PS in the objective space is named as Pareto front
(PF), which can be defined in the form of P F = {F (x)| x ∈ P S}.
CMOPs are consist of a few objectives and constraints. To solve CMOPs,
the constraint-handling technique should be applied to the framework of multiobjective evolutionary algorithm (MOEA).
According to different selection strategies, MOEAs mainly can be classified
into three types: (1) Pareto-domination-based; (2) decomposition-based; (3)
indicator-based. The typical examples of domination-based MOEAs include
NSGA-II [1], MOGA [2], PAES-II [3], SPEA-II [4] and NPGA [5]. In recent
years, decomposition-based MOEAs attract a lot of attention. The most representative algorithm of this type is MOEA/D [6]. Some variants of MOEA/D include MOEA/D-DE [7], MOEA/D-M2M [8], EAG-MOEA/D [9] and MOEA/DSAS [10]. For indicator-based MOEAs, they use a scalar metric to assist the
selection, typical examples of this type are IBEA [11], SMS-EMOA [12], HypE
[13] and FV-MOEA [14].
To solve CMOPs, constraint-handling mechanisms are important. In recent
years, many different constraint-handling mechanisms have been proposed [15,
2

16]. According to [17], constraint-handling techniques can be generally classified
into (1) penalty functions; (2) special representations and operators; (3) repair
algorithms; (4) separate objectives and constraints; and (5) hybrid methods.
As a representative objective-constraint separating method, constraineddomination principle (CDP) proposed in [1] is widely used. It solves CMOPs by
treating constraints as the top priority. Stochastic ranking [18], ε-constrained
method [19] and non-greedy constraint-handling technique [20] are also in this
category.
Currently, CTPs [21] and CFs [22] are the most widely used CMOP test
instances. The common characteristic of these benchmarks is that they all
have large feasible regions in the objective space. However, constraint-handling
mechanisms do not work when the working population falls in feasible regions, so
these two series of instances are not actually suitable for testing the effectiveness
of constraint-handling mechanisms.
The rest of this paper is organized as follows: Section 2 briefly introduces
MOEA/D and four other decomposition-based CMOEAs. Section 3 introduces
the details of the angle-based constrained dominance principle embedded in
MOEA/D. Section 4 gives comprehensive experimental results of the proposed
algorithm MOEA/D-ACDP and four other CMOEAs on LIR-CMOPs and the
I-beam optimization problem. Finally, conclusions are made in section 5.
2. Relative Work
2.1. MOEA/D
In the original framework of MOEA/D [6], given a series of uniform distributed weight vectors, a MOP is decomposed into N scalar subproblems
(SOPs), and each SOP relates to one solution. In MOEA/D, a set of N uniformly spread weight vectors λ1 , . . . , λN is initially generated for N subproblems.
A weight vector λi satisfies the following conditions:
m
X

λik = 1

and λik ≥ 0

for each k ∈ {1, . . . , m}.

(4)

k=1

There are several approaches to decompose a MOP into a number of scalar
optimization subproblems [6, 23]. Three decomposition approaches, including
weighted sum [23], Tchebycheff [23] and boundary intersection approaches [6]
are commonly used. In this paper, Tchebycheff decomposition method is used
in the MOEA/D framework. The j-th subproblem is defined as follows:
)
(
1
∗
te
∗
|fi (x) − zi |
minimize g (x|λ, z ) = max
1≤i≤m
λji
subject to x ∈ S

(5)

∗
) is the ideal point, and zi∗ = min{fi (x)|x ∈ S}.
where z ∗ = (z1∗ , . . . , zm

3

2.2. Decomposition-based CMOEAs
Decomposition-based CMOEAs combine the MOEA/D with different constrainthandling mechanisms. In this paper, we introduce four representative decompositionbased CMOEAs including C-MOEA/D [24], MOEA/D-CDP [25], MOEA/DEpsilon [26], and MOEA/D-SR [25].
• C-MOEA/D [24] uses a variant of the epsilon constraint-handling technique. In this technique, the epsilon level is set to handle constraints
according to the constraint violation and the proportion of feasible solutions in the current population. When comparing any two solutions, if
overall constraint violations of the solutions are both less than the epsilon
level, the one with a better aggregation value dominates the other. Otherwise, the one with a smaller overall constraint violation dominates the
other.
• MOEA/D-CDP [25] uses CDP [1] to judge the domination relationship
between two arbitrary solutions. CDP can be simply summarized as following three rules:
1) When two feasible solutions are compared, the one with a better aggregation value dominates the other.
2) When a feasible solution is compared with an infeasible solution, the
feasible solution dominates the infeasible solution.
3) When two infeasible solutions are compared, the one with a smaller
degree of constraint violation dominates the other.
The second and the third rules can be combined as a single rule: When at
least one of two compared solutions is infeasible, the one with a smaller
degree of constraint violation dominates the other.
• MOEA/D-Epsilon [26] uses the original epsilon constraint-handling technique. The epsilon level setting can be referred to [19]. With the generation counter K increasing, the epsilon level will dynamically decrease.
• MOEA/D-SR [25] embeds the stochastic ranking method (SR) [18] in
MOEA/D to deal with constraints. A threshold parameter rf ∈ [0, 1] is
set to balance the selection between the objectives and the constraints
in MOEA/D-SR. When comparing two solutions, if a random number in
[0, 1] is less than rf , the one with a better aggregation value is retained
into the next generation. If the random number in [0, 1] is greater than rf ,
the whole framework of MOEA/D-SR is similar to that of MOEA/D-CDP.
In the case of rf = 0, MOEA/D-SR is equivalent to MOEA/D-CDP.
3. MOEA/D with Angle-based Constrained Dominance Principle
In this section, the definition of the proposed ACDP and the effectiveness of
this mechanism in MOEA/D are detailed.

4

3.1. Angle-based Constrained Dominance Principle
In the CDP approach [1], with its three basic rules, the overall constraint
violation is the most important factor during the evolutionary process, and some
useful information in the infeasible regions tends to be ignored.
The angle between any two solutions in the objective space is useful information, which is related to the similarity between these two solutions. The
definition of angle between any two solutions x1 and x2 is given as follows:


(F(x1 ) − z ∗ )T · (F(x2 ) − z ∗ )
1
2 ∗
(6)
angle(x , x , z ) = arccos
||F(x1 ) − z ∗ || · ||F(x2 ) − z ∗ ||
∗
where z ∗ = (z1∗ , . . . , zm
) is the ideal point, and zi∗ = min{fi (x|x ∈ S}. || · || is
the two-norm of a vector.
As shown in Fig. 1, given any two solutions x1 and x2 , the angle between
them in the objective space is θ12 . Obviously, the angle between any two solutions
is less than or equal to π/2, which means that the range of angle between any
two solutions belongs in [0, π/2].

Figure 1: Illustration of the angle between x1 and x2

Given any two solutions x1 and x2 , an threshold of angle θ, a random number
of Feasible Solutions
r and a parameter pf ( NumberPopulation
) which denotes the proportion
Size
of feasible solutions in the current population, the ACDP is defined as follows:
1. If x1 and x2 are both feasible, the one dominating the other is better.
2. If there is at lease one infeasible solution and angle(x1 , x2 , z ∗ ) ≤ θ, the
one with a smaller constraint violation dominates the other.
3. When there is at least one infeasible solution and angle(x1 , x2 , z ∗ ) > θ,
if r < pf , the one dominating the other is better, otherwise, they are
incomparable.
5

3.2. ACDP in the framework of MOEA/D
As we know, MOEA/D uses the value of decomposition function of a solution
to update its neighbors. In order to use ACDP to handle constraints in the
framework of MOEA/D, here we provide a version of ACDP which is suitable
to the algorithm.
Given a subproblem sp with the weight vector λ, for two solutions x1 and
2
x , their overall constraint violations are φ1 and φ2 , and their decomposition
values on the subproblem sp are g te (x1 |λ, z ∗ ) and g te (x2 |λ, z ∗ ). The ACDP
dominance θ in the framework of MOEA/D is defined as follows:

x1 θ x2 ⇔


Rule 1 if φ1 = 0, φ2 = 0 :





g te (x1 |λ, z ∗ ) < g te (x2 |λ, z ∗ );



1
2


Rule 2 if φ < φ :
angle(x1 , x2 , z ∗ ) ≤ θ;



Rule 3 otherwise :





angle(x1 , x2 , z ∗ ) > θ, r < pf ,



g te (x1 |λ, z ∗ ) < g te (x2 |λ, z ∗ ).

(7)

where θ is a threshold parameter, which is defined by users. In Eq. (7), the
constraint-handling method ACDP is equivalent to CDP [1] when θ ≥ π2 .
In Rule 1 of ACDP, when these two solutions are both feasible, the solution
with a lower aggregation value dominates the other, which is similar to the first
rule of CDP.
When at least one of x1 and x2 is infeasible, CDP only utilizes the constraint violations of these two solutions to compare, which is difficult to keep
the diversity of the working population when most of solutions in the population
are infeasible. Nevertheless, ACDP utilizes additional information to compare
the two solutions, which includes the angle between the two compared solutions
in the objective space and the proportion of feasible solutions in the current
population (pf ). More details of ACDP in this situation are listed as follows:
• In Rule 2 of ACDP, if the angle between x1 and x2 in the objective space
is smaller than the parameter θ, ACDP considers that these two solutions are similar and compares them according to their constraint violations. Because these two solutions are similar, based on the framework of
MOEA/D, they will be considered to relate to the same subproblem. In
this situation, using the constraint violations to compare the two solutions
will not cause the loss of the diversity.
• In Rule 3 of ACDP, if the angle between x1 and x2 in the objective space
is larger than the parameter θ, ACDP considers that these two solutions
are dissimilar, and the solution with a lower decomposition value will
dominate the other with a probability of pf . Some solutions with low
aggregation values but large constraint violations will have a chance to be

6

selected in the next generation, which can enhance the convergence of the
working population effectively.
• The probability in Rule 3 of ACDP is set to be the proportion of feasible
solutions in the current population. It keeps the balance of the exploration
of the working population between infeasible regions and feasible regions.
When pf is large, ACDP tends to explore infeasible regions. When pf is
small, ACDP tends to explore feasible regions.
3.3. Effectiveness of ACDP in MOEA/D
The evolutionary process of a CMOEA can be generally divided in three
stages according to the status of the working population.
In the first stage, a population is generated randomly, and most of the individuals are far away from the real PF as shown in Fig. 2 (a) and Fig. 2
(b).
In the second stage, the working population begins to explore the search
space. As shown in Fig. 2 (c), when using CDP in MOEA/D, the working population will be attracted to feasible regions and actually difficult to get across
infeasible regions. As shown in Fig. 2 (d), when ACDP is applied to MOEA/D,
the working population can maintain the diversity by using angle information.
Some individuals can enter infeasible regions, which can help the working population to go across infeasible regions effectively. Additionally, ACDP uses the
information of the proportion of feasible solutions in the current population as
the probability to select solutions, which can help to balance the search between
feasible and infeasible regions.
In the third stage, the working population will converge to its near feasible
regions. when using CDP, the population is trapped into local optimum, because
of the difficulty to get across infeasible regions in the second stage, as shown in
Fig. 2 (e). Conversely, when using ACDP, the working population can converge
to the real PF more completely as shown in Fig. 2 (f), because the population
can keep the diversity and explore infeasible regions in the second stage.
3.4. The Parameter Setting of Theta
In the early stage of evolutionary process, the population is commonly far
away from real PF. To prevent the population from being trapped into local optimum, the value of θ should be set small to maintain the diversity. In the later
stage of evolutionary process, the convergence to the feasible regions should be
emphasized, then the value of θ should become larger. Based on the above discussions, the threshold θ(k) should be dynamically increased with the generation
counter k increasing. A method of setting θ(k) is proposed as follows:

θ(k) =

( 
θ0 1 +

k
Tmax

π
2

cp

, 1 ≤ k ≤ Tc

, Tc < k ≤ Tmax

7

(8)

(a) Stage 1 of CDP

(b) Stage 1 of ACDP

(c) Stage 2 of CDP

(d) Stage 2 of ACDP

(e) Stage 3 of CDP

(f) Stage 3 of ACDP

Figure 2: Illustrations of the evolutionary process of MOEA/D with CDP and ACDP.

8

where θ0 is an initial threshold value which is set as π/2N , N is the size of
population and Tmax is the maximum generation. α is a parameter, which is
set as 0.8. Tc = αTmax is the termination generation to control θ. Parameter
cp is initialized to log(N )/log(1 + α).
As we know, the uniform weight vectors defined in Eq. (4) decide that the
maximum angle between two vectors is π/2, and the average angle between
two adjacent vectors is π/2N , where N is the size of population. Then, θ0 is
initially set as π/2N . According to Eq. (8), when the generation counter k
reaches Tc , the value of θ(k) is π/2, and keeps constant afterwards. As shown
in Fig. 3, we assume that the population size N and the maximum generation
Tmax are set as 300 and 500, respectively. Meanwhile α is set as 0.8. We can
find that θ0 = π/2N . In the early stage of evolutionary process, θ(k) increases
continuously but slowly. It benefits the population to maintain diversity. When
k gets more and more closed to Tc , θ(k) rises faster, which helps to accelerate
the convergence speed to the feasible regions. When k reaches Tc , θ(k) is equal
to π/2, ACDP is transformed into CDP.

Figure 3: The changing trend of θ.

3.5. ACDP embedded in MOEA/D
The proposed MOEA/D-ACDP integrates the general framework of MOEA/D
and the angle-based constrained dominance principle.
The psuecode of MOEA/D-ACDP is listed in Algorithm 1. Lines 1-5 initialize some parameters in MOEA/D-ACDP. First, a CMOP is decomposed into
N subproblems which are associated with weight vectors λ1 , . . . , λN . Then the
population P , the initial increasing factor cp, the ideal point z ∗ and the neighbor
indexes B(i) are initialized. Lines 7-11 update the angle threshold value θ(k).
Line 12 updates the proportion of feasible solutions in the current population pf .
Lines 13-23 generate a set of new solutions and update the ideal point z ∗ . To be
more specific, lines 14-21 determine the set of neighboring solutions that may be
9

Algorithm 1: MOEA/D-ACDP
Input:
N : the number of subproblems.
Tmax : the maximal generation.
N weight vectors: λ1 , . . . , λN .
T : the size of the neighborhood.
δ: the selecting probability from neighbors.
nr : the maximal number of solutions replaced by a child.
θ0 , α: the parameters of ACDP method.
Output: N S : a set of feasible non-dominated solutions
1
N
1 Decompose a CMOP into N subproblems associated with λ , . . . , λ .
1
N
2 Generate an initial population P = {x , . . . , x }.
log(N )
3 Initialize cp to be log(1+α) .
∗
4 Initialize the ideal point z = (z1 , . . . , zm ).
i
i
5 For each i = 1, . . . , N , set B(i) = {i1 , . . . , iT }, where λ 1 , . . . , λ T are the
i
T closest weight vectors to λ .
6 for k ← 1 to Tmax do
7
if k ≤ αTmax then
k
8
Set θ(k) according to θ(k) = θ0 (1 + Tmax
)cp .
9
else
10
Set θ(k) to be equal to π2
11
end
12
Update pf in the current generation.
13
Generate a random permutation rp from {1, . . . , N }.
14
for i ← 1 to N do
15
Generate a random number r ∈ [0, 1].
16
j = rp(i).
17
if r < δ then
18
S = B(j)
19
else
20
S = {1, . . . , N }
21
end
22
Generate yj through DE and polynomial mutation operators.
23
Update the current ideal point.
24
Set c = 0.
25
while c 6= nr and S 6= ∅ do
26
select an index j from S randomly, S = S\{j}.
27
result = U pdateSubproblems(xj , yj , θ(k), pf )
28
if result == true then c = c + 1;
29
end
30
end
S
31
N S = NondominatedSelect(N S P )
32 end

10

updated by a newly generated solution yj . In line 22, the differential evolution
(DE) crossover operator is adopted to generate a new solution yj . Meanwhile,
yj is further mutated by the polynomial mutation operator. The ideal point
z ∗ is updated in line 23. Lines 24-39 update subproblems. In line 27, the subproblems are updated based on the ACDP approach whose detailed psuecode is
listed in Algorithm 2. At the end of each generation, non-dominated solutions
(N S) in the population are selected to update the external archive based on
non-dominated sorting in line 31.
Algorithm 2: Subproblem Update
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Function result = UpdateSubproblems(xj , yj , θ(k), pf )
result = f alse
if φ(yj ) == 0 and φ(xj ) == 0 then
if g te (yi |λj , z ∗ ) ≤ g te (xj |λj , z ∗ ) then
xj = yj
result = ture
end
else
if angle(F(yj ), F(xj ), z ∗ ) < θ(k) then
if φ(yj ) < φ(xj ) then
xj = y j
result = ture
end
else
if rand() < pf then
if g te (yi |λj , z ∗ ) ≤ g te (xj |λj , z ∗ ) then
xj = yj
result = ture
end
end
end
end
return result
end

In Algorithm 2, the algorithm updates a subproblem in terms of Eq. (7).
Lines 3-7 denote that when two feasible solutions xj and yj are compared, the
one with a better aggregation value is selected. Lines 9-12 denote that when at
least one of two solutions xj and yj is infeasible, if the angle between them in
the objective space is lower than θ, the solution with a lower constraint violation
is selected. Lines 13-17 denote that when at least one of two solutions xj and
yj is infeasible, if the angle between them in the objective space is larger than
θ, the solution with a lower aggregation value will be selected with a probability
of pf .
11

4. Experimental Study
4.1. Test Instances LIR-CMOPs
To evaluate the performance of the proposed MOEA/D-ACDP, 14 constrained multi-objective test problems with large infeasible regions in the objective space are used [27, 28].
The general characteristic of LIR-CMOPs is that their real PFs are blocked
by a number of large infeasible regions, and thus hard to be found during an
evolutionary process. Their constraint functions are comprised of controllable
shape functions and distance functions [29]. More specifically, the shape functions are used to turn the PF shapes as convex or concave, while the distance
functions are adopted to adjust the convergence difficulty for CMOEAs. Fig. 4
and Fig. 5 plot the feasible regions of LIR-CMOPs with two or three objectives,
respectively.
4.2. Real-world Engineering Optimization: I-beam
To evaluate the performance of MOEA/D-ACDP for solving real world optimization problems, an engineering optimization problem with two conflicting
objectives is studied.
As defined in [30], an optimization problem of I-beam is a bi-objective constrained optimization problem which needs to minimize the following objectives
simultaneously:
1. Cross section area of the beam;
2. Static deflection of the beam for the displacement under the force P .
To study the landscape in the objective space of the I-beam optimization problem, 1,000,000 sampling solutions are generated, where 850,000 solutions are generated randomly, and the other 150,000 solutions are generated
by MOEA/D-ACDP. In Fig. 6, it is observed that there exist a few infeasible
regions (the proportion of feasible solutions in all sampling solutions p = 0.5339,
which means that nearly a half of selected points are infeasible.) in the objective
space for the I-beam optimization problem.
4.3. Experimental Settings
To evaluate the performance of the proposed MOEA/D-ACDP, four popular CMOEAs (C-MOEA/D, MOEA/D-CDP, MOEA/D-Epsilon and MOEA/DSR), with differential evolution (DE) crossover operator, are adopted and tested
on LIR-CMOP1-14 and I-beam optimization problem. The detailed parameters
are listed as follows:
1. Mutation probability P m = 1/n (n is the number of decision variables)
and its distribution index is set to 20. For DE operator, CR = 1.0, f = 0.5.
2. Population size: N = 300. Neighborhood size: T = 30.
3. Stopping condition: each algorithm runs for 30 times independently, and
stops when 150,000 function evaluations are reached.
12

(a) LIR-CMOP1

(b) LIR-CMOP2

(c) LIR-CMOP3

(d) LIR-CMOP4

(e) LIR-CMOP5

(f) LIR-CMOP6

(g) LIR-CMOP7

(h) LIR-CMOP8

(i) LIR-CMOP9

(j) LIR-CMOP10

(k) LIR-CMOP11

(l) LIR-CMOP12

Figure 4: Illustrations of the feasible and infeasible regions of LIR-CMOP1-12.

(a) LIR-CMOP13

(b) LIR-CMOP14

Figure 5: Illustrations of the infeasible regions of LIR-CMOP13-14.

13

4. Probability of selecting individuals in the neighborhood: δ = 0.9.
5. The maximal number of solutions replaced by a child: nr = 2.
6. Parameter setting in MOEA/D-ACDP: α = 0.8 and θ0 = π/2N .
7. Parameter setting in MOEA/D-Epsilon: Tc = 400, cp = 2 and θ = 0.05N .
8. Parameter setting in MOEA/D-SR: Sr = 0.01.
4.4. Performance Metric
To measure the performance of MOEA/D-ACDP, C-MOEA/D, MOEA/DCDP, MOEA/D-Epsilon and MOEA/D-SR, two widely used metrics inverted
generation distance (IGD) [31] and hypervolume (HV ) [32] are adopted as
evaluation metrics. Their definitions are listed as follows.
• Inverted Generational Distance (IGD):
IGD is a metric which evaluates the performance related to convergence and
diversity simultaneously. Let P ∗ be a set of uniformly distributed points in the
ideal PF. Let A denote an approximate PF achieved by a certain CMOEA. The
metric IGD that represents average distance from P ∗ to A is defined as:

P
d(y ∗ , A)


∗
∗

y ∈P


IGD(P ∗ , A) =
|P ∗ |
(9)



p
Pm

∗
2

d(y ∗ , A) = min{
i=1 (yi − yi ) }
y∈A

In our experiment, for CMOPs with two objectives, 1000 points are sampled uniformly from the PF to constitute P ∗ . For CMOPs with three objectives, 10000
points are sampled uniformly from the PF to constitute P ∗ . A smaller IGD
represents a better performance regarding to both diversity and convergence.
• Hypervolume (HV ):
HV reflects the closeness between the non-dominated set achieved by a CMOEA
and the representative PF. The larger HV means that the corresponding nondominated set is closer to the true PF.
!
[
r
HV (S) = V OL
[f1 (x), z1r ] × ...[fm (x), zm
]
(10)
x∈S
r T
where V OL(·) is the Lebesgue measure, zr = (z1r , ..., zm
) is a reference point
in the objective space. For the test instances LIR-CMOPs, the reference point
is set as 1.4 times the nadir point of the real PF. The HV with a larger value
represents the better performance regarding to both diversity and convergence.

14

Figure 6: The distribution of the I-Beam problem.

As the real PF of the I-beam optimization problem is not known, IGD metric
can not be calculated. The experiment uses the HV metric [32] to measure the
performance of these CMOEAs. In the I-beam optimization case, the reference
point is set as z r = [850, 0.0615]T .
4.5. Discussion of Experimental Results
4.5.1. Performance Evaluation on LIR-CMOP Test Instances
The results of the IGD values on LIR-CMOP1-14 achieved by five CMOEAs
in 30 independent runs are shown in Table 1.
As discussed in Section 4, LIR-CMOP1-14 all have large infeasible regions
in their objective space. For LIR-CMOP3-14, MOEA/D-ACDP significantly
outperforms the other four compared algorithms in terms of the IGD metric.
For LIR-CMOP1-2, MOEA/D-ACDP significantly outperforms C-MOEA/D,
MOEA/D-CDP and MOEA/D-Epsilon.
The results of the HV values on LIR-CMOP1-14 achieved by five CMOEAs
in 30 independent runs are shown in Table 2. For LIR-CMOP2-14, MOEA/DACDP significantly outperforms the compared algorithms in terms of the HV
metric. For the LIR-CMOP1, MOEA/D-ACDP significantly outperforms CMOEA/D, MOEA/D-CDP and MOEA/D-Epsilon.
Fig. 7 (a) shows the final external archives achieved by MOEA/D-ACDP
and other four CMOEAs with the median IGD values on LIR-CMOP3 during
30 independent runs. It is obvious that MOEA/D-ACDP can almost converge
to the whole real PF and has the best diversity among the five CMOEAs.
In Fig. 7 (b), the results of each CMOEA with the median IGD values
on LIR-CMOP5 during 30 independent runs are shown. The external archive
achieved by MOEA/D-ACDP covers the real PF. However, the other four
CMOEAs are trapped into local optimum. As shown in Fig. 7 (c), for LIRCMOP10, MOEA/D-ACDP performs the best in terms of convergency. In Fig.

15

7 (d), for LIR-CMOP11, it shows that MOEA/D-ACDP can get the most of
the PF, but the other four algorithms can only achieve a few parts of the PF.
It is worthwhile to point out that for three-objective test instances (LIRCMOP13 and LIR-CMOP14), MOEA/D-ACDP also performs significantly better than the other four CMOEAs.
Based on the above performance comparison on the fourteen test instances
LIR-CMOP1-14, it is clear that MOEA/D-ACDP outperforms the other four
decomposition-based CMOEAs on most of cases.
A common feature of the above test instances LIR-CMOPs is that they all
have large infeasible regions in their objective space. The experimental results
demonstrate that the proposed ACDP method can deal with CMOPs well by
taking advantage of angle information of the working population.
Table 1: IGD results of MOEA/D-ACDP and the other four CMOEAs on LIR-CMOP1-14
test instances
Test Instances
mean
std
mean
LIR-CMOP2
std
mean
LIR-CMOP3
std
mean
LIR-CMOP4
std
mean
LIR-CMOP5
std
mean
LIR-CMOP6
std
mean
LIR-CMOP7
std
mean
LIR-CMOP8
std
mean
LIR-CMOP9
std
mean
LIR-CMOP10
std
mean
LIR-CMOP11
std
mean
LIR-CMOP12
std
mean
LIR-CMOP13
std
mean
LIR-CMOP14
std
LIR-CMOP1

MOEA/D-ACDP
5.159E-02
1.815E-02
2.269E-02
9.418E-03
4.659E-02
1.850E-02
2.784E-02
1.477E-02
1.771E-02
2.965E-02
1.757E-01
4.129E-02
1.408E-01
4.385E-02
1.812E-01
4.854E-02
3.595E-01
5.345E-02
1.388E-01
1.148E-01
1.318E-01
4.487E-02
1.497E-01
9.985E-03
7.414E-02
2.727E-03
6.732E-02
1.918E-03

C-MOEA/D
1.591E-01†
3.534E-02
1.462E-01†
4.141E-02
2.309E-01†
4.135E-02
2.080E-01†
4.197E-02
1.162E+00†
2.180E-01
1.265E+00†
3.067E-01
1.620E+00†
3.036E-01
1.607E+00†
2.680E-01
4.981E-01†
6.991E-02
3.775E-01†
7.446E-02
4.422E-01†
1.759E-01
3.597E-01†
1.074E-01
1.266E+00†
2.173E-01
1.235E+00†
1.209E-01

MOEA/D-CDP
1.348E-01†
5.996E-02
1.549E-01†
2.966E-02
2.268E-01†
4.403E-02
2.188E-01†
3.766E-02
1.207E+00†
1.660E-02
1.303E+00†
2.319E-01
1.623E+00†
2.905E-01
1.631E+00†
2.464E-01
4.868E-01†
5.372E-02
3.774E-01†
6.858E-02
4.662E-01†
1.439E-01
3.236E-01†
1.023E-01
1.289E+00†
6.321E-02
1.103E+00†
3.857E-01

MOEA/D-Epsilon
8.234E-02†
5.321E-02
4.708E-02†
1.339E-02
7.858E-02†
2.978E-02
5.662E-02†
3.366E-02
1.201E+00†
1.963E-02
1.231E+00†
3.602E-01
1.568E+00†
4.101E-01
1.577E+00†
3.767E-01
4.962E-01†
6.987E-02
3.257E-01†
9.833E-02
4.154E-01†
1.508E-01
3.680E-01†
8.664E-02
1.183E+00†
3.456E-01
1.127E+00†
3.329E-01

MOEA/D-SR
4.406E-02
3.360E-02
2.057E-02
1.072E-02
1.529E-01†
7.688E-02
2.038E-01†
7.907E-02
1.123E+00†
2.842E-01
1.175E+00†
3.967E-01
1.136E+00†
7.315E-01
1.369E+00†
5.735E-01
4.813E-01†
4.571E-02
2.821E-01†
1.135E-01
3.489E-01†
1.129E-01
3.012E-01†
8.989E-02
1.093E+00†
4.269E-01
1.143E+00†
3.002E-01

Wilcoxons rank sum test at a 0.05 significance level is performed between MOEA/D-ACDP
and each of the other four CMOEAs. † and ‡ denote that the performance of the
corresponding algorithm is significantly worse than or better than that of MOEA/D-ACDP,
respectively. The best mean is highlighted in boldface.

4.5.2. Performance Evaluation on I-beam Optimization Problem
The experimental results of HV values of MOEA/D-ACDP and the four
other CMOEAs on the I-beam optimization problem are shown in Table 3. It
can be observed that MOEA/D-ACDP significantly outperforms the compared
CMOEAs on this engineering problem.

16

Table 2: HV results of MOEA/D-ACDP and the other four CMOEAs on LIR-CMOP1-14
test instances
Test Instances
mean
std
mean
LIR-CMOP2
std
mean
LIR-CMOP3
std
mean
LIR-CMOP4
std
mean
LIR-CMOP5
std
mean
LIR-CMOP6
std
mean
LIR-CMOP7
std
mean
LIR-CMOP8
std
mean
LIR-CMOP9
std
mean
LIR-CMOP10
std
mean
LIR-CMOP11
std
mean
LIR-CMOP12
std
mean
LIR-CMOP13
std
mean
LIR-CMOP14
std
LIR-CMOP1

MOEA/D-ACDP
1.365E+00
2.493E-02
1.737E+01
1.306E-02
1.188E+00
4.929E-02
1.421E+00
1.946E-02
1.903E+00
5.658E-02
1.280E+00
4.613E-02
3.408E+00
1.409E-01
3.330E+00
1.461E-01
4.080E+00
9.501E-02
3.755E+00
2.208E-01
5.004E+00
1.564E-01
6.713E+00
05.874E-02
7.897E+00
2.943E-02
8.641E+00
1.546E-02

C-MOEA/D
9.499E-01†
7.038E-02
1.395E+01†
8.154E-02
7.558E-01†
5.730E-02
1.069E+00†
6.952E-02
1.192E-01†
3.352E-01
7.863E-02†
3.011E-01
2.990E-01†
6.927E-01
3.246E-01†
5.878E-01
3.715E+00†
2.079E-01
3.274E+00†
1.623E-01
3.937E+00†
6.479E-01
5.977E+00†
3.855E-01
6.444E-01†
1.317E+00
7.766E-01†
6.140E-01

MOEA/D-CDP
1.009E+00†
1.298E-01
1.374E+01†
6.160E-02
7.600E-01†
5.809E-02
1.051E+00†
5.462E-02
5.805E-02†
4.042E-04
4.312E-02†
2.362E-01
2.886E-01†
6.348E-01
2.695E-01†
5.297E-01
3.755E+00†
1.600E-01
3.268E+00†
1.416E-01
3.842E+00†
5.507E-01
6.134E+00†
3.617E-01
4.728E-01†
2.689E-01
1.627E+00†
2.473E+00

MOEA/D-Epsilon
1.353E+00†
4.417E-02
1.705E+01†
1.693E-02
1.184E+00†
2.898E-02
1.390E+00†
4.405E-02
5.829E-02†
2.022E-04
1.325E-01†
4.251E-01
4.055E-01†
8.879E-01
3.859E-01†
8.166E-01
3.724E+00†
2.033E-01
3.385E+00†
2.122E-01
4.038E+00†
5.727E-01
6.010E+00†
3.074E-01
1.092E+00†
2.0522E+00
1.430E+00†
2.095E+00

MOEA/D-SR
1.376E+00
3.974E-02
1.736E+01†
1.890E-02
9.313E-01†
1.620E-01
1.089E+00†
1.360E-01
1.707E-01†
4.442E-01
1.682E-01†
4.061E-01
1.313E+00†
1.567E+00
8.287E-01†
1.244E+00
3.752E+00†
1.142E-01
3.477E+00†
2.383E-01
4.274E+00†
4.463E-01
6.240E+00†
2.950E-01
1.513E+00†
2.422E+00
1.269E+00†
1.919E+00

Wilcoxons rank sum test at a 0.05 significance level is performed between MOEA/D-ACDP
and each of the other four CMOEAs. † and ‡ denotes that the performance of the
corresponding algorithm is significantly worse than or better than that of MOEA/D-ACDP,
respectively. The best mean is highlighted in boldface.

17

(a) LIR-CMOP3

(b) LIR-CMOP5

(c) LIR-CMOP10

(d) LIR-CMOP11

Figure 7: The non-dominated solutions achieved by each algorithm with the median IGD in
the 30 independent runs for LIR-CMOP3, LIR-CMOP5, LIR-CMOP10 and LIR-CMOP11.

18

To further study the superiority of the proposed method MOEA/D-ACDP,
the non-dominated solutions achieved by each CMOEA during the 30 independent runs are plotted in Fig. 8 (a)-(e).The non-dominated set of all the above
solutions generates a set of ideal reference points. It is clear that the external
archive obtained by MOEA/D-ACDP has a better performance of convergence.
The box plot of HV values of the five CMOEAs is shown in Fig. 8 (f), which
further verifies that MOEA/D-ACDP outperforms the other four CMOEAs on
the I-beam optimization problem.

(a) MOEA/D-ACDP

(b) C-MOEA/D

(c) MOEA/D-CDP

(d) MOEA/D-Epsilon

(e) MOEA/D-SR

(f) The box plots of each
CMOEA

Figure 8: The non-dominated solutions achieved by each algorithm during the 30 independent
runs are plotted in (a)-(e). In (f), the box plots of each CMOEA are plotted.

Table 3: HV results of MOEA/D-ACDP and the other four CMOEAs on the I-Beam optimization problem
Test Instances
mean
std

MOEA/D-ACDP
3.583E+01
1.950E-01

C-MOEA/D
3.481E+01†
2.968E-01

MOEA/D-CDP
3.518E+01†
2.078E-01

MOEA/D-Epsilon
3.514E+03†
2.034E-01

MOEA/D-SR
3.477E+03†
1.248E+00

Wilcoxons rank sum test at a 0.05 significance level is performed between MOEA/D-ACDP
and each of the other four CMOEAs. † and ‡ denote that the performance of the
corresponding algorithm is significantly worse than or better than that of MOEA/D-ACDP,
respectively. The best mean is highlighted in boldface.

5. Conclusions
This paper proposes a new constraint-handling mechanism named ACDP.
It utilizes the angle information of any two solutions to dynamically maintain
the diversity of the population during the evolutionary process. A set of CMOP
19

instances named LIR-CMOP1-14 are tested. All the test instances have large
infeasible regions in their objective space, which make general CMOEAs difficult
to achieve the real PFs. Compared with the other four popular CMOEAs, the
proposed algorithm can help the population to go across large infeasible regions
more effectively. Additionally, the experimental results demonstrate that the
proposed algorithm can work well in the real-world engineering problem. Thus,
we can conclude that MOEA/D-ACDP outperforms the other four CMOEAs
when CMOPs. In summary, MOEA/D-ACDP has following advantages:
• The proposed MOEA/D-ACDP utilizes the angle information of solutions
to maintain the diversity of the population for CMOPs.
• MOEA/D-ACDP enhances the convergence to PF by exploring feasible
and infeasible regions simultaneously during the evolutionary process, instead of wasting the useful information of the infeasible solutions.
Future work will focus on novel constraint-handling mechanisms to solve
CMOPs. A study on developing new mechanisms of mining more useful information during the evolutionary process to further improve the performance of
the proposed algorithm will be conducted.
Acknowledgment
This work was supported in part by the National Natural Science Foundation of China under Grant (61175073, 61300159, 61332002, 51375287) , the
Guangdong Key Laboratory of Digital signal and Image Processing, the Science
and Technology Planning Project of Guangdong Province (2013B011304002)
and the Project of Educational Commission of Guangdong Province, China
2015KGJHZ014).
References
References
[1] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary
Computation 6 (2) (2002) 182–197.
[2] T. Murata, H. Ishibuchi, Moga: Multi-objective genetic algorithms, in:
Evolutionary Computation, 1995., IEEE International Conference on,
Vol. 1, IEEE, 1995, p. 289.
[3] D. W. Corne, N. R. Jerram, J. D. Knowles, M. J. Oates, Pesa-ii: regionbased selection in evolutionary multiobjective optimization, in: Conference
on Genetic and Evolutionary Computation, 2001, pp. 283–290.
[4] E. Zitzler, M. Laumanns, L. Thiele, et al., Spea2: Improving the strength
pareto evolutionary algorithm (2001).
20

[5] J. Horn, N. Nafpliotis, D. E. Goldberg, A niched pareto genetic algorithm for multiobjective optimization, in: Evolutionary Computation,
1994. IEEE World Congress on Computational Intelligence., Proceedings
of the First IEEE Conference on, 2002, pp. 82–87 vol.1.
[6] Q. Zhang, H. Li, Moea/d: A multiobjective evolutionary algorithm based
on decomposition, IEEE Transactions on Evolutionary Computation 11 (6)
(2007) 712–731.
[7] H. Li, Q. Zhang, Multiobjective optimization problems with complicated
pareto sets, moea/d and nsga-ii, IEEE Transactions on Evolutionary Computation 13 (2) (2009) 284–302.
[8] H.-L. Liu, F. Gu, Q. Zhang, Decomposition of a Multiobjective Optimization Problem Into a Number of Simple Multiobjective Subproblems, IEEE
Transactions on Evolutionary Computation 18 (3) (2014) 450–455.
[9] X. Cai, Y. Li, Z. Fan, Q. Zhang, An External Archive Guided Multiobjective Evolutionary Algorithm Based on Decomposition for Combinatorial Optimization, IEEE Transactions on Evolutionary Computation 19 (4)
(2015) 508–523.
[10] X. Cai, Z. Yang, Z. Fan, Q. Zhang, Decomposition-Based-Sorting
and Angle-Based-Selection for Evolutionary Multiobjective and ManyObjective Optimization, IEEE Transactions on Cybernetics PP (99) (2016)
1–14.
[11] E. Zitzler, S. Künzli, Indicator-based selection in multiobjective search,
Lecture Notes in Computer Science 3242 (2004) 832–842.
[12] N. Beume, B. Naujoks, M. Emmerich, Sms-emoa: Multiobjective selection based on dominated hypervolume, European Journal of Operational
Research 181 (3) (2007) 1653–1669.
[13] J. Bader, E. Zitzler, Hype: an algorithm for fast hypervolume-based manyobjective optimization., Evolutionary Computation 19 (1) (2011) 45.
[14] S. Jiang, J. Zhang, Y.-S. Ong, A. N. Zhang, P. S. Tan, A Simple and
Fast Hypervolume Indicator-Based Multiobjective Evolutionary Algorithm,
IEEE Transactions on Cybernetics 45 (10) (2015) 2202–2213.
[15] X. Cai, Z. Hu, Z. Fan, A novel memetic algorithm based on invasive weed
optimization and differential evolution for constrained optimization, Soft
Computing 17 (10) (2013) 1893–1910.
[16] Z. Hu, X. Cai, Z. Fan, An improved memetic algorithm using ring neighborhood topology for constrained optimization, Soft Computing 18 (10)
(2013) 2023–2041.

21

[17] C. A. C. Coello, Theoretical and numerical constraint-handling techniques
used with evolutionary algorithms: a survey of the state of the art, Computer Methods in Applied Mechanics and Engineering 191 (11–12) (2002)
1245–1287.
[18] T. P. Runarsson, X. Yao, Stochastic ranking for constrained evolutionary
optimization, IEEE Transactions on evolutionary computation 4 (3) (2000)
284–294.
[19] T. Takahama, S. Sakai, Constrained optimization by the ε constrained
differential evolution with gradient-based mutation and feasible elites, in:
Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, 2006, pp.
1–8.
[20] H. K. Singh, T. Ray, W. Smith, C-psa: Constrained pareto simulated annealing for constrained multi-objective optimization, Information Sciences
180 (13) (2010) 2499–2513.
[21] K. Deb, D. Kalyanmoy, Multi-Objective Optimization Using Evolutionary
Algorithms, John Wiley & Sons, Inc, 2001.
[22] Q. Zhang, A. Zhou, S. Zhao, P. N. Suganthan, W. Liu, S. Tiwari, Multiobjective optimization test instances for the cec 2009 special session and
competition, University of Essex, Colchester, UK and Nanyang technological University, Singapore, special session on performance assessment of
multi-objective optimization algorithms, technical report 264.
[23] K. Miettinen, Nonlinear multiobjective optimization, volume 12 of international series in operations research and management science (1999).
[24] M. Asafuddoula, T. Ray, R. Sarker, K. Alam, An adaptive constraint handling approach embedded moea/d, in: Evolutionary Computation, 2012,
pp. 1–8.
[25] M. A. Jan, R. A. Khanum, A study of two penalty-parameterless constraint
handling techniques in the framework of MOEA/D, Applied Soft Computing 13 (1) (2013) 128–148.
[26] Z. Yang, X. Cai, Z. Fan, Epsilon constrained method for constrained multiobjective optimization problems: some preliminary results, in: Companion
Publication of the 2014 Conference on Genetic and Evolutionary Computation, 2014, pp. 1181–1186.
[27] Z. Fan, W. Li, X. Cai, H. Li, K. Hu, Q. Zhang, K. Deb, E. D. Goodman,
Difficulty adjustable and scalable constrained multi-objective test problem
toolkit, arXiv preprint arXiv:1612.07603.
[28] Z. Fan, W. Li, X. Cai, H. Huang, Y. Fang, Y. You, J. Mo, C. Wei, E. Goodman, An improved epsilon constraint-handling method in moea/d for cmops
with large infeasible regions, arXiv preprint arXiv:1707.08767.
22

[29] S. Huband, P. Hingston, L. Barone, L. While, A review of multiobjective
test problems and a scalable test problem toolkit, IEEE Transactions on
Evolutionary Computation 10 (5) (2006) 477–506.
[30] A. Osyczka, Multicriteria optimization for engineering design, in: Design
Optimization, 1985, pp. 193–227.
[31] P. A. N. Bosman, D. Thierens, The balance between proximity and diversity in multiobjective evolutionary algorithms, IEEE Transactions on
Evolutionary Computation 7 (2) (2003) 174–188.
[32] E. Zitzler, L. Thiele, Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Transactions on
Evolutionary Computation 3 (4) (1999) 257–271.

23

