Matching-Based Selection with Incomplete Lists
for Decomposition Multi-Objective Optimization∗
Mengyuan Wu1 , Ke Li2 , Sam Kwong1 , Yu Zhou3 and Qingfu Zhang1
1 Department

of Computer Science, City University of Hong Kong
of Engineering, Mathematics and Physical Sciences, University of Exeter
3 College of Computer Science and Software Engineering, Shenzhen University
∗ Email: k.li@exeter.ac.uk, {mengyuan.wu, yzhou57-c}@my.cityu.edu.hk, {cssamk,
qingfu.zhang}@cityu.edu.hk

arXiv:1608.08607v2 [] 25 Jan 2017

2 College

Abstract:
The balance between convergence and diversity is the cornerstone of evolutionary
multi-objective optimization. The recently proposed stable matching-based selection provides a new
perspective to handle this balance under the framework of decomposition multi-objective optimization. In particular, the one-one stable matching between subproblems and solutions, which achieves
an equilibrium between their mutual preferences, is claimed to strike a balance between convergence
and diversity. However, the original stable marriage model has a high risk of matching a solution
with an unfavorable subproblem, which finally leads to an imbalanced selection result. In this paper,
we introduce the concept of incomplete preference lists into the stable matching model to remedy the
loss of population diversity. In particular, each solution is only allowed to maintain a partial preference list consisting of its favorite subproblems. We implement two versions of stable matching-based
selection mechanisms with incomplete preference lists: one achieves a two-level one-one matching
and the other obtains a many-one matching. Furthermore, an adaptive mechanism is developed to
automatically set the length of the incomplete preference list for each solution according to its local
competitiveness. The effectiveness and competitiveness of our proposed methods are validated and
compared with several state-of-the-art evolutionary multi-objective optimization algorithms on 62
benchmark problems.
Keywords:
Convergence and diversity, stable matching with incomplete lists, adaptive mechanism, decomposition, multi-objective optimization.

1 Introduction
The multi-objective optimization problem (MOP) considered in this paper is defined as follows [1]:
minimize F(x) = (f1 (x), · · · , fm (x))T
subject to x ∈ Ω

(1)

where x = (x1 , · · · , xn )T is a n-dimensional decision vector and F(x) is a m-dimensional objective
vector. Ω ⊆ Rn is the feasible region of the decision space, while F : Ω → Rm is the corresponding
attainable set in the objective space Rm . Given two solutions x1 , x2 ∈ Ω, x1 is said to dominate x2 ,
∗

This paper has been accepted for publication by IEEE Transactions on Evolutionary Computation. Copyright will
be transferred to IEEE Press without notice.

1

denoted by x1  x2 , if and only if fi (x1 ) ≤ fi (x2 ) for all i ∈ {1, · · · , m} and F(x1 ) 6= F(x2 ). A
solution x∗ ∈ Ω is said to be Pareto optimal if and only if no solution x ∈ Ω dominates it. All Pareto
optimal solutions constitute the Pareto-optimal set (PS) and the corresponding Pareto-optimal front
(PF) is defined as P F = {F(x)|x ∈ P S}.
Evolutionary multi-objective optimization (EMO) algorithms, which are capable of approximating
the PS and PF in a single run, have been widely accepted as a major approach for multi-objective
optimization. Convergence and diversity are two cornerstones of multi-objective optimization: the
former means the closeness to the PF while the latter indicates the spread and uniformity along
the PF. Selection, which determines the survival of the fittest, plays a key role in balancing convergence and diversity. According to different selection mechanisms, the existing EMO algorithms
can be roughly classified into three categories, i.e., Pareto-based methods [?, 2–4], indicator-based
methods [5–7] and decomposition-based methods [8–10].
This paper focuses on the decomposition-based methods, especially the multi-objective evolutionary algorithm based on decomposition (MOEA/D) [8]. The original MOEA/D employs a steadystate selection mechanism, where the population is updated immediately after the generation of
an offspring. In particular, this offspring is able to replace its neighboring parents when it has a
better aggregation function value for the corresponding subproblem. To avoid a superior solution
overwhelmingly occupying the whole population, [11] suggested to restrict the maximum number of
replacements taken by an offspring. More recently, [10] developed a new perspective to understand
the selection process of MOEA/D. Specifically, the selection process of MOEA/D is modeled as a
one-one matching problem, where subproblems and solutions are treated as two sets of matching
agents whose mutual preferences are defined as the convergence and diversity, respectively. Therefore, a stable matching between subproblems and solutions achieves an equilibrium between their
mutual preferences, leading to a balance between convergence and diversity. However, as discussed
in [12] and [13], partially due to the overrated convergence property, both the original MOEA/D
and the stable matching-based selection mechanism fail to maintain the population diversity when
solving problems with complicated properties, e.g., imbalanced problem [13,14] and many objectives.
Bearing these considerations in mind, [12] modified the mutual preference definition and developed a
straightforward but more effective selection mechanism based on the interrelationship between subproblems and solutions. Later on, [15] proposed an adaptive replacement strategy, which adjusts the
replacement neighborhood size dynamically, to assign solutions to their most suitable subproblems.
It is also interesting to note that some works took the advantages of the Pareto dominance- and
decomposition-based selection mechanisms in a single paradigm [?, ?, 16–18].
To achieve a good balance between convergence and diversity, this paper suggests to introduce
the concept of incomplete preference lists into the stable matching model. Specifically, borrowing
the idea from the stable matching with incomplete preference lists [19], we restrict the number of
subproblems with which a solution is allowed to match. In this case, a solution can only be assigned
to one of its favorite subproblems. However, due to the restriction on the preference list, the stable
marriage model, which results in a one-one matching, may leave some subproblems unmatched. To
remedy this situation, this paper implements two different versions of stable matching-based selection
mechanisms with incomplete preference lists.
• The first one achieves a two-level one-one matching. At the first level, we find the stable solutions for subproblems according to the incomplete preference lists. Afterwards, at the second
level, the remaining unmatched subproblems are matched with suitable solutions according to
the remaining preference information.
• The second one obtains a many-one matching. In such a way, the unmatched subproblems give
the matching opportunities to other subproblems that have already matched with a solution
but still have openings.

2

Note that the length of the incomplete preference list has a significant impact on the performance and
is problem dependent [20]. By analyzing the underlying mechanism of the proposed stable matchingbased selection mechanisms in depth, we develop an adaptive mechanism to set the length of the
incomplete list for each solution on the fly. Comprehensive experiments on 62 benchmark problems
fully demonstrate the effectiveness and competitiveness of our proposed methods.
The rest of the paper is organized as follows. Section 2 introduces some preliminaries of this
paper. Thereafter, the proposed algorithm is described step by step in Section 3. Section 4 and
Section 5 provide the experimental settings and the analysis of the empirical results. Finally, Section 6
concludes this paper and provides some future directions.

2 Preliminaries
In this section, we first introduce some background knowledge of MOEA/D and the stable matchingbased selection. Then, our motivations are developed by analyzing their underlying mechanisms and
drawbacks.

2.1 MOEA/D
As a representative of the decomposition-based algorithms, MOEA/D has become an increasingly
popular choice for posterior multi-objective optimization. Generally speaking, there are two basic components in MOEA/D: one is decomposition and the other is collaboration. The following
paragraphs give some general descriptions of each component separately.
2.1.1 Decomposition
The basic idea of decomposition is transforming the original MOP into a single-objective optimization
subproblem. There are many established decomposition methods developed for classic multi-objective
optimization [21], among which the most popular ones are weighted sum, Tchebycheff (TCH) and
boundary intersection approaches. Without loss of generality, this paper considers the inverted TCH
approach [10], which is defined as follows:
minimize

g tch (x|w, z∗ ) = max {|fi (x) − zi∗ |/wi }
1≤i≤m

subject to x ∈ Ω

,

(2)

where w = (w1 , · · · , wm )T is a user specified weight vector, wi ≥ 0 for all i ∈ {1, · · · , m} and
P
m
−6
∗
i=1 wi = 1. In practice, wi is set to be a very small number, say 10 , when wi = 0. z =
∗
∗
T
∗
(z1 , · · · , zm ) is an Utopian objective vector where zi = min fi (x), i ∈ {1, · · · , m}. Note that the
x∈Ω

search direction of the inverted TCH approach is w, and the optimal solution of (2) is a Paretooptimal solution of the MOP defined in (1) under some mild conditions. We can expect to obtain
various Pareto-optimal solutions by using (2) with different weight vectors. In MOEA/D, a set of
uniformly distributed weight vectors are sampled from a unit simplex.
2.1.2 Collaboration
As discussed in [8], the neighboring subproblems, associated with the geometrically close weight
vectors, tend to share similar optima. In other words, the optimal solution of g tch (·|w1 , z∗ ) is close
to that of g tch (·|w2 , z∗ ), given w1 and w2 are close to each other. In MOEA/D, each solution is
associated with a subproblem. During the optimization process, the solutions cooperate with each
other via a well-defined neighborhood structure and they solve the subproblems in a collaborative
manner. In practice, the collaboration is implemented as a restriction on the mating and update

3

procedures. More specifically, the mating parents are selected from neighboring subproblems and a
newly generated offspring is only used to update its corresponding neighborhood. Furthermore, since
different subproblems might have various difficulties, it is more reasonable to dynamically allocate the
computational resources to different subproblems than treating all subproblems equally important.
In [22], a dynamic resource allocation scheme is developed to allocate more computational resources
to those promising ones according to their online performance.

2.2 Stable Matching-Based Selection
Stable marriage problem (SMP) was originally introduced in [23] and its related work won the 2012
Nobel Prize in Economics. In a nutshell, the SMP is about how to establish a stable one-one matching
between two sets of agents, say men and women, which have mutual preferences over each other. A
stable matching should not contain a man and a woman who are not matched together but prefer
each other to their assigned spouses.
In MOEA/D, subproblems and solutions can be treated as two sets of agents which have mutual
preferences over each other. In particular, a subproblem prefers a solution that optimizes its underlying single-objective optimization problem as much as possible; while a solution prefers to have a well
distribution in the objective space. The ultimate goal of selection is to select the best solution for each
subproblem, and vice versa. In this case, we can treat the selection procedure as a one-one matching
procedure between subproblems and solutions. To the best of our knowledge, MOEA/D-STM [10]
is the first one that has modeled the selection procedure of MOEA/D as an SMP, and encouraging
results have been reported therein. The framework of the stable matching-based selection contains
two basic components, i.e., preference settings and matching model. The following paragraphs briefly
describe these two components.
2.2.1 Preference Settings
The preference of a subproblem p on a solution x is defined as:
∆P (p, x) = g tch (x|w, z∗ ),

(3)

where w is the weight vector of p. Consequently, ∆P (p, x) measures the convergence of x with respect
to p. The preference of a solution x to a subproblem p is defined as:
∆X (x, p) = kF (x) −

wT · F (x)
wk,
wT · w

(4)

where F (x) is the normalized objective vector of x and k · k is the `2 -norm. Since the weight vectors
are usually uniformly distributed, it is desirable that the optimal solution of each subproblem has
the shortest perpendicular distance to its corresponding weight vector. For the sake of simplicity,
∆X (x, p) can be used to measure the diversity of a solution [10].
2.2.2 Matching Model
Based on the above preference settings, [10] employed the classic deferred acceptance procedure
(DAP) developed in [23] to find a stable matching between subproblems and solutions. The pseudo
code of this stable matching-based selection mechanism is given in Algorithm 1. ΨP and ΨX are the
preference matrices of subproblems and solutions, each row of which represents the preference list
of a subproblem over all solutions, and vice versa. In particular, a preference list is built by sorting
the preference values in an ascending order. M indicates the set of all the constructed matching
pairs. It is worth noting that the convergence and diversity have been aggregated into the preference

4

Algorithm 1: STM(P , S, ΨP , ΨX )
Input:
• subproblem set P and solution set S
• sets of preference lists ΨP and ΨX

6

Output: stable matching set M
Pu ← P , M ← ∅;
while Pu 6= ∅ do
p ← Randomly pick a subproblem from Pu ;
x ← First solution on p’s preference list;
Remove x from p’s preference list;
M ← DAP(p, x, Pu , M , ΨP , ΨX );

7

return M

1
2
3
4
5

Algorithm 2: DAP(p, x, Pu , M , ΨP , ΨX )
Input:
• current subproblem p and solution x
• unmatched subproblem set Pu
• current stable matching set M
• sets of preference lists ΨP and ΨX

8

Output: stable matching set M
if x ∈
/ M then
M ← M ∪ (p, x);
Pu ← Pu \ p;
else
p0 ← M (x);
if x prefers p to p0 then
M ← M ∪ (p, x) \ (p0 , x);
Pu ← Pu ∪ p0 \ p;

9

return M

1
2
3
4
5
6
7

// match p and x

// current partner of x

settings, thus the stable matching between subproblems and solutions strikes the balance between
convergence and diversity.

2.3 Drawbacks of MOEA/D and MOEA/D-STM
In this subsection, we discuss some drawbacks of the selection mechanisms of MOEA/D and MOEA/DSTM.
2.3.1 MOEA/D
The update mechanism of the original MOEA/D is simple and efficient, yet greedy. In a nutshell,
each subproblem simply selects its best solution according to the corresponding scalar optimization
function value. As discussed in [22], since different parts of the PF might have various difficulties,

5

𝑝1

𝑝1
𝑝

2

𝑝2

𝑝3
5

8

7

5
9

4

2
1

6

𝑝3

10

1

8

7

9

4

2

𝑝4

3

6

𝑝4

3

10

𝑝5

(a) MOEA/D

𝑝5

(b) MOEA/D-STM

Figure 1: Comparisons of MOEA/D and MOEA/D-STM.
some subproblems might be easier than the others for finding the optimal solutions. During some
intermediate stages of the optimization process, the currently elite solutions of some relatively easier
subproblems might also be good candidates for the others. In this case, these elite solutions can easily
take over all subproblems. In addition, it is highly likely that the offspring solutions generated from
these elite solutions crowd into the neighboring areas of the corresponding subproblems. Therefore,
this purely fitness-driven selection mechanism can be severely harmful for the population diversity
and may lead to the failure of MOEA/D on some challenging problems [13]. Let us consider an
example shown in Fig. 1(a), where five out of ten solutions need to be selected for five subproblems.
Since x1 is currently the best solution for {p1 , p2 , p3 } and x10 is the current best candidate for {p4 , p5 },
these two elite solutions finally take over all five subproblems. Obviously, the population diversity of
this selection result is not satisfied.
2.3.2 MOEA/D-STM
As discussed in [24], the DAP maximizes the satisfactions of the preferences of men and women
in order to maintain the stable matching relationship. According to the preference settings for
subproblems, solutions closer to the PF are always on the front of the subproblems’ preference lists.
In this case, the DAP might make some solutions match themselves with subprobolems lying on the
rear of their preference lists. Even worse, as discussed in Section 2.3.1, these currently well converged
solutions may crowd in a narrow area. This obviously goes against the population diversity. Let us
consider the same example discussed in Fig. 1(a). The preference matrices of subproblems and
solutions are:
p1
p2
ΨP = p3
p4
p5

:
:
:
:
:

[1
[1
[1
[ 10
[ 10

2
3
3
1
1

3
2
2
3
3

4
4
4
2
2

6

5
5
6
4
4

6
6
5
9
9

7 8 10 9 ]
7 8 10 9 ]
7 10 8 9 ]
6 5 7 8]
6 5 7 8]

(5)

ΨX

x1 :
x2 :
x3 :
x4 :
x5 :
= 6
x :
x7 :
x8 :
x9 :
x10 :

[
[
[
[
[
[
[
[
[
[

1
1
1
2
2
2
3
3
4
5

2
2
2
1
1
3
2
4
3
4

3
3
3
3
3
1
4
2
5
3

4
4
4
4
4
4
1
5
2
2

5
5
5
5
5
5
5
1
1
1

]
]
]
]
]
.
]
]
]
]
]

(6)

From equation (5), we can clearly see that x1 to x4 dominate the top positions of the preference lists
of all subproblems. By using Algorithm 1, we have the selection/matching result shown in Fig. 1(b),
where x1 to x4 crowd in a narrow area between p1 and p2 . This is obviously harmful for the population
diversity as well.
From the above discussions, we find that the original selection mechanism of MOEA/D is a convergence first and diversity second strategy [13], which might give excessive priority to the convergence
requirement. On the other hand, although the stable matching-based selection mechanism intends to
achieve an equilibrium between convergence and diversity, the stable matching between subproblems
and solutions may fail to keep the population diversity. This is because no restriction has been given
to the subproblem with which a solution can match. In other words, a solution can match with an
unfavorable subproblem in the resulting stable matching. To relieve this side effect, the next section
suggests a strategy to take advantages of some partial information from the preference lists when
finding the stable matching between subproblems and solutions.

3 Adaptive Stable Matching-Based Selection with Incomplete
Preference Lists
In the canonical SMP, each man/woman holds a complete and strictly ordered preference list over all
agents from the other side. However, in practice, it may happen that a man/woman declares some
unacceptable partners [24], and this results in an SMP with incomplete lists [25]. By these means,
a man/woman is only allowed to match with a matching agent that appears on his/her incomplete
preference list. Due to the restriction from the incomplete preference lists, there is no guarantee
that all agents can have a stable matching mate. A stable matching for an SMP with incomplete
lists does not contain such a pair of man and woman: 1) they are acceptable to each other but
not matched together; 2) they either do not match with anyone else or prefer each other to their
current matching mates. To overcome the drawbacks discussed in Section 2.3, here we implement
two versions of stable matching-based selection mechanisms with incomplete preference lists: one
achieves a two-level one-one matching while the other obtains a many-one matching.

3.1 Two-Level One-One Stable Matching-Based Selection
In the first level, let us assume that there are N subproblems and Q solutions, where N < Q.
After obtaining the complete preference lists of all subproblems and solutions (line 1 and line 2
of Algorithm 4), we only keep the first ri , where i ∈ {1, · · · , Q} and 0 < ri ≤ N , subproblems on the
preference list of each solution xi , while the remaining ones are not considered any longer (line 2 and
line 3 of Algorithm 3). In this case, each solution is only allowed to match with its first several favorite
subproblems which are close to itself according to equation (4). In contrast, the preference lists of
subproblems are kept unchanged. Given the incomplete preference information, we employ the DAP

7

Algorithm 3: STMIC(P , S, ΨP , ΨX , R)
Input:
• subproblem set P , solution set S
• preference matrices ΨP and ΨX
• length of solution’s preference list set R
1
2
3
4
5
6
7
8
9
10
11
12
13

Output: stable matching set M
Pu ← P , M ← ∅;
for i ← 1 to |S| do
Keep the first ri subproblems on xi ’s complete preference list and remove the remainders;
while Pu 6= ∅ do
p ← Randomly select a subproblem from Pu ;
if p’s preference list 6= ∅ then
x ← First solution on p’s preference list;
Remove x from p’s preference list;
if p is on x’s preference list then
M ← DAP(p, x, Pu , M , ΨP , ΨX );
else
Pu ← Pu \ p;
Return M ;

Algorithm 4: SelectionOOSTM2L(P , S)
Input: subproblem set P and solution set S
Output: solution set S
1 /* First-level stable matching
2 Compute Ψp and Ψx for P and S;
3 R ← Set the length of each solution’s preference list;
4 M ← STMIC(P , S, ΨP , ΨX , R);
5 /* Second-level stable matching
6 (Pm , Sm ) ← M ;
7 Pu ← P \ Pm ;
8 Su ← S \ Sm ;
9 Compute Ψ0P and Ψ0X for Pu and Su ;
10 M 0 ← STM(Pu , Su , Ψ0P , Ψ0X );
11 /* Combine the stable matching pairs
12 M ← M ∪ M 0 ;
13 Return M ;

*/

*/

*/

to find a stable matching between subproblems and solutions (line 4 to line 12 of Algorithm 3). By
these means, we can expect that the population diversity is strengthened during the first-level stable
matching. This is because a solution is not allowed to match with an unfavorable subproblem which
lies out of its incomplete preference list. The pseudo code of the stable matching with incomplete
lists is given in Algorithm 3.
During the first-level stable matching, not all subproblems are assigned with a stable solution due
to the incomplete preference information. To remedy this issue, the second-level stable matching

8

with complete preference lists is developed to find a stable solution for each unmatched subproblem.
At first, we compute the preference matrices of the unmatched subproblems and solutions (line 7
of Algorithm 4). Afterwards, we employ Algorithm 1 to find a stable matching between them (line
8 of Algorithm 4). In the end, the matching pairs of both levels of stable matching are gathered
together to form the final selection results (line 9 of Algorithm 4). The pseudo code of the two-level
stable matching-based selection mechanism is given in Algorithm 4.

3.2 Many-One Stable Matching-Based Selection
Many-one stable matching problem is an extension of the standard SMP, where a matching agent
from one side is allowed to have more than one matching mates from the other side. For example,
in the college admission problem (CAP) [23], the colleges and applicants are two sets of matching
agents. Each college has a preference list over all applicants and vice versa. Different from the SMP,
each applicant is only allowed to enter one college, whereas each college has a positive integer quota
being the maximum number of applicants that it can admit.
As the other implementation of the stable matching-based selection with incomplete preference
lists, here we model the selection process of MOEA/D as a CAP with a common quota [26]. More
specifically, subproblems and solutions are treated as colleges and applicants respectively. A solution
is only allowed to match with one subproblem while a subproblem is able to match with more than
one solution. In particular, we do not limit the separate quota for every subproblem but assign a
common quota for all subproblems, which equals the number of subproblems (i.e., N ). In other
words, N subproblems can at most match with N solutions in this many-one matching. Note that a
matching is stable if there does not exist any pair of subproblem p and solution x where:
• p and x are acceptable to each other but not matched together;
• x is unmatched or prefers p to its assigned subproblem;
• the common quota is not met or p prefers x to at least one of its assigned solutions.
The pseudo code of the many-one stable matching-based selection mechanism is given in Algorithm 5. The initialization process (line 1 to line 5 of Algorithm 5) is the same as the one-one stable
matching discussed in Section 3.1. During the main while-loop, an unmatched solution x ∈ Su at
first matches with its current favorite subproblem p according to its preference list (line 7 to line 11
of Algorithm 5). If the number of current matching pairs |M | is larger than N , we find a substitute
subproblem p0 and adjust its matching pairs by releasing the matching relationship with its least
preferred solution x0 (line 12 to line 18 of Algorithm 5). In particular, p0 is selected according to the
following criteria:
• At first, we choose the subproblems that have the largest number of matched solutions to
form P (line 13 of Algorithm 5). Its underlying motivation is to reduce the chance for overly
exploiting a particular subproblem.
• If the cardinality of P is greater than one, we need to further process P . Specifically, we
investigate the ranks of the solutions matched with subproblems in P . The subproblems,
whose least preferred solution holds the worst rank on that subproblem’s preference list, are
used to reconstruct P (line 14 of Algorithm 5).
• In the end, p0 is randomly chosen from P (line 14 of Algorithm 5).
Note that we add x0 back into Su after releasing its matching relationship with p0 (line 18 of Algorithm 5). The matching process terminates when Su becomes empty.

9

Algorithm 5: SelectionMOSTM(P , S)
Input: subproblem set P and solution set S
Output: stable matching set M
1 Compute ΨP and ΨX for P and S;
2 R ← Set the length of each solution’s preference list;
3 Su ← S, M ← ∅;
4 for i ← 1 to Q do
5
Keep the first ri subproblems on xi ’s complete preference list and remove the remainders;
while Su 6= ∅ do
x ← Randomly select a solution from Su ;
if x’s preference list 6= ∅ then
p ← First subproblem on x’s preference list;
Remove p from x’s preference list;
M ← M ∪ (p, x);
if |M | > N then
P ← arg max |M (p)|;
// |M (p)| is the cardinality of M (p)

6
7
8
9
10
11
12
13

p∈P

P ← arg max{ max rank(p, x)};

14

preference list
p0 ← Randomly select a subproblem from P ;
x0 ← arg max rank(p0 , x);

15
16

x∈M (p0 )
M \ (p0 , x0 );

M←
S u ← S u ∪ x0 ;

17
18

else
Su ← Su \ x;

19
20

return M ;

21

𝑝1

𝑝1

𝑝1

𝑝2

5

1

6

𝑝1

𝑝2

𝑝2

𝑝3
7

5
9

10

(a) STM2L (r = 4)

1

𝑝5

6

𝑝3

8

7

5
9

4

2

𝑝4

3

𝑝2

𝑝3

8

4

2

// rank(p, x) is the rank of x on p’s

x∈M (p)

p∈P

𝑝4

3

10

1

𝑝5

(b) STM2L (r = 3)

6

7

5

9

4

2

𝑝3

8

3

10

(c) STM2L (r = 2)

1

𝑝5

7

9

4

2

𝑝4

6

8

𝑝4

3

10

𝑝5

(d) STM2L (r = 1)

Figure 2: Comparisons of the two-level stable matching-based selection with incomplete lists using
different r settings.

3.3 Impacts of the Length of the Incomplete Preference List
As discussed in the previous subsections, we expect to improve the population diversity by restricting
the length of the preference list of each solution. A natural question is whether this length affects the
behavior of our proposed stable matching-based selection mechanisms? Let us consider the example

10

discussed in Fig. 1 again. For the sake of discussion, here we set the length of the incomplete
preference list of each solution as a constant (denoted by r). By using different settings of r, Fig. 2
shows the selection results of the two-level stable matching-based selection mechanism. From this
figure, we find that the diversity of the selected solutions increases with the decrease of r; on the
other hand, the improvement of the diversity is at the expense of the convergence. It is interesting
to note that the two-level stable matching-based selection mechanism totally degenerates into the
original stable matching-based selection mechanism shown in Fig. 1(a) when using r = 4. In a word,
r controls the trade-off between convergence and diversity in the stable matching-based selection with
incomplete preference lists. In the next subsection, we develop an adaptive mechanism to control the
length of each solution’s preference list on the fly.

3.4 Adaptive Mechanism
To better understand the proposed adaptive mechanism, here we introduce the concept of local
competitiveness. At first, all solutions are associated with their closest subproblems having the
shortest perpendicular distance between the objective vector of the solution and the weight vector
of the subproblem. Afterwards, for each subproblem having more than one associated solutions,
we choose the one, which has the best aggregation function value, as its representative solution. A
solution is defined as a locally competitive solution in case it dominates at least one representative
solution of its ` ≥ 1 nearest subproblems; otherwise, it is defined as a locally noncompetitive solution.
In view of the population dynamics of the evolutionary process, we develop an adaptive mechanism
to set the length of the incomplete preference list of a solution according to its local competitiveness
(Algorithm 6 gives its pseudo code). Briefly speaking, this length is set as the maximum ` that keeps
the corresponding solution locally noncompetitive.
More specifically, given N subproblems and Q solutions, each solution is associated with its closest
subproblem as shown in line 1 and line 2 of Algorithm 6. In particular, Φ[i] represents the index
of the subproblem with which a solution xi is associated, i ∈ {1, · · · , Q}. In line 4 of Algorithm 6,
we collect the associated solutions of each subproblem pj , j ∈ {1, · · · , N }, to form a temporary set
χ. Then, line 5 to line 8 of Algorithm 6 determine the representative solution of each subproblem
pj , where ϕ[j] represents the index of its representative solution. Afterwards, for each solution xi ,
line 10 to line 16 of Algorithm 6 gradually increase ` until xi becomes locally competitive, and this
final ` is used as the length of xi ’s incomplete preference list. Note that since each solution locates
within the subspace between m closest neighboring weight vectors in m-dimensional objective space,
it can be associated with any of these m subproblems in principle. Moreover, to avoid unnecessary
comparisons, it is desirable to keep the solution’s incomplete preference list within a reasonably small
length. All in all, the length of xi ’s incomplete preference list is adaptively tuned between m and
`max . In particular, `max is set as the neighborhood size T used in MOEA/D, where the mating
parents are selected from.
Let us use the example shown in Fig. 1(b) to explain the underlying principle of our proposed
adaptive mechanism. In this example, solutions x2 and x3 become locally competitive when ` > 1;
while solutions x7 and x9 are locally noncompetitive for all ` settings. It is worth noting that neither
x2 nor x3 is the representative solution of any subproblem; in the meanwhile, they are crowded in a
narrow area. Since these locally competitive solutions have better ranks in the preference lists than
those less competitive ones, the original stable matching-based selection tends to give them higher
priorities to form the matching pairs. However, this selection result is obviously harmful for the
population diversity. In addition, we also notice that x7 and x9 are the representative solutions of
p3 and p4 , thus they should contain some relevant information for optimizing these subproblems.
In contrast, although x2 and x3 have better aggregation function values, they are far away from
p3 and p4 and should be less relevant to them. To resolve these issues, our proposed adaptive
mechanism adaptively restricts the length of the preference list of each solution x by removing

11

Algorithm 6: AdaptiveSetR(P, S, ΨX )
Input:
• subproblem set P and solution set S
• solution preference matrix ΨX
1
2
3
4
5
6
7
8

Output: length of solution’s preference list set R
for i ← 1 to Q do
Φ[i] ← ΨX [i][1];
for j ← 1 to N do
χ ← {i|Φ[i] = j, i ∈ 1, 2, ..., Q};
if χ = ∅ then
ϕ[j] ← −1;
else
ϕ[j] ← arg min g tch (xi |λj , z∗ );
i∈χ

9
10
11
12
13
14
15
16
17

for i ← 1 to Q do
ri ← m;
for ` ← m + 1 to `max do
t ← ϕ[ΨX [i][`]];
if t 6= −1 then
if xi ≺ xt then
break;
ri ← `;
return R;

subproblems whose representative solution is dominated by x. By these means, we can make sure
that each solution does not consider a subproblem which prefers this solution to its own representative
solution. Thus each subproblem is prevented from matching with a less relevant solution. Note that
this adaptive mechanism can be readily plugged into both of our proposed two versions of stable
matching-based selection mechanisms by using Algorithm 6 to replace line 2 of Algorithm 4 and
Algorithm 5, respectively. The adaptive two-level one-one stable matching-based selection mechanism
and the adaptive many-one stable matching-based selection mechanism are denoted by AOOSTM
and AMOSTM for short.

3.5 Time Complexity of AOOSTM and AMOSTM
In this subsection, we analyze the complexity of AOOSTM and AMOSTM. For both selection mechanisms, the calculation of ∆P (p, x) and ∆X (x, p) cost O(N QlogQ) computations [10]. In Algorithm 6,
the association operation between subproblems and solutions costs O(Q) calculations (line 1 to line
2). As for line 3 to line 8 of Algorithm 6, the identification of the representative solution for each
subproblem requires O(mN Q) computations. Thereafter, the computation of R in line 9 to line
16 of Algorithm 6 costs O(mQ(`max − m)) computations in the worst case. Considering the twolevel one-one stable matching in Algorithm 4, the complexity of the one-one stable matching with
the incomplete lists in line 3 is O(N `max ), which is simpler than the original stable matching with
complete preference lists [10]. Next, the complexity of line 4 to line 6 of Algorithm 4 is O(N + Q).
During the second-level stable matching (line 7 to line 8 of Algorithm 4), same complexity analysis

12

Algorithm 7: MOEA/D–AOOSTM/AMOSTM
Input: algorithm parameters
Output: final population S
1 Initialize the population S, a set of weight vectors W and their neighborhood structure B;
2 M ← Random one-one matching between P and S;
3 neval ← 0, iteration ← 0;
4 while Stopping criterion is not satisfied do
5
Select the current active subproblems to form I;
6
for each i ∈ I do
7
if unif orm(0, 1) < δ && |E| >= T then
8
E ← {M (p)|p ∈ B(i)};
9
else
10
E ← S;
11
12
13
14
15
16
17
18

Randomly select mating solutions from E and generate an offspring x, S ← S ∪ x;
Evaluate F(x), neval++;
M ← SelectionOOSTM2L/MOSTM(P , S);
S ← {M (p)|p ∈ P };
iteration++;
if mod(iteration, 30) = 0 then
Update the utility of each subproblem;
return S;

can be done for the remaining subproblems and solutions. Overall, the total complexity of AOOSTM
is O(max(N QlogQ, mQ(`max − m))). When it comes to AMOSTM, since Algorithm 5 is solutionoriented, the computational complexity of line 3 to line 19 is O(Q`max ). The total complexity of
AMOSTM is still O(max(N QlogQ, mQ(`max − m))).

3.6 Incorporation with MOEA/D
Similar to [10], we choose the MOEA/D-DRA [22] as the base framework and replace the update
mechanism by the AOOSTM and AMOSTM selection mechanisms developed in Section 3.4. The
resulted algorithms are denoted by MOEA/D-AOOSTM and MOEA/D-AMOSTM, of which the
pseudo code is given in Algorithm 7. Note that the normalization scheme proposed in [27] is adopted
to handle MOPs with different scales of objectives. In the following paragraphs, some important
components of MOEA/D-AOOSTM/AMOSTM are further illustrated.
3.6.1 Initialization
Without any prior knowledge of the landscape, the initial population S = {x1 , · · · , xN } is randomly
sampled from Ω. Same as the original MOEA/D, we use the classic method suggested in [28] to
generate a set of uniformly distributed weight vectors W = {w1 , · · · , wN } on a unit simplex. In
addition, for each weight vector wi , i ∈ {1, · · · , N }, we assign its T , 1 ≤ T ≤ N , closest weight
vectors as its neighbors.
3.6.2 Reproduction
According to the underlying test problem, here we employ the widely used differential evolution
(DE) [29], simulated binary crossover (SBX) [30] and polynomial mutation [31] for offspring genera-

13

tion.
3.6.3 Utility of Subproblem [22]
The utility of subproblem pi , denoted by π i , i ∈ {1, · · · , N }, measures the improvement rate of pi .
We make some modifications on π i to fit our proposed MOEA/D-AOOSTM/AMOSTM:


if ∆i > 0.001
1
i
π = 0.95 × π i
(7)
if ∆i < 0

i

∆
) × π i otherwise
(0.95 + 0.05 × 0.001
where ∆i represents the relative decrease of the scalar objective value of pi and is evaluated as:
( gtch (xi,old |wi ,z∗ )−gtch (xi,best |wi ,z∗ )
if M (pi ) 6= ∅
g tch (xi,old |wi ,z∗ )
∆i =
(8)
0
otherwise
where xi,best = arg min g tch (x|wi , z∗ ) is the best solution matched with pi in the current generation
x∈M (pi )

and

xi,old

is the previously saved value of xi,best .

4 Experimental Settings
This section presents the general setup of our empirical studies, including the benchmark problems,
algorithms in comparisons, parameter settings and performance metrics.

4.1 Benchmark Problems
From three popular benchmark suites, i.e., MOP [13], UF [32] and WFG [33], 62 problem instances in
total, are chosen as the benchmark set in our empirical studies. These problem instances have various
characteristics, e.g., non-convexity, deceptive, multi-modality. According to the recommendations in
the original references, the number of decision variables is set as: n = 10 for the MOP instances and
n = 30 for the UF instances. As the WFG instances are scalable to any number of objectives, here
we consider m ∈ {2, 3, 5, 8, 10}. In particular, when m = 2, n = k + l [12], where the position-related
variable k = 2 and the distance-related variable l = 4; while for m ≥ 3, we use the recommended
settings in [16] and [27], i.e., k = 2 × (m − 1) and l = 20.

4.2 Algorithms in Comparisons
Nine state-of-the-art EMO algorithms, i.e., MOEA/D-STM, MOEA/D-IR [12], gMOEA/D-AGR [15],
MOEA/D-M2M [13], MOEA/D-DRA, HypE [7], NSGA-III [27], PICEA-g [34] and MOEA/DD [16],
are considered in our empirical studies. In particular, the first seven algorithms are used for comparative studies on problems with complicated PSs; while the latter five are chosen to investigate the
scalability on problems with more than three objectives. The characteristics of these algorithms are
briefly described in the supplementary file of this paper1 .

4.3 Parameter Settings
Referring to [10, 12] and [16], the settings of the population size N for different benchmark problems
are shown in Table 1. The stopping condition of each algorithm is the predefined number of function
1

https://coda-group.github.io/publications/suppASTM.pdf

14

Table 1: Settings of Population Size.
Benchmark Problem

m

Population Size

UF1 to UF7

2

600

UF8 to UF10

3

1,000

MOP1 to MOP5

2

100

MOP6 to MOP7

3

300

WFG1 to WFG9

2

250

WFG1 to WFG9

3

91

WFG1 to WFG9

5

210

WFG1 to WFG9

8

156

WFG1 to WFG9

10

275

evaluations. In particular, it is set to 300, 000 for the UF and MOP instances [10], and 25, 000 for the
bi-objective WFG instances [12]. As for the many-objective WFG instances, where m ∈ {3, 5, 8, 10},
the number of function evaluations is set as 91 × N , 210 × N , 156 × N and 275 × N , respectively [16].
The parameters of our proposed MOEA/D-AOOSTM and MOEA/D-AMOSTM are set as follows:
• Reproduction operators: As for problems with complicated properties, we use the DE operator
and polynomial mutation for offspring generation. As recommended in [12], we set CR = 1.0
and F = 0.5 for the UF and MOP instances; while CR = F = 0.5 for bi-objective WFG
instances. The mutation probability pm is set to be n1 and its distribution index ηm equals
20. For problems with more than three objectives, we use the SBX operator to replace the DE
operator, where the crossover probability pc = 1 and its distribution index ηc = 30 [27]. All
other MOEA/D variants in our experimental studies share the same settings for reproduction
operators.
• Neighborhood size: T = 20 [10, 12].
• Probability to select B in the neighborhood : δ = 0.9 [22].

4.4 Performance Metrics
To assess the performance of different algorithms, we choose the following two widely used performance metrics:
1. Inverted Generational Distance (IGD) [35]: Given P ∗ as a set of points uniformly sampled
along the PF and P as the set of solutions obtained from an EMO algorithm. The IGD value
of P is calculated as:
P
∗ dist(z, P )
∗
IGD(P , P ) = z∈P ∗
,
(9)
|P |
where dist(z, P ) is the Euclidean distance of z to its nearest point in P .
r )T be a point dominated by all the Pareto optimal
2. Hypervolume (HV) [36]: Let zr = (z1r , · · · , zm
objective vectors. The HV of P is defined as the volume of the objective space dominated by
the solutions in P and bounded by zr :
[
r
HV (P ) = VOL(
[z1 , z1r ] × · · · × [zm , zm
]),
(10)
z∈P

15

Table 2: IGD Results on MOP Test Instances.
Problem

IGD

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

MOP1

Mean
Std
Rank

3.380E-1
5.908E-2
6−↓

3.509E-1
2.786E-2
7−↓

4.726E-2
2.811E-3
5−↓

3.189E-2
9.792E-3
4−↓

1.614E-2
4.586E-4
1+↑

3.652E-1
3.337E-3
8−↓

8.013E-1
1.060E-2
9−↓

2.407E-2
2.907E-3
3k

2.390E-2
2.551E-3
2

MOP2

Mean
Std
Rank

2.836E-1
7.028E-2
6−↓

3.083E-1
6.782E-2
7−↓

3.200E-2
2.798E-2
4−↓

6.846E-2
7.344E-2
5−↓

1.061E-2
1.578E-3
1−↓

3.436E-1
1.478E-2
8−↓

5.980E-1
2.155E-1
9−↓

2.034E-2
4.301E-2
2k

3.115E-2
6.203E-2
3

MOP3

Mean
Std
Rank

4.927E-1
2.885E-2
8−↓

4.913E-1
3.391E-2
7−↓

4.267E-2
3.691E-2
4−↓

6.785E-2
8.518E-2
5−↓

1.269E-2
3.924E-3
1−↓

3.869E-1
1.337E-16
6−↓

6.094E-1
1.742E-1
9−↓

4.140E-2
7.378E-2
3k

3.203E-2
6.527E-2
2

MOP4

Mean
Std
Rank

3.068E-1
2.749E-2
6−↓

3.136E-1
1.840E-2
7−↓

3.843E-2
2.928E-2
4−↓

3.934E-2
4.065E-2
5−↓

7.774E-3
7.983E-4
1+↑

3.147E-1
1.845E-2
8−↓

7.107E-1
1.041E-2
9−↓

2.025E-2
3.284E-2
3↓

1.414E-2
1.155E-2
2

MOP5

Mean
Std
Rank

3.168E-1
7.241E-3
8−↓

3.135E-1
1.268E-2
7−↓

5.573E-2
2.524E-3
5−↓

2.379E-2
3.323E-3
4−↓

2.195E-2
2.489E-3
3−↓

2.911E-1
2.422E-2
6−↓

1.023E+0
2.343E-1
9−↓

2.035E-2
1.692E-3
1k

2.042E-2
1.803E-3
2

MOP6

Mean
Std
Rank

3.061E-1
2.161E-8
7−↓

3.046E-1
9.552E-3
6−↓

1.146E-1
7.590E-3
5−↓

8.016E-2
1.015E-2
3−↓

8.547E-2
3.941E-3
4−↓

3.065E-1
4.459E-4
8−↓

5.750E-1
1.620E-2
9−↓

5.398E-2
3.094E-3
2k

5.328E-2
2.917E-3
1

MOP7

Mean
Std
Rank

3.501E-1
7.648E-3
6−↓

3.512E-1
1.463E-7
7−↓

1.778E-1
1.052E-2
4−↓

2.458E-1
3.239E-2
5−↓

1.171E-1
8.566E-3
3−↓

3.514E-1
9.279E-4
8−↓

6.377E-1
9.311E-3
9−↓

8.186E-2
2.778E-3
2↓

7.912E-2
2.619E-3
1

Total Rank
Final Rank

47
6

48
7

31
4

31
4

14
2

52
8

63
9

16
3

13
1

According to Wilcoxon’s rank sum test, +, − and ≈ indicate that the corresponding EMO algorithm is significantly better
than, worse than or similar to MOEA/D-AOOSTM, while ↑, ↓ and k indicate that the corresponding EMO algorithm is
significantly better than, worse than or similar to MOEA/D-AMOSTM.

where VOL indicates the Lebesgue measure.
Since the objective functions of WFG instances are in different scales, we normalize their PFs
and the obtained solutions in the range of [0, 1] before calculating the performance metrics. In this
case, we constantly set zr = (1.2, · · · , 1.2)T in the HV calculation. Note that both IGD and HV
can evaluate the convergence and diversity simultaneously. A smaller IGD value or a large HV value
indicates a better approximation to the PF. Each algorithm is independently run 51 times. The mean
and standard deviation of the IGD and HV values are presented in the corresponding tables, where
the ranks of each algorithms on each problems are also given by sorting the mean metric values. The
best metric values are highlighted in boldface with a gray background. To have a statistically sound
conclusion, we use the Wilcoxon’s rank sum test at a significant level of 5% to evaluate whether the
proposed MOEA/D-AOOSTM and MOEA/D-AMOSTM are significantly better or worse than the
others. In addition, we use the two-sample Kolmogorov-Smirnov test at a significant level of 5% to
summarize the relative performance of all test EMO algorithms.

5 Empirical Studies
In this section, we first analyze the comparative results for problems with complicated properties.
Afterwards, we investigate the effectiveness of the adaptive mechanism. In the end, we summarize
the experimental studies in a statistical point of view. Due to the page limits, the empirical studies
on problems with more than three objectives are given in the supplementary file of this paper.

16

Table 3: HV Results on MOP Test Instances.
Problem

HV

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

MOP1

Mean
Std
Rank

0.564
1.097E-1
6−↓

0.540
5.309E-2
7−↓

1.027
4.908E-3
5−↓

1.062
1.202E-2
4−↓

1.080
9.058E-4
1+↑

0.515
8.867E-3
8−↓

0.292
1.355E-2
9−↓

1.071
3.882E-3
3k

1.072
3.267E-3
2

MOP2

Mean
Std
Rank

0.476
4.459E-2
6−↓

0.466
4.257E-2
7−↓

0.717
3.322E-2
4−↓

0.680
9.570E-2
5−↓

0.756
2.340E-3
1−↓

0.445
8.938E-3
8−↓

0.320
9.798E-2
9−↓

0.745
5.037E-2
2k

0.731
7.825E-2
3

MOP3

Mean
Std
Rank

0.240
1.665E-16
8−↓

0.240
1.665E-16
9−↓

0.595
5.361E-2
4−↓

0.560
1.240E-1
5−↓

0.637
4.858E-3
1−↓

0.440
2.201E-16
6−↓

0.316
9.708E-2
7−↓

0.606
7.281E-2
3k

0.617
6.263E-2
2

MOP4

Mean
Std
Rank

0.578
2.040E-2
6−↓

0.578
1.746E-2
7−↓

0.917
4.097E-2
4−↓

0.912
5.434E-2
5−↓

0.945
2.076E-3
1+↑

0.570
9.318E-3
8−↓

0.337
1.097E-2
9−↓

0.931
4.521E-2
3↓

0.939
1.518E-2
2

MOP5

Mean
Std
Rank

0.635
4.447E-9
8−↓

0.636
8.201E-3
7−↓

1.006
9.637E-3
5−↓

1.067
8.135E-3
3−↓

1.067
4.295E-3
4−↓

0.648
2.991E-2
6−↓

0.060
1.806E-1
9−↓

1.073
3.038E-3
2k

1.074
3.196E-3
1

MOP6

Mean
Std
Rank

1.221
5.183E-7
7−↓

1.224
1.470E-2
6−↓

1.418
1.843E-2
5−↓

1.463
1.639E-2
3−↓

1.439
1.100E-2
4−↓

1.216
5.601E-3
8−↓

0.682
3.505E-2
9−↓

1.494
6.155E-3
2k

1.495
5.671E-3
1

MOP7

Mean
Std
Rank

0.939
2.763E-3
6−↓

0.939
1.317E-6
7−↓

1.038
2.296E-2
4−↓

1.005
4.975E-2
5−↓

1.047
2.397E-2
3−↓

0.933
5.768E-3
8−↓

0.538
6.204E-3
9−↓

1.084
5.196E-3
2↓

1.088
4.578E-3
1

Total Rank
Final Rank

47
6

50
7

31
5

30
4

15
2

52
8

61
9

17
3

12
1

According to Wilcoxon’s rank sum test, +, − and ≈ indicate that the corresponding EMO algorithm is significantly better
than, worse than or similar to MOEA/D-AOOSTM, while ↑, ↓ and k indicate that the corresponding EMO algorithm is
significantly better than, worse than or similar to MOEA/D-AMOSTM.

5.1 Performance Comparisons on MOP Instances
As discussed in [13], MOP benchmark suite, in which different parts of the PF have various difficulties, poses significant challenges for maintaining the population diversity. Table 2 and Table 3
demonstrate the IGD and HV results of the nine EMO algorithms. From the IGD results shown in
Table 2, it can be seen that MOEA/D-AMOSTM shows the best overall performance and MOEA/DAOOSTM, obtaining a slightly lower total rank than MOEA/D-M2M, ranks in the third place. In
terms of the mean IGD values, MOEA/D-M2M gives the best results on MOP1 to MOP4, while
MOEA/D-AOOSTM ranks the first on MOP5 and MOEA/D-AMOSTM beats all other EMO algorithms on MOP6 and MOP7. When it comes to the Wilcoxon’s rank sum test results, both
MOEA/D-AMOSTM and MOEA/D-AOOSTM are significantly better the others on MOP2, MOP3
and MOP5 to MOP7. They are only beaten by MOEA/D-M2M on MOP1 and MOP4. This is because
MOEA/D-AMOSTM and MOEA/D-AOOSTM achieve better performance on MOP2 and MOP3
than MOEA/D-M2M but the former two have large variances. Comparing MOEA/D-AOOSTM
and MOEA/D-AMOSTM, they have no significant differences on five problems but the former is
outperformed by the latter on MOP4 and MOP7. Following the best three algorithms, MOEA/DIR and gMOEA/D-AGR are able to obtain a set of non-dominated solutions moderately covering
the entire PF. As for MOEA/D-DRA, MOEA/D-STM, NSGA-III and HypE, they can only obtain
some solutions lying on the boundaries. Table 3 shows similar results in HV tests, except that
MOEA/D-AMOSTM obtains better performance than MOEA/D-AOOSTM on MOP5.
We plot the final solution sets with the best IGD values in 51 runs on all test instances in the
supplementary file of this paper. From Fig. 1 to Fig. 4 of the supplementary file, we can see that
although MOEA/D-M2M obtains slightly better mean IGD and HV metric values than MOEA/DAMOSTM and MOEA/D-AOOSTM, the solutions obtained by MOEA/D-AMOSTM and MOEA/D-

17

AOOSTM have a more uniform distribution along the PF. This can be explained by the density
estimation method, i.e., the crowding distance of NSGA-II, used in MOEA/D-M2M, which is too
coarse to guarantee the population diversity. Nevertheless, the convergence ability of MOEA/DM2M is satisfied, thus contributing to promising IGD values on MOP1 to MOP4. According to [15],
gMOEA/D-AGR uses a sigmoid function to assign a same replacement neighborhood size to all
subproblems. However, since different parts of the PF require various efforts, this same setting
might not be appropriate for all subproblems. From Fig. 3 and Fig. 7 of the supplementary file, we
can obverse that the solutions obtained by gMOEA/D-AGR may miss some segments of the PF.
This can be explained by the replacement neighborhood that grows too fast for the corresponding
subproblems. In order to emphasize the population diversity, for each subproblem, MOEA/D-IR
selects the appropriate solution from a couple of related ones. However, its preference setting, which
encourages the selection in a less crowded area, tends to result in an unstable selection result. In this
case, some solutions far away from the PF can be selected occasionally. The reason behind the poor
performance of NSGA-III, HypE and MOEA/D-DRA is that their convergence first and diversity
second selection strategies may easily trap the population in some narrow areas. As discussed in
Section 2.3, the stable matching model used in MOEA/D-STM can easily match a solution with an
unfavorable subproblem, thus resulting in an unbalanced selection.

5.2 Performance Comparisons on UF Instances
The comparison results on the IGD and HV metrics between MOEA/D-AOOSTM, MOEA/DAMOSTM and the other EMO algorithms on UF benchmark suite are presented in Table 4 and
Table 5. Different from the MOP benchmark suite, the major source of difficulty for the UF benchmark suite is not the diversity preservation but the complicated PS. Generally speaking, the overall performance of MOEA/D-AOOSTM ranks the first on the UF benchmark suite, followed by
MOEA/D-AMOSTM and their predecessor MOEA/D-STM. More specifically, for both the IGD and
HV metrics, MOEA/D-AOOSTM performs the best on UF1, UF2 and UF8 and acts as the top
three algorithm on all instances except for UF4, UF5 and UF10. For UF3 and UF7, the performance
of MOEA/D-AOOSTM does not show significant difference with the best performing algorithms.
MOEA/D-AMOSTM shows similar rankings to MOEA/D-AOOSTM. It is significantly better than
MOEA/D-AOOSTM on UF4-UF6 and UF9 in terms of both the IGD and HV metrics. In contrast,
MOEA/D-AOOSTM wins on UF2, UF8 and UF10 according to Wilcoxon’s rank sum test of the
IGD results and wins on UF1, UF2, UF7, UF8 and UF10 in the HV tests.
According to the performance of different algorithms on the UF test instances, the analysis can be
divided into three groups. For UF4 and UF5, MOEA/D-M2M, NSGA-III and HypE are able to provide better performance than all other MOEA/D variants. All these three algorithms use the Pareto
dominance as the major driving force in the environmental selection, which can improve the convergence to a great extent. For UF1 to UF3 and UF6 to UF9, all the MOEA/D variants outperform
NSGA-III and HypE. In particular, The three variants with stable matching-based selection, i.e.,
MOEA/D-AOOSTM, MOEA/D-AMOSTM and MOEA/D-STM, have shown very promising results
on these six test instances. The superior performance can be attributed to the well balance between
convergence and diversity achieved by the stable matching relationship between subproblems and
solutions. gMOEA/D-AGR has shown a medium performance for the former two groups of problem
instances. This might be due to its adaptive mechanism that can hardly make a satisfied prediction
of the replacement neighborhood size. UF10 is a difficult tri-objective problem, where none of these
eight EMO algorithms are able to obtain a well approximation to the PF within the given number
of function evaluations. Nevertheless, it is worth noting that the empirical studies in [10] demonstrate that the stable matching-based selection mechanism can offer a competitive result in case the
maximum number of function evaluations is doubled.

18

Table 4: IGD Results on UF Test Instances.
Problem

IGD

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

UF1

Mean
Std
Rank

1.071E-3
2.583E-4
4−↓

1.043E-3
7.870E-5
3−↓

2.471E-3
1.180E-4
6−↓

1.813E-3
8.699E-5
5−↓

7.076E-3
2.785E-3
7−↓

9.457E-2
1.200E-2
8−↓

9.902E-2
1.089E-2
9−↓

9.631E-4
4.650E-5
1k

9.696E-4
5.158E-5
2

UF2

Mean
Std
Rank

4.601E-3
9.338E-3
5≈k

3.024E-3
9.309E-4
3−↓

5.475E-3
1.172E-3
7−↓

5.256E-3
7.183E-4
6−↓

3.957E-3
5.099E-4
4−↓

2.993E-2
2.629E-3
8−↓

2.119E-1
6.301E-2
9−↓

2.270E-3
5.587E-4
1↑

2.577E-3
5.649E-4
2

UF3

Mean
Std
Rank

1.772E-2
1.500E-2
7−↓

7.757E-3
6.213E-3
3≈↓

1.642E-2
1.289E-2
6−↓

8.141E-3
8.673E-3
4≈↓

1.549E-2
5.495E-3
5−↓

2.078E-1
4.775E-2
9−↓

1.805E-1
5.100E-2
8−↓

7.296E-3
8.380E-3
2k

4.110E-3
3.128E-3
1

UF4

Mean
Std
Rank

5.320E-2
3.115E-3
8≈↓

5.076E-2
2.857E-3
6+k

5.623E-2
2.818E-3
9−↓

5.025E-2
2.874E-3
4+k

3.994E-2
3.705E-4
1+↑

4.297E-2
8.311E-4
2+↑

4.899E-2
7.077E-3
3+↑

5.269E-2
3.523E-3
7↓

5.043E-2
2.803E-3
5

UF5

Mean
Std
Rank

3.033E-1
7.779E-2
9−↓

2.397E-1
3.369E-2
5+k

2.574E-1
4.334E-2
7≈↓

2.625E-1
1.102E-1
8≈k

1.795E-1
3.013E-2
1+↑

2.107E-1
2.131E-2
2+↑

2.289E-1
4.852E-2
3+↑

2.514E-1
1.766E-2
6↓

2.392E-1
2.220E-2
4

UF6

Mean
Std
Rank

1.504E-1
1.224E-1
7−↓

7.805E-2
4.305E-2
2+k

1.073E-1
4.600E-2
5−↓

1.126E-1
7.840E-2
6−↓

8.990E-2
5.355E-2
4≈↓

2.134E-1
6.523E-2
8−↓

2.312E-1
6.828E-2
9−↓

8.146E-2
4.048E-2
3↓

6.876E-2
3.300E-2
1

UF7

Mean
Std
Rank

1.245E-3
2.371E-4
4≈↓

1.123E-3
7.371E-5
1≈k

3.707E-3
5.295E-4
6−↓

2.145E-3
3.221E-4
5−↓

6.234E-3
1.867E-3
7−↓

6.856E-2
8.357E-2
8−↓

2.622E-1
4.540E-2
9−↓

1.150E-3
1.095E-4
3k

1.148E-3
1.481E-4
2

UF8

Mean
Std
Rank

3.104E-2
4.020E-3
3−↑

3.019E-2
8.706E-3
2≈↑

6.467E-2
1.070E-2
6−↓

4.715E-2
9.477E-3
4−↑

9.655E-2
8.181E-3
7−↓

1.674E-1
2.670E-3
8−↓

3.116E-1
3.417E-2
9−↓

2.921E-2
5.154E-3
1↑

5.393E-2
9.528E-3
5

UF9

Mean
Std
Rank

4.779E-2
3.446E-2
4−↓

2.373E-2
1.112E-3
1+k

5.794E-2
3.960E-2
5−↓

5.861E-2
4.572E-2
6−↓

1.148E-1
3.045E-2
7−↓

1.767E-1
3.924E-2
8−↓

2.353E-1
3.018E-2
9−↓

3.704E-2
3.125E-2
2↓

3.769E-2
4.306E-2
3

UF10

Mean
Std
Rank

5.184E-1
6.698E-2
4+↑

1.701E+0
2.849E-1
8−↑

7.216E-1
1.202E-1
6+↑

4.168E-1
7.165E-2
3+↑

5.572E-1
5.950E-2
5+↑

2.257E-1
5.700E-2
1+↑

2.568E-1
6.938E-2
2+↑

1.028E+0
2.943E-1
7↑

2.426E+0
1.868E-1
9

Total Rank
Final Rank

55
6

34
2

63
8

51
5

48
4

62
7

70
9

33
1

34
2

According to Wilcoxon’s rank sum test, +, − and ≈ indicate that the corresponding EMO algorithm is significantly better
than, worse than or similar to MOEA/D-AOOSTM, while ↑, ↓ and k indicate that the corresponding EMO algorithm is
significantly better than, worse than or similar to MOEA/D-AMOSTM.

5.3 Performance Comparisons on Bi-Objective WFG Instances
From the comparison results shown in Table I and Table II of the supplementary file, it can be
seen that MOEA/D-AOOSTM and MOEA/D-AMOSTM are the best two algorithms in overall
performance on the bi-objective WFG instances. Comparing with the seven existing algorithms,
MOEA/D-AOOSTM and MOEA/D-AMOSTM achieves significant better performance in 56 and
57 out of 63 IGD comparisons respectively. As for HV results, they both wins in 57 comparisons.
In particular, MOEA/D-AOOSTM and MOEA/D-AMOSTM obtain the best mean metric values
on WFG1, WFG3, WFG6, WFG7 and WFG9 and obtain very promising results on WFG3 and
WFG5. Even though the mean HV metric values of MOEA/D-AOOSTM and MOEA/D-AMOSTM
on WFG2 rank the fifth and sixth, all the other algorithms are significantly worse than them. It
is interesting to note that MOEA/D-AOOSTM and MOEA/D-AMOSTM are significantly better
than MOEA/D-STM on all WFG instances except for WFG8. One possible reason is the proper
normalization method used in MOEA/D-AOOSTM/AMOSTM. However, we also notice that the
performance of NSGA-III fluctuates significantly on difficult problem instances, though it uses the
same normalization method. The other variants of MOEA/D perform more or less the same on all

19

Table 5: HV Results on UF Test Instances.
Problem

HV

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

UF1

Mean
Std
Rank

1.104
6.732E-4
4−k

1.104
4.643E-4
3−k

1.101
6.668E-4
6−↓

1.102
4.079E-4
5−↓

1.092
5.167E-3
7−↓

0.945
2.713E-2
8−↓

0.941
2.800E-2
9−↓

1.104
3.180E-4
1↑

1.104
4.627E-4
2

UF2

Mean
Std
Rank

1.097
1.238E-2
5−k

1.100
1.889E-3
3−k

1.093
3.835E-3
7−↓

1.096
1.866E-3
6−↓

1.099
1.903E-3
4−↓

1.054
6.402E-3
8−↓

0.889
4.580E-2
9−↓

1.101
1.730E-3
1↑

1.101
1.395E-3
2

UF3

Mean
Std
Rank

1.073
2.867E-2
7−↓

1.093
1.066E-2
3−↓

1.075
2.590E-2
6−↓

1.090
1.848E-2
4≈↓

1.079
8.270E-3
5−↓

0.732
5.290E-2
9−↓

0.793
6.111E-2
8−↓

1.094
1.513E-2
2k

1.099
5.436E-3
1

UF4

Mean
Std
Rank

0.672
5.996E-3
8−↓

0.679
5.759E-3
6≈k

0.667
5.444E-3
9−↓

0.680
5.213E-3
4+k

0.701
7.356E-4
1+↑

0.698
1.257E-3
2+↑

0.685
1.459E-2
3+↑

0.676
6.500E-3
7↓

0.679
5.755E-3
5

UF5

Mean
Std
Rank

0.353
8.320E-2
9−↓

0.437
7.346E-2
5+k

0.414
8.085E-2
7≈k

0.455
1.201E-1
4+k

0.574
6.204E-2
1+↑

0.536
3.906E-2
2+↑

0.519
7.893E-2
3+↑

0.411
3.560E-2
8↓

0.434
4.814E-2
6

UF6

Mean
Std
Rank

0.591
1.152E-1
9−↓

0.645
8.742E-2
5≈k

0.610
8.839E-2
7−↓

0.647
6.045E-2
3≈↓

0.685
4.863E-2
1≈k

0.621
2.851E-2
6−↓

0.592
6.576E-2
8−↓

0.646
8.337E-2
4↓

0.666
6.562E-2
2

UF7

Mean
Std
Rank

0.937
9.245E-4
4−k

0.937
4.244E-4
1≈↑

0.931
1.589E-3
6−↓

0.935
1.674E-3
5−↓

0.928
3.597E-3
7−↓

0.831
1.055E-1
8−↓

0.610
3.176E-2
9−↓

0.937
6.227E-4
2↑

0.937
6.386E-4
3

UF8

Mean
Std
Rank

1.127
9.272E-3
2−↑

1.125
1.428E-2
3−↑

1.050
2.737E-2
6−↓

1.088
2.234E-2
4−↑

0.938
2.383E-2
7−↓

0.777
4.349E-3
9−↓

0.783
3.482E-3
8−↓

1.143
1.291E-2
1↑

1.073
2.411E-2
5

UF9

Mean
Std
Rank

1.402
6.489E-2
4−↓

1.462
3.831E-3
1−↓

1.400
7.704E-2
5−↓

1.395
9.007E-2
6−↓

1.243
5.711E-2
7−↓

0.971
7.193E-2
8−↓

0.855
8.419E-2
9−↓

1.455
6.385E-2
2↓

1.453
8.895E-2
3

UF10

Mean
Std
Rank

0.188
4.694E-2
4+↑

0.000
3.781E-4
8−k

0.063
4.914E-2
6+↑

0.311
6.402E-2
3+↑

0.172
3.272E-2
5+↑

0.653
1.121E-1
1+↑

0.612
1.286E-1
2+↑

0.015
3.031E-2
7↑

0.000
0.000E+0
9

Total Rank
Final Rank

56
6

38
2

65
8

44
4

45
5

61
7

68
9

35
1

38
2

According to Wilcoxon’s rank sum test, +, − and ≈ indicate that the corresponding EMO algorithm is significantly better
than, worse than or similar to MOEA/D-AOOSTM, while ↑, ↓ and k indicate that the corresponding EMO algorithm is
significantly better than, worse than or similar to MOEA/D-AMOSTM.

test instances except MOEA/D-M2M significantly outperforms all other EMO algorithms on WFG8.
The indicator-based algorithm HypE performs the worst on all nine problems. Comparing the IGD
and HV results, the algorithm comparisons are consistent on most test instances, except when the
performance of two algorithms are very close, the ranking of IGD and HV metric values may change
slightly. However, it is worth noting that the algorithms perform quite differently on WFG2 under
the IGD and HV assessments. NSGA-III shows the best mean IGD value but gives the second worst
mean HV value. In contrast, the mean HV value of gMOEA/D-AGR ranks the first among all
algorithms but its mean IGD value only obtains a rank of 7. This is probably because WFG2 has a
discontinuous PF, which makes the distinction between IGD and HV more obvious.

5.4 Effectiveness of the Adaptive Mechanism
To show the functionality of the adaptive mechanism proposed in Section 3.4, we choose MOP1 as
an example and plot the trajectories of r of the selected solutions of four different subproblems,
i.e., p1 , p34 , p67 and p100 , controlled by the local competitiveness-based adaptive mechanism. From
trajectories shown in Fig. 3, we notice that the r value fluctuates significantly at the early stages

20

p1

p34

15

15

r

20

r

20

10

10

5

5

0

0

0.2

0.4

0.6

0.8

1

1.2

Number of Generations

0

1.4
·104

0

0.2

0.4

0.6

0.8

1

1.2

Number of Generations

p67

1.4
·104

p100

15

15

r

20

r

20

10

10

5

5

0

0

0.2

0.4

0.6

0.8

1

1.2

Number of Generations

0

1.4
·104

0

0.2

0.4

0.6

0.8

1

1.2

Number of Generations

1.4
·104

Figure 3: The illustration of the r values of the solutions selected by subproblems p1 , p34 , p67 and
p100 .
of the evolution. Afterwards, it almost convergences to the threshold `max . This is because the
local competitiveness varies dramatically when the population is far away from but heading to the
PF. With the progress of evolution, the selected solutions gradually become non-dominated from
each other. As a consequence, the value of `, which keeps the solution locally noncompetitive,
grows and finally settles at `max . All in all, we can see that different solutions have different local
competitiveness, thus it is meaningful to have a different length of the preference list.
In order to further investigate the effectiveness brought by our proposed adaptive mechanism, we
develop two variants, denoted by MOEA/D-AOOSTM-v and MOEA/D-AMOSTM-v, in which all
solutions share the same static r setting. From the our offline parameter studies, we finally find that
r = 4 and r = 8 are the best settings for MOP and UF benchmark suites respectively. Thereafter,
in Table VII of the supplementary file, we show the IGD results of MOEA/D-AOOSTM-v and
MOEA/D-AMOSTM-v with the best r settings. Comparing with the best static settings of r, we
can see that both MOEA/D-AOOSTM and MOEA/D-AMOSTM obtain better mean IGD values
than their variant on 11 out of 17 problems. Even though MOEA/D-AOOSTM-v and MOEA/DAMOSTM-v perform better on some test instances, in most of the cases, our proposed adaptive
mechanism achieve comparable results to the best settings of r. Note that the optimal r settings are
obtained from a series of comprehensive try-and-error experiments, which are not as intelligent and
flexible as our proposed adaptive mechanism. Therefore, we conclude that our proposed adaptive
mechanism based on the local competitiveness is generally effective for dynamically setting the length
of the solution’s preference list.

5.5 Summaries
We summarize the total ranks of different algorithms based on the mean metric values in Table 6
and Table 7 and compute their final ranks over all test instances. As can be seen from the tables,
the proposed MOEA/D-AOOSTM and MOEA/D-AMOSTM remain the two best algorithms on all
test instances. It seems that MOEA/D-AOOSTM achieves better performance under the HV metric
while MOEA/D-AMOSTM obtains better IGD results.
To analyze the relative performance of different algorithms in a statistical point of view, we adopt

21

Table 6: Final Ranks of Mean Metric Values on MOP, UF and Bi-Objective WFG Test Instances.
Metric

Rank

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

IGD

Total Rank
Final Rank

146
6

124
5

160
8

123
4

115
3

154
7

214
9

68
2

66
1

HV

Total Rank
Final Rank

147
6

132
5

165
8

104
3

109
4

157
7

209
9

72
1

75
2

Table 7: Final Ranks of Mean Metric Values on 3-, 5-, 8- and 10-Objective WFG Test Instances.
Metric

Rank

DRA

MOEA/DD

PICEA-g

NSGA-III

HypE

AOOSTM

AMOSTM

HV

Total Rank
Final Rank

223
6

153
5

133
4

120
3

226
7

70
1

83
2

Table 8: Average Performance Scores on MOP, UF and Bi-Objective WFG Test Instances.
Metric

Problem

DRA

STM

IR

AGR

M2M

NSGA-III

HypE

AOOSTM

AMOSTM

IGD

MOP
UF
WFG
Overall

6.14
3.90
3.44
4.35

5.86
2.30
3.78
3.77

3.86
5.40
6.78
5.46

3.43
3.30
3.56
3.42

1.57
4.00
5.44
3.85

6.43
5.20
3.33
4.88

8.00
5.90
7.89
7.15

0.57
2.30
1.22
1.46

0.29
2.10
0.67
1.12

HV

MOP
UF
WFG
Overall

5.57
4.00
3.67
4.31

5.57
2.40
4.00
3.81

4.00
5.50
6.89
5.58

3.00
3.30
2.67
3.00

2.00
3.90
5.00
3.77

6.71
5.30
3.78
5.15

8.00
5.80
7.89
7.12

0.57
1.90
0.56
1.08

0.29
2.40
0.89
1.31

Table 9: Average Performance Scores on 3-, 5-, 8- and 10-Objective WFG Test Instances.
Metric

Problem

DRA

MOEA/DD

PICEA-g

NSGA-III

HypE

AOOSTM

AMOSTM

HV

m=3
m=5
m=8
m = 10
Overall

4.78
5.00
5.22
5.78
5.19

3.67
3.56
3.56
3.56
3.58

2.33
2.00
2.89
2.56
2.44

1.89
3.00
2.22
2.11
2.31

5.89
5.67
4.78
4.78
5.28

0.56
0.11
1.44
1.00
0.78

0.67
0.89
1.78
1.67
1.25

the performance score [7] to qualify the algorithms. Given K algorithms {A1 , · · · , AK }, the performance score of each algorithm Ai , i ∈ {1, · · · , K} on a certain test instance, is defined as:
P (Ai ) =

K
X

δi,j ,

(11)

j=1,j6=i

where δi,j = 1 when Ai is significantly outperformed by Aj ; otherwise, δi,j = 0. This time, we
use the Kolmogorov-Smirnov test to examine whether an algorithm is significantly outperformed by
another. The performance score indicates how many other algorithms are significantly better than
the corresponding algorithm on a certain test instance. Thus, the smaller the performance score,
the better the algorithm. Table 8 and Table 9 present the average performance scores of different
algorithms over all test instances, where we add a gray background to the top two algorithms and
highlight the best algorithms in boldface. Coincident with the total ranks on mean metric values,
MOEA/D-AOOSTM and MOEA/D-AMOSTM obtain the best average performance scores on all
test instances with different number of objectives. Comparing with all other algorithms, the leads
of the two proposed algorithms employing stable matching-based selection with incomplete lists are
statistically significant.

22

6 Conclusions
The stable matching-based selection mechanism paves the way to address the balance between convergence and diversity from the perspective of achieving the equilibrium between the preferences
of subproblems and solutions. However, considering the population diversity, it might not be appropriate to allow each solution to match with any subproblem on its preference list. This paper
has introduced the incomplete preference lists into the stable matching-based selection model, in
which the length of the preference list of each solution is restricted so that a solution is only allowed
to match with one of its favorite subproblems. To overcome the drawbacks of incomplete preference lists, a two-level one-one stable matching-based selection mechanism and a many-one stable
matching-based selection mechanism are proposed and integrated into MOEA/D. In particular, the
length of the preference list of each solution is problem dependent and is related to the difficulty
of the corresponding subproblem. To address this issue, an adaptive mechanism is proposed to
dynamically control the length of the preference list of each solution according to the local competitiveness information. Comprehensive experiments are conducted on 62 benchmark problems which
cover various characteristics, e.g., multi-modality, deceptive, complicated PSs and many objectives.
From the experimental studies in Section 5, we can clearly observe the competitive performance
obtained by our proposed MOEA/D-AOOSTM and MOEA/D-AMOSTM, comparing with a variety
of state-of-the-art EMO algorithms.
Although our proposed MOEA/D-AOOSTM and MOEA/D-AMOSTM have shown very competitive performance in the empirical studies, we also notice that the stable matching relationship
between subproblems and solutions may sacrifice the convergence property of the population to some
extent. One possible reason might be both the two-level one-one matching and the many-one matching restricts that each solution can only be selected by at most one subproblem. Future work could
be focused on assigning higher priorities for elite solutions to produce offspring solutions or allowing
elite solutions to be matched with more than one subproblem. It is also interesting to apply the
proposed algorithms to real-world application scenarios.

References
[1] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms.
John Wiley & Sons, Inc., 2001.

New York, NY, USA:

[2] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, “A fast and elitist multiobjective genetic
algorithm: NSGA-II,” IEEE Trans. Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
[3] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength pareto evolutionary
algorithm for multiobjective optimization,” in Evolutionary Methods for Design, Optimisation,
and Control, 2002, pp. 95–100.
[4] J. D. Knowles and D. Corne, “Approximating the nondominated front using the pareto archived
evolution strategy,” Evolutionary Computation, vol. 8, no. 2, pp. 149–172, 2000.
[5] E. Zitzler and S. Künzli, “Indicator-based selection in multiobjective search,” in PPSN’04: Proc.
of the 8th International Conference on Parallel Problem Solving from Nature, 2004, pp. 832–842.
[6] N. Beume, B. Naujoks, and M. T. M. Emmerich, “SMS-EMOA: multiobjective selection based
on dominated hypervolume,” European Journal of Operational Research, vol. 181, no. 3, pp.
1653–1669, 2007.
[7] J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” Evolutionary Computation, vol. 19, no. 1, pp. 45–76, 2011.

23

[8] Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.
[9] K. Li, Á. Fialho, S. Kwong, and Q. Zhang, “Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evolutionary Computation, vol. 18, no. 1, pp. 114–130, 2014.
[10] K. Li, Q. Zhang, S. Kwong, M. Li, and R. Wang, “Stable matching-based selection in evolutionary multiobjective optimization,” IEEE Trans. Evolutionary Computation, vol. 18, no. 6, pp.
909–923, 2014.
[11] H. Li and Q. Zhang, “Multiobjective optimization problems with complicated pareto sets,
MOEA/D and NSGA-II,” IEEE Trans. Evolutionary Computation, vol. 13, no. 2, pp. 284–302,
2009.
[12] K. Li, S. Kwong, Q. Zhang, and K. Deb, “Interrelationship-based selection for decomposition
multiobjective optimization,” IEEE Trans. Cybernetics, vol. 45, no. 10, pp. 2076–2088, 2015.
[13] H.-L. Liu, F. Gu, and Q. Zhang, “Decomposition of a multiobjective optimization problem into a
number of simple multiobjective subproblems,” IEEE Trans. Evolutionary Computation, vol. 18,
no. 3, pp. 450–455, 2014.
[14] H.-L. Liu, L. Chen, K. Deb, and E. D. Goodman, “Investigating the effect of imbalance between
convergence and diversity in evolutionary multi-objective algorithms,” IEEE Trans. Evolutionary Computation, 2016, accepted for publication.
[15] Z. Wang, Q. Zhang, A. Zhou, M. Gong, and L. Jiao, “Adaptive replacement strategies for
MOEA/D,” IEEE Trans. Cybernetics, vol. 46, no. 2, pp. 474–486, 2016.
[16] K. Li, K. Deb, Q. Zhang, and S. Kwong, “An evolutionary many-objective optimization algorithm based on dominance and decomposition,” IEEE Trans. Evolutionary Computation, vol. 19,
no. 5, pp. 694–716, 2015.
[17] X. Cai, Y. Li, Z. Fan, and Q. Zhang, “An external archive guided multiobjective evolutionary
algorithm based on decomposition for combinatorial optimization,” IEEE Trans. Evolutionary
Computation, vol. 19, no. 4, pp. 508–523, 2015.
[18] K. Li, S. Kwong, and K. Deb, “A dual-population paradigm for evolutionary multiobjective
optimization,” Inf. Sci., vol. 309, pp. 50–72, 2015.
[19] Q. Liu, G. J. Mailath, A. Postlewaite, and L. Samuelson, “Stable matching with incomplete
information,” Econometrica, vol. 82, no. 2, pp. 541–587, 2014.
[20] M. Wu, S. Kwong, Q. Zhang, K. Li, R. Wang, and B. Liu, “Two-level stable matching-based selection in MOEA/D,” in SMC’15: Proc. of the 2015 IEEE International Conference on Systems,
Man, and Cybernetics, 2015, pp. 1720–1725.
[21] K. Miettinen, Nonlinear Multiobjective Optimization.
vol. 12.

Kluwer Academic Publishers, 1999,

[22] Q. Zhang, W. Liu, and H. Li, “The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances,” in Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2009, Trondheim, Norway, 18-21 May, 2009, 2009, pp. 203–208.
[23] D. Gale and L. S. Shapley, “College admissions and the stability of marriage,” The American
Mathematical Monthly, vol. 120, no. 5, pp. 386–391, 1962.

24

[24] D. Gusfield and R. W. Irving, The Stable marriage problem - structure and algorithms, ser.
Foundations of computing series. MIT Press, 1989.
[25] K. Iwama, D. Manlove, S. Miyazaki, and Y. Morita, “Stable marriage with incomplete lists and
ties,” in Automata, Languages and Programming, 26th International Colloquium, ICALP’99,
Prague, Czech Republic, July 11-15, 1999, Proceedings, 1999, pp. 443–452.
[26] P. Biró, T. Fleiner, R. W. Irving, and D. Manlove, “The college admissions problem with lower
and common quotas,” Theor. Comput. Sci., vol. 411, no. 34-36, pp. 3136–3153, 2010.
[27] K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using referencepoint-based nondominated sorting approach, part I: solving problems with box constraints,”
IEEE Trans. Evolutionary Computation, vol. 18, no. 4, pp. 577–601, 2014.
[28] I. Das and J. E. Dennis, “Normal-Boundary Intersection: A new method for generating the
Pareto surface in nonlinear multicriteria optimization problems,” SIAM Journal on Optimization, vol. 8, pp. 631–657, 1998.
[29] S. Das and P. N. Suganthan, “Differential evolution: A survey of the state-of-the-art,” IEEE
Trans. on Evolutionary Computation, vol. 15, no. 1, pp. 4–31, 2011.
[30] R. B. Agrawal, K. Deb, and R. B. Agrawal, “Simulated binary crossover for continuous search
space,” 1994.
[31] K. Deb and M. Goyal, “A combined genetic adaptive search (geneas) for engineering design,”
Computer Science and Informatics, vol. 26, pp. 30–45, 1996.
[32] 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,” University of Essex,
Colchester, UK and Nanyang technological University, Singapore, special session on performance
assessment of multi-objective optimization algorithms, technical report, vol. 264, 2008.
[33] S. Huband, P. Hingston, L. Barone, and R. L. While, “A review of multiobjective test problems
and a scalable test problem toolkit,” IEEE Trans. Evolutionary Computation, vol. 10, no. 5, pp.
477–506, 2006.
[34] R. Wang, R. C. Purshouse, and P. J. Fleming, “Preference-inspired coevolutionary algorithms
for many-objective optimization,” IEEE Trans. Evolutionary Computation, vol. 17, no. 4, pp.
474–494, 2013.
[35] P. A. N. Bosman and D. Thierens, “The balance between proximity and diversity in multiobjective evolutionary algorithms,” IEEE Trans. Evolutionary Computation, vol. 7, no. 2, pp.
174–188, 2003.
[36] E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: a comparative case study
and the strength pareto approach,” IEEE Trans. Evolutionary Computation, vol. 3, no. 4, pp.
257–271, 1999.

25

