# A Multiobjective Genetic Algorithm Based on a Discrete Selection Procedure

Authors: Qiang Long; Changzhi Wu; Xiangyu Wang; Lin Jiang; Jueyou Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Multiobjective genetic algorithm (MOGA) is a direct search method for multiobjective optimization problems. It is based on the process of the genetic algorithm; the population-based property of the genetic algorithm is well applied in MOGAs. Comparing with the traditional multiobjective algorithm whose aim is to find a single Pareto solution, the MOGA intends to identify numbers of Pareto solutions. During the process of solving multiobjective optimization problems using genetic algorithm, one needs to consider the elitism and diversity of solutions. But, normally, there are some trade-offs between the elitism and diversity. For some multiobjective problems, elitism and diversity are conflicting with each other. Therefore, solutions obtained by applying MOGAs have to be balanced with respect to elitism and diversity. In this paper, we propose metrics to numerically measure the elitism and diversity of solutions, and the optimum order method is applied to identify these solutions with better elitism and diversity metrics. We test the proposed method by some well-known benchmarks and compare its numerical performance with other MOGAs; the result shows that the proposed method is efficient and robust.


---

## Body

## 1. Introduction

In this paper, we consider the following multiobjective optimization problem:(1)(MOP)MinimizeF(x)Subjecttox∈X,where F(x)=(f1(x),f2(x),…,fp(x))T is a multiobjective function (vector valued function), X={x∈Rn:lb≤x≤ub}⊂Rn is a box set, and lb and ub are lower bound and upper bound, respectively. We assume that each function in F(x) is Lipschitz continuous but not necessarily differentiable.The multiobjective optimization has extensive applications in engineering and management [1–3]. Most of the optimization problems appearing in the real-world application have multiple objectives; they can be modeled as multiobjective optimization problems. However, due to the theoretical and computational challenges, it is not easy to numerically solve multiobjective optimization problems. Therefore, the multiobjective optimization attracted lots of researches over the last decades [4–8].So far, there are two types of methods to solve multiobjective optimization problems: the indirect method and direct method. The indirect method converts multiple objectives into a single one. One strategy is to combine the multiple objective functions using the utility theory [9] or the weighted sum method [10, 11]. The difficulty for such method is the selection of the utility function or proper weights so as to satisfy the decision-maker’s preference. Another indirect method is to formulate the multiple objectives, except one, as constraints. However, it is not easy to determine the upper bounds of these objectives. On the one hand, small upper bounds could exclude some Pareto solutions; on the other hand, large upper bounds could enlarge the objective function value space which leads to some sub-Pareto solutions. Additionally, the indirect method can only obtain a single Pareto solution in each run. However, in practical applications, decision-makers often prefer a number of Pareto solutions so that they can choose one strategy according to their preferences.Direct methods are devoted to exploring the entire set of Pareto solutions or a representative subset. However, it is extremely hard or impossible to obtain the entire set of Pareto solutions for most multiobjective optimization problems, except for some simple cases. Therefore, stepping back to a representative subset is preferred. Genetic algorithm, as a population-based algorithm, is a good choice to achieve this goal. The generic single-objective genetic algorithm can be modified to find a set of nondominated solutions in a single run [12–14]. The ability of the genetic algorithm to simultaneously search different regions of a solution space makes it possible to find a diverse set of solutions for difficult problems. The crossover and mutation operators of the genetic algorithm can be applied to various domains defined by different objectives, which in return creates new nondominated solutions in unexplored parts of the Pareto front. In addition, multiobjective genetic algorithm does not require the user to prioritize, scale, or weight objectives. Therefore, the genetic algorithm is one of the most popular metaheuristic approaches for solving multiobjective optimization problems [15–17].The first multiobjective optimization method based on the genetic algorithm, called the vector evaluated genetic algorithm (VEGA), was proposed by Schaffer [18]. Afterwards, several multiobjective evolutionary algorithms were developed, such as multiobjective genetic algorithm (MOGA) [19], niched Pareto genetic algorithm (NPGA) [20], weight-based genetic algorithm (WBGA) [21], random weighted genetic algorithm (RWGA) [22], nondominated sorting genetic algorithm (NSGA) [23], strength Pareto evolutionary algorithm (SPEA) [24], improved SPEA (SPEA2) [25], Pareto-archived evolution strategy (PAES) [26], Pareto envelope-based selection algorithm (PESA) [27].There are two basic criteria to measure a set of solutions for the multiobjective optimization problem [28].(1)
Elitism. The obtained solutions should be as close to the real Pareto solutions as possible. This can be measured by the closeness between the real Pareto frontier and the image of the obtained solutions since the image set of the real Pareto solutions is the real Pareto frontier.(2)
Diversity. In order to extensively describe Pareto solutions, the obtained solutions should distribute uniformly over the set of real Pareto solutions. The diversity of the obtained solutions is measured by the diversity of their images.These two criteria of Pareto solutions are often in conflict with each other. Therefore, one has to balance the trade-off between elitism and diversity. The aim of this paper is to introduce new techniques to tackle these issues. The rest of the paper is organized as follows. In Section2, we review some basic definitions of multiobjective optimization and the process of genetic algorithm. In Section 3, we propose an improved genetic algorithm for solving multiobjective optimization problems. In Section 4, some numerical experiments are carried out and the results are analyzed. Section 5 concludes the paper.


## 2. Preliminaries

In this section, we first review some definitions and theorems in the multiobjective optimization and then introduce the general procedure of genetic algorithm.


### 2.1. Definitions in Multiobjective Optimization

First of all, we present the following notations which are often used in vector optimization. Given two vectors(2)x=x1,x2,…,xnT,y=y1,y2,…,ynT∈Rn,then (i)
x=y⇔xi=yi for all i=1,2,…,n;(ii)
x<y⇔xi<yi for all i=1,2,…,n;(iii)
x≤y⇔xi≤yi for all i=1,2,…,n, and there is at least one i∈{1,2,…,n} such that xi<yi; that is, x≠y;(iv)
x≦y⇔xi≤yi for all i=1,2,…,n. “>,” “≥,” and “≧” can be defined similarly. In this paper, we call x≤y by x dominates y or y is dominated by x (in some literatures, x≥y is called x dominates y or y is dominated by y; we reverse this definition since we are solving minimization problem in this paper).Definition 1.
Suppose thatx⊆Rn and x*∈X. If x*≦x for any x∈X, then x* is called an absolute optimal point of X.Absolute optimal point is an ideal point, but it may not exist.Definition 2.
Letx∈Rn and x*∈X. If there is no x∈X such that (3)x≤x*(orx<x*),then x* is called anefficient point (orweakly efficient point).The sets of absolute optimal points, efficient points, and weakly efficient points ofX are denoted as Xab, Xep, and Xwp, respectively. For the problem MOP, X⊆Rn is called thedecision variable space and its image set F(X)={y∈Rp∣y=F(x),x∈X}⊂Rp is called theobjective function value space.Definition 3.
Suppose thatx*∈X. If (4)F(x*)≦F(x),for any x∈X, x* is called anabsolute optimal solution of the problem MOP. The set of absolute optimal solutions is denoted as Sas.The concept of the absolute optimal solution is a direct extension of that for single-objective optimization. It is the ideal solution but may not exist for most cases.Definition 4.
Suppose thatx*∈X. If there is no x∈X such that (5)Fx≤Fx*orFx<Fx*;that is, F(x*) is an efficient point (or weakly efficient point) of the objective function value space F(X), then x* is called anefficient solution (orweakly efficient solution) of the problem MOP. The sets of efficient solutions and weakly efficient solutions are denoted as Ses and Sws, respectively.Another name of the efficient solution isPareto solution, which was introduced by Koopmans and Reiter in 1951 [29]. The meaning of the Pareto solution is that if x*∈Ses, then there is no feasible solution x∈X, such that any fi(x) of F(x) is not worse than that of F(x*). In other words, x* is the best solution in the sense of “≤.” Another intuitive interpretation of Pareto solution is that it cannot be improved with respect to any objective without worsening at least one of the other objectives. The set of Pareto solutions is denoted by P*. Its image set F(P*) is called thePareto frontier, denoted by PF*. The following two theorems are well known.Theorem 5 (see [6]).
For the multiobjective optimization, it holds that(6)Sas⊂Ses(P*)⊂Sws⊂X.Theorem 6 (see [6]).
For the objective function value spaceF(X), if the sets of efficient points and weakly efficient points (i.e., Fes and Fws, resp.) are known, then, in the feasible set X, it holds that (7)Ses=⋃F¯∈Fes‍x∈X∣Fx=F¯,Sws=⋃F¯∈Fws‍x∈X∣F(x)=F¯.Theorem5 illustrates the relationship of the sets of absolute optimal solutions, efficient solutions, and weakly efficient solutions. Theorem 6 reveals that the preimage of efficient points (or weakly efficient points) in F(X) is efficient solutions (or weakly efficient solutions) of the problem MOP.


### 2.2. Genetic Algorithm

Genetic algorithm is one of the most important evolutionary algorithms. It was introduced by Holland in the 1960s and then developed by his students and colleagues at the University of Michigan between the 1960s and 1970s [30]. Over the last two decades, the genetic algorithm was increasingly enriched by plenty of literatures, such as [31–34]. Nowadays various genetic algorithms are applied in different areas, for example, mathematical programming, combinational optimization, automatic control, and image processing.Suppose thatP(t) and O(t) represent parents and offspring at the tth generation, respectively. Then, the general structure of genetic algorithm can be described in the following pseudocode.General Structure of Genetic Algorithm
(
1
)
Initialization
(
1.1
)
Generate the initial populationP(0).
(
1.2
)
Set crossover rate, mutation rate, and maximal generation time.
(
1.3
)
Lett←0.
(
2
)
Since the maximal generation time is not reached, do the following.
(
2.1
)
Crossover operator: generateO1(t).
(
2.2
)
Mutation operator: generateO2(t).
(
2.3
)
EvaluateO1(t) and O2(t): compute the fitness function.
(
2.4
)
Select operator: build the next population.
(
2.5
)
t
←
t
+
1, go to (2.1).
End
End.From the pseudocode, we can see that there are three important operators in a general genetic algorithm: the crossover, mutation, and selection operators. The implementation of these operators is highly dependent on the way of encoding.


## 2.1. Definitions in Multiobjective Optimization

First of all, we present the following notations which are often used in vector optimization. Given two vectors(2)x=x1,x2,…,xnT,y=y1,y2,…,ynT∈Rn,then (i)
x=y⇔xi=yi for all i=1,2,…,n;(ii)
x<y⇔xi<yi for all i=1,2,…,n;(iii)
x≤y⇔xi≤yi for all i=1,2,…,n, and there is at least one i∈{1,2,…,n} such that xi<yi; that is, x≠y;(iv)
x≦y⇔xi≤yi for all i=1,2,…,n. “>,” “≥,” and “≧” can be defined similarly. In this paper, we call x≤y by x dominates y or y is dominated by x (in some literatures, x≥y is called x dominates y or y is dominated by y; we reverse this definition since we are solving minimization problem in this paper).Definition 1.
Suppose thatx⊆Rn and x*∈X. If x*≦x for any x∈X, then x* is called an absolute optimal point of X.Absolute optimal point is an ideal point, but it may not exist.Definition 2.
Letx∈Rn and x*∈X. If there is no x∈X such that (3)x≤x*(orx<x*),then x* is called anefficient point (orweakly efficient point).The sets of absolute optimal points, efficient points, and weakly efficient points ofX are denoted as Xab, Xep, and Xwp, respectively. For the problem MOP, X⊆Rn is called thedecision variable space and its image set F(X)={y∈Rp∣y=F(x),x∈X}⊂Rp is called theobjective function value space.Definition 3.
Suppose thatx*∈X. If (4)F(x*)≦F(x),for any x∈X, x* is called anabsolute optimal solution of the problem MOP. The set of absolute optimal solutions is denoted as Sas.The concept of the absolute optimal solution is a direct extension of that for single-objective optimization. It is the ideal solution but may not exist for most cases.Definition 4.
Suppose thatx*∈X. If there is no x∈X such that (5)Fx≤Fx*orFx<Fx*;that is, F(x*) is an efficient point (or weakly efficient point) of the objective function value space F(X), then x* is called anefficient solution (orweakly efficient solution) of the problem MOP. The sets of efficient solutions and weakly efficient solutions are denoted as Ses and Sws, respectively.Another name of the efficient solution isPareto solution, which was introduced by Koopmans and Reiter in 1951 [29]. The meaning of the Pareto solution is that if x*∈Ses, then there is no feasible solution x∈X, such that any fi(x) of F(x) is not worse than that of F(x*). In other words, x* is the best solution in the sense of “≤.” Another intuitive interpretation of Pareto solution is that it cannot be improved with respect to any objective without worsening at least one of the other objectives. The set of Pareto solutions is denoted by P*. Its image set F(P*) is called thePareto frontier, denoted by PF*. The following two theorems are well known.Theorem 5 (see [6]).
For the multiobjective optimization, it holds that(6)Sas⊂Ses(P*)⊂Sws⊂X.Theorem 6 (see [6]).
For the objective function value spaceF(X), if the sets of efficient points and weakly efficient points (i.e., Fes and Fws, resp.) are known, then, in the feasible set X, it holds that (7)Ses=⋃F¯∈Fes‍x∈X∣Fx=F¯,Sws=⋃F¯∈Fws‍x∈X∣F(x)=F¯.Theorem5 illustrates the relationship of the sets of absolute optimal solutions, efficient solutions, and weakly efficient solutions. Theorem 6 reveals that the preimage of efficient points (or weakly efficient points) in F(X) is efficient solutions (or weakly efficient solutions) of the problem MOP.


## 2.2. Genetic Algorithm

Genetic algorithm is one of the most important evolutionary algorithms. It was introduced by Holland in the 1960s and then developed by his students and colleagues at the University of Michigan between the 1960s and 1970s [30]. Over the last two decades, the genetic algorithm was increasingly enriched by plenty of literatures, such as [31–34]. Nowadays various genetic algorithms are applied in different areas, for example, mathematical programming, combinational optimization, automatic control, and image processing.Suppose thatP(t) and O(t) represent parents and offspring at the tth generation, respectively. Then, the general structure of genetic algorithm can be described in the following pseudocode.General Structure of Genetic Algorithm
(
1
)
Initialization
(
1.1
)
Generate the initial populationP(0).
(
1.2
)
Set crossover rate, mutation rate, and maximal generation time.
(
1.3
)
Lett←0.
(
2
)
Since the maximal generation time is not reached, do the following.
(
2.1
)
Crossover operator: generateO1(t).
(
2.2
)
Mutation operator: generateO2(t).
(
2.3
)
EvaluateO1(t) and O2(t): compute the fitness function.
(
2.4
)
Select operator: build the next population.
(
2.5
)
t
←
t
+
1, go to (2.1).
End
End.From the pseudocode, we can see that there are three important operators in a general genetic algorithm: the crossover, mutation, and selection operators. The implementation of these operators is highly dependent on the way of encoding.


## 3. A New Multiobjective Genetic Algorithm

In this section, we present a new multiobjective genetic algorithm for solving the problem MOP. We first propose a ranking strategy called the optimum order method and then metrics for the elitism and diversity of solutions. Finally, a new selection operator for genetic algorithm is designed using the optimum order method and the elitism and diversity metrics.Theoretically, the terminology “solution” means the point in the decision variable space, while the corresponding point in the objective function value space is named as “image of solution.” However, most of the following discussions are in the objective function value space. In order to simplify the description, we indiscriminately call the point from the decision variable space and its corresponding image from the objective function value space as the “solution,” if there is no confusion to do so.


### 3.1. The Optimum Order Method

In numerical optimization, in order to compare the numerical performance of different solutions, it is necessary to assign a fitness value for each solution. For the single-valued function, fitness is normally assigned as its function value. However, to assign the fitness of a multiobjective function is not straightforward. So far, there are three typical approaches. The first one is weighted sum approach [22, 35], which converts the multiple objectives into a single one using normalized weight ∑i=1p‍λi=1, λi>0, i=1,2,…,p. The decision of weight parameters is not an easy task for this approach. The second one is to alter the objective functions [18, 25], which randomly divides the current population into p equal subpopulations: P1,P2,…,Pp. Then, each solution in the subpopulation Pi is assigned a fitness value based on the objective function fi. In fact, this approach is a straightforward extension of the single-objective genetic algorithm. The last one is Pareto-ranking approach [4, 23, 36], which is a direct application of the definition of Pareto solution. In the following, we present a rank strategy called the optimum order method [6].Definition 7.
LetP={1,2,…,p} and N={1,2,…,n}; for any xi,xj∈X, define(8)aijl=1,iffl(xi)<fl(xj);0.5,iffl(xi)=fl(xj);0,iffl(xi)>flxjori=j.Then, (9)aij=∑l∈P‍aijli,j∈Nis called theoptimal number of xi corresponding to xj for all objectives. Furthermore, Ki=∑j∈Naij is defined asthe total optimal number of xi corresponding to all the other solutions for all objectives.Obviously, for a minimization problem, a larger optimal number corresponds to a better solution. Therefore, optimal numbers can be considered as criteria for ranking a set of solutions. Due to this observation, we propose the following algorithm to rank a population of solutions.Algorithm 8 (optimum order method (OOM)).
Consider the following steps.
Step  1 (input). It includes the population of solutions and their objective function values.
Step  2 (compute optimal numbers). Compute the optimal number and total optimal number of each solution; fill these numbers into Table 1 according to (8).
Step  3 (rank the solution). Rearrange the order of solutions according to the decreasing order of the total optimal numbers Ki. More precisely, denote (10)Kα1=max⁡i∈N{Ki},Kα2=max⁡i∈N∖{α1}Ki,and so on.Table 1
Table of optimal numbers.
x
i
x
j
x
1
x
2
⋯
x
j
⋯
x
n
K
i
x
1
0
a
12
⋯
a
1
j
⋯
a
1
n
K
1
x
2
a
21
0
⋯
a
2
j
⋯
a
2
n
K
2
⋮
⋮
⋮
⋮
⋮
⋮
x
i
a
i
1
a
i
2
⋯
a
i
j
⋯
a
i
n
K
i
⋮
⋮
⋮
⋮
⋮
⋮
x
n
a
n
1
a
n
2
⋯
a
n
j
⋯
0
K
nThe solutionsxα1 and xα2, which are corresponding to Kα1, Kα2, and so forth, are calledthe best solution,the second best solution, and so forth. The new order is called theoptimal order. It is worth mentioning that the optimum order method does not necessarily rank Pareto solutions in the frontier positions; however, those solutions who are more reasonable with respect to all objectives are more likely to be ranked in the foremost positions. This property is different from Pareto-ranking approach.Lemma 9.
Suppose thatxi,xj∈X. If F(xi)≤F(xj), then aij>aji.Proof.
Let(11)A=l∈P∣fl(xi)<fl(xj),a=A;B=l∈P∣fl(xi)=fl(xj),b=B,where · denotes the number of components in a set. Obviously, we have a>0, b>0 and a+b=p. Then, (12)aijl=1,l∈A,0.5,l∈B,ajil=0,l∈A,0.5,l∈B.Therefore, (13)aij=∑l∈A‍aijl+∑l∈B‍aijl=a+0.5b,aji=∑l∈A‍ajil+∑l∈B‍ajil=0.5b.Since a>0, aij>aji.Lemma 10.
Suppose thatxi,xj∈X. If F(xi)≤F(xj), then, for any xk  (k≠i,j,  k∈N), aik>ajk.Proof.
For anyxk(k≠i,j,k∈N), let (14)A=l∈P∣flxk<flxi,a=A;B=l∈P∣fl(xk)>fl(xi),b=B;C=l∈P∣fl(xk)=fl(xi),c=C.Then, we have a,b,c≥0 and a+b+c=p. (i)
Whenl∈A. Since F(xi)≤F(xj), we have (15)flxk<flxi,fl(xk)<fl(xj).Therefore,(16)aik1=∑l∈A‍aikl=0·a=0,ajk1=∑l∈A‍ajkl=0·a=0.(ii)
Whenl∈B. We have fl(xk)>fl(xi). Thus,(17)aik2=∑l∈B‍aikl=1·b=b.On the other hand, let (18)M1=l∈B∣flxk<flxj,m1=M1;M2=l∈B∣flxk=flxj,m2=M2;M3=l∈B∣fl(xk)>fl(xj),m3=M3.Obviously, m1,m2,m3≥0 and m1+m2+m3=b. Therefore,(19)ajk2=m1·0+m2·0.5+m3·1≤b.(iii)
Whenl∈C. We have(20)aik3=∑l∈C‍aikl=0.5·c.On the other hand, let (21)M1=l∈C∣fl(xk)<fl(xj),m1=M1;M2=l∈C∣fl(xk)=fl(xj),m2=M2.Note that it is not possible to have fl(xk)>fl(xj). Otherwise, we will have fl(xi)>fl(xj), which is contrary to F(xi)≤F(xj). Again, we have m1,m2≥0 and m1+m2=c. Thus,(22)ajk3=∑l∈C‍ajkl=m1·0+m2·0.5≤0.5c.In light of (16)–(22), we have (23)aik=∑α=13‍αikα≥ajk=∑α=13‍ajkα.Theorem 11.
IfKe=max⁡i∈N{Ki}, then the solution xe corresponding to Ke must be an efficient solution (Pareto solution).Proof.
Ifxe is not an efficient solution, then there exists an xs∈X, such that (24)F(xs)≤F(xe).Therefore, according to Lemma 9,(25)aes<ase.Due to Lemma 10, we have, for any xj(j∈N,j≠e,s),(26)aej≤asj.Based on (25), (26) and aee=ass=0, we have (27)Ke=∑j∈N‍aej<∑j∈N‍asj=Ks,which is a contradiction to the assumption ke=max⁡i∈N⁡{Ki}. The proof is completed.Based on Theorem11, the following results are obvious.Corollary 12.
Ifxa is an absolute optimal solution, then (28)Ka=max⁡j∈N{Kj}.Corollary 13.
Ifxe is corresponding to Ke=max⁡j∈N⁡{Kj} and xs is corresponding to Ks=max⁡j∈N∖{e}⁡{Kj}, then xs is an efficient solution of the population without xe.Theorem11 and Corollary 13 reveal the rationality of the optimum order method because the best solution must be an efficient solution, and the second best solution, although may not be an efficient solution, is an efficient solution without the best one. This statement is true until the solution with the smallest total optimal number (ranked as the last reasonable solution). Therefore, It is reasonable for us to choose solutions with large total optimal numbers as parents for the next generation.


### 3.2. The Elitism Metric

Over the last two decades, a number of different evolutionary algorithms were suggested to solve multiobjective optimization problems, such as MOGA [37], NSGA [23], NPGA [20], SPEA [24], PAES [38], and NSGA-II [4]. Among them, MOGA, NSGA, and NPGA did not introduce any elitism strategy at all. Therefore, although they were successful in finding solutions for many test problems and a number of engineering problems, researchers realized that they are still needed to be improved in the sense of obtaining better Pareto solutions [28]. Elitism is one of the main issues considered to be improved. After that, SPEA, PAES, and NSGA-II started to take into account the elitism of solutions.SPEA introduces an external population which stores all nondominated solutions discovered so far beginning from the initial population. At each generation, a combined population based on the external population and the current population is generated firstly. Then, all the nondominated solutions in the combined population are identified and assigned a fitness based on the number of solutions they dominate. Furthermore, the dominated solutions are assigned a fitness which is worse than the worst fitness of the nondominated solution. Then, the next generation is selected based on the fitness of each solution. This elitism strategy makes sure that the search is directed toward the nondominated solutions. Although the computational complexity of SPEA isO(MN3) (where M is the number of objectives and N is the size of the population), with proper bookkeeping, the complexity can be reduced to O(MN2).PAES uses a single-parent single-offspring evolutionary algorithm which is similar to(1+1)-evolution strategy. In PAES, the elitism strategy is implemented by comparing between one parent and one offspring. If the offspring dominates the parent, the offspring is accepted as the next parent; on the other hand, if the parent dominates the offspring, the offspring is replaced by another mutated solution (a new offspring) and the comparison between the parent and offspring is made again. However, if the parent and the offspring do not dominate each other, the choice between them is made by comparing them with an archive of the best solutions found so far. More specifically, if the offspring dominates any solution stored in the archive, then the offspring is accepted by the archive and all the dominated solutions are eliminated from the archive. On the contrary, if the offspring does not dominate any solution stored in the archive, then the parent and offspring are accepted by the archive after checking the diversity. The computational complexity of PAES is calculated as O(aMN), where a is the length of the archive. Since the archive size is usually chosen proportional to the population size N, the overall complexity of PAES is O(MN2).NSGA implements the elitism strategy using naive nondominated sorting approach. For a population of solutions, the naive nondominated sorting first identifies the nondominated solutions in the population and then the nondominated solutions without considering the solutions which have already been identified. This process is repeated until all the solutions in the population have been identified. In this way, the solutions are classified into different Pareto frontiers and selected based on their Pareto ranking. The native nondominated sorting approach is based on the definition of Pareto frontier. It is easy to be implemented, but in the worst case, the task of identifying all the Pareto frontier requires a computational complexity ofO(MN3). In order to reduce the complexity of NSGA, NSGA-II improved the sorting approach and presented the fast nondominated sorting approach. NSGA-II introduced two entities, domination count (np) and dominated count (Sp). The domination count represents the number of solutions which dominates the solution p; the dominated count represents the number of solutions which are dominated by the solutions p.All solution in the first nondominated front will have their domination count as zero. Now, for each solutionp with np=0, we visit each member (q) of its set Sp and reduce its domination count by one. In doing so, if for any member q the domination count becomes zero, we put it in a separate list Q. These members belong to the second nondominated front. Now, the above procedure is continued with each member of Q and the third front is identified. This process continues until all frontiers are identified. It is evident to observe that the naive nondominated sorting approach and the fast nondominated sorting approach lead to the same Pareto ranking for a population of solutions. The overall computational complexity of the fast nondominated sorting approach is O(MN2).The previous elitism strategies use the definitions of domination or Pareto ranking, but they do not quantify the elitism of solutions. In this paper, we introduce a new elitism strategy which is still based on Pareto ranking but quantifies the elitism of solutions.Definition 14.
Suppose thatP1 is a population of solutions, we define theelitism metric of the nondominated solutions in P1, say F1, as 1; define the elitism metric of the nondominated solutions in P2=P1∖F1, say F2, as 2; and so forth; and define the elitism metric of the nondominated solutions in Pi=Pi-1∖Fi-1, say Fi as i.Remark 15.
The process in Definition14 is the same as the native nondominated sorting approach. And the elitism metric of each solution is actually its index of Pareto ranking.According to Definition14, the elitism measure of solutions can be taken as a function of the solutions, the value of the function is the elitism metric of solutions. We call this functionthe elitism function. Mathematically,(29)θ:P1⟶Z+,whereP1⊂Rnis  a  population  andZ+is  the  positive  integer.It is obvious that a small value of θ(x) means that x enjoys a good Pareto ranking. Therefore, in order to find solutions with better Pareto ranking, we should minimize function θ(x). In the following, we present a method to calculate the value of function θ.Suppose thatP1={x1,x2,…,xN}, we calculate the value of α(xi,xj) by (30)αxi,xj=1,ifxidominatesxj;-1,ifxidominatedbyxj;0,ifxiandxjarenotdominatedbyeachother.Then we construct the domination table (see Table 2).Table 2
The domination table ofP1.
x
1
x
2
⋯
x
N
-
1
x
N
x
1
—
α
(
x
1
,
x
2
)
⋯
α
(
x
1
,
x
N
-
1
)
α
(
x
1
,
x
N
)
x
2
α
(
x
2
,
x
1
)
—
⋯
α
(
x
2
,
x
N
-
1
)
α
(
x
2
,
x
N
)
⋮
⋮
⋮
⋱
⋮
⋮
x
N
-
1
α
(
x
N
-
1
,
x
1
)
α
(
x
N
-
1
,
x
2
)
⋯
—
α
(
x
N
-
1
,
x
N
)
x
N
α
(
x
N
,
x
1
)
α
(
x
N
,
x
2
)
⋯
α
(
x
N
,
x
N
-
1
)
—Obviously, entries of Table2 are just -1, 0, and 1. Now we successively check every row of the table, if any row, say the ith one, whose entries are only 0 or 1; then we can claim that there is no solution dominating xi, which means that xi’s elitism metric is 1. Then discard the rows and columns in which these solutions with elitism metric of 1 locate. This means that we do not consider these solutions any more in the following process since they have already been identified. This process is repeated again and the identified solutions are assigned with elitism metric of 2 and so forth until all the solutions are identified.In Table2, it is evident that α(xi,xj)=-α(xj,xi), where 1≤i≠j≤N. So the computational complexity of assigning elitism metrics for the population is O((1/2)M(N-1)2). We provide the following example to illustrate the process described above.Figure1 illustrated a population of solutions. There are 35 solutions in this population. The numbers on the side are indexes of these solutions. Table 2 is the domination table of this population. First, we successively check rows of Table 3; rows with only 0 and 1 are 1, 2, 5, 8, 9, 10, 16, 17, 19, 20, and 28. So solutions corresponding to these rows are in the first Pareto frontier and should be assigned elitism metric 1. Then, discard the corresponding rows and columns from the domination table and do the same search again. We assign the solutions corresponding to the identified rows with elitism metric 2. This process is repeated until all the rows of the domination table are discarded. We depict the elitism metric assignment in Figure 2.Table 3
The domination table ofP1.
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
1
—
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
—
1
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
−1
−1
—
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
−1
0
—
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
0
0
—
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
−1
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
−1
−1
−1
−1
−1
0
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
—
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
—
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
0
0
1
0
0
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
11
0
0
0
0
0
0
0
0
0
−1
—
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
0
−1
0
−1
−1
0
0
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
0
0
0
0
0
0
0
−1
−1
−1
−1
0
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
−1
0
0
0
—
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
15
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
—
0
0
1
0
0
1
1
1
0
1
1
0
0
0
1
1
1
1
1
1
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
0
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
18
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
—
0
0
1
1
1
0
1
1
0
0
0
1
1
1
1
1
1
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
21
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
1
0
0
0
0
22
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
—
1
0
1
1
0
0
0
0
1
0
1
1
1
23
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
—
0
0
0
0
0
0
0
1
0
0
0
0
24
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
−1
−1
0
0
0
—
1
1
1
0
1
1
1
1
1
1
1
25
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
0
−1
—
0
0
0
0
0
1
0
0
0
0
26
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
—
0
0
0
0
1
0
0
0
0
27
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
−1
0
−1
−1
0
0
0
−1
0
0
—
0
1
1
1
1
1
1
1
28
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
1
1
29
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
0
1
−1
0
−1
−1
0
0
0
−1
0
0
−1
−1
—
1
1
1
1
1
1
30
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
0
0
−1
0
0
−1
−1
−1
—
1
1
1
1
1
31
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
—
0
0
0
0
32
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
0
0
−1
0
0
−1
−1
−1
−1
0
—
1
1
1
33
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
—
1
0
34
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
−1
—
0
35
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
0
0
—Figure 1
The population of solutions.Figure 2
The elitism metric assignment for the population.


### 3.3. The Diversity Metric

As discussed before, diversity of solutions is another criterion for solutions obtained by the multiobjective genetic algorithm. In order to obtain uniformly distributed solutions, it is important to maintain the diversity of the population in the iteration process. Without this, solutions in the population tend to form relatively few clusters. This phenomenon is known asgenetic drift. Several approaches have been developed to maintain the diversity of solutions. Among them, the sharing function approach [19, 39] is one of the earliest approaches. The sharing function approach degrades the objective fitness of solutions by setting a threshold θshare. This threshold is still calledsharing parameter. For a solution xi in the current population, aniche countmi is first calculated. The niche count mi=1 if there is no solution in the θshare-niche (neighborhood) of xi (i.e., there is no solution whose distance with xi is less than θshare); the niche count mi>1 if there are some solutions in the θshare-niche (neighborhood) of xi (i.e., there are some solutions whose distances with xi) less than θshare. Then, the degradation is obtained through dividing the objective fitness by the niche count, that is, fi/mi. This proportion is called theshared fitness. The original NSGA [23] used the sharing function approach to maintain the diversity of solutions. The performance of the sharing function approach terribly depends on the sharing parameter θshare. However, θshare is a user-decided parameter and it is difficult to choose a proper one. Since each solution must be compared with all other solutions in the population, the overall complexity of the sharing function approach is O(MN2).Deb et al. [4] introduced the crowding distance approach to maintain the diversity of solutions. This approach calculates the density estimation of a solution by summarizing the average distance of two solutions on either side of this solution along each of the objective function. The density estimation, which is still called crowding distance, serves as an estimate of the perimeter of the cuboid formed by using the nearest neighbors as the vertices. Obviously, a solution with a smaller value of crowding distance is more crowded by other solutions. Thus, the crowding distance can be considered as a measure of the diversity of a solution. The crowding distance approach does not require any user-defined parameter. Its computational complexity is O(MNlog⁡N), which is better than the sharing function approach. However, the crowing distance just reflects the local diversity of a solution.The cell-based density approach [6, 26, 38, 40, 41] divides the objective space into p-dimensional cells. The number of solutions in each cell is defined as thedensity of the cell, and thedensity of a solution is equal to the density of the cell in which the solution locates. An efficient approach to dynamically divide the objective function space into cells is proposed by Lu and Yen [40, 41]. The main advantage of the cell-based density approach is that a global density map of the objective function value space can be obtained. But the process of the cell-based density approach is complicated. For a single solution, in the worst case, it requires O(LM) comparison to locate the solution into a proper cell, where L is the number of cells for each objective function. Thus, the total complexity of the cell-based density approach is O(LMN). And furthermore, L is a user-defined parameter which is not easy to be chosen properly.In this section, we define the metric about measuring the degree of crowdedness around a solution. Then, a specifical diversity metric is introduced.Definition 16.
Suppose thatP1 is a population, xi and xj are two solutions from P1, and ϕi and ϕj are two scalars corresponding to xi and xj, respectively. We call ϕi and ϕj thediversity metrics of xi and xj, respectively, if ϕi<ϕj implies that solutions around xj are more crowded than those around xi.Definition16 is just a qualitative description of the diversity metric. In the following, we introduce a specifical definition of the diversity metric which quantitatively measures the degree of crowdedness around a solution.Definition 17.
Suppose thatP1 is a population with N solutions, xi is a solution in P1. We provide a function ϕ:P1↦R+ as(31)ϕ(xi)=∑j=1,j≠iN‍β(dij),where β:R+↦R+ is a decrease function and dij is the Euclidean distance between solutions xi and xj. Then we call the value of ϕ(xi) theglobal diversity metric of xi.It is obvious that the global diversity metric is coincident with the definition of diversity metric. One improvement of the global diversity metric is that it reflects the diversity ofxi with respect to all the other solutions since the function ϕ involves the whole population. The requirement for calculating the global diversity metric is only the Euclidean distance between any two solutions, so the computational complexity of the global diversity metric is O((1/2)(N-1)2). A proper choice of function β is (32)β(d)=1-1Dd,where D=max⁡1≤i,j≤N⁡{dij}.As an example, Figure3 illustrates the global diversity metric of the population presented in Figure 1. From Figure 3, one can observe that these solutions which are less crowded enjoy smaller global diversity metrics, such as solutions x35 and x34 (the index of the solution can be found in Figure 1) with 7.1157 and 15.6234, respectively. On the contrary, these solutions which are more crowded have larger global diversity metrics, such as solutions x15, x17, and x21 with 19.3926, 29.3777, and 29.3826, respectively.Figure 3
The global diversity metric for the population.


### 3.4. A New Selection Operator

As discussed before, the core criteria for multiobjective optimization are to obtain solutions with better elitism and, at the same time, maintain the diversity of solutions. If we tackle these criteria from a multiobjective optimization point of view, we need to solve a multiobjective optimization problem with two objectives: minimizing the elitism metric and the global diversity metric of the solution. Noting the definition of the elitism metricθ(x) and the global diversity metric ϕ(x) presented in the previous subsections, we design the following multiobjective subproblem:(33)MinimizeH(x)Subjecttox∈P1,where H(x)=(θ(x),ϕ(x))T is a multiobjective function and P1⊂X is a population of candidate solutions. It is clear that the image of H(·)(34)H=θx,ϕxT∣x∈P1is a finite set whose cardinal is the same as P1. One property of the multiobjective subproblem (33) is that its domain P1 and image set H are finite; that is, the problem (33) is discrete. Thus, if we rank points in H by the optimum order method (Algorithm 8), it is reasonable to say that those points who have smaller optimal orders are better points; that is, solutions corresponding to these points should be maintained to the next generation. This process is summarized by the following algorithm.Algorithm 18 (multiobjective selection operator).
Consider the following steps.
Step  1. Input the selection pool P1 and its objective function values F(P1)={F(x)∣x∈P1}. Input the prefixed population size N (N is less than the cardinal of P1).
Step  2. Calculate the elitism metric and global diversity metric of the solution in P1 using the function (29) and (31), respectively. Let the result be (35)Θ=θx∣x∈P1,Φ=ϕ(x)∣x∈P1.
Step  3. Construct the objective function value space of the multiobjective subproblem (36)H=θx,ϕxT∣θx∈Θ,ϕx∈Φ.
Step  4. Rank points in H by the optimum order method (Algorithm 8) and take the first N solutions according to their optimal orders as parents for the next generation.In Table4, we use the multiobjective selection operator to evaluate the population presented in Figure 1. In this table, θi, ϕi, Ki, and σi represent the elitism metric, global diversity metric, total optimal number, and optimal order of solution xi, respectively. We can observe that the multiobjective selection operator systematically considers the criteria of elitism and diversity. We select 15 solutions whose optimal orders are the smallest as parents of the next generation. They are marked as red squares in Figure 4. However, from Figure 4, distribution of the selected points is not ideal. This is because there are some irregular distributed points, such as points 33, 34, and 35. They are far away from the others, which means that they should be eliminated. But because of their very small diversity metric, they are selected by the selection operator. In order to tackle this issue, we pretreat the diversity metric before running the selection operator.Table 4
The total optimal number and optimal order without pretreatment of the diversity metric.
x
i
θ
i
ϕ
i
K
i
σ
i
x
1
1
25.8013
59.0
1
x
2
1
26.5934
57.0
2
x
3
2
26.7268
47.5
5
x
4
2
27.7626
44.5
8
x
5
1
28.2829
49.0
4
x
6
3
28.0889
36.5
10
x
7
3
28.3563
33.5
17
x
8
1
28.6122
47.0
6
x
9
1
28.8617
45.0
7
x
10
1
28.8972
44.0
9
x
11
2
29.0363
33.5
18
x
12
3
29.0259
28.5
26
x
13
3
29.2131
24.5
28
x
14
2
29.2940
26.5
27
x
15
2
29.3926
21.5
30
x
16
1
29.3800
32.0
25
x
17
1
29.3777
33.0
20
x
18
3
29.4494
14.5
34
x
19
1
29.3475
34.0
16
x
20
1
29.2939
36.0
11
x
21
4
29.3826
12.0
35
x
22
4
29.2878
18.0
31
x
23
5
29.2419
15.5
33
x
24
2
29.0505
32.5
22
x
25
5
29.0794
17.5
32
x
26
5
28.7751
23.5
29
x
27
3
28.1192
35.5
12
x
28
1
27.8471
52.0
3
x
29
4
27.7568
35.0
14
x
30
5
27.4767
32.5
23
x
31
6
26.1417
32.5
24
x
32
6
22.9761
34.5
15
x
33
7
21.0339
33.5
19
x
34
8
15.6234
33.0
21
x
35
7
7.1157
35.5
13Figure 4
The selected point without pretreatment of the diversity metric.In sport matches, the statistician always eliminates the highest and the lowest marks before calculating the average. We borrow this idea to pretreat the diversity metric. We simply identify the10% points with the highest and lowest diversity metric and eliminate them before the running of selection operator. In the example, the 10% points with the highest and lowest diversity metrics are 14, 15, 16, and 18 and 32, 33, 34, and 35, respectively. Thus, we run the selection operator without considering them.Table5 presents the total optimal number and optimal order with pretreatment of the diversity metric. It can be observed that points 14–16, 18, and 32–35 are excluded in the ranking process. This gives more chance to some point close to the Pareto frontier. For example, points 24 and 30 (which were ranked as 22 and 23, resp.) were not selected without pretreatment of the diversity metric, but they are selected (ranked as 13 and 14, resp.) after considering the pretreatment of the diversity metric. From Figure 5, we can see that the selected points are now well distributed and closer to the Pareto frontier.Table 5
The total optimal number and optimal order with pretreatment of the diversity metric.
x
i
θ
i
ϕ
i
K
i
σ
i
x
1
1
25.8013
59.0
1
x
2
1
26.5934
57.0
2
x
3
2
26.7268
47.5
4
x
4
2
27.7626
44.5
6
x
5
1
28.2829
49.0
5
x
6
3
28.0889
36.5
15
x
7
3
28.3563
33.5
17
x
8
1
28.6122
47.0
7
x
9
1
28.8617
45.0
12
x
10
1
28.8972
44.0
8
x
11
2
29.0363
33.5
21
x
12
3
29.0259
28.5
24
x
13
3
29.2131
24.5
26
x
14
2
29.2940
—
—
x
15
2
29.3926
—
—
x
16
1
29.3800
—
—
x
17
1
29.3777
33.0
19
x
18
3
29.4494
—
—
x
19
1
29.3475
34.0
18
x
20
1
29.2939
36.0
10
x
21
4
29.3826
12.0
27
x
22
4
29.2878
18.0
22
x
23
5
29.2419
15.5
25
x
24
2
29.0505
32.5
13
x
25
5
29.0794
17.5
23
x
26
5
28.7751
23.5
20
x
27
3
28.1192
35.5
9
x
28
1
27.8471
52.0
3
x
29
4
27.7568
35.0
11
x
30
5
27.4767
32.5
14
x
31
6
26.1417
32.5
16
x
32
6
22.9761
—
—
x
33
7
21.0339
—
—
x
34
8
15.6234
—
—
x
35
7
7.1157
—
—Figure 5
The selected point with pretreatment of the diversity metric.


### 3.5. A New Multiobjective Genetic Algorithm

Given the multiobjective selection operator, we are now ready to propose a new multiobjective genetic algorithm.Algorithm 19 (optimum order multiobjective genetic algorithm (OOMOGA)).
Consider the following.(1)
Initialization
(1.1)
Generate the initial populationP(0).(1.2)
Set the crossover rate, mutation rate, and number of maximal generations.(1.3)
Lett←0.(2)
Since the number of maximal generations has not been reached, do the following.
(2.1)
Run the crossover operator: generate the offspringO1(t).(2.2)
Run the mutation operator: generate the offspringO2(t).(2.3)
Construct a selection poolS(t) by combining P(t), O1(t), and O2(t); that is, S(t)=P(t)∪O1(t)∪O2(t). Compute their multiobjective function values; that is, FS(t)={F(x)∣x∈S(t)}.(2.4)
Run the multiobjective selection operator (Algorithm18) by inputting S(t) and FS(t); the selected solutions are maintained as the parents of the next generation, that is, P(t+1).(2.5)
Lett←t+1; go to (2.1).EndEnd.


## 3.1. The Optimum Order Method

In numerical optimization, in order to compare the numerical performance of different solutions, it is necessary to assign a fitness value for each solution. For the single-valued function, fitness is normally assigned as its function value. However, to assign the fitness of a multiobjective function is not straightforward. So far, there are three typical approaches. The first one is weighted sum approach [22, 35], which converts the multiple objectives into a single one using normalized weight ∑i=1p‍λi=1, λi>0, i=1,2,…,p. The decision of weight parameters is not an easy task for this approach. The second one is to alter the objective functions [18, 25], which randomly divides the current population into p equal subpopulations: P1,P2,…,Pp. Then, each solution in the subpopulation Pi is assigned a fitness value based on the objective function fi. In fact, this approach is a straightforward extension of the single-objective genetic algorithm. The last one is Pareto-ranking approach [4, 23, 36], which is a direct application of the definition of Pareto solution. In the following, we present a rank strategy called the optimum order method [6].Definition 7.
LetP={1,2,…,p} and N={1,2,…,n}; for any xi,xj∈X, define(8)aijl=1,iffl(xi)<fl(xj);0.5,iffl(xi)=fl(xj);0,iffl(xi)>flxjori=j.Then, (9)aij=∑l∈P‍aijli,j∈Nis called theoptimal number of xi corresponding to xj for all objectives. Furthermore, Ki=∑j∈Naij is defined asthe total optimal number of xi corresponding to all the other solutions for all objectives.Obviously, for a minimization problem, a larger optimal number corresponds to a better solution. Therefore, optimal numbers can be considered as criteria for ranking a set of solutions. Due to this observation, we propose the following algorithm to rank a population of solutions.Algorithm 8 (optimum order method (OOM)).
Consider the following steps.
Step  1 (input). It includes the population of solutions and their objective function values.
Step  2 (compute optimal numbers). Compute the optimal number and total optimal number of each solution; fill these numbers into Table 1 according to (8).
Step  3 (rank the solution). Rearrange the order of solutions according to the decreasing order of the total optimal numbers Ki. More precisely, denote (10)Kα1=max⁡i∈N{Ki},Kα2=max⁡i∈N∖{α1}Ki,and so on.Table 1
Table of optimal numbers.
x
i
x
j
x
1
x
2
⋯
x
j
⋯
x
n
K
i
x
1
0
a
12
⋯
a
1
j
⋯
a
1
n
K
1
x
2
a
21
0
⋯
a
2
j
⋯
a
2
n
K
2
⋮
⋮
⋮
⋮
⋮
⋮
x
i
a
i
1
a
i
2
⋯
a
i
j
⋯
a
i
n
K
i
⋮
⋮
⋮
⋮
⋮
⋮
x
n
a
n
1
a
n
2
⋯
a
n
j
⋯
0
K
nThe solutionsxα1 and xα2, which are corresponding to Kα1, Kα2, and so forth, are calledthe best solution,the second best solution, and so forth. The new order is called theoptimal order. It is worth mentioning that the optimum order method does not necessarily rank Pareto solutions in the frontier positions; however, those solutions who are more reasonable with respect to all objectives are more likely to be ranked in the foremost positions. This property is different from Pareto-ranking approach.Lemma 9.
Suppose thatxi,xj∈X. If F(xi)≤F(xj), then aij>aji.Proof.
Let(11)A=l∈P∣fl(xi)<fl(xj),a=A;B=l∈P∣fl(xi)=fl(xj),b=B,where · denotes the number of components in a set. Obviously, we have a>0, b>0 and a+b=p. Then, (12)aijl=1,l∈A,0.5,l∈B,ajil=0,l∈A,0.5,l∈B.Therefore, (13)aij=∑l∈A‍aijl+∑l∈B‍aijl=a+0.5b,aji=∑l∈A‍ajil+∑l∈B‍ajil=0.5b.Since a>0, aij>aji.Lemma 10.
Suppose thatxi,xj∈X. If F(xi)≤F(xj), then, for any xk  (k≠i,j,  k∈N), aik>ajk.Proof.
For anyxk(k≠i,j,k∈N), let (14)A=l∈P∣flxk<flxi,a=A;B=l∈P∣fl(xk)>fl(xi),b=B;C=l∈P∣fl(xk)=fl(xi),c=C.Then, we have a,b,c≥0 and a+b+c=p. (i)
Whenl∈A. Since F(xi)≤F(xj), we have (15)flxk<flxi,fl(xk)<fl(xj).Therefore,(16)aik1=∑l∈A‍aikl=0·a=0,ajk1=∑l∈A‍ajkl=0·a=0.(ii)
Whenl∈B. We have fl(xk)>fl(xi). Thus,(17)aik2=∑l∈B‍aikl=1·b=b.On the other hand, let (18)M1=l∈B∣flxk<flxj,m1=M1;M2=l∈B∣flxk=flxj,m2=M2;M3=l∈B∣fl(xk)>fl(xj),m3=M3.Obviously, m1,m2,m3≥0 and m1+m2+m3=b. Therefore,(19)ajk2=m1·0+m2·0.5+m3·1≤b.(iii)
Whenl∈C. We have(20)aik3=∑l∈C‍aikl=0.5·c.On the other hand, let (21)M1=l∈C∣fl(xk)<fl(xj),m1=M1;M2=l∈C∣fl(xk)=fl(xj),m2=M2.Note that it is not possible to have fl(xk)>fl(xj). Otherwise, we will have fl(xi)>fl(xj), which is contrary to F(xi)≤F(xj). Again, we have m1,m2≥0 and m1+m2=c. Thus,(22)ajk3=∑l∈C‍ajkl=m1·0+m2·0.5≤0.5c.In light of (16)–(22), we have (23)aik=∑α=13‍αikα≥ajk=∑α=13‍ajkα.Theorem 11.
IfKe=max⁡i∈N{Ki}, then the solution xe corresponding to Ke must be an efficient solution (Pareto solution).Proof.
Ifxe is not an efficient solution, then there exists an xs∈X, such that (24)F(xs)≤F(xe).Therefore, according to Lemma 9,(25)aes<ase.Due to Lemma 10, we have, for any xj(j∈N,j≠e,s),(26)aej≤asj.Based on (25), (26) and aee=ass=0, we have (27)Ke=∑j∈N‍aej<∑j∈N‍asj=Ks,which is a contradiction to the assumption ke=max⁡i∈N⁡{Ki}. The proof is completed.Based on Theorem11, the following results are obvious.Corollary 12.
Ifxa is an absolute optimal solution, then (28)Ka=max⁡j∈N{Kj}.Corollary 13.
Ifxe is corresponding to Ke=max⁡j∈N⁡{Kj} and xs is corresponding to Ks=max⁡j∈N∖{e}⁡{Kj}, then xs is an efficient solution of the population without xe.Theorem11 and Corollary 13 reveal the rationality of the optimum order method because the best solution must be an efficient solution, and the second best solution, although may not be an efficient solution, is an efficient solution without the best one. This statement is true until the solution with the smallest total optimal number (ranked as the last reasonable solution). Therefore, It is reasonable for us to choose solutions with large total optimal numbers as parents for the next generation.


## 3.2. The Elitism Metric

Over the last two decades, a number of different evolutionary algorithms were suggested to solve multiobjective optimization problems, such as MOGA [37], NSGA [23], NPGA [20], SPEA [24], PAES [38], and NSGA-II [4]. Among them, MOGA, NSGA, and NPGA did not introduce any elitism strategy at all. Therefore, although they were successful in finding solutions for many test problems and a number of engineering problems, researchers realized that they are still needed to be improved in the sense of obtaining better Pareto solutions [28]. Elitism is one of the main issues considered to be improved. After that, SPEA, PAES, and NSGA-II started to take into account the elitism of solutions.SPEA introduces an external population which stores all nondominated solutions discovered so far beginning from the initial population. At each generation, a combined population based on the external population and the current population is generated firstly. Then, all the nondominated solutions in the combined population are identified and assigned a fitness based on the number of solutions they dominate. Furthermore, the dominated solutions are assigned a fitness which is worse than the worst fitness of the nondominated solution. Then, the next generation is selected based on the fitness of each solution. This elitism strategy makes sure that the search is directed toward the nondominated solutions. Although the computational complexity of SPEA isO(MN3) (where M is the number of objectives and N is the size of the population), with proper bookkeeping, the complexity can be reduced to O(MN2).PAES uses a single-parent single-offspring evolutionary algorithm which is similar to(1+1)-evolution strategy. In PAES, the elitism strategy is implemented by comparing between one parent and one offspring. If the offspring dominates the parent, the offspring is accepted as the next parent; on the other hand, if the parent dominates the offspring, the offspring is replaced by another mutated solution (a new offspring) and the comparison between the parent and offspring is made again. However, if the parent and the offspring do not dominate each other, the choice between them is made by comparing them with an archive of the best solutions found so far. More specifically, if the offspring dominates any solution stored in the archive, then the offspring is accepted by the archive and all the dominated solutions are eliminated from the archive. On the contrary, if the offspring does not dominate any solution stored in the archive, then the parent and offspring are accepted by the archive after checking the diversity. The computational complexity of PAES is calculated as O(aMN), where a is the length of the archive. Since the archive size is usually chosen proportional to the population size N, the overall complexity of PAES is O(MN2).NSGA implements the elitism strategy using naive nondominated sorting approach. For a population of solutions, the naive nondominated sorting first identifies the nondominated solutions in the population and then the nondominated solutions without considering the solutions which have already been identified. This process is repeated until all the solutions in the population have been identified. In this way, the solutions are classified into different Pareto frontiers and selected based on their Pareto ranking. The native nondominated sorting approach is based on the definition of Pareto frontier. It is easy to be implemented, but in the worst case, the task of identifying all the Pareto frontier requires a computational complexity ofO(MN3). In order to reduce the complexity of NSGA, NSGA-II improved the sorting approach and presented the fast nondominated sorting approach. NSGA-II introduced two entities, domination count (np) and dominated count (Sp). The domination count represents the number of solutions which dominates the solution p; the dominated count represents the number of solutions which are dominated by the solutions p.All solution in the first nondominated front will have their domination count as zero. Now, for each solutionp with np=0, we visit each member (q) of its set Sp and reduce its domination count by one. In doing so, if for any member q the domination count becomes zero, we put it in a separate list Q. These members belong to the second nondominated front. Now, the above procedure is continued with each member of Q and the third front is identified. This process continues until all frontiers are identified. It is evident to observe that the naive nondominated sorting approach and the fast nondominated sorting approach lead to the same Pareto ranking for a population of solutions. The overall computational complexity of the fast nondominated sorting approach is O(MN2).The previous elitism strategies use the definitions of domination or Pareto ranking, but they do not quantify the elitism of solutions. In this paper, we introduce a new elitism strategy which is still based on Pareto ranking but quantifies the elitism of solutions.Definition 14.
Suppose thatP1 is a population of solutions, we define theelitism metric of the nondominated solutions in P1, say F1, as 1; define the elitism metric of the nondominated solutions in P2=P1∖F1, say F2, as 2; and so forth; and define the elitism metric of the nondominated solutions in Pi=Pi-1∖Fi-1, say Fi as i.Remark 15.
The process in Definition14 is the same as the native nondominated sorting approach. And the elitism metric of each solution is actually its index of Pareto ranking.According to Definition14, the elitism measure of solutions can be taken as a function of the solutions, the value of the function is the elitism metric of solutions. We call this functionthe elitism function. Mathematically,(29)θ:P1⟶Z+,whereP1⊂Rnis  a  population  andZ+is  the  positive  integer.It is obvious that a small value of θ(x) means that x enjoys a good Pareto ranking. Therefore, in order to find solutions with better Pareto ranking, we should minimize function θ(x). In the following, we present a method to calculate the value of function θ.Suppose thatP1={x1,x2,…,xN}, we calculate the value of α(xi,xj) by (30)αxi,xj=1,ifxidominatesxj;-1,ifxidominatedbyxj;0,ifxiandxjarenotdominatedbyeachother.Then we construct the domination table (see Table 2).Table 2
The domination table ofP1.
x
1
x
2
⋯
x
N
-
1
x
N
x
1
—
α
(
x
1
,
x
2
)
⋯
α
(
x
1
,
x
N
-
1
)
α
(
x
1
,
x
N
)
x
2
α
(
x
2
,
x
1
)
—
⋯
α
(
x
2
,
x
N
-
1
)
α
(
x
2
,
x
N
)
⋮
⋮
⋮
⋱
⋮
⋮
x
N
-
1
α
(
x
N
-
1
,
x
1
)
α
(
x
N
-
1
,
x
2
)
⋯
—
α
(
x
N
-
1
,
x
N
)
x
N
α
(
x
N
,
x
1
)
α
(
x
N
,
x
2
)
⋯
α
(
x
N
,
x
N
-
1
)
—Obviously, entries of Table2 are just -1, 0, and 1. Now we successively check every row of the table, if any row, say the ith one, whose entries are only 0 or 1; then we can claim that there is no solution dominating xi, which means that xi’s elitism metric is 1. Then discard the rows and columns in which these solutions with elitism metric of 1 locate. This means that we do not consider these solutions any more in the following process since they have already been identified. This process is repeated again and the identified solutions are assigned with elitism metric of 2 and so forth until all the solutions are identified.In Table2, it is evident that α(xi,xj)=-α(xj,xi), where 1≤i≠j≤N. So the computational complexity of assigning elitism metrics for the population is O((1/2)M(N-1)2). We provide the following example to illustrate the process described above.Figure1 illustrated a population of solutions. There are 35 solutions in this population. The numbers on the side are indexes of these solutions. Table 2 is the domination table of this population. First, we successively check rows of Table 3; rows with only 0 and 1 are 1, 2, 5, 8, 9, 10, 16, 17, 19, 20, and 28. So solutions corresponding to these rows are in the first Pareto frontier and should be assigned elitism metric 1. Then, discard the corresponding rows and columns from the domination table and do the same search again. We assign the solutions corresponding to the identified rows with elitism metric 2. This process is repeated until all the rows of the domination table are discarded. We depict the elitism metric assignment in Figure 2.Table 3
The domination table ofP1.
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
1
—
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
—
1
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
−1
−1
—
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
−1
0
—
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
0
0
—
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
−1
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
−1
−1
−1
−1
−1
0
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
—
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
—
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
0
0
1
0
0
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
11
0
0
0
0
0
0
0
0
0
−1
—
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
12
0
−1
0
−1
−1
0
0
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
13
0
0
0
0
0
0
0
−1
−1
−1
−1
0
—
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
−1
0
0
0
—
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
15
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
—
0
0
1
0
0
1
1
1
0
1
1
0
0
0
1
1
1
1
1
1
16
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
0
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
18
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
—
0
0
1
1
1
0
1
1
0
0
0
1
1
1
1
1
1
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
20
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
21
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
—
0
0
0
0
0
0
0
0
0
1
0
0
0
0
22
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
—
1
0
1
1
0
0
0
0
1
0
1
1
1
23
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
—
0
0
0
0
0
0
0
1
0
0
0
0
24
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
−1
−1
0
0
0
—
1
1
1
0
1
1
1
1
1
1
1
25
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
0
−1
—
0
0
0
0
0
1
0
0
0
0
26
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
—
0
0
0
0
1
0
0
0
0
27
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
−1
0
−1
−1
0
0
0
−1
0
0
—
0
1
1
1
1
1
1
1
28
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
—
1
1
1
1
1
1
1
29
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
0
1
−1
0
−1
−1
0
0
0
−1
0
0
−1
−1
—
1
1
1
1
1
1
30
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
0
0
−1
0
0
−1
−1
−1
—
1
1
1
1
1
31
0
0
0
0
0
0
0
0
0
−1
0
0
0
−1
−1
1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
−1
—
0
0
0
0
32
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
0
0
−1
0
0
−1
−1
−1
−1
0
—
1
1
1
33
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
—
1
0
34
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
−1
—
0
35
0
0
0
0
0
0
0
0
0
−1
0
0
0
0
−1
1
−1
−1
−1
−1
0
−1
0
−1
0
0
−1
−1
−1
−1
0
−1
0
0
—Figure 1
The population of solutions.Figure 2
The elitism metric assignment for the population.


## 3.3. The Diversity Metric

As discussed before, diversity of solutions is another criterion for solutions obtained by the multiobjective genetic algorithm. In order to obtain uniformly distributed solutions, it is important to maintain the diversity of the population in the iteration process. Without this, solutions in the population tend to form relatively few clusters. This phenomenon is known asgenetic drift. Several approaches have been developed to maintain the diversity of solutions. Among them, the sharing function approach [19, 39] is one of the earliest approaches. The sharing function approach degrades the objective fitness of solutions by setting a threshold θshare. This threshold is still calledsharing parameter. For a solution xi in the current population, aniche countmi is first calculated. The niche count mi=1 if there is no solution in the θshare-niche (neighborhood) of xi (i.e., there is no solution whose distance with xi is less than θshare); the niche count mi>1 if there are some solutions in the θshare-niche (neighborhood) of xi (i.e., there are some solutions whose distances with xi) less than θshare. Then, the degradation is obtained through dividing the objective fitness by the niche count, that is, fi/mi. This proportion is called theshared fitness. The original NSGA [23] used the sharing function approach to maintain the diversity of solutions. The performance of the sharing function approach terribly depends on the sharing parameter θshare. However, θshare is a user-decided parameter and it is difficult to choose a proper one. Since each solution must be compared with all other solutions in the population, the overall complexity of the sharing function approach is O(MN2).Deb et al. [4] introduced the crowding distance approach to maintain the diversity of solutions. This approach calculates the density estimation of a solution by summarizing the average distance of two solutions on either side of this solution along each of the objective function. The density estimation, which is still called crowding distance, serves as an estimate of the perimeter of the cuboid formed by using the nearest neighbors as the vertices. Obviously, a solution with a smaller value of crowding distance is more crowded by other solutions. Thus, the crowding distance can be considered as a measure of the diversity of a solution. The crowding distance approach does not require any user-defined parameter. Its computational complexity is O(MNlog⁡N), which is better than the sharing function approach. However, the crowing distance just reflects the local diversity of a solution.The cell-based density approach [6, 26, 38, 40, 41] divides the objective space into p-dimensional cells. The number of solutions in each cell is defined as thedensity of the cell, and thedensity of a solution is equal to the density of the cell in which the solution locates. An efficient approach to dynamically divide the objective function space into cells is proposed by Lu and Yen [40, 41]. The main advantage of the cell-based density approach is that a global density map of the objective function value space can be obtained. But the process of the cell-based density approach is complicated. For a single solution, in the worst case, it requires O(LM) comparison to locate the solution into a proper cell, where L is the number of cells for each objective function. Thus, the total complexity of the cell-based density approach is O(LMN). And furthermore, L is a user-defined parameter which is not easy to be chosen properly.In this section, we define the metric about measuring the degree of crowdedness around a solution. Then, a specifical diversity metric is introduced.Definition 16.
Suppose thatP1 is a population, xi and xj are two solutions from P1, and ϕi and ϕj are two scalars corresponding to xi and xj, respectively. We call ϕi and ϕj thediversity metrics of xi and xj, respectively, if ϕi<ϕj implies that solutions around xj are more crowded than those around xi.Definition16 is just a qualitative description of the diversity metric. In the following, we introduce a specifical definition of the diversity metric which quantitatively measures the degree of crowdedness around a solution.Definition 17.
Suppose thatP1 is a population with N solutions, xi is a solution in P1. We provide a function ϕ:P1↦R+ as(31)ϕ(xi)=∑j=1,j≠iN‍β(dij),where β:R+↦R+ is a decrease function and dij is the Euclidean distance between solutions xi and xj. Then we call the value of ϕ(xi) theglobal diversity metric of xi.It is obvious that the global diversity metric is coincident with the definition of diversity metric. One improvement of the global diversity metric is that it reflects the diversity ofxi with respect to all the other solutions since the function ϕ involves the whole population. The requirement for calculating the global diversity metric is only the Euclidean distance between any two solutions, so the computational complexity of the global diversity metric is O((1/2)(N-1)2). A proper choice of function β is (32)β(d)=1-1Dd,where D=max⁡1≤i,j≤N⁡{dij}.As an example, Figure3 illustrates the global diversity metric of the population presented in Figure 1. From Figure 3, one can observe that these solutions which are less crowded enjoy smaller global diversity metrics, such as solutions x35 and x34 (the index of the solution can be found in Figure 1) with 7.1157 and 15.6234, respectively. On the contrary, these solutions which are more crowded have larger global diversity metrics, such as solutions x15, x17, and x21 with 19.3926, 29.3777, and 29.3826, respectively.Figure 3
The global diversity metric for the population.


## 3.4. A New Selection Operator

As discussed before, the core criteria for multiobjective optimization are to obtain solutions with better elitism and, at the same time, maintain the diversity of solutions. If we tackle these criteria from a multiobjective optimization point of view, we need to solve a multiobjective optimization problem with two objectives: minimizing the elitism metric and the global diversity metric of the solution. Noting the definition of the elitism metricθ(x) and the global diversity metric ϕ(x) presented in the previous subsections, we design the following multiobjective subproblem:(33)MinimizeH(x)Subjecttox∈P1,where H(x)=(θ(x),ϕ(x))T is a multiobjective function and P1⊂X is a population of candidate solutions. It is clear that the image of H(·)(34)H=θx,ϕxT∣x∈P1is a finite set whose cardinal is the same as P1. One property of the multiobjective subproblem (33) is that its domain P1 and image set H are finite; that is, the problem (33) is discrete. Thus, if we rank points in H by the optimum order method (Algorithm 8), it is reasonable to say that those points who have smaller optimal orders are better points; that is, solutions corresponding to these points should be maintained to the next generation. This process is summarized by the following algorithm.Algorithm 18 (multiobjective selection operator).
Consider the following steps.
Step  1. Input the selection pool P1 and its objective function values F(P1)={F(x)∣x∈P1}. Input the prefixed population size N (N is less than the cardinal of P1).
Step  2. Calculate the elitism metric and global diversity metric of the solution in P1 using the function (29) and (31), respectively. Let the result be (35)Θ=θx∣x∈P1,Φ=ϕ(x)∣x∈P1.
Step  3. Construct the objective function value space of the multiobjective subproblem (36)H=θx,ϕxT∣θx∈Θ,ϕx∈Φ.
Step  4. Rank points in H by the optimum order method (Algorithm 8) and take the first N solutions according to their optimal orders as parents for the next generation.In Table4, we use the multiobjective selection operator to evaluate the population presented in Figure 1. In this table, θi, ϕi, Ki, and σi represent the elitism metric, global diversity metric, total optimal number, and optimal order of solution xi, respectively. We can observe that the multiobjective selection operator systematically considers the criteria of elitism and diversity. We select 15 solutions whose optimal orders are the smallest as parents of the next generation. They are marked as red squares in Figure 4. However, from Figure 4, distribution of the selected points is not ideal. This is because there are some irregular distributed points, such as points 33, 34, and 35. They are far away from the others, which means that they should be eliminated. But because of their very small diversity metric, they are selected by the selection operator. In order to tackle this issue, we pretreat the diversity metric before running the selection operator.Table 4
The total optimal number and optimal order without pretreatment of the diversity metric.
x
i
θ
i
ϕ
i
K
i
σ
i
x
1
1
25.8013
59.0
1
x
2
1
26.5934
57.0
2
x
3
2
26.7268
47.5
5
x
4
2
27.7626
44.5
8
x
5
1
28.2829
49.0
4
x
6
3
28.0889
36.5
10
x
7
3
28.3563
33.5
17
x
8
1
28.6122
47.0
6
x
9
1
28.8617
45.0
7
x
10
1
28.8972
44.0
9
x
11
2
29.0363
33.5
18
x
12
3
29.0259
28.5
26
x
13
3
29.2131
24.5
28
x
14
2
29.2940
26.5
27
x
15
2
29.3926
21.5
30
x
16
1
29.3800
32.0
25
x
17
1
29.3777
33.0
20
x
18
3
29.4494
14.5
34
x
19
1
29.3475
34.0
16
x
20
1
29.2939
36.0
11
x
21
4
29.3826
12.0
35
x
22
4
29.2878
18.0
31
x
23
5
29.2419
15.5
33
x
24
2
29.0505
32.5
22
x
25
5
29.0794
17.5
32
x
26
5
28.7751
23.5
29
x
27
3
28.1192
35.5
12
x
28
1
27.8471
52.0
3
x
29
4
27.7568
35.0
14
x
30
5
27.4767
32.5
23
x
31
6
26.1417
32.5
24
x
32
6
22.9761
34.5
15
x
33
7
21.0339
33.5
19
x
34
8
15.6234
33.0
21
x
35
7
7.1157
35.5
13Figure 4
The selected point without pretreatment of the diversity metric.In sport matches, the statistician always eliminates the highest and the lowest marks before calculating the average. We borrow this idea to pretreat the diversity metric. We simply identify the10% points with the highest and lowest diversity metric and eliminate them before the running of selection operator. In the example, the 10% points with the highest and lowest diversity metrics are 14, 15, 16, and 18 and 32, 33, 34, and 35, respectively. Thus, we run the selection operator without considering them.Table5 presents the total optimal number and optimal order with pretreatment of the diversity metric. It can be observed that points 14–16, 18, and 32–35 are excluded in the ranking process. This gives more chance to some point close to the Pareto frontier. For example, points 24 and 30 (which were ranked as 22 and 23, resp.) were not selected without pretreatment of the diversity metric, but they are selected (ranked as 13 and 14, resp.) after considering the pretreatment of the diversity metric. From Figure 5, we can see that the selected points are now well distributed and closer to the Pareto frontier.Table 5
The total optimal number and optimal order with pretreatment of the diversity metric.
x
i
θ
i
ϕ
i
K
i
σ
i
x
1
1
25.8013
59.0
1
x
2
1
26.5934
57.0
2
x
3
2
26.7268
47.5
4
x
4
2
27.7626
44.5
6
x
5
1
28.2829
49.0
5
x
6
3
28.0889
36.5
15
x
7
3
28.3563
33.5
17
x
8
1
28.6122
47.0
7
x
9
1
28.8617
45.0
12
x
10
1
28.8972
44.0
8
x
11
2
29.0363
33.5
21
x
12
3
29.0259
28.5
24
x
13
3
29.2131
24.5
26
x
14
2
29.2940
—
—
x
15
2
29.3926
—
—
x
16
1
29.3800
—
—
x
17
1
29.3777
33.0
19
x
18
3
29.4494
—
—
x
19
1
29.3475
34.0
18
x
20
1
29.2939
36.0
10
x
21
4
29.3826
12.0
27
x
22
4
29.2878
18.0
22
x
23
5
29.2419
15.5
25
x
24
2
29.0505
32.5
13
x
25
5
29.0794
17.5
23
x
26
5
28.7751
23.5
20
x
27
3
28.1192
35.5
9
x
28
1
27.8471
52.0
3
x
29
4
27.7568
35.0
11
x
30
5
27.4767
32.5
14
x
31
6
26.1417
32.5
16
x
32
6
22.9761
—
—
x
33
7
21.0339
—
—
x
34
8
15.6234
—
—
x
35
7
7.1157
—
—Figure 5
The selected point with pretreatment of the diversity metric.


## 3.5. A New Multiobjective Genetic Algorithm

Given the multiobjective selection operator, we are now ready to propose a new multiobjective genetic algorithm.Algorithm 19 (optimum order multiobjective genetic algorithm (OOMOGA)).
Consider the following.(1)
Initialization
(1.1)
Generate the initial populationP(0).(1.2)
Set the crossover rate, mutation rate, and number of maximal generations.(1.3)
Lett←0.(2)
Since the number of maximal generations has not been reached, do the following.
(2.1)
Run the crossover operator: generate the offspringO1(t).(2.2)
Run the mutation operator: generate the offspringO2(t).(2.3)
Construct a selection poolS(t) by combining P(t), O1(t), and O2(t); that is, S(t)=P(t)∪O1(t)∪O2(t). Compute their multiobjective function values; that is, FS(t)={F(x)∣x∈S(t)}.(2.4)
Run the multiobjective selection operator (Algorithm18) by inputting S(t) and FS(t); the selected solutions are maintained as the parents of the next generation, that is, P(t+1).(2.5)
Lett←t+1; go to (2.1).EndEnd.


## 4. Numerical Experiments

In this section, we investigate the numerical performance of OOMOGA. In order to evaluate the numerical performance of solvers, we use the performance metricIGD proposed in [42]. Suppose that P* is a set of uniformly distributed points along the Pareto frontier (in the objective function value space). Let A be a set of solutions obtained by a certain solver. Then, the average distance from P* to A is defined as (37)IGD(A,P*)=∑v∈P*‍d(v,A)P*,where d(v,A) is the minimum Euclidean distance between v and the points in A; that is, (38)d(v,A)=min⁡y∈Av-y.In fact, P* represents a sample set of the real Pareto frontiers, if P* is large enough to approximate the Pareto frontier very well, IGD(A,P*) could measure both the diversity and convergence of A in a sense. A smaller IGD(A,P*) means the set A is closer to the real Pareto frontier and has better diversity.The referential algorithms are those submitted to the special session on performance assessment of unconstrained/bound constrained multiobjective optimization algorithms at CEC’09. There are13 algorithms submitted to the special session. They are listed as follows:(1)
MOEAD [43];(2)
GDE3 [44];(3)
MOEADGM [45];(4)
MTS [46];(5)
LiuLiAlgorithm [47];(6)
DMOEADD [48];(7)
NSGAIILS [49];(8)
OWMOSaDE [50];(9)
ClusteringMOEA [51];(10)
AMGA [52];(11)
MOEP [53];(12)
DECMOSA-SQP [54];(13)
OMOEAII [55].The benchmarks are taken from [42] which are still used in CEC’09. Figure 6 illustrates the objective function value space of these test problems (the figure of test problem 2 is ignored here since it is similar to that of the test problem 1); the red curve/surface represents their Pareto frontiers. Among these test problems, Problems 1–7 have two objective functions, whereas Problems 8–10 have three objective functions. The Pareto solutions of Problems 5, 6, and 9 are disconnected, while the others are connected.Figure 6
The objective function value space for test problems.In order to keep consistency with the final report of CEC’09 [56], in the implementation of OOMOGA, we set the population size as 100 for problems with two objectives and 150 for problems with three objectives; the number of function evaluations is less than 300,000. For each test instance, we run OOMOGA independently for 30 times. The numerical performance evaluated by IGD is illustrated in Table 6.Table 6
The numerical performance evaluated by IGD.
Rank
UF1
UF2
UF3
1
MOEAD
0.00435
OOMOGA
0.00527
MOEAD
0.00742
2
GDE3
0.00534
MTS
0.00615
LiuLiAlgorithm
0.01497
3
MOEADGM
0.0062
MOEADGM
0.0064
OOMOGA
0.0331
4
MTS
0.00646
DMOEADD
0.00679
DMOEADD
0.03337
5
LiuLiAlgorithm
0.00785
MOEAD
0.00679
MOEADGM
0.049
6
DMOEADD
0.01038
OWMOSaDE
0.0081
MTS
0.0531
7
NSGAIILS
0.01153
GDE3
0.01195
ClusteringMOEA
0.0549
8
OOMOGA
0.0118
LiuLiAlgorithm
0.0123
AMGA
0.06998
9
OWMOSaDE
0.0122
NSGAIILS
0.01237
DECMOSA-SQP
0.0935
10
ClusteringMOEA
0.0299
AMGA
0.01623
MOEP
0.099
11
AMGA
0.03588
MOEP
0.0189
OWMOSaDE
0.103
12
MOEP
0.0596
ClusteringMOEA
0.0228
NSGAIILS
0.10603
13
DECMOSA-SQP
0.07702
DECMOSA-SQP
0.02834
GDE3
0.10639
14
OMOEAII
0.08564
OMOEAII
0.03057
OMOEAII
0.27141
Rank
UF4
UF5
UF6
1
MTS
0.02356
MTS
0.01489
MOEAD
0.00587
2
GDE3
0.0265
GDE3
0.03928
MTS
0.05917
3
DECMOSA-SQP
0.03392
AMGA
0.09405
DMOEADD
0.06673
4
OOMOGA
0.0347
LiuLiAlgorithm
0.16186
OMOEAII
0.07338
5
AMGA
0.04062
DECMOSA-SQP
0.16713
ClusteringMOEA
0.0871
6
DMOEADD
0.04268
OMOEAII
0.1692
MOEP
0.1031
7
MOEP
0.0427
MOEAD
0.18071
DECMOSA-SQP
0.12604
8
LiuLiAlgorithm
0.0435
MOEP
0.2245
AMGA
0.12942
9
OMOEAII
0.04624
ClusteringMOEA
0.2473
OOMOGA
0.1411
10
MOEADGM
0.0476
DMOEADD
0.31454
LiuLiAlgorithm
0.17555
11
OWMOSaDE
0.0513
OWMOSaDE
0.4303
OWMOSaDE
0.1918
12
NSGAIILS
0.0584
NSGAIILS
0.5657
GDE3
0.25091
13
ClusteringMOEA
0.0585
OOMOGA
0.7695
NSGAIILS
0.31032
14
MOEAD
0.06385
MOEADGM
1.7919
MOEADGM
0.5563
Rank
UF7
UF8
UF9
1
MOEAD
0.00444
MOEAD
0.0584
DMOEADD
0.04896
2
LiuLiAlgorithm
0.0073
DMOEADD
0.06841
OOMOGA
0.0601
3
MOEADGM
0.0076
LiuLiAlgorithm
0.08235
NSGAIILS
0.0719
4
DMOEADD
0.01032
NSGAIILS
0.0863
MOEAD
0.07896
5
MOEP
0.0197
OWMOSaDE
0.0945
GDE3
0.08248
6
NSGAIILS
0.02132
MTS
0.11251
LiuLiAlgorithm
0.09391
7
ClusteringMOEA
0.0223
AMGA
0.17125
OWMOSaDE
0.0983
8
DECMOSA-SQP
0.02416
OMOEAII
0.192
MTS
0.11442
9
GDE3
0.02522
OOMOGA
0.2137
DECMOSA-SQP
0.14111
10
OMOEAII
0.03354
DECMOSA-SQP
0.21583
MOEADGM
0.1878
11
MTS
0.04079
ClusteringMOEA
0.2383
AMGA
0.18861
12
AMGA
0.05707
MOEADGM
0.2446
OMOEAII
0.23179
13
OWMOSaDE
0.0585
GDE3
0.24855
ClusteringMOEA
0.2934
14
OOMOGA
0.1267
MOEP
0.423
MOEP
0.342
Rank
UF10
1
MTS
0.15306
2
DMOEADD
0.32211
3
AMGA
0.32418
4
MOEP
0.3621
5
DECMOSA-SQP
0.36985
6
ClusteringMOEA
0.4111
7
GDE3
0.43326
8
LiuLiAlgorithm
0.44691
9
MOEAD
0.47415
10
MOEADGM
0.5646
11
OMOEAII
0.62754
12
OOMOGA
0.7269
13
OWMOSaDE
0.743
14
NSGAIILS
0.84468From Table6, the proposed solver OOMOGA performs the best at solving the test problem 2; its IGD evaluation is 0.00527, which is better than all the other solvers. In solving the test Problem 9, OOMOGA (whose IGD evaluation is 0.0601) performs only worse than DMOEADD (whose IGD evaluation is 0.4896) but better than all the other solvers. In solving the test Problem 3, the IGD evaluation of OOMOGA (0.0331) is ranked in the third position, worse than MOEAD (0.0072) and LiuLiAlgorithm (0.01497). In solving the test Problem 4, the IGD evaluation of OOMOGA (0.0347) is ranked in the fourth one, worse than MTS (0.02356), GDE3 (0.0265), and DECMOSA-SQP (0.03392). The numerical performance of OOMOGA is moderate in solving test Problems 1, 6, and 8; the IGD ranks are 8, 9, and 9, respectively. For test Problems 5 and 10, the numerical performance of the solver OOMOGA is not so good, ranking in 13 and 12, respectively. The worst performance of OOMOGA appears in solving the test Problem 7; the IGD evaluation is 0.1267, which is worse than all the other solvers.It is not uncommon that the numerical performance of the proposed solver OOMOGA is unstable among different test problems because the numerical results are not only affected by the performance of solvers, but also impacted by the linearity and structure of objective function themselves. Furthermore, the crossover and mutation operators are also affected by the distribution of points in the objective function value space. Generally speaking, if a new point generated by the crossover or mutation operators has a higher probability of locating around the Pareto frontier, then the Pareto frontier can be well approximated by the solver, for example, the test Problems 2, 3, and 4. On the contrary, if it is hard for the crossover or mutation operators to generate new point around the Pareto frontier, then the problem is difficult to be solved by MOGAs, for instance, the test Problems 5, 6, and 7. In fact, this instability still appears in the other solvers, such as MOEAD which is reported to be the best solver in [56]. The IGD evaluation of MOEAD in solving the test Problems 4, 5, and 10 is not very good, ranking in 14, 7, and 9, respectively.Figure7 demonstrates Pareto frontiers of test Problems 1, 2, 4, and 9, respectively. From Figures 7(a) and 7(b), we can observe that, for the test Problems 1 and 2, the proposed solver obtained very good representations of their Pareto frontiers. Results for the test Problem 4 (see Figure 7(c)) is not very uniformly distributed, which may affect the performance of IGD evaluation. Figure 7(d) illustrates the approximate Pareto frontier of the test Problem 9; we can see that the structure is more or less an approximation of the real Pareto frontier.Figure 7
The approximated Pareto frontier of Problems 1, 2, 4, and 9.
(a)
Problem 1
(b)
Problem 2
(c)
Problem 4
(d)
Problem 9


## 5. Conclusion

This paper proposed a solver based on genetic algorithm for multiobjective optimization. In the process of using genetic algorithm to solve multiobjective optimization, the evolutionary procedure prefers to select individuals with better elitism and diversity. Therefore, in the algorithm, we have to consider the trade-off between elitism and diversity. To tackle this issue, we first developed strategies to measure the elitism and diversity of populations. Then we used the proposed elitism and diversity metrics to construct a discrete multiobjective subproblem. Finally, the new selection operator is designed by applying the optimum order method to solve the multiobjective subproblem. We tested the proposed solver by the test instances used in CEC’09 and compared the numerical result with the referential solvers proposed in CEC’09. The numerical performance analysis shows that the proposed solver is good at solving problems whose objective function value space is high density around the Pareto frontier.We will further study this topic from the following two points of view.(i)
Improving the performance of crossover and mutation operators of the genetic algorithm: the crossover and mutation operators are very important for the diversity of solutions. However, the distribution of new individuals generated by the current crossover and mutation operators is coincident with the distribution of parents. This leads the excessive search of the “rich” area, but insufficient search of the “poor” area.(ii)
Introducing some more reasonable diversity metrics: it is very important to maintain the diversity of population in the evolutionary process of genetic algorithm. However, measuring diversity is not an easy task. The global diversity metric proposed in this paper is a proper diversity metric, but it is far from perfect.



---

*Source: 349781-2015-09-16.xml*