A Decomposition-based Evolutionary Algorithm
for Multi-modal Multi-objective Optimization
Ryoji Tanabe and Hisao Ishibuchi
Shenzhen Key Laboratory of Computational Intelligence, Department of Computer
Science and Engineering, Southern University of Science and Technology, China
rt.ryoji.tanabe@gmail.com, hisao@sustc.edu.cn

Abstract. This paper proposes a novel decomposition-based evolutionary algorithm for multi-modal multi-objective optimization, which is the
problem of locating as many as possible (almost) equivalent Pareto optimal solutions. In the proposed method, two or more individuals canbe assigned to each decomposed subproblem to maintain the diversity ofthe population in the solution space. More precisely, a child is assigned
to a subproblem whose weight vector is closest to its objective vector, interms of perpendicular distance. If the child is close to one of individuals that have already been assigned to the subproblem in the solution
space, the replacement selection is performed based on their scalarizing
function values. Otherwise, the child is newly assigned to the subproblem, regardless of its quality. The effectiveness of the proposed method is
evaluated on seven problems. Results show that the proposed algorithm
is capable of finding multiple equivalent Pareto optimal solutions.

1

Introduction

A multi-objective optimization problem (MOP) is the problem of finding asolution x = (x1 , ..., xD )T ∈ S that minimizes an objective function vector
f : S → RM . Here, S is the D-dimensional solution space, and RM is the
M -dimensional objective space. Usually, f consists of M conflicting objectivefunctions. A solution x1 is said to dominate x2 iff fi (x1 ) ≤ fi (x2 ) for alli ∈ {1, ..., M } and fi (x1 ) < fi (x2 ) for at least one index i. If there exists no x in
S such that x dominates x∗ , x∗ is called a Pareto optimal solution. The set of
all x∗ is the Pareto optimal solution set, and the set of all f (x∗ ) is the Pareto
front. The goal of MOPs is usually to find a set of nondominated solutions thatapproximates the Pareto front well in the objective space.
An evolutionary multi-objective optimization algorithm (EMOA) is an efficient population-based optimization method to approximate the Pareto front ofa given MOP in a single run [1]. Although several paradigms of EMOAs (e.g.,dominance-based EMOAs) have been proposed, decomposition-based EMOAs
are recently popular in the EMO community. In particular, MOEA/D [18] is
one of the most representative decomposition-based EMOAs [14].
There are multiple equivalent Pareto optimal solutions in some real-world
problems (e.g., space mission design problems [12], rocket engine design problems [7], and path-planning problems [17]). Fig. 1 explains such a situation.

Solution space

Objective space

Fig. 1: Illustration of a situation where three solutions are identical or close to eachother in the objective space but are far from each other in the solution space. This
figure was made using [8,13] as reference.

Diverse solutions are helpful for decision-making [3,11,12,13]. If two or more
solutions having (almost) the same objective vector are found, users can makea final decision according to their preference which cannot be represented by
the objective functions. For example, in Fig. 1, if xa becomes unavailable forsome reasons (e.g., materials shortages and traffic accidents), xb and xc can becandidates for the final solution instead of xa .
A multi-modal MOP (MMOP) [3,8,17] is the problem of locating as many as
possible (almost) equivalent Pareto optimal solutions. Unlike the general MOPs,
the goal of MMOPs is to find a good approximation of the Pareto-optimal solution set. For example, in Fig. 1, it is sufficient to find one of xa , xb , and xc for
MOPs, because their objective vectors are almost the same. In contrast, EMOAs
need to find all of xa , xb , and xc for MMOPs. Some EMOAs for MMOPs havebeen proposed in the literature (e.g., [3,6,12,13,17]).
While MMOPs can be found in real-world problems [7,12,17], it is likelythat most MOEA/D-type algorithms [14] are not capable of locating multiple
equivalent Pareto optimal solutions. This is because they do not have any explicit
mechanism to maintain the diversity of the population in the solution space. If
the ability to keep solution space diversity in the population is incorporated into
MOEA/D, an efficient multi-modal multi-objective optimizer may be realized.
This paper proposes a novel MOEA/D algorithm with addition and deletion operators (MOEA/D-AD) for multi-modal multi-objective optimization. In
MOEA/D-AD, the population size µ is dynamically changed during the search
process. Multiple individuals that are far from each other in the solution spacecan be assigned to the same decomposed single-objective subproblem. Only similar individuals in the solution space are compared based on their scalarizing
function values. Thus, MOEA/D-AD maintains the diversity in the population
by performing environmental selection for each subproblem among individuals
that are close to each other in the solution space.
This paper is organized as follows. Section 2 introduces MOEA/D-AD. Section 3 describes experimental setup. Section 4 presents experimental results of
MOEA/D-AD, including performance comparison and its analysis. Section 5
concludes this paper with discussions on directions for future work.

Algorithm 1: The procedure of MOEA/D-AD
t ← 1, initialize the population P = {x1 , ..., xN };i
2 for i ∈ {1, ..., N } do Assign x to the i-th subproblem;
3 while The termination criteria are not met do4µ ← |P |;5
Randomly select r1 and r2 from {1, ..., µ} such that r1 6= r2 ;6Generate the child u by recombining xr1 and xr2 ;7
Apply the mutation operator to u;
0
8
for i ∈ {1, ..., N } do di ← PD(f (u), wi );9j ← arg min {di };1i∈{1,...,N }

10
11
12
13
14
15

bwinner ← FALSE and bexplorer ← TRUE;
for x ∈ P | x has been assigned to the j-th subproblem do
if isNeighborhood(u, x) = TRUE thenbexplorer ← FALSE;
if g(u|wj ) ≤ g(x|wj ) thenP ← P \{x} and bwinner ← TRUE;

17

if bwinner = TRUE or bexplorer = TRUE thenP ← P ∪ {u} and assign u to the j-th subproblem;18t ← t + 1;

16

19
20

2

A ← selectSparseSolutions(P );return A;

Proposed MOEA/D-AD

MOEA/D decomposes a given M -objective MOP into N single-objective subproblems using a scalarizing function g : RM → R and a set of uniformly disi T) for each
tributed weight vectors W = {w1 , ..., wN }, where wi = (w1i , ..., wMPMii ∈ {1, ..., N }, and j=1 wj = 1. One individual in the population P is assigned
to each decomposed subproblem. Thus, the population size µ of MOEA/D always equals N (i.e., µ = N and |P | = |W |).
Algorithm 1 shows the procedure of the proposed MOEA/D-AD for multimodal multi-objective optimization. While the number of subproblems N is still
constant in MOEA/D-AD, µ is nonconstant. Although it is ensured that µ ≥ N ,µ is dynamically changed during the search process (i.e., µ 6= N and |P | =6|W |) unlike MOEA/D. After the initialization of the population (lines 1–2), thefollowing steps are repeatedly applied until a termination condition is satisfied.
At the beginning of each iteration, parent individuals are selected from thewhole population P (line 5). Unlike the original MOEA/D, the mating selection
is not restricted to neighborhood individuals to generate diverse new solutions.
Then, a child u is generated by applying the variation operators (lines 6–7).
After u has been generated, the environmental selection is performed (lines
8–17). Note that our subproblem selection method (described below) was derived

Algorithm 2: The isNeighborhood(u, x) function/* The population P = {y 1 , ..., y µ }*/Ei
1 for i ∈ {1, ..., µ} do di ← NED(y , u);EEE
2 Sort individuals based on their distance values such that d1 ≤ d2 ≤ ... ≤ dµ ;3 for i ∈ {1, ..., L} do
4
if y i = x then return TRUE;
5

return FALSE;

from MOEA/D-DU [16]. However, unlike MOEA/D-DU, only one subproblem
is updated for each iteration in MOEA/D-AD to preserve the diversity. First,
the perpendicular distance di between the normalized objective vector f 0 (u) of
u and wi is calculated for each i ∈ {1, ..., N } (line 8), where PD represents theperpendicular distance between two input vectors. Here, f 0 (u) is obtained asfollows: fk0 (u) = (fk (u) − fkmin )/(fkmax − fkmin ), where fkmin = miny ∈P {fk (y)},and fkmax = maxy ∈P {fk (y)} for each k ∈ {1, ..., M }. Then, the j-th subproblem
having the minimum d value is selected (line 9). The environmental selection is
performed only on the j-th subproblem.
The child u is compared to all the individuals that have been assigned tothe j-th subproblem (line 11–15). Two Boolean variables bwinner and bexplorer ∈{TRUE, FALSE} (line 10) are used for the addition operation of MOEA/D-AD.
More precisely, bwinner represents whether u outperforms at least one individual
belonging to the j-th subproblem regarding the scalarizing function value, andbexplorer indicates whether u is far from all the individuals assigned to the j-th
subproblem in the solution space. If at least one of bwinner and bexplorer is TRUE,u enters the population P (lines 16–17).
In line 12 of Algorithm 1, the isNeighborhood(u, x) function returns TRUE
if u is close to x in the solution space (otherwise, it returns FALSE). Algorithm
2 shows details of the function, where the NED function returns the normalized
Euclidean distance between two input vectors using the upper and lower bounds
for each variable of a given problem. In Algorithm 2, L (1 ≤ L ≤ µ) is a control
parameter of MOEA/D-AD. First, the normalized Euclidean distance between
each individual in P and u is calculated. Then, all the µ individuals are sorted
based on their distance values in descending order. Finally, if x is within the Lnearest individuals from u among the µ individuals, the function returns TRUE.
If x is in the neighborhood of u in the solution space (line 12), they are compared based on their scalarizing function values (lines 14–15). The environmental
selection is performed only among similar individuals in the solution space inorder to maintain the diversity of the population. If x is worse than u, x isremoved from P (line 15). This is the deletion operation of MOEA/D-AD.
Since µ is not bounded, P may include a large number of solutions at theend of the search. This is undesirable in practice because decision-makers arelikely to want to examine only a small number of nondominated solutions thatapproximate the Pareto front and the Pareto solution set [18]. To address thisAlgorithm 3: The selectSparseSolutions(P ) function/* The population P = {x1 , ..., xµ }P ← selectNondominatedSolutions(P ), µ ← |P |, A ← ∅;selected
2 for i ∈ {1, ..., µ} do bi← FALSE, Di ← ∞;3 Randomly select j from {1, ..., µ};jselected
4 A ← A ∪ {x }, bj← TRUE;
5 for i ∈ {1, ..., µ} do
6
if bselected= FALSE then Di ← min(NED(xi , xj ), Di );
i

*/

1

7
8

while |A| < N doj←arg max

Di , A ← A ∪ {xj }, bselected← TRUE;ji∈{1,...,µ}|bselected=FALSEi

91011for i ∈ {1, ..., µ} do
if bselected= FALSE then Di ← min(NED(xi , xj ), Di );ireturn A, which is the N or fewer nondominated solutions selected from P ;issue, a method of selecting N nondominated solutions is applied to the final
population (line 19). Recall that N denotes the number of subproblems.
Algorithm 3 shows details of the selectSparseSolutions function, which returns N or less nondominated solutions A. First, nondominated solutions are
selected from P . Then, one individual is randomly selected from P and inserted
into A. Then, a solution having the maximum distance to solutions in A is repeatedly stored into A. It is expected that a set of nondominated solutions being
far from each other in the solution space are obtained by this procedure.

3

Experimental settings

Test problems. We used the following seven two-objective MMOPs: the TwoOn-One problem [10], the Omni-test problem [3], the three SYM-PART problems[11], and the two SSUF problems [9]. The number of variables D is five for the
Omni-test problem and two for the other problems. In the Two-On-One and
SSUF1 problems, there are two symmetrical Pareto optimal solutions that aremapped to the same objective vector. In the other problems, Pareto optimal
solutions are regularly distributed. The number of equivalent Pareto optimal
solutions is two for the SSUF3 problem, nine for the three SYM-PART problems,and 45 for the Omni-test problem.
Performance indicators. We used the inverted generational distance (IGD)[20] and IGDX [19] for performance assessment of EMOAs. Below, A denotes a
set of nondominated solutions of the final population of an EMOA. The IGD and
IGDX metrics require a set of reference points A∗ . For A∗ for each problem, weused 5 000 solutions which were selected from randomly generated 10 000 Paretooptimal solutions by using the selectSparseSolutions function (Algorithm 3).

The IGD value is the average distance from each reference solution in A∗ to
its nearest solution in A in the objective space as follows:


n
o
1  X
IGD(A) =min ED f (x), f (z)  ,
|A∗ |
∗ x∈A
z ∈A

where ED(x1 , x2 ) represents the Euclidean distance between x1 and x2 .
Similarly, the IGDX value of A is given as follows:


n
o
1  X
min ED x, z  .
IGDX(A) =
|A∗ |
x∈A
z ∈A∗

While IGD measures the quality of A in terms of both convergence to thePareto front and diversity in the objective space, IGDX evaluates how well A approximates the Pareto-optimal solution set in the solution space. Thus, EMOAs
that can find A with small IGD and IGDX values are efficient multi-objective
optimizers and multi-modal multi-objective optimizers, respectively. It should
be noted that small IGD values do not always mean small IGDX values.

Setup for EMOAs. We compared MOEA/D-AD with the following five methods: MO Ring PSO SCD [17], Omni-optimizer [3], NSGA-II [2], MOEA/D [18],and MOEA/D-DU [16]. Omni-optimizer is a representative EMOA for MMOPs.
MO Ring PSO SCD is a recently proposed PSO algorithm for MMOPs. NSGAII and MOEA/D are widely used EMOAs for MOPs. Since the selection methodof the subproblem to be updated in MOEA/D-AD was derived from MOEA/DDU, we also included it in our experiments.
Available source code through the Internet were used for algorithm implementation. For the implementation of MOEA/D-AD, we used the jMetal framework [4]. Source code of MOEA/D-AD can be downloaded from the first author’s
website (https://ryojitanabe.github.io/). The population size µ and thenumber of weight vectors N were set to 100 for all the methods. In MOEA/DAD, µ is dynamically changed as shown in Fig. 4(a). For a fair comparison, weused a set of nondominated solutions of the size N = 100 selected from the final
population by using the selectSparseSolutions function (Algorithm 3). Thus, the
EMOAs were compared using the obtained solution sets of the same size (100).
For all the six EMOAs, the number of maximum function evaluations was set
to 30 000, and 31 runs were performed. The SBX crossover and the polynomial
mutation were used in all the EMOAs (except for MO Ring PSO SCD). Their
control parameters were set as follows: pc = 1, ηc = 20, pm = 1/D, and ηm = 20.
We used the Tchebycheff function [18] for MOEA/D and MOEA/D-AD as
the scalarizing function. The control parameter L of MOEA/D-AD was set to
L = b0.1µc (e.g., L = 201 when µ = 2 018). According to [16,18], the neighborhood size T of MOEA/D and MOEA/D-DU was set to T = 20. All other parameters of MOEA/D-DU and MO Ring PSO SCD were set according to [16,17].

Table 1: Results of the six EMOAs on the seven MMOPs. The tables (a) and (b)show the mean IGD and IGDX values, respectively. The best and second best data
are represented by the bold and italic font. The numbers in parenthesis indicate theranks of the EMOAs. The symbols +, −, and ≈ indicate that a given EMOA performs
significantly better (+), significantly worse (−), and not significantly better or worse(≈) compared to MOEA/D-AD according to the Wilcoxon rank-sum test with p < 0.05.
(a) IGD
MOEA/D- MO RingAD
PSO SCD

Omnioptimizer

NSGA-II

MOEA/D

MOEA/DDU

Two-On-One 0.0637 (5) 0.0606≈ (4) 0.0489+ (2) 0.0490+ (3) 0.0450+ (1) 0.0709− (6)Omni-test 0.0755 (5) 0.1814− (6) 0.0303+ (2) 0.0297+ (1) 0.0517+ (4) 0.0458+ (3)SYM-PART1 0.0302 (4) 0.0283+ (3) 0.0236+ (2) 0.0210+ (1) 0.0467− (5) 0.0478− (6)SYM-PART2 0.0305 (3) 0.0312≈ (4) 0.0284+ (2) 0.0229+ (1) 0.0466− (5) 0.0474− (6)SYM-PART3 0.0307 (2) 0.0323− (3) 0.0343− (4) 0.0228+ (1) 0.0455− (5) 0.0470− (6)SSUF10.0075 (6) 0.0065+ (5) 0.0060+ (4) 0.0055+ (2) 0.0055+ (3) 0.0042+ (1)SSUF3
0.0190 (5) 0.0106+ (3) 0.0170+ (4) 0.0073+ (1) 0.0629− (6) 0.0082+ (2)(b) IGDXMOEA/D- MO RingPSO SCDAD

Omnioptimizer

NSGA-II

MOEA/D

MOEA/DDU

Two-On-One 0.0353 (1) 0.0369− (2) 0.0383− (3) 0.1480− (4) 0.2805− (6) 0.2067− (5)Omni-test 1.3894 (1) 2.2227− (3) 2.0337− (2) 2.5664− (4) 4.3950− (6) 2.9251− (5)SYM-PART1 0.0686 (1) 0.1482− (2) 3.8027− (3) 7.9287− (5) 9.1551− (6) 5.0426− (4)SYM-PART2 0.0783 (1) 0.1610− (2) 1.0863− (3) 5.3711− (5) 9.4834− (6) 5.1610− (4)SYM-PART3 0.1480 (1) 0.4909− (2) 1.3620− (3) 5.8410− (5) 7.3969− (6) 4.6767− (4)SSUF1
0.0761 (1) 0.0860− (2) 0.0899− (3) 0.1323− (5) 0.2443− (6) 0.1143− (4)SSUF30.0302 (2) 0.0198+ (1) 0.0541− (3) 0.0710− (5) 0.3083− (6) 0.0599− (4)4Experimental results

4.1

Performance comparison

IGD metric. Table 1 shows the comparison of the EMOAs on the seven problems. The IGD and IGDX values are reported in Tables 1(a) and (b), respectively.
Table 1(a) shows that the performance of NSGA-II regarding the IGD metricis the best on five problems. MOEA/D and MOEA/D-DU also perform best on
the Two-On-One and SSUF1 problems, respectively. In contrast, MOEA/D-AD
and MO Ring PSO SCD perform poorly on most problems. Note that such apoor performance of multi-modal multi-objective optimizers for multi-objective
optimization has already been reported in [13,17]. Since multi-modal multiobjective optimizers try to locate all equivalent Pareto optimal solutions, theirability to find a good approximation of the Pareto front is usually worse thanthat of multi-objective optimizers, which directly approximate the Pareto front.

4

4

4

3

3

3

2

2

2

1

1

1

0
0

1

2

3

(a) MOEA/D-AD

4

0
0

1

2

3

4

(b) MO Ring PSO SCD

0
0

4

4

4

3

3

3

2

2

2

1

1

1

0
0

1

2

3

(d) NSGA-II

4

0
0

1

2

3

(e) MOEA/D

4

0
0

1

2

3

4

1

2

3

4

(c) Omni-optimizer(f) MOEA/D-DU

Fig. 2: Distribution of nondominated solutions in the final population of each EMOA
in the objective space on the SYM-PART1 problem. The horizontal and vertical axis
represent f1 and f2 , respectively.

However, the IGD values achieved by MOEA/D-AD are only 1.3–2.6 times worse
than the best IGD values on all the problems.
IGDX metric. Table 1(b) indicates that the three multi-modal multi-objective
optimizers (MOEA/D-AD, MO Ring PSO SCD, and Omni-optimizer) have good
performance, regarding the IGDX indicator. In particular, MOEA/D-AD performs the best on the six MMOPs. MOEA/D-AD shows the second best performance only on the SSUF3 problem. In contrast, the performance of MOEA/Dand MOEA/D-DU regarding the IGDX metric is quite poor. The IGDX values
obtained by MOEA/D are 3.2–121.1 times worse than those by MOEA/D-AD.
Thus, the new mechanism that maintains the solution space diversity in the
population mainly contributes to the effectiveness of MOEA/D-AD.
Distribution of solutions found. Figs. 2 and 3 show the distribution of
nondominated solutions in the final population of each EMOA in the objective
and solution spaces on the SYM-PART1 problem. Again, we emphasize that
only N = 100 nondominated solutions selected from the final population byusing the selectSparseSolutions function (Algorithm 3) are shown for MOEA/DAD in Figs. 2 and 3. Results of a single run with median IGD and IGDX values
among 31 runs are shown in Figs. 2 and 3, respectively.
As shown in Fig. 2, the Pareto front of the SYM-PART1 problem is convex. While the distribution of nondominated solutions found by MOEA/D and
MOEA/D-DU in the objective space is biased to the center of the Pareto front,

15
10
5
0
−5
−10
−15
−15−10 −5 05(a) MOEA/D-AD

15
10
5
0
−5
−10
−15
−15−10 −5 05(d) NSGA-II

15
10
5
0
−5
−10
−15
10 15
−15−10 −5 0

5

15
10
5
0
−5
−10
−15
10 15
−15−10 −5 0(b) MO Ring PSO SCD

15
10
5
0
−5
−10
−15
10 15
−15−10 −5 05(e) MOEA/D

5

10 15

5

10 15

(c) Omni-optimizer

15
10
5
0
−5
−10
−15
10 15
−15−10 −5 0(f) MOEA/D-DU

Fig. 3: Distribution of nondominated solutions in the final population of each EMOA
in the solution space on the SYM-PART1 problem. The horizontal and vertical axis
represent x1 and x2 , respectively.

that by NSGA-II is uniform. Compared to the result of NSGA-II, nondominatedsolutions obtained by MOEA/D-AD and MO Ring PSO SCD are not uniformly
distributed in the objective space. This is because they also take into accountthe diversity of the population in the solution space.
The Pareto optimal solutions are on the nine lines in the SYM-PART1 problem. Fig. 3 shows that Omni-optimizer, NSGA-II, MOEA/D, and MOEA/D-DU
fail to locate all the nine equivalent Pareto optimal solution sets. Solutions obtained by the four methods are only on a few lines. In contrast, MOEA/D-AD
and MO Ring PSO SCD successfully find nondominated solutions on all thenine lines. In particular, solutions obtained by MOEA/D-AD are more evenly
distributed on the nine lines. Similar results to Figs. 2 and 3 are observed inother test problems. In summary, our results indicate that MOEA/D-AD is anefficient method for multi-modal multi-objective optimization.
4.2

Analysis of MOEA/D-AD

Influence of L on the performance of MOEA/D-AD. MOEA/D-AD
has the control parameter L, which determines the neighborhood size of thechild in the solution space. Generally speaking, it is important to understandthe influence of control parameters on the performance of a novel evolutionary
algorithm. Here, we investigate how L affects the effectiveness of MOEA/D-AD.
Table 2 shows results of MOEA/D-AD with six L values on the seven test
problems. Due to space constraint, only aggregations of statistical testing resultsto MOEA/D-AD with L = b0.1µc are shown here. Intuitively, MOEA/D-AD
with a large L value should perform well regarding the IGD metric because
large L values relax the restriction for the environmental selection and mayTable 2: Results of MOEA/D-AD with various L values on the seven MMOPs. The
tables (a) and (b) show aggregations of statistical testing results (+, −, and ≈) of the
IGD and IGDX metrics. Each entry in the table shows the number of problems where
the performance of MOEA/D-AD with each value of L is significantly better (worse)or has no significant difference from that of MOEA/D-AD with L = b0.1µc.
(a) IGD(b) IGDX
0.1µ+ (better)− (worse)≈ (no sig.)

0.05µ 0.2µ 0.3µ 0.4µ 0.5µ
1
0
6

0
3
4

0
5
2

0
5
2

0
5
2

0.1µ
+ (better)− (worse)≈ (no sig.)

0.05µ 0.2µ 0.3µ 0.4µ 0.5µ
2
3
2

1
2
4

0
5
2

0
6
1

0
7
0

improve its ability for multi-objective optimization. However, Table 2(a) showsthat the performance of MOEA/D-AD with a large L value is poor, regarding
the IGD indicator. As pointed out in [15], the solution space diversity may help
MOEA/D-AD to approximate the Pareto front well.
Table 2(b) indicates that the best IGDX values are obtained by L = b0.05µc
and L = b0.2µc on two problems and one problem, respectively. Thus, the performance of MOEA/D-AD depends on the L value. A control method of L is likely
to be beneficial for MOEA/D-AD. However, MOEA/D-AD with L = b0.1µc
performs well on most problems. Therefore, L = b0.1µc can be the first choice.
Adaptive behavior of MOEA/D-AD. Unlike other MOEA/D-type algorithms, the population size µ and the number of individuals belonging to each
subproblem are adaptively adjusted in MOEA/D-AD.
Fig. 4(a) shows the evolution of µ of MOEA/D-AD on the seven problems.
In Fig. 4(a), µ is increased as the search progresses. This is because the diverse
individuals in the solution space are iteratively added in the population. Recall that the number of equivalent Pareto optimal solutions nsame is 45 for the
Omni-test problem, nine for the three SYM-PART problems, and two for otherproblems. Fig. 4(a) indicates that the trajectory of µ is problem-dependent. Ideally, µ should equal nsame ×N so that nsame Pareto optimal solutions are assigned
to each of N subproblems. However, the actual µ values are significantly larger
than the expected values. For example, while the ideal µ value is 200 (2×100) on
the Two-On-One problem, the actual µ value at the end of the search is 2 480.
To analyze the reason, we show the number of individuals assigned to each
subproblem at the end of the search on the Two-On-One, Omni-test, and SYMPART1 problems in Fig. 4(b). Fig. 4(b) indicates that the distribution of individuals is not even. More extra individuals are allocated to subproblems whose
indices are close to 50. That is, MOEA/D-AD allocates unnecessary individuals
to most subproblems. If individuals can be evenly assigned to each subproblem,the performance of MOEA/D-AD may be improved. An in-depth analysis of theadaptive behavior of MOEA/D-AD is needed.

Two-On-One
Omni-test

SYM-PART1SYM-PART2

Number of individuals

Population size µ

6000
5000
4000
3000
2000
1000
0
0

10000
20000
Number of evaluations(a) Evolution of µ30000

SYM-PART3
SSUF1

90
80
70
60
50
40
30
20
10
0
0

SSUF3

20

40
60
80
100
Subproblem index(b) # of individuals on each subproblem

Fig. 4: (a) Evolution of the population size µ of MOEA/D-AD. (b) Number of individuals assigned to the j-th subproblem (j ∈ {1, ..., N }) at the end of the search, whereN = 100. Results of a single run with a median IGDX value among 31 runs are shown.

5

Conclusion

We proposed MOEA/D-AD, which is a novel MOEA/D for multi-modal multiobjective optimization. In order to locate multiple equivalent Pareto optimal
solutions, MOEA/D-AD assigns one or more individuals that are far from eachother in the solution space to each subproblem. We examined the performance of
MOEA/D-AD on the seven two-objective problems having equivalent Pareto optimal solutions. Our results indicate that MOEA/D-AD is capable of finding multiple equivalent Pareto optimal solutions. The results also show that MOEA/DAD performs significantly better than Omni-optimizer and MO Ring PSO SCD,
which are representative multi-modal multi-objective optimizers.
Several interesting directions for future work remain. Any neighborhood criterion (e.g., sharing and clustering [8]) can be introduced in MOEA/D-AD. Although we used the relative distance-based neighborhood decision (Algorithm 2)
in this study, investigating the performance of MOEA/D-AD with other neighborhood criteria is one future research topic. Also, the effectiveness of MOEA/DAD could be improved by using an external archive that stores diverse solutions[12]. A more efficient search can be performed by utilizing a decision-maker’s
preference [5]. Incorporating the decision-maker’s preference into the search process of MOEA/D-AD is an avenue for future work. Since the existing multimodal multi-objective test problems are not scalable in the number of objectives
and variables, this paper dealt with only two-objective problems with up to fivevariables. Designing scalable test problems is another research topic.
Acknowledgments. This work was supported by the Science and Technology
Innovation Committee Foundation of Shenzhen (Grant No. ZDSYS201703031748284).

References
1. K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley& Sons, 2001.
2. K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective
genetic algorithm: NSGA-II. IEEE TEVC, 6(2):182–197, 2002.
3. K. Deb and S. Tiwari. Omni-optimizer: A generic evolutionary algorithm for single
and multi-objective optimization. EJOR, 185(3):1062–1087, 2008.
4. J. J. Durillo and A. J. Nebro. jMetal: A Java framework for multi-objective optimization. Adv. Eng. Softw., 42(10):760–771, 2011.
5. M. Gong, F. Liu, W. Zhang, L. Jiao, and Q. Zhang. Interactive MOEA/D for
multi-objective decision making. In GECCO, pages 721–728, 2011.
6. O. Kramer and H. Danielsiek. DBSCAN-based multi-objective niching to approximate equivalent pareto-subsets. In GECCO, pages 503–510, 2010.
7. F. Kudo, T. Yoshikawa, and T. Furuhashi. A study on analysis of design variables
in Pareto solutions for conceptual design optimization problem of hybrid rocket
engine. In IEEE CEC, pages 2558–2562, 2011.
8. X. Li, M. G. Epitropakis, K. Deb, and A. P. Engelbrecht. Seeking Multiple Solutions: An Updated Survey on Niching Methods and Their Applications. IEEE
TEVC, 21(4):518–538, 2017.
9. J. J. Liang, C. T. Yue, and B. Y. Qu. Multimodal multi-objective optimization: A
preliminary study. In IEEE CEC, pages 2454–2461, 2016.
10. M. Preuss, B. Naujoks, and G. Rudolph. Pareto Set and EMOA Behavior for
Simple Multimodal Multiobjective Functions. In PPSN, pages 513–522, 2006.
11. G. Rudolph, B. Naujoks, and M. Preuss. Capabilities of EMOA to Detect andPreserve Equivalent Pareto Subsets. In EMO, pages 36–50, 2007.
12. O. Schütze, M. Vasile, and C. A. C. Coello. Computing the Set of Epsilon-Efficient
Solutions in Multiobjective Space Mission Design. JACIC, 8(3):53–70, 2011.
13. O. M. Shir, M. Preuss, B. Naujoks, and M. T. M. Emmerich. Enhancing Decision
Space Diversity in Evolutionary Multiobjective Algorithms. In EMO, pages 95–
109, 2009.
14. A. Trivedi, D. Srinivasan, K. Sanyal, and A. Ghosh. A Survey of Multiobjective
Evolutionary Algorithms Based on Decomposition. IEEE TEVC, 21(3):440–462,
2017.
15. T. Ulrich, J. Bader, and E. Zitzler. Integrating decision space diversity into
hypervolume-based multiobjective search. In GECCO, pages 455–462, 2010.
16. Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao. Balancing Convergence andDiversity in Decomposition-Based Many-Objective Optimizers. IEEE TEVC,
20(2):180–198, 2016.
17. C. Yue, B. Qu, and J. Liang. A Multi-objective Particle Swarm Optimizer Using
Ring Topology for Solving Multimodal Multi-objective Problems. IEEE TEVC,
2017 (in press).
18. Q. Zhang and H. Li. MOEA/D: A multiobjective evolutionary algorithm based on
decomposition. IEEE TEVC, 11(6):712–731, 2007.
19. A. Zhou, Q. Zhang, and Y. Jin. Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution
Algorithm. IEEE TEVC, 13(5):1167–1189, 2009.
20. 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, 7(2):117–132, 2003.