# A New Multiobjective Evolutionary Algorithm Based on Decomposition of the Objective Space for Multiobjective Optimization

Authors: Cai Dai; Yuping Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

In order to well maintain the diversity of obtained solutions, a new multiobjective evolutionary algorithm based on decomposition of the objective space for multiobjective optimization problems (MOPs) is designed. In order to achieve the goal, the objective space of a MOP is decomposed into a set of subobjective spaces by a set of direction vectors. In the evolutionary process, each subobjective space has a solution, even if it is not a Pareto optimal solution. In such a way, the diversity of obtained solutions can be maintained, which is critical for solving some MOPs. In addition, if a solution is dominated by other solutions, the solution can generate more new solutions than those solutions, which makes the solution of each subobjective space converge to the optimal solutions as far as possible. Experimental studies have been conducted to compare this proposed algorithm with classic MOEA/D and NSGAII. Simulation results on six multiobjective benchmark functions show that the proposed algorithm is able to obtain better diversity and more evenly distributed Pareto front than the other two algorithms.


---

## Body

## 1. Introduction

Since there are many problems with several optimization problems or criteria in real world [1], multiobjective optimization has become a hot research topic. Unlike single-objective optimization problem, multiobjective optimization problem has a series of noninferior alternative solutions, also known as Pareto optimal solutions (the set of Pareto optimal solutions is called Pareto front [2]), which represent the possible trade-off among various conflicting objectives. Therefore, multiobjective optimization algorithms for MOP should be able to (1) discover solutions as close to the optimal solutions as possible; (2) find solutions as uniform as possible in the obtained nondominated front; (3) determine solutions to cover the true Pareto front (PF) as broad as possible. However, achieving these three goals simultaneously is still a challenge for multiobjective optimization algorithms.Among various multiobjective optimization algorithms, multiobjective evolutionary algorithms (MOEA), which make use of the strategy of the population evolutionary to optimize the problems, are an effective method for solving MOPs. In recent years, many MOEAs have been proposed for solving the multiobjective optimization problems [3–18]. In the MOEA literatures, Goldberg’s population categorization strategy [19] based on nondominance is important. Many algorithms use the strategy to assign a fitness value based on the nondominance rank of members. For example, the nondominated sorting genetic algorithm II [3] was proposed by Deb et al. in 2002, which uses the crowding measure and the elitism strategy; Zitzler et al. [20] proposed the strength Pareto evolutionary algorithm II (SPEA2) which was also based on the elitism strategy; Soylu and Köksalan proposed a favorable weight-based evolutionary algorithm (FWEA) [21]. These algorithms mainly rely on Pareto dominance to guide their search, particularly their selection operators. In contrast, MOEA/D (multiobjective evolutionary algorithm based on decomposition) [22] makes use of traditional aggregation methods to transform the task of approximating the Pareto front (PF) into a number of single-objective optimization subproblems. MOEA/D works well on a wide range of multiobjective problems with many objectives, discrete decision variables, and complicated Pareto sets [23, 24]. MOEA/D has also been used as a basic element in some hybrid algorithms; for example, MOEA/D with differential evolution and particle swarm optimization is proposed by Mashwani [25], Li and Landa-Silva [26] combine MOEA/D and simulated annealing to solve MOPs, and other hybrid algorithms also use MOEA/D to solve MOPs (e.g., [27–29]). Moreover, MOEA/D is used to solve various kinds of problems (e.g., [30, 31]). In MOEA/D, weight vectors and aggregate functions play a very important role. In the literature [32], the uniform design is used to generate the weight vectors; Qi et al. [33] design an adaptive weight vector adjustment to adaptively generate uniform distribution weight vectors. Ishibuchi et al. [34] propose an idea of automatically choosing between the weighted sum and the weighted Tchebycheff for each solution in each generation.Any effective MOEAs must well maintain population diversity since their goal is to approximate a set instead of a single point. Pareto-dominance-based algorithms achieve the goal by maintaining the diversity of obtained Pareto optimal solutions. If these algorithms obtaining Pareto optimal solutions cannot cover the entire PF, this goal cannot be achieved. The current MOEA/D algorithms achieve their population diversity via the diversity of their subproblems. An elite diversity is used for their selection in these algorithms. The aggregation function values of a new solution and an old solution completely determined whether the new solution replaces the old solution or not. In some cases, such replacement can cause a severe loss of population diversity, which is because the aggregation function value of a solution only reflects the extent of the solution close to the ideal point which is determined by the aggregation function and the weight vector, but it does not reflect the space where the objective vector of the solution locates. Thus, the objective space where the objective vector of the solution locates should be considered to maintain the diversity of obtained Pareto optimal solutions. In this paper, the objective space of a MOP is decomposed into a set of subobjective spaces by a set of direction vectors. Each subobjective space has a solution: if a new solution will replace the solution, the new solution must dominate the solution and its objective vector locates in the subobjective space. In such a way, the diversity of obtained solutions can be maintained. In addition, the crowding distance [3] is used to calculate the fitness value of a solution for the selection operators. In this cause, if a solution is dominated by other solutions, the solution is more likely to be selected than other solutions, so it can generate more new solutions to quickly find the optimal solution of the subobjective space, which makes the solution of each subobjective space converge to the optimal solutions as far as possible. Based on these approaches, a new multiobjective evolutionary algorithm, EASS, is designed. We show that EASS can significantly outperform MOEA/D and NSGAII on a set of test instances used in our experimental studies.This paper is organized as follows. Section2 introduces the main concepts of the multiobjective optimization; Section 3 describes the evolutionary algorithm based on decomposition of the objective space, while Section 4 shows the experiment results of proposed algorithm; finally, Section 5 gives the conclusions and future works.


## 2. Multiobjective Optimization

A multiobjective optimization problem can be formulated as follows [35]:
(1)miny=F(x)=(f1(x),f2(x),…,fm(x))s.t.gi(x)≤0,i=1,2,…,qhj(x)=0,j=1,2,…,p,
where x=(x1,…,xn)∈X⊂Rn is called decision variable and X is n-dimensional decision space. fi(x)(i=1,…,m) is the ith objective to be minimized, gj(x)(j=1,2…,q) definesjth inequality constraint, and hj(x)(j=1,2,…,p) defines jth equality constraint. Furthermore, all the constraints determine the set of feasible solutions which is denoted by Ω. To be specific, we try to find a feasible solutionx∈Ωminimizing each objective function fi(x)(i=1,…,m) in F. In the following, four important definitions [36] for multiobjective problems are given.Definition 1 (Pareto dominance).
Pareto dominance between solutionsx, z∈Ω is defined as follows. If
(2)∀i∈{1,2,…,m}fi(x)≤fi(z),∧∃i∈{1,2,…,m}fi(x)<fi(z)
are satisfied, x dominates (Pareto dominate) z (denoted as x≻z).Definition 2 (Pareto optimal).
A solution vectorx is said to be Pareto optimal with respect to Ω if ∄z∈Ω:z≻x.Definition 3 (Pareto optimal set (PS)).
The set of Pareto optimal solutions (PS) is defined as(3)PS={x∈Ω∣∄z∈Ω:z≻x}.Definition 4 (Pareto front).
The Pareto optimal front (PF) is defined as(4)PF={F(x)∣x∈PS}.


## 3. A New Multiobjective Evolutionary Algorithm Based on Decomposition of the Objective Space

This new algorithm consists of three parts: solutions classification, update strategy, and selection strategy which will be introduced one by one in this section.


### 3.1. Solutions Classification

The objective space of an MOP is decomposed into a set of subobjective spaces by a set of direction vectors, and then obtained solutions are classified by these direction vectors to make each subobjective space have a solution. For a given set of direction vectors(γ1,γ2,…,γN), and the set of current obtained solutions being POP, these solutions will be classified by the following formula:
(5)Pi={x∣x∈POP,Δ(F(x),γi)=max1≤j≤N{Δ(F(x),γj)}},Δ(F(x),γi)=γi*(F(x)-Z)T∥γi∥*∥F(x)-Z∥,i=1,…,m,
where Z=(Z1,…,Zm) is a reference point and Zi=min{fi(x)∣x∈Ω}, Δ(F(x),γi)} is the cosine of the angle between γi and F(x)-Z. These solutions are divided into N classes by the formula (5) and the objective space Ω is divided into N subobjective spaces Ω1,…,ΩN, where Ωk(k=1,…,N) is
(6)Ωk={F(x)∣x∈Ω,Δ(F(x),γk)=max1≤j≤N{Δ(F(x),γj)}}.If aPi(1≤i≤N) is empty, a solution is randomly selected from POP and put to Pi. We would like to make the following comments on the classification (decomposition) method.(1)
This method is equivalent in a sense that the PFs of all these subobjective spaces constitute the PF of (1).(2)
Even when the PS of (1) has a nonlinear geometric shape, the PS of each subobjective space could be close to linear because it is just a small part of the PS of (1). Therefore, formulas (5) and (6) make (1) simpler than before, at least in terms of PS shapes.(3)
This classification (decomposition) method does not require any aggregation methods. A user only needs to choose a set of direction vectors. To some extent, it requires little human labor.


### 3.2. Update Strategy

The elitist strategy is used to update solutions. When it meets one of the following conditions, a new solution will replace the current solution of a subobjective space:(1)
if the objective vector of the current solution does not locate in this subobjective space, the objective vector of the new solution locates in this space or the current solution is dominated by the new solution;(2)
if the objective vector of the current solution locates in this subobjective space, the objective vector of the new solution also locates in this space and the current solution is dominated by the new solution.The first update condition makes each subobjective space have a solution whose objective vector locates in this subobjective space, which can well maintain the diversity of obtained solutions. The second update condition makes nondominated solution be kept, which can make solutions converge to the PF.


### 3.3. Selection Strategy

In this work, we hope that those solutions which are kept after the above update strategy and dominated by other solutions have a stronger ability to survive than other solutions. In such a way, these solutions are more likely to be selected to generate new solutions, and then their subobjective spaces can quickly find their optimal solutions. Therefore, the finally obtained solution of each subobjective space is as close as possible to the PF. In order to achieve the goal, the crowding distance [3] is used to calculate the fitness value of a solution for the selection operators. Because these solutions are dominated by other solutions and the objective vectors of those solutions do not locate in these subobjective spaces of these solutions, so in the term of the objective vector, these solutions have fewer solutions in their surround than other solutions. Thus, by using the crowding distance to calculate the fitness value of a solution, the fitness values of these solutions are better than those solutions and these solutions are more likely to be selected to generate new solutions.


### 3.4. Steps of the Proposed Algorithm

Based on the above methods, a new multiobjective evolutionary algorithm (EASS) is proposed and the steps of the algorithm EASS are as follows.Step 1 (initialization).
GivenN direction vectors (γ1,γ2,…,γN), randomly generate an initial population POP(k), and its size is N; let k=0. Set Zi=min{fi(x)∣x∈POP(k)}, 1≤i≤m.Step 2 (fitness).
Solutions ofPOP(k) are firstly divided into N classes by the formula (5) and the fitness value of each solution in POP(k) is calculated by the crowding distance. Then, some better solutions are selected from the population POP(k) and put into the population POP. In this work, binary tournament selection is used.Step 3 (new solutions).
Apply genetic operators to the parent population to generate offspring. The set of all these offspring is denoted asO.Step 4 (update).
Z is firstly updated. For each j=1,…,m, if Zj>min{fj(x)∣x∈O}, then set Zj=min{fj(x)∣x∈O}. The solutions of POP(k)∪O are firstly classed by the formula (5); then N best solutions are selected by the update strategy of Section 3.2 and put into POP(k+1). Let k=k+1.Step 5 (termination).
If stop condition is satisfied, stop; otherwise, go to Step2.


## 3.1. Solutions Classification

The objective space of an MOP is decomposed into a set of subobjective spaces by a set of direction vectors, and then obtained solutions are classified by these direction vectors to make each subobjective space have a solution. For a given set of direction vectors(γ1,γ2,…,γN), and the set of current obtained solutions being POP, these solutions will be classified by the following formula:
(5)Pi={x∣x∈POP,Δ(F(x),γi)=max1≤j≤N{Δ(F(x),γj)}},Δ(F(x),γi)=γi*(F(x)-Z)T∥γi∥*∥F(x)-Z∥,i=1,…,m,
where Z=(Z1,…,Zm) is a reference point and Zi=min{fi(x)∣x∈Ω}, Δ(F(x),γi)} is the cosine of the angle between γi and F(x)-Z. These solutions are divided into N classes by the formula (5) and the objective space Ω is divided into N subobjective spaces Ω1,…,ΩN, where Ωk(k=1,…,N) is
(6)Ωk={F(x)∣x∈Ω,Δ(F(x),γk)=max1≤j≤N{Δ(F(x),γj)}}.If aPi(1≤i≤N) is empty, a solution is randomly selected from POP and put to Pi. We would like to make the following comments on the classification (decomposition) method.(1)
This method is equivalent in a sense that the PFs of all these subobjective spaces constitute the PF of (1).(2)
Even when the PS of (1) has a nonlinear geometric shape, the PS of each subobjective space could be close to linear because it is just a small part of the PS of (1). Therefore, formulas (5) and (6) make (1) simpler than before, at least in terms of PS shapes.(3)
This classification (decomposition) method does not require any aggregation methods. A user only needs to choose a set of direction vectors. To some extent, it requires little human labor.


## 3.2. Update Strategy

The elitist strategy is used to update solutions. When it meets one of the following conditions, a new solution will replace the current solution of a subobjective space:(1)
if the objective vector of the current solution does not locate in this subobjective space, the objective vector of the new solution locates in this space or the current solution is dominated by the new solution;(2)
if the objective vector of the current solution locates in this subobjective space, the objective vector of the new solution also locates in this space and the current solution is dominated by the new solution.The first update condition makes each subobjective space have a solution whose objective vector locates in this subobjective space, which can well maintain the diversity of obtained solutions. The second update condition makes nondominated solution be kept, which can make solutions converge to the PF.


## 3.3. Selection Strategy

In this work, we hope that those solutions which are kept after the above update strategy and dominated by other solutions have a stronger ability to survive than other solutions. In such a way, these solutions are more likely to be selected to generate new solutions, and then their subobjective spaces can quickly find their optimal solutions. Therefore, the finally obtained solution of each subobjective space is as close as possible to the PF. In order to achieve the goal, the crowding distance [3] is used to calculate the fitness value of a solution for the selection operators. Because these solutions are dominated by other solutions and the objective vectors of those solutions do not locate in these subobjective spaces of these solutions, so in the term of the objective vector, these solutions have fewer solutions in their surround than other solutions. Thus, by using the crowding distance to calculate the fitness value of a solution, the fitness values of these solutions are better than those solutions and these solutions are more likely to be selected to generate new solutions.


## 3.4. Steps of the Proposed Algorithm

Based on the above methods, a new multiobjective evolutionary algorithm (EASS) is proposed and the steps of the algorithm EASS are as follows.Step 1 (initialization).
GivenN direction vectors (γ1,γ2,…,γN), randomly generate an initial population POP(k), and its size is N; let k=0. Set Zi=min{fi(x)∣x∈POP(k)}, 1≤i≤m.Step 2 (fitness).
Solutions ofPOP(k) are firstly divided into N classes by the formula (5) and the fitness value of each solution in POP(k) is calculated by the crowding distance. Then, some better solutions are selected from the population POP(k) and put into the population POP. In this work, binary tournament selection is used.Step 3 (new solutions).
Apply genetic operators to the parent population to generate offspring. The set of all these offspring is denoted asO.Step 4 (update).
Z is firstly updated. For each j=1,…,m, if Zj>min{fj(x)∣x∈O}, then set Zj=min{fj(x)∣x∈O}. The solutions of POP(k)∪O are firstly classed by the formula (5); then N best solutions are selected by the update strategy of Section 3.2 and put into POP(k+1). Let k=k+1.Step 5 (termination).
If stop condition is satisfied, stop; otherwise, go to Step2.


## 4. Experimental Study

In this section, EASS has been fully compared with a promising multiobjective evolutionary algorithm based on decomposition (MOEA/D) [22], which was ranked first in the unconstrained MOEA competition [37], and nondominated sorting genetic algorithm II (NSGAII) [3] on seven continuous test problems.


### 4.1. Test Problem

The following modified ZDT [36] and DTLZ [38] instances are used in this paper. g(x) functions are modified to increase the difficulty of these instances. These strategies for constructing these test problems are used in [39]. These functions with complicated Pareto set shapes can cause difficulties for MOEAs. Their search space is [0,1]n and n=10. All these instances are for minimization and described in Table 1.Table 1
Multiobjective benchmark functions.
Instance
Objective function
F1
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F2
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
2
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F3
f1(x)=(1+g(x))cos(πx12)
f
2
(
x
)
=
(
1
+
g
(
x
)
)
sin
(
π
x
1
2
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F4
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
0.5
cos
2
(
2
π
x
1
)
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F5
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
x
2
f
2
(
x
)
=
(
1
+
g
(
x
)
)
x
1
(
1
-
x
2
)
f
3
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
3
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
x
1
x
2
F6
f
1
(
x
)
=
(
1
+
g
(
x
)
)
cos
(
0.5
π
x
1
)
cos
(
0.5
π
x
2
)
f
2
(
x
)
=
(
1
+
g
(
x
)
)
cos
(
0.5
π
x
1
)
sin
(
0.5
π
x
2
)
f
3
(
x
)
=
(
1
+
g
(
x
)
)
sin
(
0.5
π
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
3
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
x
1
x
2


### 4.2. Parameter Settings

Algorithms are implemented on a personal computer (Intel Xeon CPU 2.53 GHz, 3.98 G RAM). The individuals are all coded as the real vectors. Polynomial mutation [40] operators are applied directly to real parameter values in three algorithms, that is, NSGAII, MOEA/D, and EASS. For crossover operators, simulated binary crossover (SBX [40]) is used in NSGAII and EASS; differential evolution (DE) [41] is used in MOEA/D. The parameter settings in this paper are as follows.(1)
Control parameters in reproduction operators:
(a)
distribution index is 20 and crossover probability is 1 in the SBX operator;(b)
crossover rate is 1.0 and scaling factor is 0.5 in the DE operator;(c)
distribution index is 20 and mutation probability is 0.1 in mutation operator.(2)
For two-objective and three-objective instances, the population size is 105 in the three algorithms. Weight vectors are generated by using the method which is used in [22]. The direction vectors of EASS are the weight vectors. The number of weight vectors is the same as the population size. The number of the weight vectors in the neighborhood in MOEA/D is 20 for all test problems. The Tchebycheff approach [22] is used for MOEA/D as an aggregate function. Other control parameters in MOEA/D are the same as in [22].(3)
Each algorithm is run 20 times independently for each test instance. All the three algorithms stop after 1000 generations.


### 4.3. Experimental Measures

In order to compare the performance of the different algorithms quantitatively, performance metrics are needed. In this paper, the following performance metrics are used to compare the performance of the different algorithms quantitatively: generational distance (GD) [42], inverted generational distance (IGD) [42], and hypervolume indicator (HV) [43].GDmeasures how far the known Pareto front is away from the true Pareto front. IfGDis equal to 0, all points of the known PF belong to the true PF.GDallows us to observe whether the algorithm can converge to some region in the true PF. IGDmeasures how far the true PF is away from the known PF. IfIGDis equal to 0, the known PF contains every point of the true PF.IGDshows whether points of the known PF are evenly distributed throughout the true PF. Here,GDandIGDindicators are used simultaneously to observe whether the solutions are distributed over the entire PF and define a suboptimal solution as a good solution. In experiments, we select 500 evenly distributed points on the PF for four two-objective test instances and 1000 points for three-objective test instances. The hypervolume indicator has been used widely in evolutionary multiobjective optimization to evaluate the performance of search algorithms. It computes the volume of the dominated portion of the objective space relative to a reference point. Higher values of this performance indicator imply more desirable solutions. The hypervolume indicator measures both the convergence to the true Pareto front and diversity of the obtained solutions. In our experiments, the reference point is set to (1,…,1).


### 4.4. Comparisons of EASS with MOEA/D and NSGAII

In this section, some simulation results and comparisons that prove the potential of EASS are presented and the comparisons mainly focus on three aspects:(1) the convergence of the obtained solutions to the true PF; (2) the coverage of the obtained solutions to the true PF; and (3) the diversity of the obtained solutions. Although such comparisons are not sufficient, they provide a good basis to estimate the performance of EASS.To visually compare the performance of the three algorithms, the solutions obtained by them on these test problems are shown in Figures1 and 2. Obviously, both MOEA/D and NSGAII cannot locate the global PF on any instance. In contrast, EASS can approximate the PFs of these instances quite well. These Figures indicate that the diversity of solutions obtained by the algorithm EASS is better than those obtained by MOEA/D and NSGAII on these test problems.Solutions obtained by EASS, MOEA/D, and NSGAII on F1–F3.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Solutions obtained by EASS, MOEA/D, and NSGAII on F4–F6.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Table2 presents the mean and standard deviation of IGD, GD, and HV obtained by EASS, MOEA/D, and NSGAII. Best solutions obtained are highlighted bold in this table. From the table, we can obtain that the mean values of IGD obtained by EASS are much smaller than those obtained by the other two algorithms for these six test problems, which indicates that for these test problems, the coverage of solutions obtained by EASS to the true PF is better than those obtained by MOEA/D and NSGAII. In addition, standard deviations of IGD obtained by EASS are very small for these test problems, which show that the performance of EASS is well stable on these problems. We can also see that the mean values of GD obtained by EASS are smaller than those obtained by the other two algorithms for test problems F1 and F3, which indicate that the convergence of solutions obtained by EASS to the true PF is better than those obtained by MOEA/D and NSGAII. For problems F2 and F4, the mean values ofGDobtained by EASS are slightly larger than those obtained by NSGAII but smaller than those obtained by MOEA/D. For problems F5 and F6, the mean values ofGDobtained by EASS are larger than those obtained by MOEA/D and NSGAII. For these four test problems, the convergence of solutions obtained by EASS to the true PF is worse than that obtained by NSGAII, which is because the solutions obtained by NSGAII and MOEA/D are concentrated in certain regions of the PF, but solutions obtained by EASS are distributed throughout the PF and converge to the PF. From the mean values ofGDobtained by EASS, we can obtain that solutions obtained by EASS can well converge to the true PF for these six test problems. In terms of the mean value ofHV, the values ofHVobtained by EASS are much bigger than those obtained by other two algorithms, which illustrate that the diversities of solutions obtained by EASS are better than those obtained by MOEA/D and NSGAII.Table 2
IGD, GD, and HV obtained by EASS, MOEA/D, and NSGAII on F1–F6.
IGD
GD
HV
Mean
SD
Mean
SD
Mean
SD
F1
EASS
0.0042
0.0000
0.0012
0.0001
0.6605
0.0001
MOEA/D
0.1271
0.0415
0.0053
0.0012
0.4308
0.0847
NSGAII
0.2697
0.0040
0.0037
0.0017
0.2890
0.0077
F2
EASS
0.0051
0.0002
0.0014
0.0001
0.3260
0.0002
MOEA/D
0.1141
0.0106
0.0025
0.0008
0.2506
0.0088
NSGAII
0.3437
0.0427
0.0005
0.0001
0.0116
0.0465
F3
EASS
0.0055
0.0002
0.0019
0.0001
0.2065
0.0003
MOEA/D
0.1758
0.1098
0.0019
0.0011
0.0978
0.0549
NSGAII
0.3753
0.0364
0.0030
0.0002
0.0027
0.0108
F4
EASS
0.0046
0.0001
0.0014
0.0001
0.5139
0.0003
MOEA/D
0.2313
0.0263
0.0728
0.0187
0.1977
0.0729
NSGAII
0.2650
0.0010
0.0011
0.0018
0.2119
0.0009
F5
EASS
0.0423
0.0008
0.0209
0.0005
0.7719
0.0025
MOEA/D
0.2999
0.0000
0.0066
0.0000
0.4810
0.0000
NSGAII
0.2898
0.0341
0.0171
0.0005
0.5062
0.0443
F6
EASS
0.0556
0.0016
0.0259
0.0006
0.4039
0.0015
MOEA/D
0.3698
0.0000
0.0075
0.0000
0.1992
0.0000
NSGAII
0.2611
0.0326
0.0209
0.0011
0.3110
0.0306


## 4.1. Test Problem

The following modified ZDT [36] and DTLZ [38] instances are used in this paper. g(x) functions are modified to increase the difficulty of these instances. These strategies for constructing these test problems are used in [39]. These functions with complicated Pareto set shapes can cause difficulties for MOEAs. Their search space is [0,1]n and n=10. All these instances are for minimization and described in Table 1.Table 1
Multiobjective benchmark functions.
Instance
Objective function
F1
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F2
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
2
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F3
f1(x)=(1+g(x))cos(πx12)
f
2
(
x
)
=
(
1
+
g
(
x
)
)
sin
(
π
x
1
2
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F4
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
f
2
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
0.5
cos
2
(
2
π
x
1
)
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
2
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
sin
(
0.5
π
x
i
)
F5
f
1
(
x
)
=
(
1
+
g
(
x
)
)
x
1
x
2
f
2
(
x
)
=
(
1
+
g
(
x
)
)
x
1
(
1
-
x
2
)
f
3
(
x
)
=
(
1
+
g
(
x
)
)
(
1
-
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
3
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
x
1
x
2
F6
f
1
(
x
)
=
(
1
+
g
(
x
)
)
cos
(
0.5
π
x
1
)
cos
(
0.5
π
x
2
)
f
2
(
x
)
=
(
1
+
g
(
x
)
)
cos
(
0.5
π
x
1
)
sin
(
0.5
π
x
2
)
f
3
(
x
)
=
(
1
+
g
(
x
)
)
sin
(
0.5
π
x
1
)
g
(
x
)
=
2
sin
(
π
x
1
)
(
n
-
1
+
∑
i
=
3
n
(
t
i
2
-
cos
(
2
π
t
i
)
)
)
t
i
=
x
i
-
x
1
x
2


## 4.2. Parameter Settings

Algorithms are implemented on a personal computer (Intel Xeon CPU 2.53 GHz, 3.98 G RAM). The individuals are all coded as the real vectors. Polynomial mutation [40] operators are applied directly to real parameter values in three algorithms, that is, NSGAII, MOEA/D, and EASS. For crossover operators, simulated binary crossover (SBX [40]) is used in NSGAII and EASS; differential evolution (DE) [41] is used in MOEA/D. The parameter settings in this paper are as follows.(1)
Control parameters in reproduction operators:
(a)
distribution index is 20 and crossover probability is 1 in the SBX operator;(b)
crossover rate is 1.0 and scaling factor is 0.5 in the DE operator;(c)
distribution index is 20 and mutation probability is 0.1 in mutation operator.(2)
For two-objective and three-objective instances, the population size is 105 in the three algorithms. Weight vectors are generated by using the method which is used in [22]. The direction vectors of EASS are the weight vectors. The number of weight vectors is the same as the population size. The number of the weight vectors in the neighborhood in MOEA/D is 20 for all test problems. The Tchebycheff approach [22] is used for MOEA/D as an aggregate function. Other control parameters in MOEA/D are the same as in [22].(3)
Each algorithm is run 20 times independently for each test instance. All the three algorithms stop after 1000 generations.


## 4.3. Experimental Measures

In order to compare the performance of the different algorithms quantitatively, performance metrics are needed. In this paper, the following performance metrics are used to compare the performance of the different algorithms quantitatively: generational distance (GD) [42], inverted generational distance (IGD) [42], and hypervolume indicator (HV) [43].GDmeasures how far the known Pareto front is away from the true Pareto front. IfGDis equal to 0, all points of the known PF belong to the true PF.GDallows us to observe whether the algorithm can converge to some region in the true PF. IGDmeasures how far the true PF is away from the known PF. IfIGDis equal to 0, the known PF contains every point of the true PF.IGDshows whether points of the known PF are evenly distributed throughout the true PF. Here,GDandIGDindicators are used simultaneously to observe whether the solutions are distributed over the entire PF and define a suboptimal solution as a good solution. In experiments, we select 500 evenly distributed points on the PF for four two-objective test instances and 1000 points for three-objective test instances. The hypervolume indicator has been used widely in evolutionary multiobjective optimization to evaluate the performance of search algorithms. It computes the volume of the dominated portion of the objective space relative to a reference point. Higher values of this performance indicator imply more desirable solutions. The hypervolume indicator measures both the convergence to the true Pareto front and diversity of the obtained solutions. In our experiments, the reference point is set to (1,…,1).


## 4.4. Comparisons of EASS with MOEA/D and NSGAII

In this section, some simulation results and comparisons that prove the potential of EASS are presented and the comparisons mainly focus on three aspects:(1) the convergence of the obtained solutions to the true PF; (2) the coverage of the obtained solutions to the true PF; and (3) the diversity of the obtained solutions. Although such comparisons are not sufficient, they provide a good basis to estimate the performance of EASS.To visually compare the performance of the three algorithms, the solutions obtained by them on these test problems are shown in Figures1 and 2. Obviously, both MOEA/D and NSGAII cannot locate the global PF on any instance. In contrast, EASS can approximate the PFs of these instances quite well. These Figures indicate that the diversity of solutions obtained by the algorithm EASS is better than those obtained by MOEA/D and NSGAII on these test problems.Solutions obtained by EASS, MOEA/D, and NSGAII on F1–F3.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Solutions obtained by EASS, MOEA/D, and NSGAII on F4–F6.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Table2 presents the mean and standard deviation of IGD, GD, and HV obtained by EASS, MOEA/D, and NSGAII. Best solutions obtained are highlighted bold in this table. From the table, we can obtain that the mean values of IGD obtained by EASS are much smaller than those obtained by the other two algorithms for these six test problems, which indicates that for these test problems, the coverage of solutions obtained by EASS to the true PF is better than those obtained by MOEA/D and NSGAII. In addition, standard deviations of IGD obtained by EASS are very small for these test problems, which show that the performance of EASS is well stable on these problems. We can also see that the mean values of GD obtained by EASS are smaller than those obtained by the other two algorithms for test problems F1 and F3, which indicate that the convergence of solutions obtained by EASS to the true PF is better than those obtained by MOEA/D and NSGAII. For problems F2 and F4, the mean values ofGDobtained by EASS are slightly larger than those obtained by NSGAII but smaller than those obtained by MOEA/D. For problems F5 and F6, the mean values ofGDobtained by EASS are larger than those obtained by MOEA/D and NSGAII. For these four test problems, the convergence of solutions obtained by EASS to the true PF is worse than that obtained by NSGAII, which is because the solutions obtained by NSGAII and MOEA/D are concentrated in certain regions of the PF, but solutions obtained by EASS are distributed throughout the PF and converge to the PF. From the mean values ofGDobtained by EASS, we can obtain that solutions obtained by EASS can well converge to the true PF for these six test problems. In terms of the mean value ofHV, the values ofHVobtained by EASS are much bigger than those obtained by other two algorithms, which illustrate that the diversities of solutions obtained by EASS are better than those obtained by MOEA/D and NSGAII.Table 2
IGD, GD, and HV obtained by EASS, MOEA/D, and NSGAII on F1–F6.
IGD
GD
HV
Mean
SD
Mean
SD
Mean
SD
F1
EASS
0.0042
0.0000
0.0012
0.0001
0.6605
0.0001
MOEA/D
0.1271
0.0415
0.0053
0.0012
0.4308
0.0847
NSGAII
0.2697
0.0040
0.0037
0.0017
0.2890
0.0077
F2
EASS
0.0051
0.0002
0.0014
0.0001
0.3260
0.0002
MOEA/D
0.1141
0.0106
0.0025
0.0008
0.2506
0.0088
NSGAII
0.3437
0.0427
0.0005
0.0001
0.0116
0.0465
F3
EASS
0.0055
0.0002
0.0019
0.0001
0.2065
0.0003
MOEA/D
0.1758
0.1098
0.0019
0.0011
0.0978
0.0549
NSGAII
0.3753
0.0364
0.0030
0.0002
0.0027
0.0108
F4
EASS
0.0046
0.0001
0.0014
0.0001
0.5139
0.0003
MOEA/D
0.2313
0.0263
0.0728
0.0187
0.1977
0.0729
NSGAII
0.2650
0.0010
0.0011
0.0018
0.2119
0.0009
F5
EASS
0.0423
0.0008
0.0209
0.0005
0.7719
0.0025
MOEA/D
0.2999
0.0000
0.0066
0.0000
0.4810
0.0000
NSGAII
0.2898
0.0341
0.0171
0.0005
0.5062
0.0443
F6
EASS
0.0556
0.0016
0.0259
0.0006
0.4039
0.0015
MOEA/D
0.3698
0.0000
0.0075
0.0000
0.1992
0.0000
NSGAII
0.2611
0.0326
0.0209
0.0011
0.3110
0.0306


## 5. Conclusion

In this paper, a new evolutionary algorithm based on decomposition of the objective space is designed to well maintain the diversity of obtained solutions. In order to achieve the goal, the objective space of an MOP is decomposed into a number of subobjective spaces, and the obtained solutions are classed to make each subobjective space have a solution. For each subobjective space, if a new solution will replace its current solution whose objective vector locates in this sub-region, the new solution must dominate the current solution and its objective vector locates in the sub-region; if the objective vector of the current solution does not locate in this sub-region, the new solution dominate the current solution or its objective vector locates in the sub-region. In such a way, good population diversity can be achieved, which is essential for solving some MOPs. In addition, in order to improve the convergence of all obtained solutions, the crowding distance is used to calculate the fitness value of a solution for the selection operators, which can make dominated solutions be more likely to be selected to generate new solutions. Experimental studies on six test instances have implied that this proposed algorithm can significantly outperform MOEA/D and NSGAII on these test problems.The future work includes combination of this algorithm and other evolutionary search techniques and investigation of its performance on other hard multiobjective optimization problems.


## Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.



---

*Source: 906147-2014-01-12.xml*