A Note on Constrained Multi-Objective
Optimization Benchmark Problems
Ryoji Tanabe

Akira Oyama

Institute of Space and Astronautical Science
Japan Aerospace Exploration Agency
Email: rt.ryoji.tanabe@gmail.com

Institute of Space and Astronautical Science
Japan Aerospace Exploration Agency
Email: oyama@flab.isas.jaxa.jp

Abstract—We herein investigate the properties of widely used
constrained multi-objective optimization benchmark problems.
A number of multi-objective evolutionary algorithms (MOEAs)
for constrained multi-objective optimization problems (CMOPs)
have been proposed in the past few years. The C-DTLZ functions
and real-world-like problems (RWLPs) have frequently beenused to evaluate the performance of MOEAs on CMOPs. In
this paper, however, we show that the C-DTLZ functions andwidely used RWLPs have some unnatural problem features.
The experimental results show that an MOEA without any
constraint handling techniques (CHTs) can successfully find wellapproximated nondominated feasible solutions on the C1-DTLZ1,C1-DTLZ3, and C2-DTLZ2 functions. It is widely believed that
RWLPs are MOEA-hard problems, and finding feasible solutions
on these problems is a very difficult task. However, we show thatan MOEA without any CHTs can find feasible solutions on widelyused RWLPs, such as the speed reducer design problem, the twobar truss design problem, and the water problem. Moreover,the infeasible solution seldom simultaneously violates multiple
constraints in the RWLPs. For the above reasons, we conclude
that constrained multi-objective optimization benchmark problems require a careful reconsideration.

I. I NTRODUCTION
A constrained multi-objective continuous optimization problem (CMOP), which frequently appears in engineering problems [1], [2], [3], [4], can be formulated as follows:
minimize fi (x), i ∈ {1, ..., M }subject to gi (x) ≤ 0, i ∈ {1, ..., p}hi (x) = 0, i ∈ {p + 1, ..., N }(1)where f : S → RM is an objective function vector consistingof M conflicting objective functions, and RM is the objectivefunction space. x = (x1 , ..., xD )T is a D-dimensional solution
vector, and S = ΠD
j=1 [aj , bj ] is the bound-constrained search
space, where aj ≤ xj ≤ bj for each j ∈ {1, ..., D}.
The feasible solution satisfies p inequality constraint functions {g1 , ..., gp } and N − p equality constraint functions{h1 , ..., jN −p }. The set of all feasible solutions is called thefeasible region F ⊆ S, whereas x 6∈ F in S is the infeasible
solution. In the same manner, the set of all infeasible solutions
is called the infeasible region F.
For the N inequality and equality constraint functions
in Equation (1), the constraint violation value ci (x), i ∈{1, ..., N } of the solution x can be defined as follows:(
max(0, gi (x)),
ci (x) =max(0, |hi (x) − δ|),i ∈ {1, ..., p}i ∈ {p + 1, ..., N }(2)where the tolerance value δ is generally used for relaxing theequality constraints to the inequality constraints, and δ should
be set to a sufficientlyPsmall value (e.g., δ = 10−6 ). If theNsolution x is feasible, i=1 ci (x) = 0.
For x1 , x2 ∈ F, we say that x1 dominates x2 and denote
1x ≺ x2 if and only if fi (x1 ) ≤ fi (x2 ) for all i ∈ {1, ..., M }and fi (x1 ) < fi (x2 ) for at least one index i. x∗ is a Pareto
optimal solution if there exists no x ∈ F such that x ≺ x∗ .
f (x∗ ) is also called a Pareto optimal objective function vector.
The set of all x∗ is the Pareto optimal solution set (PS), andthe set of all f (x∗ ) is the Pareto frontier (PF). The goal of
CMOPs is to find a set of nondominated feasible solutions
that are well-distributed and close to the PF in the objectivefunction space.
A multi-objective evolutionary algorithm (MOEA) is oneof most promising approaches for solving (C)MOPs [5].
Since MOEAs use a set of individuals (solutions of a given
problem) for the search, it is possible that they can findgood nondominated feasible solutions in a single run. Unfortunately, as pointed out in [6], the evolutionary computation
community has focused primarily on studies of MOEAs forunconstrained or bound-constrained MOPs, and the numberof studies on CMOPs is much smaller. However, a number ofnovel, efficient MOEAs for CMOPs has been proposed in thepast few years. Recently proposed representative MOEAs for(C)MOPs include NSGA-III [7], U-NSGA-III [8], I-DBEA[9], MOEA/DD [10], and RVEA [11]. Surrogate-assisted
MOEAs for CMOPs have also been studied [12].
In general, the performance of MOEAs (and EAs) is difficult
to evaluate theoretically and thus is instead evaluated experimentally through computational simulation. Suppose that
we apply an MOEA to a specific real-world problem andevaluate its performance. In this case, reproducing experiments
conducted by other researchers is often very difficult because
the computational simulation of real-world problems often
requires special hardware or software. Therefore, artificiallydesigned benchmark functions have been widely used toevaluate the performance of MOEAs.

Typical constrained multi-objective benchmark functions
include the SRN function [13], the TNK function [14], theOSY function [15], the CTP functions [16], and the CF
functions [17]. However, most of these functions are twoobjective CMOPs, in which M cannot be set to an arbitrary
number. In other words, the benchmark functions describedabove are not suitable for evaluating the scalability of MOEAs
with respect to M . On the other hand, the number of objectivesof the recently proposed C-DTLZ functions [7] can be set
to an arbitrary number, where the C-DTLZ functions areextended variants of the DTLZ functions [18]. Therefore, the
C-DTLZ functions have frequently been used to evaluate theperformance of MOEAs in recent studies [7], [8], [10], [11],[12]. While all of the benchmark functions described above
are artificially designed functions, real-world-like problems(RWLPs) have also been used in comparative studies. Typical
RWLPs include the two-bar truss design problem [19], thecar side impact problem [7], and the water problem [20]. It
is widely believed that finding feasible solutions for RWLPs
is a very difficult task because most RWLPs have many
complex constraints. Thus, RWLPs have been considered to
be challenging, difficult problems for MOEAs. In summary,
there are a number of benchmark problems for evaluating
the performance of MOEAs on CMOPs. However, as far as
we know, their properties have been poorly investigated, and,with some few exceptions (e.g., [16], [21]), their suitability as
benchmark problems for MOEAs has barely been discussed.
In this paper, we investigate the properties of the C-DTLZ
functions and widely used RWLPs, and show that they havesome issues. For the C-DTLZ functions, we demonstratethat an MOEA without any constraint handling techniques(CHTs) can find well-approximated nondominated feasible
solutions for the C1-DTLZ1, C1-DTLZ3, and C2-DTLZ2
functions. As mentioned above, many researchers in the evolutionary computation community have considered RWLPs to
be MOEA-hard problems, and finding feasible solutions tosuch problems is a difficult task. However, the experimental
results obtained in this paper reveal that an MOEA without
any CHTs can find feasible solutions for widely used RWLPs.
Nevertheless, infeasible solutions often simultaneously violate
multiple constraints for the widely used RWLPs. For thesereasons, although the C-DTLZ functions and RWLPs havefrequently been used to evaluate the performance of MOEAs
in recent studies [7], [8], [10], [11], [12], they may require
careful reconsideration.
The remainder of this paper is organized as follows. Section
II introduces typical constrained multi-objective benchmark
problems. Section III describes the experimental settings, andwe investigate the properties of constrained multi-objective
benchmark problems in Section IV. Finally, Section V concludes this paper and discusses our future work.
II. R EVIEW OF CONSTRAINED MULTI - OBJECTIVE
OPTIMIZATION BENCHMARK PROBLEMS

Table I shows some properties of typical constrained multiobjective optimization benchmark problems described in thisTABLE I: Properties of typical constrained multi-objective
optimization benchmark problems (the number of objectives
M , the number of constraint functions N , the dimensionality
D, and the feasibility ratio). The feasibility ratio of the search
space (i.e., |F|/|S|) was experimentally estimated by calculating the percentage of feasible solutions in 105 uniformly
randomly generated solutions, as in [22], [23].
ProblemM

N

D

Feasibility ratio

SRN

2

2

2

0.08

TNK

2

2

2

0.03

OSY

2

6

6

0.02

C1-DTLZ1≥2

1

M +k−10.0

C1-DTLZ3≥2

1

M +k−10.0

C2-DTLZ2≥2

1

M +k−1

0.02

C3-DTLZ1≥2

M

M +k−1

0.5

C3-DTLZ4≥2

M

M +k−1

0.12

fTBTD

2

3

3

0.0

fSRD

2

11

7

0.043

fDBD

2

5

4

0.319

fWB

2

4

4

0.058

fCSI

3

10

7

0.181

fSPD

3

9

6

0.026

fW

5

7

3

0.920

section. It is widely believed that the feasibility ratio represents
the difficulty of finding feasible solutions [22], [23]. For details
on each CMOP in Table I, see the corresponding paper.
The SRN function [13], the TNK function [14], and the
OSY function [15] are among the most widely used benchmark
functions. These three functions were proposed in 1994 ∼1995 and have been used in numerous studies [24], [25], [23],[26]. However, Deb et al. pointed out that these functions havethe following three issues: the dimensionality D is too small,finding good solutions is not so difficult, and the difficulty andcomplexity of optimization cannot be tuned [16].
In order to address the above issues, Deb et al. proposed
the CTP functions [16]. The CTP can be considered to be a
general framework for constructing novel constrained multiobjective optimization benchmark problems. Various benchmark functions can be generated using the CTP framework. In[16], seven CTP functions (CTP1, ..., CTP7) were designed.
The CTP framework was also used for constructing the CF
functions [17] for the IEEE CEC2009 MOEA Competition1 .
Very recently, Li et al. proposed more difficult variants of the
CTP functions [21]. Unfortunately, most of the CTP functions
described above are two-objective CMOPs and are not suitable
1 http://dces.essex.ac.uk/staff/zhang/moeacompetition09.htm

for evaluating the scalability of MOEAs with respect to M 2 .
In [7], Jain and Deb propose five C-DTLZ functions. The
C-DTLZ functions are extended variants of the DTLZ functions [18] for benchmarking MOEAs for CMOPs. Unlike theclassical benchmark functions described above, the number ofobjectives of the C-DTLZ functions can be set to an arbitrary
number, and thus they have frequently been used in recent
comparative studies [7], [10], [11], [12]. According to thecharacteristics of the feasible region in the objective function
space, the C-DTLZ functions are classified into the following
three categories: Type-1, Type-2, and Type-3 problems.
Figure 1 shows the feasible or infeasible region of each
C-DTLZ function in the objective space (M = 2). The
C2-DTLZ2 and C3-DTLZ4 functions are unimodal, and theC1-DTLZ1, C1-DTLZ3, and C3-DTLZ1 functions are multimodal. In Type-1 constraint C-DTLZ functions (C1-DTLZ∗),
the shape and position of the PF are the same as in theoriginal DTLZ functions, but there is “an infeasible barrier”
that prevents MOEAs from approaching the PF. Thus, thepopulation must overcome this infeasible barrier to converge
to the true PF, which can be considered a difficult task.
In Type-2 constraint C-DTLZ functions (C2-DTLZ∗), partof the PF becomes the infeasible region by introducing a
constraint. In other words, the shape of the PF of C2-DTLZ∗
is discontinuous. In general, handling the discontinuously of
the PF is difficult for MOEAs. Note that the constraint isnevertheless introduced, and the position of the PF of C1DTLZ∗ and C2-DTLZ∗ remains unchanged from the original
DTLZ functions. On the other hand, in Type-3 constraint CDTLZ functions (C3-DTLZ∗), the region of the original PF
is made infeasible by introducing M linear constraints, and
the PF of C3-DTLZ∗ is a boundary line between the feasible
and infeasible region. Note that most constraint multi-objective
benchmark functions such as the SRN, TNK, OSY, and the
CTP functions (except for the CTP7 function) can be classified
as Type-3 constraint functions.
RWLPs have also frequently been used for comparative
studies [19], [27], [23], [26], [7]. Typical RWLPs include thetwo-bar truss design problem (fTBTD ) [19], [26], the speedreducer design problem (fSRD ) [19], [26], the disc brakedesign problem (fDBD ) [19], [26], the welded beam problem(fWB ) [28], [26], the car side-impact problem (fCSI ) [7], theship parametric design problem (fSPD ) [29], [27], and thewater problem (fW ) [20], [7]. It is generally believed thatfinding feasible solutions for RWLPs is a very difficult task
because most RWLPs have many complex constraints [7].
In fact, as shown in Table I, for most RWLPs, N is muchlarger than that for the artificially designed functions (e.g.,fCSI has 11 constraints), and the feasibility ratios of some
RWLPs are low. Therefore, RWLPs have been considered to
be challenging, difficult problems for MOEAs.

2 The idea of constructing CTP functions with M ≥ 3 is briefly introducedin [16], but to the best of our knowledge, they have never been realized.

(a) C1-DTLZ1(b) C1-DTLZ3(c) C2-DTLZ2(d) C3-DTLZ1(e) C3-DTLZ4

Fig. 1: Feasible or infeasible region of each C-DTLZ function in theobjective space (M = 2). All figures were derived from [7].

III. E XPERIMENTAL SETTINGSIn this paper, we investigate the properties of the two groupsof constrained multi-objective optimization benchmark problems (C-DTLZ functions and RWLPs) described in Section II.
Here, we describe the experimental settings. The results will
be discussed in Section IV.
A. Problems and performance evaluation methods
We used the two- and three-objective C-DTLZ functions3 .
As suggested in [7], the position parameter k was set to k = 10
for the C1-DTLZ3 and C2-DTLZ2 functions and to k = 5 forthe remaining functions. We also used the seven RWLPs in
Table I.
We used the hypervolume (HV) indicator [30] for evaluating
the quality of a set of obtained nondominated solutions A.
Before calculating the HV value, the objective function vector
3 We used the source code of the C-DTLZ functions implemented by Li.
The code was downloaded from http://www.cs.bham.ac.uk/∼likw/.

f (x) of each x ∈ A was normalized using the ideal point
and the nadir point. The ideal point and the nadir point for
all problems were experimentally estimated using all solutions
obtained by all methods for all 101 runs. The reference point
for calculating HV was set to (1.1, ..., 1.1)T . Note that we used
only the feasible solutions dominating the reference point for
the HV calculation.
Almost all previous studies (e.g., [7], [8], [10], [9], [11],[12]) used nondominated solutions in the population at theend of the search for calculating the HV value. In general, an
MOEA maintains (nondominated) solutions obtained during
the search process in the population, but the population size
is limited. When using the nondominated solutions in the
population for the HV calculation, a monotonic increase in
HV over time (= the number of function evaluations) cannot
be ensured [31], [32]. Thus, we cannot exactly evaluate theperformance of MOEAs using such traditional evaluation
methodology.
In order to address this issue, we used an unbounded
external archive as suggested in [32], [33]. The unbounded
external archive stores all nondominated feasible solutions
found during the search process and can be introduced into
any MOEAs without any changes to their original algorithms[32], [33]. Solutions in the unbounded external archive are notused in the search of an MOEA. When using the unbounded
external archive, the above-described issue can be addressed[31], [32]. Since, in practice, users of MOEAs want to obtain
nondominated solutions whenever possible, we believe thatthe benchmark methodology using the unbounded externalarchive is more practical. The unbounded external archive isalso used in the recently proposed BBOB-biobj benchmark
suite [34] in the COCO framework4 . When the number ofobtained nondominated solutions in the unbounded externalarchive is too large, a method that selects only representative
solutions (e.g., [35]) should be used.
B. MOEAs
We analyzed the performance of five variants of (C)NSGAII [24] because it is one of the most widely used MOEAs
for CMOPs. CNSGA-II is the NSGA-II algorithm using
the constraint-domination ≺const , instead of the Paretodomination ≺ described in Section I. For x1 , x2 ∈ S, we
say that x1 constraint-dominates x2 and denote x1 ≺const x2
if the two vectors satisfy one of the following three conditions:(1) x1 ∈ F and x2 6∈ F, (2) x1 , x2 6∈ F and C(x1 ) < C(x2 ),and (3) x1 , x2 ∈ F and x1 ≺ x2 , where C is a constraint
violation function summarizing how the solution x violates
N constraints in Equation (1).
We investigate the performance of the following five(C)NSGA-II algorithms using different types of C:
1. NSGA-II: The NSGA-II using ≺, rather than ≺const .
2. CNSGA-II-S: The CNSGA-II using the sum of the constraint violation values {cP1N(x), ..., cN (x)} defined in Equation(2) as C, i.e., C(x) = i=1 ci (x).
4 http://coco.gforge.inria.fr/

3. CNSGA-II-NS: The CNSGA-II using the normalized sumPof the constraint violation values as C, i.e.,NC(x) = i=1 (ci (x) − cmin)/(cmax− cmin), where cmin
=
i
i
i
i
max
miny ∈P {ci (y)}, ci= maxy ∈P {ci (y)}, and P is the
population.
4. CNSGA-II-CD: The CNSGA-II using the Paretodominance relationship in the constraint violation value space
RN [36] as C.
5. CNSGA-II-RR: The CNSGA-II using the relative ranking(RR) [27] as C.
For details on CD and RR, see [36], [27], respectively.
CNSGA-II-S is identical to the original “CNSGA-II” proposedin [24] and most typical variant in the five (C)NSGA-II algorithms. The aim of the normalization procedure of CNSGAII-NS and the sophisticated techniques of CNSGA-II-CD and
CNSGA-II-RR is to handle the different scale of the constraint
violation values. For CNSGA-II-CD and CNSGA-II-RR, if thetwo compared individuals x1 and x2 have the same rank level,
then the sum of the constraint violation values, as in CNSGAII-S, is used as a tie-breaking method. Note that, as far as
we know, no previous study analyzed the impact of C on theperformance of CNSGA-II, in isolation.
We used the jMetal5 source code of NSGA-II. We used
the SBX crossover and polynomial mutation as in the original
CNSGA-II paper [24]. As suggested in [24], we set the control
parameters of the variation operators as follows: pc = 1.0,
ηc = 20, pm = 1/D, and ηm = 20. The population size of
the CNSGA-II algorithms was set to 100. For handling thedifferent scale of the objective function values, we introduced
the normalization procedure of the objective function values
to all five algorithms. The maximum number of function
evaluations was set to 5 × 104 , and 101 independent runs were
performed. Owing to a sufficiently large sample size, statisticaltests are not necessary.
IV. E XPERIMENTAL RESULTS AND DISCUSSION
Here, we report and discuss the experimental results for thefive (C)NSGA-II algorithms for the five C-DTLZ functions
and the seven RWLPs listed in Table I. First, we describe theresults for the five C-DTLZ functions and seven RWLPs in
Sections IV-A and IV-B, respectively. Finally, in Section IV-C,
we generally discuss the experimental results for the C-DTLZ
functions and RWLPs.
A. Results for the five C-DTLZ functions
Figure 2 shows the performance comparison of the five(C)NSGA-II algorithms for the two-objective C-DTLZ functions. Due to space constraints, we do not show the results forthree objective functions, but they are similar to those shownin Figure 2. Note that the behavior of the four CNSGA-II
algorithms for the C1-DTLZ1, C1-DTLZ3, and C2-DTLZ2
functions is exactly the same, because N = 1 in these
problems.
For the Type-1 functions, CNSGA-II performs well on the
C1-DTLZ1 function for a number of function evaluations
5 The code was downloaded from http://jmetal.sourceforge.net/

0.8

C1-DTLZ1
NSGA-II

0.7
0.6

CNSGA-II-SMedian hypervolume values

0.5

0.45

NSGA-II

0.35

CNSGA-II-S

0.30

CNSGA-II-NS 0.25

0.4

CNSGA-II-NS

0.20

0.3

CNSGA-II-CD 0.15

0.2

0.10

CNSGA-II-RR

0.1
0.0
0

10000 20000 30000 40000 50000

1.0

C3-DTLZ1CNSGA-II-S

0.8

CNSGA-II-NS

0.6

CNSGA-II-CD
CNSGA-II-RR

0.05
0.00
0

10000 20000 30000 40000 50000

0.68

C3-DTLZ4

0.45

C2-DTLZ2
NSGA-II

0.40

CNSGA-II-S

0.35

CNSGA-II-NS

0.30

CNSGA-II-CD

0.25
0.20
0

CNSGA-II-RR

10000 20000 30000 40000 50000

CNSGA-II-NS

0.66
0.64

CNSGA-II-S

0.62

CNSGA-II-CD 0.60

CNSGA-II-CD

0.58

0.4

CNSGA-II-RR 0.56

0.2
0.0
0

C1-DTLZ3

0.40

NSGA-II

10000 20000 30000 40000 50000

CNSGA-II-RR

0.54

NSGA-II

0.52
0.50
0

10000 20000 30000 40000 50000

Number of function evaluations

Fig. 2: Convergence behavior of the five (C)NSGA-II algorithms for the five C-DTLZ functions with M = 2. The median HV values acrossall the 101 runs are plotted.

(FEvals) of approximately 1.2 × 104 . However, for FEvals= 1.2 × 104 ∼ 2.3 × 104 , the four CNSGA-II algorithms
are clearly outperformed by NSGA-II, which does not use
any CHTs. For FEvals > 2.3 × 104 , there is no significant
difference in performance among the five algorithms.
To explain the results for the C1-DTLZ1 function,
we show the distributions of individuals in the populations of (a) CNSGA-II-S and (b) NSGA-II for FEvals ∈{7 000, 14 000, 21 000} in Figure 3. As shown in Figure 3, for
FEvals = 7 000, CNSGA-II-S converges to the feasible region
as well as the PF faster than NSGA-II. The reason for thisresult is that when all individuals in the population of CNSGAII-S are infeasible, the environmental selection of CNSGA-IIS is performed based on only the amount of the constraint
violation values (see Section III-B). In other words, when all
individuals in the population are infeasible, the algorithmic
behavior of CNSGA-II-S is identical to that of a singleobjective GA minimizing
the sum of the constraint violation
PN
values C(x) = i=1 ci (x). Due to this reason, we believethat CNSGA-II-S could find good feasible solutions fasterthan NSGA-II. However, the distribution of the individuals of
CNSGA-II is clearly biased to f2 for FEvals = 7 000. Afterfinding the feasible solutions, the population of CNSGA-II
gradually creeps towards the f1 along the PF. In summary,
CNSGA-II-S finds the feasible solutions quickly, but requires
many FEvals in order to obtain good solutions for the PF. On
the other hand, the individuals in the population of NSGAII are widely distributed when reaching the feasible region(FEvals = 14 000). For FEvals = 21 000, NSGA-II finds welldistributed feasible solutions while the population of CNSGAII-S still moves toward f1 . These are the reasons why the
HV values of NSGA-II are higher than those of the CNSGA

algorithms for FEvals = 1.2 × 104 ∼ 2.3 × 104 for the C1DTLZ1 function.
For the C1-DTLZ3 function, surprisingly, NSGA-II clearly
outperforms the four CNSGA-II algorithms at all times. The
reason for this result is that the infeasible barrier of the C1DTLZ3 function (Figure 1(b)) does not affect the search of an
MOEA without any CHTs.
For the C2-DTLZ2 function, there is no performance difference between NSGA-II and CNSGA-II. In the C2-DTLZ2
function, part of the PF is the infeasible region, but theposition of the PF remains unchanged. Recall that, in thisexperiment, we used the unbounded external archive that stores
all nondominated feasible solutions found during the search
process. The shape of the PF of the C2-DTLZ2 function
is disconnected, and it is widely believed that handling thediscontinuities in the PF is difficult [7]. However, whenusing the unbounded external archive, the distribution of theindividuals in the population is not relevant to the HV value,so the effect of discontinuity might not be so significant. The
results for the CTP7 function [16] are also shown in Figure 4.
We selected the CTP7 function because part of its PF is theinfeasible region, and it can be classified as a Type-2 constraintfunction. As expected, the results for the CTP7 function are
similar to the results for the C2-DTLZ2 function.
Finally, although unsurprising, the four CNSGA-II algorithms perform significantly better than NSGA-II for the C3DTLZ1 and C3-DTLZ4 functions, especially the C3-DTLZ4
function. Although not shown here, but the poor performanceof NSGA-II was also observed for the SRN, TNK, and OSY
functions. In explaining this result, we show the distributionsof individuals in the populations of CNSGA-II-S and NSGA-II
for the C3-DTLZ4 function in Figure 5. Note that all individ-

8

0.6

7
0.5

6

f2

f2

0.4
0.3

5
4
3

0.2

2
0.1
0.0
0.0

1
0.1

0.2

f1

0.3

0.4

0
0

0.5

FEvals = 14000

0.7

1

2

3

4

f1

5

6

7

8

9

FEvals = 14000

0.7

CTP7

0.86

FEvals = 7000

9Median hypervolume values

FEvals = 7000

0.7

CNSGA-II-S

0.84
CNSGA-II-NS

0.82
0.80

CNSGA-II-CD

0.78
CNSGA-II-RR

0.76
NSGA-II

0.74
0.72
0

10000

20000

30000

40000

50000

0.6

0.5

0.5

0.4

0.4

Fig. 4: Convergence behavior of the five (C)NSGA-II algorithms for0.3

the two-objective CTP7 function. The median HV values are plotted.

f2

f2

0.6

0.3
0.2

0.2

0.1

0.1
0.1

0.2

f1

0.3

0.4

0.0
0.0

0.5

FEvals = 21000

0.7

0.5

0.4

0.4

0.3
f1

0.4

0.5

0.3

CNSGA-II-S
NSGA-II

2.0
1.5

0.3

0.2

FEvals = 50000

2.5

0.6

f2

f2

0.6

0.5

0.2

FEvals = 21000

0.7

0.6

1.0

0.2

0.1
0.0
0.0

0.1

f2

0.0
0.0

Number of function evaluations

0.1
0.1

0.2

f1

0.3

0.4

0.5

(a) CNSGA-II-S

0.0
0.0

0.5
0.1

0.2

0.3
f1

0.4

0.5

0.6

(b) NSGA-II

Fig. 3: Distributions of individuals in the populations of (a) CNSGAII-S and (b) NSGA-II for the two-objective C1-DTLZ1 function ina single run (FEvals ∈ {7 000, 14 000, 21 000}). The red and black
circles represent the infeasible and feasible solutions respectively. The
bold blue line indicates the PF, and the shaded region indicates thefeasible region.

uals of CNSGA-II-S and NSGA-II are feasible and infeasible,
respectively. For the C3-DTLZ4 function, the original PF is
infeasible, and its PF is a boundary line between the feasible
and infeasible region. For this reason, in Figure 5, NSGAII, which does not use any CHTs, passes the true PF andconverges to the original PF. As a result, NSGA-II fails tofind good feasible solutions.
B. Results for the seven RWLPs
Figure 6 shows the performance comparisons of the five(C)NSGA-II algorithms on the six RWLPs (fTBTD , fWB ,fSRD , fCSI , fSPD , and fW ). We do not show the result for
fDBD , which are similar to the results for fSRD .
As shown in Figure 6, the results for the RWLPs are similar
to the results for the Type-3 constraint C-DTLZ functions.
Namely, NSGA-II performs significantly worse than the four
CNSGA-II algorithms, especially for fDBD and fSPD . For
fWB , NSGA-II achieves good feasible solutions only for
FEvals = 103 . We believe that the reason for the poor
performance of NSGA-II for the RWLPs is the same as thatfor the C3-DTLZ4 function described in Section IV-A. Notethat NSGA-II finds the feasible solutions for all seven RWLPs

0.0
0.0

0.5

1.0

f1

1.5

2.0

2.5

Fig. 5: Distributions of individuals in the populations of CNSGA-IIS and NSGA-II for the two-objective C3-DTLZ4 function in a single
run (FEvals = 50 000). All individuals of CNSGA-II-S and NSGA-II
are feasible and infeasible, respectively.

while many researchers consider these problems to be difficult
for finding the feasible solutions. Moreover, it is widelybelieved that well-designed CHTs are needed to handle thedifferent scale of each constraint violation value in {c1 , ..., cN }for the RWLPs [36], [27], [23], [7]. However, in this study,
we compared the four CNSGA-II algorithms (CNSGA-IIS, CNSGA-II-NS, CNSGA-II-CD, and CNSGA-II-RR), but
contrary to intuition, there is no significant difference between
their performance. CNSGA-II-S uses the most simple C, andso it should perform worse than the remaining CNSGA-II
algorithms using the more sophisticated C.
To analyze the results, we show the cumulative number of
constraints that the infeasible solutions generated by CNSGAII-S simultaneously violate for fSRD , fCSI , and fW in Figure 7. As shown in Figure 7, the number of constraintfunctions that are simultaneously violated can be found out.
For example, for fSRD , until FEvals = 8 000, CNSGA-IIS generated about the 1 700 and 300 infeasible solutions
that simultaneously violate one and two constraint functions
respectively. The infeasible solutions generated by CNSGAII-S never simultaneously violated more than four constraints
for fSRD . As shown in Table I, there are the 11, 10, and sevenconstraints in fSPD , fCSI , and fW , respectively. Handling

1.2

fTBTD (Two bar truss design, M = 2)
CNSGA-II-S

1.0

Median hypervolume values

0.8
0.6

1.08

CNSGA-II-RR

CNSGA-II-NS 1.04

CNSGA-II-RR 1.10

CNSGA-II-NSCNSGA-II-NS 1.08

CNSGA-II-S

NSGA-II

NSGA-II

NSGA-II

1.02
1.00
0.98
0.96
0

10000 20000 30000 40000 50000

fCSI (Car side impact, M = 3)f

CNSGA-II-NS

0.85

CNSGA-II-CD
CNSGA-II-S

0.70

1.06

10000 20000 30000 40000 50000

0.85 SPD0(Ship parametric design, M = 3)
CNSGA-II-CD

0.80

CNSGA-II-RR 0.75

0.75

0.70
0.65
0.60

0.60
0

NSGA-II

10000 20000 30000 40000 50000

CNSGA-II-S

0.86

CNSGA-II-NS 0.82

CNSGA-II-CD

NSGA-II

0.45
0fW (Water, M = 5)

CNSGA-II-NSCNSGA-II-S

0.50

10000 20000 30000 40000 50000

0.88

CNSGA-II-RR 0.84

0.55
0.65

CNSGA-II-CD

1.12

0.2

0.80

fWB (Welded beam, M = 2)

1.14

CNSGA-II-S

CNSGA-II-RR

0.90

CNSGA-II-CD

CNSGA-II-CD 1.06

0.4

0.0
0

fDBD (Disc brake design, M = 2)

1.10

0.80

CNSGA-II-RR

0.78

NSGA-II

0.76
0.74
0

10000 20000 30000 40000 50000

10000 20000 30000 40000 50000

Number of function evaluations

Fig. 6: Convergence behavior of the five (C)NSGA-II algorithms for the six RWLPs (fTBTD , fWB , fSRD , fCSI , fSPD , and fW ). The median

Cumulative number of violations

HV values across all 101 runs are plotted.

2500

fSRD (Speed reducer design, M = 2)
1

2000

450

fCSI (Car side impact, M = 3)
1

400

2

2

300

3

500

250
3

150

2000

4000

6000

8000

10000

0
0

3

300
200

100

4

50
0
0

2

500
400

200

1000

1

600

350

1500

fW (Water, M = 5)

700

2000

4000

6000

8000

10000

Number of function evaluations

4

100
0
0

2000

4000

6000

8000

10000

Fig. 7: Cumulative number of constraints that the infeasible solutions generated by CNSGA-II-S simultaneously violate.

many constraints and finding good feasible solutions for suchproblems appears to be difficult. However, as shown in Figure
7, most solutions obtained during the search process arefeasible, and, in many cases, the infeasible solutions violate
only one constraint. This is the reason why the four CNSGAII algorithms perform similarly to each other on the seven
RWLPs in Figure 6. Although there are many constraints inthe seven RWLPs, finding the feasible solutions appears to berelatively easy.
C. Overall discussion of the experimental results for the CDTLZ functions and RWLPs
Based on the experimental results described in Section IV-A,
we can say that an MOEA without any CHTs (e.g., NSGA-II)
can find well-approximated feasible solutions for the Type1 and Type-2 constraint functions. Since the position of the
PF of the Type-1 and Type-2 functions is unchanged fromthe original functions, improving the solution according to theobjective function values is identical to minimizing the con-straint violation values (i.e., searching the feasible solutions).
The Type-1 and Type-2 constraint functions should probably
not be used for evaluating the performance of MOEAs for
CMOPs in light of our experimental results.
RWLPs have been considered to be challenging, difficult
problems [7]. However, in Section IV-B, we showed that even
NSGA-II without any CHTs can easily find feasible solutions
for the seven RWLPs. Moreover, the CNSGA-II algorithms
with the simple C (i.e., CNSGA-II-S) and the more sophisticated C (i.e., CNSGA-II-NS, CNSGA-II-CD, and CNSGA-IIRR) perform similarly to each other for the RWLPs. Therefore,
RWLPs might be not as difficult as researchers expected.
We believe that finding good feasible solutions for actual
real-world problems is a difficult task due to their complex
constraints [4]. In other words, finding good feasible solutions
for real-world CMOPs should be more difficult than finding
good feasible solutions for the C-DTLZ functions or widelyused RWLPs. More complex, difficult benchmark problems are
required to evaluate the performance of MOEAs for CMOPs.

V. C ONCLUSION
We have analyzed the properties of the C-DTLZ functions
and the seven RWLPs listed in Table I. The experimental
results revealed that the Type-1 and Type-2 C-DTLZ functions have some critical issues and may be inappropriate forbenchmarking MOEAs for CMOPs. Researchers in the evolutionary computation community had considered RWLPs to bechallenging problems due to their numerous constraints, but
we showed that RWLPs might be not as difficult as they had
believed. In light of our experimental results, it is possible that
constrained multi-objective optimization benchmark problems
require careful reconsideration.
There is a great deal of room for designing novel, appropriate problems for benchmarking MOEAs for CMOPs.
Among the five C-DTLZ functions, Type-3 functions appear
to be one of the most appropriate types of benchmark problems. Therefore, we believe that constructing novel benchmark
problems based on Type-3 DTLZ functions is a promising
future direction. The PF of the Type-1 and Type-2 C-DTLZ
functions is identical to that of the original DTLZ functions,which causes the problem described in this paper. However,
the region of the PF of the Type-1 and Type-2 functions canbe made infeasible by adding the properties of the Type-3functions to them. We will construct composite functions of
the Type-3 functions and the Type-1 and Type-2 functions.
ACKNOWLEDGMENT
This research is supported by the HPCI System Research
Project “Research and development of multiobjective design
exploration and high-performance computing technologies fordesign innovation” (Project ID:hp160203).
R EFERENCES[1] H. K. Singh, T. Ray, and R. A. Sarker, “Optimum Oil Production
Planning Using Infeasibility Driven Evolutionary Algorithm,” Evol.
Comput., vol. 21, no. 1, pp. 65–82, 2013.
[2] S. Z. Martı́nez, A. A. Montaño, and C. A. C. Coello, “Constrained multiobjective aerodynamic shape optimization via swarm intelligence,” in
GECCO, 2014, pp. 81–88.
[3] H. K. Singh, K. Alam, and T. Ray, “Use of Infeasible Solutions During
Constrained Evolutionary Search: A Short Survey,” in ACALCI, 2016,
pp. 193–205.
[4] A. K. Sharma, R. Datta, M. Elarbi, B. Bhattacharya, and S. Bechikh,“Practical Applications in Constrained Evolutionary Multi-objective
Optimization,” in Recent Advances in Evolutionary Multi-objective Optimization, 2017, pp. 159–179.
[5] B. Li, J. Li, K. Tang, and X. Yao, “Many-Objective Evolutionary
Algorithms: A Survey,” ACM Comput. Surv., vol. 48, no. 1, p. 13, 2015.
[6] E. Mezura-Montes and C. A. C. Coello, “Constraint-handling in natureinspired numerical optimization: Past, present and future,” Swarm andEvol. Comput., vol. 1, no. 4, pp. 173–194, 2011.
[7] H. Jain and K. Deb, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach,Part II: Handling Constraints and Extending to an Adaptive Approach,”
IEEE TEVC, vol. 18, no. 4, pp. 602–622, 2014.
[8] H. Seada and K. Deb, “A Unified Evolutionary Optimization Procedurefor Single, Multiple, and Many Objectives,” IEEE TEVC, vol. 20, no. 3,
pp. 358–369, 2016.
[9] M. Asafuddoula, T. Ray, and R. A. Sarker, “A Decomposition-Based
Evolutionary Algorithm for Many Objective Optimization,” IEEE TEVC,
vol. 19, no. 3, pp. 445–460, 2015.
[10] K. Li, K. Deb, Q. Zhang, and S. Kwong, “An Evolutionary ManyObjective Optimization Algorithm Based on Dominance and Decomposition,” IEEE TEVC, vol. 19, no. 5, pp. 694–716, 2015.

[11] R. Cheng, Y. Jin, M. Olhofer, and B. Sendhoff, “A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization,”
IEEE TEVC, vol. 20, no. 5, pp. 773–791, 2016.
[12] T. Chugh, K. Sindhya, K. Miettinen, J. Hakanen, and Y. Jin, “On
Constraint Handling in Surrogate-Assisted Evolutionary Many-Objective
Optimization,” in PPSN, 2016, pp. 214–224.
[13] N. Srinivas and K. Deb, “Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,” Evol. Comput., vol. 2, no. 3, pp.
221–248, 1994.
[14] M. Tanaka, H. Watanabe, Y. Furukawa, and T. Tanino, “GA-based
decision support system for multicriteria optimization,” in IEEE SMC,
1995, pp. 1556–1561.
[15] A. Osyczka and S. Kundu, “A new method to solve generalized
multicriteria optimization problems using the simple genetic algorithm,”
Stru. and Multi. Opt., vol. 10, no. 2, pp. 94–99, 1995.
[16] K. Deb, A. Pratap, and T. Meyarivan, “Constrained Test Problems forMulti-objective Evolutionary Optimization,” in EMO, 2001, pp. 284–
298.
[17] Q. Zhang, A. Zhou, S. Zhao, P. N. Suganthan, W. Liu, and S. Tiwari,“Multiobjective optimization test instances for the CEC 2009 special
session and competition,” Univ. of Essex, Tech. Rep. CES-487, 2008.
[18] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable multiobjective optimization test problems,” in IEEE CEC, 2002, pp. 825–830.
[19] C. A. C. Coello and G. T. Pulido, “Multiobjective structural optimization
using a microgenetic algorithm,” Stru. and Multi. Opt., vol. 30, no. 5,
pp. 388–403, 2005.
[20] T. Ray, K. Tai, and C. Seow, “An evolutionary algorithm for multiobjective optimization,” Eng. opt., vol. 33, no. 3, pp. 399–424, 2001.
[21] J. Li, Y. Wang, S. Yang, and Z. Cai, “A comparative study of constrainthandling techniques in evolutionary constrained multiobjective optimization,” in IEEE CEC, 2016, pp. 4175–4182.
[22] S. Venkatraman and G. G. Yen, “A Generic Framework for Constrained
Optimization Using Genetic Algorithms,” IEEE TEVC, vol. 9, no. 4, pp.
424–435, 2005.
[23] Y. G. Woldesenbet, G. G. Yen, and B. G. Tessema, “Constraint Handlingin Multiobjective Evolutionary Optimization,” IEEE TEVC, vol. 13,
no. 3, pp. 514–525, 2009.
[24] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist
multiobjective genetic algorithm: NSGA-II,” IEEE TEVC, vol. 6, no. 2,
pp. 182–197, 2002.
[25] P. Hingston, L. Barone, S. Huband, and R. L. While, “Multi-level
Ranking for Constrained Multi-objective Evolutionary Optimisation,” in
PPSN, 2006, pp. 563–572.
[26] W. Gong, Z. Cai, and Z. Li, “An efficient multiobjective differential
evolution algorithm for engineering design,” Stru. and Multi. Opt.,
vol. 38, no. 2, pp. 137–157, 2009.
[27] H. K. Singh, A. Isaacs, T. Ray, and W. Smith, “Infeasibility Driven
Evolutionary Algorithm (IDEA) for Engineering Design Optimization,”in AI2008, 2008, pp. 104–115.
[28] T. Ray and K. M. Liew, “A swarm metaphor for multiobjective design
optimization,” Eng. opt., vol. 34, no. 2, pp. 141–153, 2002.
[29] M. G. Parsons and R. L. Scott, “Formulation of Multicriterion Design
Optimization Problems for Solution With Scalar Numerical Optimization
Methods,” J. Ship Research, vol. 48, no. 1, pp. 61–76, 2004.
[30] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. da Fonseca, “Performance assessment of multiobjective optimizers: an analysis
and review,” IEEE TEVC, vol. 7, no. 2, pp. 117–132, 2003.
[31] M. López-Ibáñez, J. D. Knowles, and M. Laumanns, “On Sequential
Online Archiving of Objective Vectors,” in EMO, 2011, pp. 46–60.
[32] A. Radulescu, M. López-Ibáñez, and T. Stützle, “Automatically Improving the Anytime Behaviour of Multiobjective Evolutionary Algorithms,”
in EMO, 2013, pp. 825–840.
[33] D. Brockhoff, T. Tran, and N. Hansen, “Benchmarking Numerical
Multiobjective Optimizers Revisited,” in GECCO, 2015, pp. 639–646.
[34] T. Tusar, D. Brockhoff, N. Hansen, and A. Auger, “COCO: The Biobjective Black Box Optimization Benchmarking (bbob-biobj) Test
Suite,” CoRR, vol. abs/1604.00359, 2016.
[35] H. Ishibuchi, Y. Sakane, N. Tsukamoto, and Y. Nojima, “Selecting a small number of representative non-dominated solutions by a
hypervolume-based solution selection approach,” in FUZZ-IEEE, 2009,
pp. 1609–1614.
[36] A. Oyama, K. Shimoyama, and K. Fujii, “New Constraint-Handling
Method for Multi-Objective and Multi-Constraint Evolutionary Optimization,” T. JSASS, vol. 50, no. 167, pp. 56–62, 2007.