# An Improved SPEA2 Algorithm with Adaptive Selection of Evolutionary Operators Scheme for Multiobjective Optimization Problems

Authors: Fuqing Zhao; Wenchang Lei; Weimin Ma; Yang Liu; Chuck Zhang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A fixed evolutionary mechanism is usually adopted in the multiobjective evolutionary algorithms and their operators are static during the evolutionary process, which causes the algorithm not to fully exploit the search space and is easy to trap in local optima. In this paper, a SPEA2 algorithm which is based on adaptive selection evolution operators (AOSPEA) is proposed. The proposed algorithm can adaptively select simulated binary crossover, polynomial mutation, and differential evolution operator during the evolutionary process according to their contribution to the external archive. Meanwhile, the convergence performance of the proposed algorithm is analyzed with Markov chain. Simulation results on the standard benchmark functions reveal that the performance of the proposed algorithm outperforms the other classical multiobjective evolutionary algorithms.


---

## Body

## 1. Introduction

The multiobjective optimization problems (MOPs) [1] usually have more than two objectives. However, the evolutionary multiobjective optimization (EMO) researchers are only interested in the problems whose objectives are in conflict. For example, to produce a product, it not only requires short production time but also needs high quality. Those two objectives are in conflict.Because no single solution can simultaneously optimize all the objectives on the condition that these objectives are in conflict, therefore the purpose of the MOP is to achieve a group of Pareto optimal set and make it that the solutions distribution on the Pareto front has best possible approximation and uniformity. The traditional optimization algorithms can transform the multiobjective optimization problem into single objective problem with positive coefficient. The common weakness of the traditional algorithm is to produce single Pareto optima in a single run. However, the evolutionary algorithm is a population-based random search approach, which can generate a group of Pareto optimal solutions set in a single run and is very suitable for solving the MOPs. Since Schaffer [2] used multiobjective evolutionary algorithms (MOEAs) to solve MOPs, a variety of evolutionary algorithms have been developed. The characteristic of the first generation of MOEAs was using Pareto ranking to fitness assignment and making use of the niche or fitness sharing to maintain diversity. The representative algorithms contain nondominated sorting genetic algorithm (NSGA) [3], the multiobjective genetic algorithm (MOGA) [4], and the Niched Pareto genetic algorithm (NPGA) [5]. The feature of the second generation of MOEAs was whether the elitism is used or not. The classical algorithms are the Pareto archived evolution strategy (PAES) [6], the Pareto envelope based selection algorithm (PESA) [7] and its revised version PESA-II [8], the strength Pareto evolutionary algorithm (SPEA) [9] and its improved version SPEA2 [10], and the improved version of NSGA (NSGA-II) [11]. In recent years, some new frameworks of MOEAs have been proposed. The MOEA/D [12, 13] which combines traditional mathematical programming method with multiobjective evolutionary algorithm is one of the new frameworks. It shows high performance when solving MOPs with complicated PS shapes [14]. Meanwhile, many other nature-inspired metaheuristics including Ant Colony Optimization [15, 16], Particle Swarm Optimization [17, 18], Immune Algorithm [19, 20], and Estimation of Distribution Algorithm [21, 22] have been successfully applied to handle MOPs. Moreover, MOEAs for complicated MOPs have also been extensively investigated, such as MOEA for constraint MOPs [23], dynamic MOPs [24], and many objective optimization problems [25].SPEA2 is one of the second generation MOEAs. Bleuler et al. [26] considered the program size as a second, independent objective besides the program functionality and combined with SPEA2. Over the past decade, SPEA2 has been successfully combined with other optimization strategies to form improved SPEA2 algorithms. Kim et al. [27] added a more efficient crossover mechanism and an archive mechanism to maintain diversity of the solutions in the objective and variable spaces. Zheng et al. [28] combined SPEA2 with the parallel genetic algorithm (PGA) to obtain the final solution. Wu et al. [29] proposed a modified method of calculating fitness value based on SPEA2. A more reasonable strategy of elitism population selection is used to improve the distribution performance of the multiobjective optimization. Li et al. [30] combined several specific local search strategies with SPEA2 to enhance the algorithm’s exploiting capability. Belgasmi et al. [31] improved the performance of SPEA2 by adequately applying a multiobjective quasigradient local search to some candidate solutions that have lower density estimation. Al-Hajri and Abido [32] adopted truncation algorithms to manage the Pareto optimal set size. Meanwhile, the best compromise solution is extracted by using fuzzy set theory in SPEA2. Sheng et al. [33] present an Improved Strength Pareto Evolutionary Algorithm 2 (ISPEA2), which introduces a penalty factor in objective function constraints and adopts an adaptive crossover as well as a mutation operator in the evolutionary process; besides, it combines simulated annealing iterative process over SPEA2. Maheta and Dabhi [34] proposed the enhancements to improve convergence performance and diversity simultaneously for SPEA2. K-nearest neighbor density estimation technique is used to maintain diversity among solutions.Some researchers have shown that the operators are more suitable for certain types of problems but can not be available in the whole evolutionary process. For instance, simulated binary crossover (SBX) is widely used in MOEAs, but Deb [35] observed that SBX operator was unable to address problems with variable linkages. Therefore, an efficient evolutionary operator plays an important role in the evolutionary process of the optimization methods. And the operators have a great influence on the algorithms’ performance. Therefore, it is necessary to designate efficient operators for the MOEAs. At present, many efficient evolutionary operators are designed to enhance the performance of algorithms [36–39]. Pulido and Coello [40] introduced the best elected evolutionary operator to solve a given problem. A microgenetic algorithm called µGA2 is proposed, which runs several simultaneous instances of µGA2 with different evolutionary operators. Periodically, the instance with the poorest performance was replaced by the best performance ones after several generations. Thus, all the parallel instances only worked with the best performing operators after several generations. A disadvantage of this approach is that once an operator had been discarded, it could not be used again in the remaining evolutionary process. Huang et al. [41] utilized four different DE operators. Four operators were chosen in an adaptive way: the operator which contributed the most to the search was given a higher probability to create new solutions. Nebro et al. proposed two improved NSGA-II algorithms which are NSGA-IIr and NSGA-IIa [42]. NSGA-IIr is an extension of NSGA-II which employed three different evolutionary operators: the simulated binary crossover (SBX), polynomial mutation (PM), and DE. These operators are randomly selected when a new solution is to be produced. NSGA-IIa applies the same evolutionary operators as NSGA-II-r does; each operator selection probability is adjusted by considering operator success in the last iteration. And the algorithms’ performance has been greatly improved by making use of the adaptive way with evolutionary operators.In this paper, an improved SPEA2 algorithm with adaptive selection of evolutionary operators (AOSPEA) is proposed. Multiobjective evolutionary operators including the simulated binary crossover, polynomial mutation, and differential evolution operator are employed to enhance the convergence performance and diversity of the SPEA2. Simulation results on the standard benchmarks show that the proposed algorithm outperforms SPEA2, NSGA-II, and PESA-II.The rest of the paper is organized as follows: Section2 provides a brief description of SPEA2 framework. In Section 3, the main loop of AOSPEA, with a particularly detailed description and analysis of the proposed adaptive the selection of evolutionary operator’s scheme. The convergence and complexity analysis of AOSPEA are also presented in detail in this section. Section 4 describes the experimental results. Section 5 makes a conclusion.


## 2. Multiobjective Problems (MOPs)

### 2.1. The Description of Multiobjective Problems (MOPs)

As no single solution can optimize all the objectives at the same time on the condition that these objectives are in conflict, the solution of a MOPs is a set of decision variable vectors rather than a unique solution. Letxa,xb∈Ω be two decision vectors, xa is said to dominate xb (xa≻xb), if fi(xa)≤fi(xb) for all i=1,2,…,m, and Fxa≠Fxb. Besides, at least one objective function should satisfy fi(xa)<f(xb). A point x∗∈Ω is called Pareto optimal solution or nondominated solution if there is no x∈Ω such that Fx dominates Fx∗. The set of all the Pareto optimal solutions is called the Pareto set, denoted by PS. The set of all the Pareto optimal objective vectors, PF={F(x∗)∣x∗∈PS}, is called the Pareto front. It is impossible to find entire PS of continuous MOPs; the purpose is aiming at finding a finite set of Pareto optimal vectors which are uniformly scattered along the true PF and highly representative of the entire PF.In general, the Multiobjective Problems can be illustrated mathematically as follows:(1)min/max⁡y=Fx=f1x,f2x,…,fnxsubto:giX≤0,i=1,2,…,k1giX=0,i=k1+1,…,k2,where:x=x1,x2,…,xj∈X,y=y1,y2,…,yt∈Y.In the equation,x is the decision vector and X is the decision space. y is the objective vector and Y is the objective space. The most difficult reason to treat the Multiobjective Problems is that each Objective fi(x) is related, restrained, and even conflicted with each other. And in every MOPs, there are different objectives to confine the results.


### 2.2. Pareto Dominance

Vectory=(y1,y2,…,yk) is said to Pareto dominate another vector z=(z1,z2,…,zk) if and only if ∀j∈1,…,k,  yi≥zj  ∃j∈1,…k,  y>zj.Definition 1 (Pareto optimal point).
A vectorz∈Z is said to be Pareto optimal (in Z) if and only if  ¬∃y∈Z, y≻z.Definition 2 (Pareto front).
The Pareto front, denoted byZ∗, of a set Z is given by {z∈Z∣¬∃y∈Z,y≻z}.Definition 3 (general MOPs).
A general MOPs is defined as minimizing (or maximizing)F(x)=(f1(x),f2(x),…,fk(x)) subject to gi(x)≤0, i={1,2,…,m}, and hj(x)=0, j=1,2,…,p, x∈Ω. A MOPs solution minimizes (or maximizes) the components of a vector F(x) where x is a n-dimensional decision variable vector x=(x1,x2,…,xn) from some universe Ω. It is noted that gi(x)≤0 and hj(x)=0 represent constraints that must be fulfilled while minimizing (or maximizing) F(x) and Ω contains all possible x that can be used to satisfy an evaluation of F(x). Thus, MOPs consist of k objectives reflected in the k objective functions, m + p constraints on the objective functions, and n decision variables. The k objective functions may be linear or nonlinear and continuous or discrete in nature. The evaluation function, F:Ω→Δ, is a mapping from the vector of decision variables (x=x1,x2,…,xn) to output vectors (y=a1,a2,…,ak). The vector of decision variables xi can also be continuous or discrete.


## 2.1. The Description of Multiobjective Problems (MOPs)

As no single solution can optimize all the objectives at the same time on the condition that these objectives are in conflict, the solution of a MOPs is a set of decision variable vectors rather than a unique solution. Letxa,xb∈Ω be two decision vectors, xa is said to dominate xb (xa≻xb), if fi(xa)≤fi(xb) for all i=1,2,…,m, and Fxa≠Fxb. Besides, at least one objective function should satisfy fi(xa)<f(xb). A point x∗∈Ω is called Pareto optimal solution or nondominated solution if there is no x∈Ω such that Fx dominates Fx∗. The set of all the Pareto optimal solutions is called the Pareto set, denoted by PS. The set of all the Pareto optimal objective vectors, PF={F(x∗)∣x∗∈PS}, is called the Pareto front. It is impossible to find entire PS of continuous MOPs; the purpose is aiming at finding a finite set of Pareto optimal vectors which are uniformly scattered along the true PF and highly representative of the entire PF.In general, the Multiobjective Problems can be illustrated mathematically as follows:(1)min/max⁡y=Fx=f1x,f2x,…,fnxsubto:giX≤0,i=1,2,…,k1giX=0,i=k1+1,…,k2,where:x=x1,x2,…,xj∈X,y=y1,y2,…,yt∈Y.In the equation,x is the decision vector and X is the decision space. y is the objective vector and Y is the objective space. The most difficult reason to treat the Multiobjective Problems is that each Objective fi(x) is related, restrained, and even conflicted with each other. And in every MOPs, there are different objectives to confine the results.


## 2.2. Pareto Dominance

Vectory=(y1,y2,…,yk) is said to Pareto dominate another vector z=(z1,z2,…,zk) if and only if ∀j∈1,…,k,  yi≥zj  ∃j∈1,…k,  y>zj.Definition 1 (Pareto optimal point).
A vectorz∈Z is said to be Pareto optimal (in Z) if and only if  ¬∃y∈Z, y≻z.Definition 2 (Pareto front).
The Pareto front, denoted byZ∗, of a set Z is given by {z∈Z∣¬∃y∈Z,y≻z}.Definition 3 (general MOPs).
A general MOPs is defined as minimizing (or maximizing)F(x)=(f1(x),f2(x),…,fk(x)) subject to gi(x)≤0, i={1,2,…,m}, and hj(x)=0, j=1,2,…,p, x∈Ω. A MOPs solution minimizes (or maximizes) the components of a vector F(x) where x is a n-dimensional decision variable vector x=(x1,x2,…,xn) from some universe Ω. It is noted that gi(x)≤0 and hj(x)=0 represent constraints that must be fulfilled while minimizing (or maximizing) F(x) and Ω contains all possible x that can be used to satisfy an evaluation of F(x). Thus, MOPs consist of k objectives reflected in the k objective functions, m + p constraints on the objective functions, and n decision variables. The k objective functions may be linear or nonlinear and continuous or discrete in nature. The evaluation function, F:Ω→Δ, is a mapping from the vector of decision variables (x=x1,x2,…,xn) to output vectors (y=a1,a2,…,ak). The vector of decision variables xi can also be continuous or discrete.


## 3. The Improved SPEA2 Algorithm with Adaptive Selection of Evolutionary Operators Scheme (AOSPEA)

### 3.1. Brief Introduction to SPEA2

SPEA2 is an improved version of the Strength Pareto Evolutionary Algorithm (SPEA). Compared with SPEA, a fine-grained fitness assignment strategy which incorporates density information is employed in SPEA2. The fixed archive size is adopted, that is, whenever the number of nondominated individuals is less than the predefined archive size, the archive is filled up by dominated individuals. Moreover, an alternative truncation method is used to replace the clustering technique in original SPEA but does not loose boundary points, which can guarantee the preservation of boundary solution. Finally, SPEA2 only makes members of the archive participate in the mating selection process. The procedure of the SPEA2 is as follows.SPEA2 Algorithm Input:
Ne: population size N: archive size T: maximum number of generations. Output: NDS: nondominated set.Step 1 (initialization). Generate an initial population P(0) and create an empty archive (external archive) A(0). Set t=0.Step 2 (fitness assignment). Calculate fitness values of individuals in P(t) and A(t).Step 3 (environment selection). Copy all nondominated individuals in P(t) and A(t) to A(t+1). If size of A(t+1) exceeds N then reduce A(t+1) by means of the truncation operator; otherwise if size of A(t+1) is less than N then fill A(t+1) with dominated individuals in P(t) and A(t).Step 4 (termination). If t>T is satisfied, then stop and output NDS. Otherwise, continue.Step 5 (mating selection). Perform binary tournament selection with replacement on A(t+1) in order to fill mating pool. The size of mating pool is Ne.Step 6 (reproduction). Apply recombination and mutation operators to the mating pool P(t+1) to the resulting population. Set t=t+1; go to Step 2.


### 3.2. The Evolutionary Operators Used in the AOSPEA

Due to the fixed evolutionary operator in the SPEA2 algorithm, it is easy to trap into local optima. The single operator can hardly meet the whole evolutionary process and different operators in the stage should be designed according to their contribution. Therefore, three different evolutionary operators including DE operator [43], the simulated binary crossover (SBX) operator [44], and PM operator [45] are employed to improve the performance of SPEA2. The description of different operators is as follows.(1) DE Operator. Differential evolution (DE) has three processes including mutation, crossover, and selection. DE owns good global search ability [46] and makes use of the differences between randomly selected vectors (individuals) as the source of evolutionary dynamics. Besides, DE can control the evolutionary variation similar to the concept jump in neighborhood search by adding weighted vectors to the target vector properly. Therefore, DE operators are adopted in SPEA2. It can efficiently improve the convergence and the exploration ability of the SPEA2. The procedure of DE operators is displayed as follows.DE Operator Input:Ne: population size, population P(t). Output: A new individual xi.Step 1. Randomly select three different individuals xr1,t, xr2,t, and xr3,t; they cannot dominate each other from P(t).Step 2 (mutation operator). Produce the mutation individual vi,t+1=vi,1,vi,2,…,vi,j,…,vi,D; D is the number of dimensions with (4):(2)vi,t+1=xr1,t+F∗xr2,t-xr3,t,where F is the scale factor; F∈[0,2].Step 3 (crossover operator). Produce the new individual xi with (6):(3)xij,t+1=vij,t+1,ifrandj≤CRorj=jrandxij,t,ifrandj>CRorj≠jrand,where CR is a crossover rate, rand(j) is a uniformly distributed random number between 0 and 1, and jrand is randomly selected from {1,2,…,D}.DE operator employs the relative position of nondominated solutions to produce the evolutionary direction of the ideal Pareto front and the new search space. Figure1 describes the theory of the DE operator, where xi is the offspring individual. It can be seen from Figure 1(a) that DE operator employs the relative position of nondominated individual in neighborhood to produce the offspring individual close to ideal Pareto front. Figure 1(b) expresses that DE operator can obtain more broad offspring.Figure 1
The theory of DE operator.
(a) (b)(2) SBX Operator. One of the three operators is provided by the SBX operator which performs local search combined with random search near the recombination parents. Unlike other real-parameter crossover operators, SBX uses a probability distribution which is similar in principle to the probability of creating children solution in crossover operators used in binary-coded GA. SBX operator possesses strong local search ability and maintains the diversity of the population. So it can maintain the distribution of the solution. The procedure of SBX operator is displayed as follows.SBX Operator Input:Ne: population size, population P(t). Output: Two new individual yi1 and yi2.Step 1. Randomly select two different individuals x1=(x11,x21,…,xD1) and x2=(x12,x22,…,xD2) from P(t).Step 2 (SBX operator). Produce the new individual yi,t+1=yi,1,yi,2,…,yi,j,…,yi,D; D is the number of dimensions with (7):(4)yi1=0.5×1+βixi1+1-βixi2,yi2=0.5×1-βixi1+1+βixi2,where (5)βi=2ui1/ηc+1,ifui≤0.5121-ui1/ηc+1,otherwisewhich is called spread factor; ui is a uniformly distributed random number between 0 and 1.The probability distribution of the spread factor is as follows:(6)pβi=0.5ηc+1βiηc,ifβi≤10.5ηc+11βiηc+2,otherwise,where ηc is the distribution index which determines the shape of the distribution.(3) PM Operator. PM operator attempts to simulate the offspring distribution of binary-encoded bit-flip mutation on real-valued decision variables. PM operator is of benefit to maintain the diversity of the population and efficiently explore the solution space. Figure 2 displays the theory of PM operator. It can be seen from Figure 2 that PM can obtain more broad offspring individuals. Meanwhile, compared with linear mutation, the offspring individuals produced by PM are close to ideal Pareto set. The procedure of PM operator is displayed as follows.Figure 2
The theory of PM operator.PM Operator Input: An individual xi, the upper bound xUB,i, and the lower bound xLB,i of the ith decision variable. Output: A new individual yi.Step 1 (PM operator). Produce the new individual yi,t+1=yi,1,yi,2,…,yi,j,…,yi,D; D is the number of dimensions with (9):(7)yi=xi+xUB,i-xLB,i×δ,where the probability distribution of δ is p(δ)=0.5(ηm+1)(1-δ)ηm and ηm is the distribution index which determines the shape of the distribution. δ can be calculated as follows:(8)δu=2u1/ηm+1-1ifu<0.51-21-u1/ηm+1ifu≥0.5.


### 3.3. Adaptive Selection of Evolutionary Operators Scheme

AOSPEA makes use of three evolutionary operators including SBX, PM, and DE. The selection probability of each operator is a third in the first generation. In the following generations, the selection probability is assigned in an adaptive way. Assuming that the number of solutions in the external archive is total and the number of solutions in the external archive produced by SBX, PM, and DE is noSBX, noPM, and noDE, respectively, the contribution of each operator can be calculated as follows:(9)contriSBX=noSBXtotal,contriPM=noPMtotal,contriDE=noDEtotal.In order to avoid any operator to be discarded when producing no solutions in one generation, a minimum selection probability is set. The rest probability is assigned according to their contribution to the external archive. Assuming that the minimum selection probability is Thres, the selection probability of SBX is PSB, the selection probability of PM is PM, and the selection probability of DE is PD, and their selection probability can be calculated as follows:(10)PSB=Thres+1-3∗Thres∗contriSBX,PM=Thres+1-3∗Thres∗contriPM,PD=Thres+1-3∗Thres∗contriDE.The algorithm chooses corresponding evolutionary operator to generate offspring according to their selection probability. Rand is a uniformly distributed random number between 0 and 1. Ifrand≤PSB, the algorithm chooses SBX to generate new solutions. If PS<rand≤PSB+PM, the algorithm selects PM to produce new solutions. Otherwise, the algorithm chooses DE to generate new solutions.


### 3.4. The Proposed Algorithm (AOSPEA)

According to the above descriptions of the simulated binary crossover, polynomial mutation, and differential evolution operator, SPEA2, and adaptive selection of evolutionary operators’ scheme, an improved SPEA2 algorithm with adaptive selection of evolutionary operators scheme (AOSPEA) is proposed. The procedure is shown as follows. And Figure3 gives the flowchart of the AOSPEA.Figure 3
Flowchart of AOSPEA.AOSPEA Algorithm Input:
Ne: population size N: archive size T: maximum number of generations. Output: NDS: nondominated set.Step 1 (initialization). Generate an initial population P(0) and create an empty archive (external archive) A(0). Set t=0.Step 2 (fitness assignment). Calculate fitness values of individuals in P(t) and A(t).Step 3 (environment selection). Copy all nondominated individuals in P(t) and A(t) to A(t+1). If size of A(t+1) exceeds N then reduce A(t+1) by means of the truncation operator; otherwise if size of A(t+1) is less than N then fill A(t+1) with dominated individuals in P(t) and A(t).Step 4 (termination). If t>T is satisfied, then stop and output NDS. Otherwise, continue.Step 5 (mating selection). Perform binary tournament selection with replacement on A(t+1) in order to fill mating pool. The size of mating pool is Ne.Step 6 (reproduction). If t=0, randomly select SBX, PM, and DE to generate individuals in P(t+1); if t>1, assign minimum selection probability to all the operators and then assign the rest probability according to their contribution to the external archive. Set t=t+1; go to Step 2.


### 3.5. Convergence Analysis

For multiobjective optimization with infinite optimal Pareto solutions, the evolutionary algorithms based on finite population cannot obtain all Pareto solutions. Therefore, the target of multiobjective optimization algorithms is to obtain a subset of ideal Pareto set and make the subset distribute as broadly and uniformly as possible. We employ finite Markov chain to prove that AOSPEA algorithm asymptotically converges to the ideal Pareto set with probability 1.Definition 4.
IfS is a finite set, a random sequence {Xt,t=0,1,2,3,…} is from S. And if all t≥0, {i,j} belongs to S×S, there will exist(11)PXt=1Xt=i,Xt-1=it-1,…,X0=i0=PXt=1Xt=i=pij;the sequence {Xt,t=0,1,2,…} can be called a homogeneous finite Markov chain with state space S. The homogeneous finite Markov chain has the property that the current status now corresponds with the status for previous time.Definition 5.
LetTm:SN→S denote the mutation in DE operator and its probability distribution can be described with (13):(12)PTmX=vi=∑xr1,xr2,xr3∈S3PTm1X=xr1,xr2,xr3,F.Definition 6.
LetTc:S2→S denote crossover in DE operator and its probability distribution can be described with (14), in which k is the number of crossovers:(13)PTcxi,vi=ηi=CDkCRk1-CRD-k,k=1,2,3,…,D.Definition 7.
LetTSBX:SN→S denote SBX crossover and its probability distribution can be described with (15),(14)PTSBXX,β=yi=∑xr1,xr2∈S2PTSBXX=xr1,xr2×β.Definition 8.
LetTPM:SN→S denote PM crossover and its probability distribution can be described with (16):(15)PTPMxi,xi,UB,xi,LB,δ=yi=δ.Definition 9.
The transfer matrix of the homogeneous finite Markov chain is irreducible. If(16)pijk>0,∀i,j∈S,S∈Tm,Tc,TSBX,TPM,k∈1,2,…,where pij(k) denotes the probability from the status i to the status j though k steps.Definition 10 (see [47]).
If a matrixA=aijn×m, there exists aij>0, i=0,1,…,n; j=0,1,…,m; A is the positive matrix.Lemma 11 (see [48]).
A Markov chain which has finite space and irreducible transition matrix will infinitely visit any state inS and is not relevant to the initial distribution probability 1.Theorem 12.
The population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is homogeneous and nonperiodic Markov chain with positive transition matrix.Proof.
In AOSPEA algorithm, the state setS∈Tm,Tc,TSBX,TPM is a finite set. The population sequence of the proposed algorithm can be shown as follows:(17)Xt→MSBX,MPM,MDEXt+1=TXt=aTmXt+TcXt+bTSBXXt+cTPMXt,where a, b, and c which satisfy a+b+c=1 denote the selection probability by DE, SBX, PM, and DE. MSBX, MPM, and MDE represent the transition matrix of SBX, PM, and DE, respectively. Tc, Tm, TSBX, and TPM are not relevant to the time t. Therefore, it can be concluded from Definition 4 that {Xt,t=0,1,2,…} can be described as Markov chain in finite state set S.
The evolution process of AOSPEA can be described asXt⟶PXt+1; that is, Xt+1=Xt×P=Xt×MSBX×MPM×MDE; the transition matrix of the population sequence P=MSBX×MPM×MDE, where there exist P(Tm(X)=vi)>0, P(Tc(xi,vi)=ηi)>0, P(TSBX(X,β)=yi)>0, and P(TPM(xi,xi,UB,xi,LB,δ)=yi)>0, MSBX, MPM, and MDE are positive transition matrix. Therefore, P=MSBX×MPM×MDE is positive matrix. Therefore, {Xt,t=0,1,2,…} is homogeneous and nonperiodic Markov chain with positive transition matrix.Theorem 13.
The population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is asymptotically converged to a subset of the Pareto set with probability 1.Proof.
PS is defined to the ideal Pareto set for multiobjective problem. The population sequence{Xt,t=0,1,2,…} of AOSPEA is converged to any subset of PS with probability 1; that is to say, when t→+∞, for any elementa in Xt, there exists a∈PS.
We supposea∉PS, so there exists a Pareto optimal solutionb in PS, which satisfies thatb dominatesa. Definition 4 has demonstrated that {Xt,t=0,1,2,…} is homogeneous and nonperiodic Markov chain, and the transition matrix  P is the positive matrix. Due to the positive matrix P, P is irreducible from Definition 9. Therefore, it can be concluded from Lemma 11 that {Xt,t=0,1,2,…} visits any state in S∈Tm,Tc,TSBX,TPM and is not relevant to the initial distribution with probability 1. Thereupon, when t→+∞, the Pareto optimal solutionb appears in Xt with probability 1. Since AOSPEA only retain the Pareto optima,a will be obsoleted byb, which contradicted to the prior assumption.
Therefore, the population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is gradually converged to a subset of the Pareto set with probability 1.


### 3.6. Computational Complexity

The algorithm mainly includes fitness assignment, environment selection, and evolutionary operation according to the algorithm process. Assuming that the size of the population isN, the size of external archive is N-, the number of objectives ism, the number of generations isT, and the dimension of decision variable isD, the time complexity of one generation for the algorithm can be calculated as follows: the time complexity for fitness assignment is O(M2log⁡M)+O(M2)+O(M2), where M=N+N-; the time complexity for calculating objective values is O(Nm), and the worst time complexity for environment selection is O(M3). The evolutionary operation includes SBX, PM, and DE operation. Assuming that the proportion of them are a, b, and c (a+b+c=1), respectively, the time complexity of the total evolutionary operation is O((a+b+c)ND)=O(ND). The worst total time complexity of one generation is(18)OM2log⁡M+OM2+OM2+ONm+OM3+OND=OM3.So the worst total time complexity is O(TM3) in T generations.


## 3.1. Brief Introduction to SPEA2

SPEA2 is an improved version of the Strength Pareto Evolutionary Algorithm (SPEA). Compared with SPEA, a fine-grained fitness assignment strategy which incorporates density information is employed in SPEA2. The fixed archive size is adopted, that is, whenever the number of nondominated individuals is less than the predefined archive size, the archive is filled up by dominated individuals. Moreover, an alternative truncation method is used to replace the clustering technique in original SPEA but does not loose boundary points, which can guarantee the preservation of boundary solution. Finally, SPEA2 only makes members of the archive participate in the mating selection process. The procedure of the SPEA2 is as follows.SPEA2 Algorithm Input:
Ne: population size N: archive size T: maximum number of generations. Output: NDS: nondominated set.Step 1 (initialization). Generate an initial population P(0) and create an empty archive (external archive) A(0). Set t=0.Step 2 (fitness assignment). Calculate fitness values of individuals in P(t) and A(t).Step 3 (environment selection). Copy all nondominated individuals in P(t) and A(t) to A(t+1). If size of A(t+1) exceeds N then reduce A(t+1) by means of the truncation operator; otherwise if size of A(t+1) is less than N then fill A(t+1) with dominated individuals in P(t) and A(t).Step 4 (termination). If t>T is satisfied, then stop and output NDS. Otherwise, continue.Step 5 (mating selection). Perform binary tournament selection with replacement on A(t+1) in order to fill mating pool. The size of mating pool is Ne.Step 6 (reproduction). Apply recombination and mutation operators to the mating pool P(t+1) to the resulting population. Set t=t+1; go to Step 2.


## 3.2. The Evolutionary Operators Used in the AOSPEA

Due to the fixed evolutionary operator in the SPEA2 algorithm, it is easy to trap into local optima. The single operator can hardly meet the whole evolutionary process and different operators in the stage should be designed according to their contribution. Therefore, three different evolutionary operators including DE operator [43], the simulated binary crossover (SBX) operator [44], and PM operator [45] are employed to improve the performance of SPEA2. The description of different operators is as follows.(1) DE Operator. Differential evolution (DE) has three processes including mutation, crossover, and selection. DE owns good global search ability [46] and makes use of the differences between randomly selected vectors (individuals) as the source of evolutionary dynamics. Besides, DE can control the evolutionary variation similar to the concept jump in neighborhood search by adding weighted vectors to the target vector properly. Therefore, DE operators are adopted in SPEA2. It can efficiently improve the convergence and the exploration ability of the SPEA2. The procedure of DE operators is displayed as follows.DE Operator Input:Ne: population size, population P(t). Output: A new individual xi.Step 1. Randomly select three different individuals xr1,t, xr2,t, and xr3,t; they cannot dominate each other from P(t).Step 2 (mutation operator). Produce the mutation individual vi,t+1=vi,1,vi,2,…,vi,j,…,vi,D; D is the number of dimensions with (4):(2)vi,t+1=xr1,t+F∗xr2,t-xr3,t,where F is the scale factor; F∈[0,2].Step 3 (crossover operator). Produce the new individual xi with (6):(3)xij,t+1=vij,t+1,ifrandj≤CRorj=jrandxij,t,ifrandj>CRorj≠jrand,where CR is a crossover rate, rand(j) is a uniformly distributed random number between 0 and 1, and jrand is randomly selected from {1,2,…,D}.DE operator employs the relative position of nondominated solutions to produce the evolutionary direction of the ideal Pareto front and the new search space. Figure1 describes the theory of the DE operator, where xi is the offspring individual. It can be seen from Figure 1(a) that DE operator employs the relative position of nondominated individual in neighborhood to produce the offspring individual close to ideal Pareto front. Figure 1(b) expresses that DE operator can obtain more broad offspring.Figure 1
The theory of DE operator.
(a) (b)(2) SBX Operator. One of the three operators is provided by the SBX operator which performs local search combined with random search near the recombination parents. Unlike other real-parameter crossover operators, SBX uses a probability distribution which is similar in principle to the probability of creating children solution in crossover operators used in binary-coded GA. SBX operator possesses strong local search ability and maintains the diversity of the population. So it can maintain the distribution of the solution. The procedure of SBX operator is displayed as follows.SBX Operator Input:Ne: population size, population P(t). Output: Two new individual yi1 and yi2.Step 1. Randomly select two different individuals x1=(x11,x21,…,xD1) and x2=(x12,x22,…,xD2) from P(t).Step 2 (SBX operator). Produce the new individual yi,t+1=yi,1,yi,2,…,yi,j,…,yi,D; D is the number of dimensions with (7):(4)yi1=0.5×1+βixi1+1-βixi2,yi2=0.5×1-βixi1+1+βixi2,where (5)βi=2ui1/ηc+1,ifui≤0.5121-ui1/ηc+1,otherwisewhich is called spread factor; ui is a uniformly distributed random number between 0 and 1.The probability distribution of the spread factor is as follows:(6)pβi=0.5ηc+1βiηc,ifβi≤10.5ηc+11βiηc+2,otherwise,where ηc is the distribution index which determines the shape of the distribution.(3) PM Operator. PM operator attempts to simulate the offspring distribution of binary-encoded bit-flip mutation on real-valued decision variables. PM operator is of benefit to maintain the diversity of the population and efficiently explore the solution space. Figure 2 displays the theory of PM operator. It can be seen from Figure 2 that PM can obtain more broad offspring individuals. Meanwhile, compared with linear mutation, the offspring individuals produced by PM are close to ideal Pareto set. The procedure of PM operator is displayed as follows.Figure 2
The theory of PM operator.PM Operator Input: An individual xi, the upper bound xUB,i, and the lower bound xLB,i of the ith decision variable. Output: A new individual yi.Step 1 (PM operator). Produce the new individual yi,t+1=yi,1,yi,2,…,yi,j,…,yi,D; D is the number of dimensions with (9):(7)yi=xi+xUB,i-xLB,i×δ,where the probability distribution of δ is p(δ)=0.5(ηm+1)(1-δ)ηm and ηm is the distribution index which determines the shape of the distribution. δ can be calculated as follows:(8)δu=2u1/ηm+1-1ifu<0.51-21-u1/ηm+1ifu≥0.5.


## 3.3. Adaptive Selection of Evolutionary Operators Scheme

AOSPEA makes use of three evolutionary operators including SBX, PM, and DE. The selection probability of each operator is a third in the first generation. In the following generations, the selection probability is assigned in an adaptive way. Assuming that the number of solutions in the external archive is total and the number of solutions in the external archive produced by SBX, PM, and DE is noSBX, noPM, and noDE, respectively, the contribution of each operator can be calculated as follows:(9)contriSBX=noSBXtotal,contriPM=noPMtotal,contriDE=noDEtotal.In order to avoid any operator to be discarded when producing no solutions in one generation, a minimum selection probability is set. The rest probability is assigned according to their contribution to the external archive. Assuming that the minimum selection probability is Thres, the selection probability of SBX is PSB, the selection probability of PM is PM, and the selection probability of DE is PD, and their selection probability can be calculated as follows:(10)PSB=Thres+1-3∗Thres∗contriSBX,PM=Thres+1-3∗Thres∗contriPM,PD=Thres+1-3∗Thres∗contriDE.The algorithm chooses corresponding evolutionary operator to generate offspring according to their selection probability. Rand is a uniformly distributed random number between 0 and 1. Ifrand≤PSB, the algorithm chooses SBX to generate new solutions. If PS<rand≤PSB+PM, the algorithm selects PM to produce new solutions. Otherwise, the algorithm chooses DE to generate new solutions.


## 3.4. The Proposed Algorithm (AOSPEA)

According to the above descriptions of the simulated binary crossover, polynomial mutation, and differential evolution operator, SPEA2, and adaptive selection of evolutionary operators’ scheme, an improved SPEA2 algorithm with adaptive selection of evolutionary operators scheme (AOSPEA) is proposed. The procedure is shown as follows. And Figure3 gives the flowchart of the AOSPEA.Figure 3
Flowchart of AOSPEA.AOSPEA Algorithm Input:
Ne: population size N: archive size T: maximum number of generations. Output: NDS: nondominated set.Step 1 (initialization). Generate an initial population P(0) and create an empty archive (external archive) A(0). Set t=0.Step 2 (fitness assignment). Calculate fitness values of individuals in P(t) and A(t).Step 3 (environment selection). Copy all nondominated individuals in P(t) and A(t) to A(t+1). If size of A(t+1) exceeds N then reduce A(t+1) by means of the truncation operator; otherwise if size of A(t+1) is less than N then fill A(t+1) with dominated individuals in P(t) and A(t).Step 4 (termination). If t>T is satisfied, then stop and output NDS. Otherwise, continue.Step 5 (mating selection). Perform binary tournament selection with replacement on A(t+1) in order to fill mating pool. The size of mating pool is Ne.Step 6 (reproduction). If t=0, randomly select SBX, PM, and DE to generate individuals in P(t+1); if t>1, assign minimum selection probability to all the operators and then assign the rest probability according to their contribution to the external archive. Set t=t+1; go to Step 2.


## 3.5. Convergence Analysis

For multiobjective optimization with infinite optimal Pareto solutions, the evolutionary algorithms based on finite population cannot obtain all Pareto solutions. Therefore, the target of multiobjective optimization algorithms is to obtain a subset of ideal Pareto set and make the subset distribute as broadly and uniformly as possible. We employ finite Markov chain to prove that AOSPEA algorithm asymptotically converges to the ideal Pareto set with probability 1.Definition 4.
IfS is a finite set, a random sequence {Xt,t=0,1,2,3,…} is from S. And if all t≥0, {i,j} belongs to S×S, there will exist(11)PXt=1Xt=i,Xt-1=it-1,…,X0=i0=PXt=1Xt=i=pij;the sequence {Xt,t=0,1,2,…} can be called a homogeneous finite Markov chain with state space S. The homogeneous finite Markov chain has the property that the current status now corresponds with the status for previous time.Definition 5.
LetTm:SN→S denote the mutation in DE operator and its probability distribution can be described with (13):(12)PTmX=vi=∑xr1,xr2,xr3∈S3PTm1X=xr1,xr2,xr3,F.Definition 6.
LetTc:S2→S denote crossover in DE operator and its probability distribution can be described with (14), in which k is the number of crossovers:(13)PTcxi,vi=ηi=CDkCRk1-CRD-k,k=1,2,3,…,D.Definition 7.
LetTSBX:SN→S denote SBX crossover and its probability distribution can be described with (15),(14)PTSBXX,β=yi=∑xr1,xr2∈S2PTSBXX=xr1,xr2×β.Definition 8.
LetTPM:SN→S denote PM crossover and its probability distribution can be described with (16):(15)PTPMxi,xi,UB,xi,LB,δ=yi=δ.Definition 9.
The transfer matrix of the homogeneous finite Markov chain is irreducible. If(16)pijk>0,∀i,j∈S,S∈Tm,Tc,TSBX,TPM,k∈1,2,…,where pij(k) denotes the probability from the status i to the status j though k steps.Definition 10 (see [47]).
If a matrixA=aijn×m, there exists aij>0, i=0,1,…,n; j=0,1,…,m; A is the positive matrix.Lemma 11 (see [48]).
A Markov chain which has finite space and irreducible transition matrix will infinitely visit any state inS and is not relevant to the initial distribution probability 1.Theorem 12.
The population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is homogeneous and nonperiodic Markov chain with positive transition matrix.Proof.
In AOSPEA algorithm, the state setS∈Tm,Tc,TSBX,TPM is a finite set. The population sequence of the proposed algorithm can be shown as follows:(17)Xt→MSBX,MPM,MDEXt+1=TXt=aTmXt+TcXt+bTSBXXt+cTPMXt,where a, b, and c which satisfy a+b+c=1 denote the selection probability by DE, SBX, PM, and DE. MSBX, MPM, and MDE represent the transition matrix of SBX, PM, and DE, respectively. Tc, Tm, TSBX, and TPM are not relevant to the time t. Therefore, it can be concluded from Definition 4 that {Xt,t=0,1,2,…} can be described as Markov chain in finite state set S.
The evolution process of AOSPEA can be described asXt⟶PXt+1; that is, Xt+1=Xt×P=Xt×MSBX×MPM×MDE; the transition matrix of the population sequence P=MSBX×MPM×MDE, where there exist P(Tm(X)=vi)>0, P(Tc(xi,vi)=ηi)>0, P(TSBX(X,β)=yi)>0, and P(TPM(xi,xi,UB,xi,LB,δ)=yi)>0, MSBX, MPM, and MDE are positive transition matrix. Therefore, P=MSBX×MPM×MDE is positive matrix. Therefore, {Xt,t=0,1,2,…} is homogeneous and nonperiodic Markov chain with positive transition matrix.Theorem 13.
The population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is asymptotically converged to a subset of the Pareto set with probability 1.Proof.
PS is defined to the ideal Pareto set for multiobjective problem. The population sequence{Xt,t=0,1,2,…} of AOSPEA is converged to any subset of PS with probability 1; that is to say, when t→+∞, for any elementa in Xt, there exists a∈PS.
We supposea∉PS, so there exists a Pareto optimal solutionb in PS, which satisfies thatb dominatesa. Definition 4 has demonstrated that {Xt,t=0,1,2,…} is homogeneous and nonperiodic Markov chain, and the transition matrix  P is the positive matrix. Due to the positive matrix P, P is irreducible from Definition 9. Therefore, it can be concluded from Lemma 11 that {Xt,t=0,1,2,…} visits any state in S∈Tm,Tc,TSBX,TPM and is not relevant to the initial distribution with probability 1. Thereupon, when t→+∞, the Pareto optimal solutionb appears in Xt with probability 1. Since AOSPEA only retain the Pareto optima,a will be obsoleted byb, which contradicted to the prior assumption.
Therefore, the population sequence{Xt,t=0,1,2,…} of AOSPEA algorithm is gradually converged to a subset of the Pareto set with probability 1.


## 3.6. Computational Complexity

The algorithm mainly includes fitness assignment, environment selection, and evolutionary operation according to the algorithm process. Assuming that the size of the population isN, the size of external archive is N-, the number of objectives ism, the number of generations isT, and the dimension of decision variable isD, the time complexity of one generation for the algorithm can be calculated as follows: the time complexity for fitness assignment is O(M2log⁡M)+O(M2)+O(M2), where M=N+N-; the time complexity for calculating objective values is O(Nm), and the worst time complexity for environment selection is O(M3). The evolutionary operation includes SBX, PM, and DE operation. Assuming that the proportion of them are a, b, and c (a+b+c=1), respectively, the time complexity of the total evolutionary operation is O((a+b+c)ND)=O(ND). The worst total time complexity of one generation is(18)OM2log⁡M+OM2+OM2+ONm+OM3+OND=OM3.So the worst total time complexity is O(TM3) in T generations.


## 4. Experiment and Results

### 4.1. Benchmark Problems

To verify the performance of the proposed algorithm, 17 well-known multiobjective function optimization test instances are employed in this paper. There are five ZDT (ZDT1, ZDT2, ZDT3, ZDT4, and ZDT6) problems [49], four DTLZ (DTLZ1, DTLZ2, DTLZ3, and DTLZ4) problems [50], and eight LZ09 (LZ09_F1, LZ09_F2, LZ09_F3, LZ09_F4, LZ09_F5, LZ09_F6, LZ09_F7, and LZ09_F9) problems [14]. All the test instances are the minimization of the objectives.


### 4.2. Performance Metrics

The performance ofPFknow obtained by an algorithm is evaluated by convergence and diversity. The following five performance metrics [51–53] are adopted to measure its performance in this paper. There are Generational Distance (GD), Inverted Generational Distance (IGD), Spacing (SP), Maximum Spread (MS), and Hypervolume (HV).


### 4.3. Experimental Setting

All the algorithms were implemented in MATLAB. AOSPEA is compared with SPEA2, NSGA-II, PESA-II, and MODEA [46]. The simulations were running on a PC with 2.1-GHz CPU and 2-GB RAM.The SBX and PM operators are used in all the algorithms. The parameter values are listed in Table1, wherem is the number of variables. For SPEA2, the population size is 100 and the size of external archive is 100. For NSGA-II, the population size is 100. For PESA-II, the internal population size is 100, the archive size is 100, and the number of hypergrid cells of each dimension is 32. For AOSPEA, the population size is 100, the size of external archive is 100, the minimum selection probability is 0.05, and CR = 1.0 and F = 0.5. For DE operation, since the problem size and complexity are different, the number of function evaluations is differently designed. For ZDT problems, the number of function evaluations is kept at 15000. For DTLZ, LZ09_F6, LZ09_F7, and LZ09_F9 problems, the number of function evaluations is kept at 50000. For LZ09_F1–F5 problems, the number of function evaluations is kept at 25000. Each algorithm is run 20 times independently for each test instance.Table 1
Parameter settings.
Parameters SPEA2 NSGA-II PESA-II AOSPEA Cross probability 0.8 0.8 0.8 1 SBX distribution index 15 15 15 15 Mutation probability 1/m 1/m 1/m 1/m PM distribution index 20 20 20 20


### 4.4. Experimental Results

In order to validate the effectiveness and efficiency of the adaptive scheme, a group of experiments are executed and the statistical results are listed in Table2. In Table 2, the HV is chosen as the performance measurement. For the nonadaptive selection scheme, the selection probability is set with fixed value. It can be seen that the average value obtained by AOSPEA with adaptive scheme is better than that of AOSPEA without adaptive scheme, which demonstrate the efficiency of adaptive scheme.Table 2
Compared results on the performance of adaptive scheme through the AOSPEA.
Problems AOSPEA with adaptive scheme AOSPEA without adaptive scheme Best Mean SD Best Mean SD ZDT1 2.0542 e - 001 3.6619 e + 000 8.9979 e - 005 8.5312 e + 000 6.2351 e + 001 8.9979 e - 004 ZDT2 2.0542 e - 001 3.3286 e + 000 1.4725 e - 004 3.8524 e + 000 4.6035 e + 001 3.5604 e - 003 DTLZ1 1.3192 e - 001 7.8933 e - 001 1.1547 e - 003 1.4201 e + 000 8.5367 e + 000 6.8359 e - 002 DTLZ2 1.2063 e - 001 4.1406 e - 001 1.1547 e - 003 1.0076 e + 000 3.1204 e + 000 4.3518 e - 002 LZ09_F1 6.8972 e - 001 3.6591 e + 000 3.5637 e - 004 2.2571 e + 001 7.0986 e + 001 2.6439 e - 003 LZ09_F2 1.1047 e - 002 3.5931 e + 000 8.5929 e - 003 3.5931 e + 000 6.2857 e + 001 2.9061 e - 002  Average value 2.2736 e - 001 2.5743 e + 000 1.9160 e - 003 6.8292 e + 000 4.2314 e + 001 2.4674 e - 002Table3 shows the mean and standard deviation of the metrics in four algorithms for ZDT problems. In each table cell, the first line is the mean value, the second line is the standard deviation, and bold indicates the optimal values among the compared algorithms. Figure 4 shows the nondominated solutions achieved by five algorithms for ZDT problems. The ZDT2 and ZDT6 test instances are chosen. These five problems have two objectives. For GD, AOSPEA is optimal for all the test instances except for ZDT2. For SP, AOSPEA is optimal for all the test instances except for ZDT3. For MS, SPEA2, NSGA-II, MODEA, and AOSPEA are close to one, but AOSPEA is slightly better than SPEA2, NSGA-II, and MODEA. The MS of PESA-II is worst because its boundary solutions can be replaced. For IGD and HV, AOSPEA is optimal for all the test instances. As a whole, it is can be seen from Table 3 and Figure 2 that AOSPEA is better than that of the others. Because PESA-II just reserve nondominated solutions in the archive, SPEA2, NSGA-II, MODEA, and AOPSEA can reserve dominated solutions when the number of nondominated solutions is less than the size. So the table also presents the fact that it is useful to reserve dominated solutions for ZDT problems at the early stage.Table 3
Mean values and standard deviations of performance indicators on ZDT test instances.
Problems Algorithm GD SP HV MS IGD ZDT1 SPEA2 2.5857 e - 005 2.0969 e - 003 3.6614 e + 000 9.9991 e - 001 1.5820 e - 004 4.3495 e - 006 1.7634 e - 004 2.7732 e - 004 2.3685 e - 004 1.6398 e - 005 NSGA-II 2.0347 e - 004 5.8214 e - 003 3.6605 e + 000 9.9713 e - 001 8.9535 e - 004 5.3345 e - 005 5.3461 e - 004 5.4561 e - 004 2.6547 e - 004 3.2995 e - 005 PESA-II 7.7737 e - 003 5.5438 e - 003 3.6419 e + 000 9.9487 e - 001 5.9252 e - 004 6.9582 e - 004 3.9421 e - 004 3.5694 e - 003 1.4235 e - 003 3.4621 e - 005 MODEA 1.4378 e - 005 3.4534 e - 003 3.6604 e + 000 9.9335 e - 001 6.0936 e - 004 3.7645 e - 006 3.5613 e - 004 3.5472 e - 003 3.6346 e - 003 4.5382 e - 005 AOSPEA 1.1964 e - 005 1.8849 e - 003 3.6619 e + 000 9.9985 e - 001 1.5234 e - 004 3.1517 e - 006 2.2202 e - 004 8.9979 e - 005 1.1150 e - 004 1.5427 e - 005  ZDT2 SPEA2 2.0069 e - 005 2.1141 e - 003 3.3267 e + 000 9.9935 e - 001 7.1849 e - 005 3.6952 e - 006 1.6354 e - 003 2.1098 e - 004 3.6254 e - 004 3.2556 e - 006 NSGA-II 2.4227 e - 005 6.0673 e - 003 3.3243 e + 000 9.9985 e - 001 4.7150 e - 004 7.5982 e - 006 4.9912 e - 004 2.8301 e - 004 1.3691 e - 003 6.9781 e - 005 PESA-II 7.1028 e - 003 5.3460 e - 003 3.3067 e + 000 9.9266 e - 001 4.5366 e - 004 7.6543 e - 004 3.8254 e - 004 4.2365 e - 003 2.6353 e - 003 8.6342 e - 005 MODEA 3.3681 e - 005 2.3824 e - 003 3.3218 e + 000 9.9896 e - 001 73002 e - 005 3.5021 e - 006 2.0351 e - 003 2.5003 e - 004 4.6293 e - 004 35983 e - 006 AOSPEA 2.3626 e - 005 1.9097 e - 003 3.3286 e + 000 9.9990 e - 001 4.6632 e - 005 2.9557 e - 006 2.0761 e - 004 1.4725 e - 004 1.0184 e - 004 2.4459 e - 006  ZDT3 SPEA2 3.8079 e - 004 2.5907 e - 003 4.8151 e + 000 9.9938 e - 001 3.8079 e - 004 2.5568 e - 005 1.2369 e - 003 1.5448 e - 004 5.3691 e - 005 1.8657 e - 004 NSGA-II 9.3972 e - 005 7.2424 e - 003 4.8141 e + 000 9.9897 e - 001 3.3769 e - 003 4.8137 e - 006 3.9789 e - 003 2.6538 e - 004 6.4512 e - 003 5.6231 e - 004 PESA-II 6.9455 e - 003 8.4691 e - 003 4.7910 e + 000 9.9470 e - 001 4.3002 e - 004 4.0251 e - 004 1.2139 e - 003 2.6304 e - 003 9.5614 e - 003 5.1324 e - 005 MODEA 1.3972 e - 004 6.5645 e - 003 4.8023 e + 000 9.9901 e - 001 7.2410 e - 003 5.3567 e - 006 3.9821 e - 003 2.5431 e - 004 6.2461 e - 003 5.8453 e - 004 AOSPEA 8.2750 e - 005 2.8098 e - 003 4.8150 e + 000 9.9976 e - 001 3.6550 e - 004 1.3478 e - 005 2.8932 e - 003 1.1334 e - 004 6.3041 e - 004 1.7126 e - 005  ZDT4 SPEA2 6.7015 e - 004 2.2502 e - 003 3.6523 e + 000 9.9809 e - 001 4.6003 e - 004 2.5639 e - 005 3.5980 e - 004 5.0213 e - 004 1.6554 e - 004 1.6398 e - 005 NSGA-II 4.8822 e - 004 4.2264 e - 003 3.6536 e + 000 9.9738 e - 001 3.6178 e - 003 2.9807 e - 005 2.3649 e - 004 4.8092 e - 004 2.9708 e - 004 3.5621 e - 004 PESA-II 9.2848 e - 003 8.1803 e - 003 3.6469 e + 000 9.8374 e - 001 3.1883 e - 003 5.3690 e - 004 3.2013 e - 004 2.3058 e - 003 3.5627 e - 003 8.5671 e - 004 MODEA 3.5656 e - 004 3.5445 e - 003 3.6527 e + 000 9.9801 e - 001 3.7861 e - 003 3.7248 e - 005 3.2003 e - 004 4.3504 e - 004 2.8079 e - 004 3.2367 e - 004 AOSPEA 1.4636 e - 004 1.9829 e - 003 3.6618 e + 000 9.9931 e + 000 1.5982 e - 004 1.6977 e - 005 2.1056 e - 004 1.2257 e - 004 1.5588 e - 004 1.5130 e - 005  ZDT6 SPEA2 6.1089 e - 004 1.9464 e - 003 3.0328 e + 000 9.9730 e - 001 5.5711 e - 004 2.6390 e - 005 2.5681 e - 004 3.2156 e - 005 3.9657 e - 004 1.5396 e - 005 NSGA-II 7.8852 e - 004 2.8317 e - 003 3.0311 e + 000 9.9718 e - 001 6.4428 e - 003 3.9817 e - 005 2.3655 e - 004 3.6541 e - 005 8.2456 e - 004 4.8106 e - 005 PESA-II 5.1988 e - 004 5.3687 e - 003 3.0284 e + 000 9.9533 e - 001 5.2983 e - 004 2.3642 e - 005 2.9820 e - 004 2.2347 e - 004 5.2107 e - 004 2.5419 e - 005 MODEA 7.3699 e - 004 2.6249 e - 003 3.0338 e + 000 9.9792 e - 001 6.9355 e - 003 3.6078 e - 005 2.6674 e - 004 3.2567 e - 005 8.7635 e - 004 4.5907 e - 005 AOSPEA 2.0740 e - 004 1.5639 e - 003 3.0376 e + 000 9.9861 e - 001 4.3419 e - 004 1.7334 e - 005 1.3660 e - 004 1.2996 e - 005 2.3794 e - 004 1.2755 e - 005Figure 4
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on ZDT2 and ZDT6 test instances.
(a)
ZDT2 (b)
ZDT6Figure5 shows boxplots of the metrics for ZDT1. A boxplot is used to show the statistical results of a group data through five numerical data which are the lower bound, lower quartile, median, upper quartile, and upper bound. For GD, SP, and IGD, the five numerical data of SPEA and AOPSEA are less than others. But AOSPEA is slight better than SPEA2, and AOPSEA is steadier than SPEA2 because the difference of lower quartile and upper quartile of AOSPEA is less than SPEA2. AOSPEA has the same performance with SPEA2 for MS, but AOSPEA is steadier. AOPSEA is better than others for HV and shows good robustness.Figure 5
Boxplots of the metrics for ZDT1.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDTable4 and Figure 6 show statistic values and nondominated solutions on DTLZ test instances. These four problems have three objectives. For GD, AOSPEA is optimal for all the test instances but DTLZ1. For SP, AOSPEA is optimal on DTLZ4 and a little worse than the optimal value on the rest test instances. For MS, AOSPEA and SPEA2 are better than NSGA-II, MODEA, and PESA-II. So AOSPEA has a better diversity considering SP and MS. For HV, AOSPEA is the best of all. For IGD, PESA-II is optimal for all the test instances but DTLZ2. The solutions obtained by PESA-II are easily gathered together due to the fact that the MS of PESA-II is small. So the IGD of PESA-II is optimal for DTLZ test instances. It is clear from Figure 3 that AOSPEA performs much better than the others in terms of diversity. Overall, AOSPEA is better than others for DTLZ test instances.Table 4
Mean values and standard deviations of performance indicators on DTLZ test instances.
Problem Algorithm GD SP HV MS IGD DTLZ1 SPEA2 4.8125 e - 006 2.3621 e - 002 7.8824 e - 001 9.9927 e - 001 7.9758 e - 004 6.3254 e - 007 1.1239 e - 002 3.9501 e - 004 4.2361 e - 004 6.2380 e - 005 NSGA-II 5.9303 e - 006 1.2539 e - 002 7.5291 e - 001 9.8246 e - 001 5.9104 e - 004 6.2413 e - 007 2.6354 e - 002 9.8541 e - 004 5.2146 e - 004 5.6941 e - 005 PESA-II 3.7277 e - 008 1.1629 e - 002 7.3672 e - 001 8.6170 e - 001 4.0547 e - 004 5.4261 e - 009 2.5461 e - 002 8.5421 e - 004 4.8521 e - 004 6.3214 e - 005 MODEA 5.4140 e - 006 1.8241 e - 002 7.8104 e - 001 9.9834 e - 001 6.5028 e - 004 6.2031 e - 007 2.3425 e - 002 9.7452 e - 004 5.7523 e - 004 5.2507 e - 005 AOSPEA 8.6914 e - 007 1.3913 e - 002 7.8933 e - 001 9.9988 e - 001 6.4388 e - 004 3.2262 e - 007 1.8606 e - 002 4.4794 e - 004 8.5999 e - 004 1.8286 e - 005  DTLZ2 SPEA2 5.1666 e - 006 1.2948 e - 002 4.0465 e - 001 9.9997 e - 001 1.0390 e - 003 5.6241 e - 007 3.2154 e - 003 2.1245 e - 003 5.6297 e - 004 8.2415 e - 005 NSGA-II 4.9925 e - 005 4.2959 e - 002 3.7997 e - 001 9.9897 e - 001 1.3961 e - 003 3.5462 e - 006 1.0241 e - 002 6.2584 e - 003 3.4564 e - 004 5.0195 e - 004 PESA-II 7.3671 e - 005 1.9045 e - 002 2.4641 e - 001 6.2671 e - 001 1.4426 e - 003 3.6259 e - 006 2.3124 e - 002 5.3654 e - 003 3.2654 e - 003 4.2381 e - 004 MODEA 4.3248 e - 005 2.8483 e - 002 3.8018 e - 001 9.9899 e - 001 1.1582 e - 003 3.3756 e - 006 1.2531 e - 002 6.3741 e - 003 3.5765 e - 004 5.6021 e - 004 AOSPEA 7.1591 e - 007 1.3037 e - 002 4.1406 e - 001 9.9936 e - 001 6.4520 e - 004 6.9969 e - 007 7.6431 e - 004 1.1547 e - 003 7.3505 e - 004 3.7002 e - 005  DTLZ3 SPEA2 2.1735 e - 005 1.3862 e - 002 4.0516 e - 001 9.9648 e - 001 1.2801 e - 003 2.0841 e - 006 1.2541 e - 003 3.2610 e - 004 3.0214 e - 004 9.0250 e - 004 NSGA-II 1.0351 e - 005 4.1432 e - 002 3.7923 e - 001 9.9911 e - 001 6.8628 e - 004 5.6210 e - 006 3.2514 e - 003 5.2601 e - 003 3.0981 e - 004 8.0214 e - 005 PESA-II 1.8136 e - 005 2.4120 e - 002 1.5832 e - 001 5.0406 e - 001 4.9005 e - 004 2.9015 e - 006 2.3694 e - 003 2.3654 e - 003 3.5089 e - 002 2.3456 e - 005 MODEA 1.6241 e - 005 2.2543 e - 002 3.9348 e - 001 9.9885 e - 001 6.9379 e - 004 5.9015 e - 006 3.5263 e - 003 5.2173 e - 003 3.1092 e - 004 8.5231 e - 005 AOSPEA 1.4928 e - 006 1.5251 e - 002 4.1376 e - 001 9.9914 e - 001 6.2648 e - 004 3.9654 e - 007 1.9804 e - 003 2.1354 e - 004 8.0265 e - 004 5.2245 e - 004  DTLZ4 SPEA2 3.9576 e - 005 1.2211 e - 002 4.0063 e - 001 9.9953 e - 001 1.5867 e - 003 1.2309 e - 006 2.5364 e - 003 4.0167 e - 004 5.0234 e - 004 5.2347 e - 004 NSGA-II 5.4451 e - 005 4.5550 e - 002 3.7327 e - 001 9.9925 e - 001 1.3183 e - 003 1.2354 e - 005 1.2107 e - 002 7.1234 e - 004 1.2547 e - 004 5.6362 e - 004 PESA-II 5.6680 e - 005 4.2256 e - 002 3.2743 e - 001 9.8605 e - 001 9.7414 e - 004 5.4231 e - 006 2.3154 e - 002 2.1563 e - 003 5.2147 e - 003 5.2134 e - 005 MODEA 5.9832 e - 005 3.2566 e - 002 3.9563 e - 001 9.9836 e - 001 1.4924 e - 003 1.3643 e - 005 1.6123 e - 002 7.3201 e - 004 1.8563 e - 004 5.3747 e - 004 AOSPEA 1.4634 e - 005 1.0901 e - 002 4.0934 e - 001 9.9936 e - 001 1.0468 e - 003 5.6842 e - 006 9.2014 e - 004 2.1325 e - 004 9.1231 e - 004 6.9821 e - 004Figure 6
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on DTLZ test instances.
(a)
DTLZ1 (b)
DTLZ4Figure7 shows boxplots of the metrics for DTLZ4. The lower quartile, median quartile, and upper quartile of AOSPEA are less than others for GD, but SPEA is steadier than SPEA2. AOSPEA performs the best for SP and HV and shows better steady. PESA-II has the best value for IGD, but the MS performs the worst. For the value of MS and IGD, AOSPEA shows slighter worse than the best.Figure 7
Boxplots of the metrics for DTLZ4.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDTable5 and Figure 8 show statistic values, nondominated solutions, and boxplots on LZ09 test instances. These eight problems have two objectives except F6 has three objectives. For GD, AOSPEA is optimal on LZ09_F1 and LZ09_F2, PESA-II is optimal on LZ09_F4, LZ09_F5, and LZ09_F9, SPEA2 is optimal on LZ09_F6, and MODEA is optimal on LZ09_F7. AOSPEA is a little worse than the optimal on LZ09_F3, LZ09_F5, LZ09_F6, and LZ09_F9. For SP, AOSPEA is optimal on LZ09_F1 and LZ09_F7, PESA-II is optimal on LZ09_F2, LZ09_F3, LZ09_F6, and LZ09_F9, SPEA2 is optimal on LZ09_F4, and NSGA-II is optimal on LZ09_F5. AOSPEA is a little worse than the optimal on LZ09_F2, LZ09_F3, LZ09_F4, LZ09_F5, and LZ09_F6. For MS, AOSPEA is optimal for all the test instances but LZ09_F1 and LZ09_F7. AOSPEA has the best diversity considering SP and MS. PESA-II has a good SP, but its MS is the worst. For HV, AOSPEA is optimal for all the test instances but LZ09_F7. For IGD, AOSPEA is optimal on LZ09_F1, SPEA2 is optimal on LZ09_F6 and LZ09_F7, and PESA-II is optimal for the rest of test instances. AOPSEA is slightly worse than the optimal for LZ09_F2, LZ09_F5, LZ09_F6, LZ09_F7, and LZ09_F9. Figure 4 shows that AOSPEA have better spread and it is hard to converge for all the algorithms on LZ09_F7 and LZ09_F9. Overall, AOPSEA is better than other algorithms for most of LZ09 test instances.Table 5
Mean values and standard deviations of performance indicators on LZ09 test instances.
Problem Algorithm GD SP HV MS IGD LZ09_F1 SPEA2 3.7556 e - 003 3.5552 e - 002 3.6424 e + 000 9.9340 e - 001 7.7606 e - 003 1.8319 e - 003 3.0150 e - 002 2.0262 e - 002 9.4758 e - 003 4.5673 e - 003 NSGA-II 2.7616 e - 003 8.5761 e - 003 3.6499 e + 000 9.9960 e - 001 3.3906 e - 003 2.1032 e - 003 2.3946 e - 003 2.4461 e - 003 7.7068 e - 004 3.0904 e - 003 PESA-II 2.4732 e - 003 1.4495 e - 002 3.6381 e + 000 9.9267 e - 001 3.2740 e - 003 1.2440 e - 003 7.6753 e - 003 9.0751 e - 003 6.9128 e - 003 2.3093 e - 003 MODEA 1.5258 e - 003 4.4632 e - 003 3.6487 e + 000 9.9326 e - 001 3.7104 e - 003 2.1412 e - 003 2.5382 e - 003 2.5572 e - 003 7.9718 e - 004 3.5101 e - 003 AOSPEA 3.3856 e - 004 2.1617 e - 003 3.6591 e + 000 9.9899 e - 001 3.3817 e - 004 3.8197 e - 005 2.5993 e - 004 3.5637 e - 004 1.1890 e - 003 2.6264 e - 005  LZ09_F2 SPEA2 1.9169 e - 003 1.6310 e - 002 3.3038 e + 000 6.7685 e - 001 1.5532 e - 003 3.3207 e - 003 3.4150 e - 002 1.1211 e - 001 1.5286 e - 001 2.7729 e - 003 NSGA-II 3.2721 e - 003 5.8267 e - 003 3.4290 e + 000 8.8184 e - 001 1.6837 e - 003 2.7291 e - 003 9.4258 e - 003 4.7836 e - 002 1.3044 e - 001 1.4259 e - 003 PESA-II 1.0923 e - 003 8.6235 e - 004 3.1987 e + 000 5.4580 e - 001 5.3251 e - 004 9.0903 e - 004 1.1030 e - 003 1.7616 e - 001 1.5717 e - 001 5.9315 e - 004 MODEA 2.0361 e - 003 5.8738 e - 003 3.4388 e + 000 8.9295 e - 001 1.0004 e - 003 1.9983 e - 003 9.7413 e - 003 4.5487 e - 002 1.5504 e - 001 1.0635 e - 003 AOSPEA 1.5443 e - 003 5.5098 e - 003 3.5931 e + 000 9.3087 e - 001 9.1089 e - 004 4.1867 e - 004 6.8755 e - 003 8.5929 e - 003 4.5133 e - 002 3.0157 e - 004  LZ09_F3 SPEA2 3.3606 e - 003 7.3026 e - 003 3.3997 e + 000 8.1966 e - 001 2.6561 e - 003 3.4579 e - 004 4.9259 e - 003 1.0650 e - 001 1.5015 e - 001 3.1125 e - 004 NSGA-II 4.3339 e - 003 9.8427 e - 003 3.5319 e + 000 9.6780 e - 001 3.5023 e - 003 2.4645 e - 004 6.7163 e - 003 3.6437 e - 002 1.7952 e - 002 3.3908 e - 004 PESA-II 2.6867 e - 003 5.4008 e - 003 3.3372 e + 000 7.4076 e - 001 1.9135 e - 003 7.3607 e - 004 1.7362 e - 003 1.8021 e - 001 2.0984 e - 001 6.7320 e - 004 MODEA 5.0573 e - 003 6.8359 e - 003 3.5621 e + 000 9.7804 e - 001 3.0103 e - 003 2.4645 e - 004 6.4528 e - 003 3.8457 e - 002 13608 e - 002 3.9184 e - 004 AOSPEA 3.1731 e - 003 7.0248 e - 003 3.6167 e + 000 9.9442 e - 001 2.8883 e - 003 2.6854 e - 004 2.6986 e - 003 1.0643 e - 002 5.6899 e - 003 6.4646 e - 004  LZ09_F4 SPEA2 4.0761 e - 003 6.4456 e - 003 3.4087 e + 000 8.4116 e - 001 3.3267 e - 003 6.9912 e - 004 1.5510 e - 003 1.9678 e - 002 4.7887 e - 002 6.2428 e - 004 NSGA-II 3.7630 e - 003 7.3996 e - 003 3.4417 e + 000 8.4098 e - 001 2.9932 e - 003 5.2942 e - 004 2.5646 e - 003 2.7276 e - 002 5.5535 e - 002 4.8189 e - 004 PESA-II 3.6948 e - 003 7.8493 e - 003 3.3937 e + 000 7.7238 e - 001 2.8426 e - 003 9.0100 e - 004 1.0287 e - 003 2.8955 e - 002 3.8750 e - 002 7.6701 e - 004 MODEA 3.8743 e - 003 7.0885 e - 003 3.5228 e + 000 9.4187 e - 001 3.1143 e - 003 5.3053 e - 004 2.6757 e - 003 2.8387 e - 002 5.6646 e - 002 4.9298 e - 004 AOSPEA 4.5735 e - 003 6.6016 e - 006 3.6236 e + 000 9.9572 e - 001 3.2898 e - 003 1.7735 e - 003 2.1646 e - 006 1.1086 e - 002 3.6365 e - 003 4.8174 e - 003  LZ09_F5 SPEA2 4.2443 e - 003 7.6946 e - 003 3.5087 e + 000 9.3333 e - 001 3.9660 e - 003 9.0707 e - 004 5.4273 e - 003 5.0148 e - 002 7.5440 e - 002 1.1625 e - 003 NSGA-II 3.9777 e - 003 5.8253 e - 003 3.5712 e + 000 9.8091 e - 001 3.4926 e - 003 4.9673 e - 004 2.2365 e - 003 2.1052 e - 002 1.6274 e - 002 2.5889 e - 004 PESA-II 2.5690 e - 003 1.4395 e - 002 3.4477 e + 000 8.3870 e - 001 1.8529 e - 003 5.4005 e - 004 1.8361 e - 002 5.7840 e - 002 9.7133 e - 002 4.8959 e - 004 MODEA 2.9658 e - 003 9.9364 e - 003 3.5832 e + 000 9.9562 e - 001 3.5047 e - 003 4.8584 e - 004 2.6534 e - 003 2.2602 e - 002 1.5383 e - 002 2.8994 e - 004 AOSPEA 2.6175 e - 003 6.8127 e - 003 3.6261 e + 000 9.9676 e - 001 3.0101 e - 003 7.1940 e - 004 2.1710 e - 003 6.0387 e - 003 4.6184 e - 003 2.0291 e - 003  LZ09_F6 SPEA2 1.0019 e - 003 1.2787 e - 001 2.4692 e - 001 9.9883 e - 001 7.2812 e - 002 5.5156 e - 004 4.2707 e - 002 8.5666 e - 003 1.1774 e - 004 2.0840 e - 002 NSGA-II 7.0744 e - 003 2.2985 e - 001 1.5436 e - 001 9.7899 e + 000 1.6556 e - 001 8.7776 e - 003 1.9554 e - 001 6.5348 e - 002 7.7052 e - 006 8.6470 e - 002 PESA-II 3.0472 e - 002 1.0007 e - 001 9.1255 e - 002 6.6200 e - 001 2.1902 e - 001 2.0434 e - 002 1.1519 e - 001 1.2405 e - 001 1.7424 e - 001 1.6415 e - 001 MODEA 5.3345 e - 003 2.1874 e - 001 1.5456 e - 001 9.8768 e + 000 1.7667 e - 001 8.5666 e - 003 1.3448 e - 001 6.7324 e - 002 7.1618 e - 006 8.9635 e - 002 AOSPEA 4.2271 e - 003 1.2543 e - 001 2.9381 e - 001 9.9923 e - 001 1.5651 e - 001 8.3194 e - 003 1.4478 e - 001 5.9100 e - 002 1.2849 e - 003 1.6190 e - 001  LZ09_F7 SPEA2 2.7152 e - 003 1.8610 e - 002 2.7996 e + 000 2.6474 e - 001 1.6641 e - 003 3.2924 e - 003 2.7461 e - 002 1.7878 e - 001 2.8438 e - 001 1.6817 e - 003 NSGA-II 1.4830 e - 002 1.1319 e - 003 3.0175 e + 000 5.5930 e - 001 1.3810 e - 002 1.5153 e - 002 1.4869 e - 003 2.3518 e - 001 1.9580 e - 001 1.5221 e - 002 PESA-II 8.6571 e - 003 6.3791 e - 003 2.7293 e + 000 3.1134 e - 001 6.9771 e - 003 9.2704 e - 003 8.2636 e - 003 2.0280 e - 001 1.9539 e - 001 7.7519 e - 003 MODEA 1.9428 e - 003 1.8242 e - 003 2.8634 e + 000 3.4062 e - 001 1.0021 e - 002 1.2626 e - 003 1.5976 e - 003 2.9264 e - 001 1.9748 e - 001 1.2336 e - 002 AOSPEA 3.0445 e - 003 5.0273 e - 004 2.9012 e + 000 3.4429 e - 001 2.5283 e - 003 4.2071 e - 003 6.3906 e - 004 2.2058 e - 001 2.7334 e - 001 3.2431 e - 003  LZ09_F9 SPEA2 1.3536 e - 003 2.5205 e - 003 3.1197 e + 000 9.5827 e - 001 9.9841 e - 004 1.0519 e - 003 1.3774 e - 003 9.1038 e - 002 6.1881 e - 002 1.0710 e - 003 NSGA-II 3.5979 e - 003 7.1248 e - 003 3.0928 e + 000 9.4306 e - 001 1.7312 e - 003 5.1786 e - 003 8.3145 e - 003 7.2511 e - 002 5.6148 e - 002 2.2128 e - 003 PESA-II 2.0336 e - 004 8.4083 e - 004 2.7822 e + 000 7.3696 e - 001 1.5132 e - 004 6.1281 e - 005 2.6371 e - 004 2.4980 e - 001 2.0321 e - 001 3.1092 e - 005 MODEA 2.1416 e - 003 6.7310 e - 003 3.1039 e + 000 9.6328 e - 001 1.1324 e - 003 5.7982 e - 003 8.6524 e - 003 7.2263 e - 002 5.7305 e - 002 2.9323 e - 003 AOSPEA 5.5511 e - 004 4.2319 e - 003 3.2355 e + 000 9.7243 e - 001 3.1984 e - 004 1.9785 e - 004 6.7590 e - 003 1.0563 e - 001 5.9679 e - 002 9.0466 e - 005Figure 8
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on LZ09 test instances.
(a)
LZ09_F2 (b)
LZ09_F4 (c)
LZ09_F5 (d)Figure9 shows boxplots of the metrics for LA09_F1. The lower quartile, median quartile, and upper quartile of AOSPEA perform the best for GD, SP, HV, and IGD and show the best robustness at the same time. AOSPEA performs slighter worse than NSGA-II and NSGA-II obtains the best maximum spread. AOSPEA shows the best convergence and diversity on LA09_F1.Figure 9
Boxplots of the metrics for LA09_F1.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDFor LZ problems, AOSPEA was compared with other four typical MOEAS which are SPEA2, NSGA-II, PESA-II, and MODEA. For NSGA-II, it adopts the operation-based representation to encode a chromosome. The POX crossover method and bit-flip mutation are used as reproduction operators. The probability of crossover and mutation are set to 0.5 and 0.1, respectively. The population size is set to 30. The other settings of the above algorithms keep consistent with the proposed algorithm. Each instance is executed by SPEA2, NSGA-II, PESA-II, and MODEA for 20 times independently, respectively. Table6 reports the computational results obtained by SPEA2, NSGA-II, PESA-II, and MODEA. Table 6 includes problem name (Instances) and problem size (Dimension). The results of the mean relative error (MRE, MRE=100×(MRE-BKS(orUB))/BKS(orUB)) and the running time (CPU times) of AOSPEA, SPEA2, NSGA-II, PESA-II, and MODEA. The graphical representation in Figure 10 shows the comparison of benchmark standard problems results obtained from AOSPEA with SPEA2, NSGA-II, PESA-II, and MODEA. From Table 5, we know that the results obtained by the proposed algorithms are better than these four typical algorithms. Although AOSPEA does not obtain the best known solutions in the number of generations for large problems, the evolutionary trend of the population does not stagnate. That is to say, AOSPEA can further optimize obtaining the better solution. Meanwhile, the CPU time of all the compared algorithms is provided in Figure 11; it can be seen that the running time of AOSPEA is also superior to other algorithms. The population size of SPEA2, NSGA-II, PESA-II, and MODEA must keep a certain scale; otherwise they are easily trapped in local optimum, but the large population will increase the running time. AOSPEA has strong disturbance capacity, so even if the population is relatively small, it can boost the searching and readily escape the local optimum.Table 6
Results using AGS_PAES for MK problems.
Instance Dimension AOSPEA SPEA2 NSGA-II PESA-II MODEA MRE CPU times MRE CPU times MRE CPU times MRE CPU times MRE CPU times ZDT1 30 4.003 735.1 4.591 839.6 4.612 856.9 5.317 857.5 5.401 858.9 ZDT2 30 4.892 725.9 4.445 841.5 4.961 837.7 5.116 848.3 5.921 849.7 ZDT3 30 5.129 100.3 5.312 150.3 5.378 125.4 5.865 126.6 5.977 127.3 ZDT4 10 5.549 273.3 6.068 378.1 6.543 405.1 6.651 415.7 7.076 417.1 ZDT6 10 6.002 479.5 6.132 592.1 6.298 601.3 6.769 621.9 8.012 633.3 DTLZ1 7 4.198 279.1 4.226 399.8 4.331 400.9 4.821 401.5 5.086 412.9 DTLZ2 12 5.012 434.8 5.203 531.1 5.302 556.6 5.825 557.2 6.325 568.6 DTLZ3 12 3.471 499.2 3.821 645.1 4.828 621.0 5.336 621.6 6.253 633.1 DTLZ4 12 4.021 619.6 4.325 778.9 5.952 781.4 5.409 812.9 6.612 824.3 LZ09_F1 10 5.887 647.3 6.208 751.2 6.802 789.1 7.337 829.7 8.389 831.1 LZ09_F2 30 9.021 1415.1 9.101 1781.2 9.199 1576.9 9.657 1597.5 10.897 1618.9 LZ09_F3 30 7.312 1268 7.625 1459.9 7.883 1469.8 8.331 1480.4 9.441 1501.8 LZ09_F4 30 8.872 1199.8 9.105 1410.1 9.919 1461.6 9.664 1472.2 9.982 1483.6 LZ09_F5 30 5.885 1170.3 6.115 1312.9 6.231 1332.1 6.723 1362.7 6.905 1399.1 LZ09_F6 10 9.002 1149.7 9.205 1341.1 9.902 1361.5 10.008 1392.1 12.911 1419.5 LZ09_F7 10 8.884 1074.4 9.012 1231.1 9.218 1236.2 9.733 1266.8 10.023 1289.2 LZ09_F9 30 5.768 1141.9 6.003 1366.5 6.177 1399.7 6.691 1430.3 7.116 1459.7 MRE — 7.395 — 7.552 — 7.629 — 7.895 — 8.915 —Figure 10
MRE of AOSPEA algorithm compared with SPEA2, NSGA-II, PESA-II, and MODEA.Figure 11
CPU time of AOSPEA compared with SPEA2, NSGA-II, PESA-II, and MODEA.


## 4.1. Benchmark Problems

To verify the performance of the proposed algorithm, 17 well-known multiobjective function optimization test instances are employed in this paper. There are five ZDT (ZDT1, ZDT2, ZDT3, ZDT4, and ZDT6) problems [49], four DTLZ (DTLZ1, DTLZ2, DTLZ3, and DTLZ4) problems [50], and eight LZ09 (LZ09_F1, LZ09_F2, LZ09_F3, LZ09_F4, LZ09_F5, LZ09_F6, LZ09_F7, and LZ09_F9) problems [14]. All the test instances are the minimization of the objectives.


## 4.2. Performance Metrics

The performance ofPFknow obtained by an algorithm is evaluated by convergence and diversity. The following five performance metrics [51–53] are adopted to measure its performance in this paper. There are Generational Distance (GD), Inverted Generational Distance (IGD), Spacing (SP), Maximum Spread (MS), and Hypervolume (HV).


## 4.3. Experimental Setting

All the algorithms were implemented in MATLAB. AOSPEA is compared with SPEA2, NSGA-II, PESA-II, and MODEA [46]. The simulations were running on a PC with 2.1-GHz CPU and 2-GB RAM.The SBX and PM operators are used in all the algorithms. The parameter values are listed in Table1, wherem is the number of variables. For SPEA2, the population size is 100 and the size of external archive is 100. For NSGA-II, the population size is 100. For PESA-II, the internal population size is 100, the archive size is 100, and the number of hypergrid cells of each dimension is 32. For AOSPEA, the population size is 100, the size of external archive is 100, the minimum selection probability is 0.05, and CR = 1.0 and F = 0.5. For DE operation, since the problem size and complexity are different, the number of function evaluations is differently designed. For ZDT problems, the number of function evaluations is kept at 15000. For DTLZ, LZ09_F6, LZ09_F7, and LZ09_F9 problems, the number of function evaluations is kept at 50000. For LZ09_F1–F5 problems, the number of function evaluations is kept at 25000. Each algorithm is run 20 times independently for each test instance.Table 1
Parameter settings.
Parameters SPEA2 NSGA-II PESA-II AOSPEA Cross probability 0.8 0.8 0.8 1 SBX distribution index 15 15 15 15 Mutation probability 1/m 1/m 1/m 1/m PM distribution index 20 20 20 20


## 4.4. Experimental Results

In order to validate the effectiveness and efficiency of the adaptive scheme, a group of experiments are executed and the statistical results are listed in Table2. In Table 2, the HV is chosen as the performance measurement. For the nonadaptive selection scheme, the selection probability is set with fixed value. It can be seen that the average value obtained by AOSPEA with adaptive scheme is better than that of AOSPEA without adaptive scheme, which demonstrate the efficiency of adaptive scheme.Table 2
Compared results on the performance of adaptive scheme through the AOSPEA.
Problems AOSPEA with adaptive scheme AOSPEA without adaptive scheme Best Mean SD Best Mean SD ZDT1 2.0542 e - 001 3.6619 e + 000 8.9979 e - 005 8.5312 e + 000 6.2351 e + 001 8.9979 e - 004 ZDT2 2.0542 e - 001 3.3286 e + 000 1.4725 e - 004 3.8524 e + 000 4.6035 e + 001 3.5604 e - 003 DTLZ1 1.3192 e - 001 7.8933 e - 001 1.1547 e - 003 1.4201 e + 000 8.5367 e + 000 6.8359 e - 002 DTLZ2 1.2063 e - 001 4.1406 e - 001 1.1547 e - 003 1.0076 e + 000 3.1204 e + 000 4.3518 e - 002 LZ09_F1 6.8972 e - 001 3.6591 e + 000 3.5637 e - 004 2.2571 e + 001 7.0986 e + 001 2.6439 e - 003 LZ09_F2 1.1047 e - 002 3.5931 e + 000 8.5929 e - 003 3.5931 e + 000 6.2857 e + 001 2.9061 e - 002  Average value 2.2736 e - 001 2.5743 e + 000 1.9160 e - 003 6.8292 e + 000 4.2314 e + 001 2.4674 e - 002Table3 shows the mean and standard deviation of the metrics in four algorithms for ZDT problems. In each table cell, the first line is the mean value, the second line is the standard deviation, and bold indicates the optimal values among the compared algorithms. Figure 4 shows the nondominated solutions achieved by five algorithms for ZDT problems. The ZDT2 and ZDT6 test instances are chosen. These five problems have two objectives. For GD, AOSPEA is optimal for all the test instances except for ZDT2. For SP, AOSPEA is optimal for all the test instances except for ZDT3. For MS, SPEA2, NSGA-II, MODEA, and AOSPEA are close to one, but AOSPEA is slightly better than SPEA2, NSGA-II, and MODEA. The MS of PESA-II is worst because its boundary solutions can be replaced. For IGD and HV, AOSPEA is optimal for all the test instances. As a whole, it is can be seen from Table 3 and Figure 2 that AOSPEA is better than that of the others. Because PESA-II just reserve nondominated solutions in the archive, SPEA2, NSGA-II, MODEA, and AOPSEA can reserve dominated solutions when the number of nondominated solutions is less than the size. So the table also presents the fact that it is useful to reserve dominated solutions for ZDT problems at the early stage.Table 3
Mean values and standard deviations of performance indicators on ZDT test instances.
Problems Algorithm GD SP HV MS IGD ZDT1 SPEA2 2.5857 e - 005 2.0969 e - 003 3.6614 e + 000 9.9991 e - 001 1.5820 e - 004 4.3495 e - 006 1.7634 e - 004 2.7732 e - 004 2.3685 e - 004 1.6398 e - 005 NSGA-II 2.0347 e - 004 5.8214 e - 003 3.6605 e + 000 9.9713 e - 001 8.9535 e - 004 5.3345 e - 005 5.3461 e - 004 5.4561 e - 004 2.6547 e - 004 3.2995 e - 005 PESA-II 7.7737 e - 003 5.5438 e - 003 3.6419 e + 000 9.9487 e - 001 5.9252 e - 004 6.9582 e - 004 3.9421 e - 004 3.5694 e - 003 1.4235 e - 003 3.4621 e - 005 MODEA 1.4378 e - 005 3.4534 e - 003 3.6604 e + 000 9.9335 e - 001 6.0936 e - 004 3.7645 e - 006 3.5613 e - 004 3.5472 e - 003 3.6346 e - 003 4.5382 e - 005 AOSPEA 1.1964 e - 005 1.8849 e - 003 3.6619 e + 000 9.9985 e - 001 1.5234 e - 004 3.1517 e - 006 2.2202 e - 004 8.9979 e - 005 1.1150 e - 004 1.5427 e - 005  ZDT2 SPEA2 2.0069 e - 005 2.1141 e - 003 3.3267 e + 000 9.9935 e - 001 7.1849 e - 005 3.6952 e - 006 1.6354 e - 003 2.1098 e - 004 3.6254 e - 004 3.2556 e - 006 NSGA-II 2.4227 e - 005 6.0673 e - 003 3.3243 e + 000 9.9985 e - 001 4.7150 e - 004 7.5982 e - 006 4.9912 e - 004 2.8301 e - 004 1.3691 e - 003 6.9781 e - 005 PESA-II 7.1028 e - 003 5.3460 e - 003 3.3067 e + 000 9.9266 e - 001 4.5366 e - 004 7.6543 e - 004 3.8254 e - 004 4.2365 e - 003 2.6353 e - 003 8.6342 e - 005 MODEA 3.3681 e - 005 2.3824 e - 003 3.3218 e + 000 9.9896 e - 001 73002 e - 005 3.5021 e - 006 2.0351 e - 003 2.5003 e - 004 4.6293 e - 004 35983 e - 006 AOSPEA 2.3626 e - 005 1.9097 e - 003 3.3286 e + 000 9.9990 e - 001 4.6632 e - 005 2.9557 e - 006 2.0761 e - 004 1.4725 e - 004 1.0184 e - 004 2.4459 e - 006  ZDT3 SPEA2 3.8079 e - 004 2.5907 e - 003 4.8151 e + 000 9.9938 e - 001 3.8079 e - 004 2.5568 e - 005 1.2369 e - 003 1.5448 e - 004 5.3691 e - 005 1.8657 e - 004 NSGA-II 9.3972 e - 005 7.2424 e - 003 4.8141 e + 000 9.9897 e - 001 3.3769 e - 003 4.8137 e - 006 3.9789 e - 003 2.6538 e - 004 6.4512 e - 003 5.6231 e - 004 PESA-II 6.9455 e - 003 8.4691 e - 003 4.7910 e + 000 9.9470 e - 001 4.3002 e - 004 4.0251 e - 004 1.2139 e - 003 2.6304 e - 003 9.5614 e - 003 5.1324 e - 005 MODEA 1.3972 e - 004 6.5645 e - 003 4.8023 e + 000 9.9901 e - 001 7.2410 e - 003 5.3567 e - 006 3.9821 e - 003 2.5431 e - 004 6.2461 e - 003 5.8453 e - 004 AOSPEA 8.2750 e - 005 2.8098 e - 003 4.8150 e + 000 9.9976 e - 001 3.6550 e - 004 1.3478 e - 005 2.8932 e - 003 1.1334 e - 004 6.3041 e - 004 1.7126 e - 005  ZDT4 SPEA2 6.7015 e - 004 2.2502 e - 003 3.6523 e + 000 9.9809 e - 001 4.6003 e - 004 2.5639 e - 005 3.5980 e - 004 5.0213 e - 004 1.6554 e - 004 1.6398 e - 005 NSGA-II 4.8822 e - 004 4.2264 e - 003 3.6536 e + 000 9.9738 e - 001 3.6178 e - 003 2.9807 e - 005 2.3649 e - 004 4.8092 e - 004 2.9708 e - 004 3.5621 e - 004 PESA-II 9.2848 e - 003 8.1803 e - 003 3.6469 e + 000 9.8374 e - 001 3.1883 e - 003 5.3690 e - 004 3.2013 e - 004 2.3058 e - 003 3.5627 e - 003 8.5671 e - 004 MODEA 3.5656 e - 004 3.5445 e - 003 3.6527 e + 000 9.9801 e - 001 3.7861 e - 003 3.7248 e - 005 3.2003 e - 004 4.3504 e - 004 2.8079 e - 004 3.2367 e - 004 AOSPEA 1.4636 e - 004 1.9829 e - 003 3.6618 e + 000 9.9931 e + 000 1.5982 e - 004 1.6977 e - 005 2.1056 e - 004 1.2257 e - 004 1.5588 e - 004 1.5130 e - 005  ZDT6 SPEA2 6.1089 e - 004 1.9464 e - 003 3.0328 e + 000 9.9730 e - 001 5.5711 e - 004 2.6390 e - 005 2.5681 e - 004 3.2156 e - 005 3.9657 e - 004 1.5396 e - 005 NSGA-II 7.8852 e - 004 2.8317 e - 003 3.0311 e + 000 9.9718 e - 001 6.4428 e - 003 3.9817 e - 005 2.3655 e - 004 3.6541 e - 005 8.2456 e - 004 4.8106 e - 005 PESA-II 5.1988 e - 004 5.3687 e - 003 3.0284 e + 000 9.9533 e - 001 5.2983 e - 004 2.3642 e - 005 2.9820 e - 004 2.2347 e - 004 5.2107 e - 004 2.5419 e - 005 MODEA 7.3699 e - 004 2.6249 e - 003 3.0338 e + 000 9.9792 e - 001 6.9355 e - 003 3.6078 e - 005 2.6674 e - 004 3.2567 e - 005 8.7635 e - 004 4.5907 e - 005 AOSPEA 2.0740 e - 004 1.5639 e - 003 3.0376 e + 000 9.9861 e - 001 4.3419 e - 004 1.7334 e - 005 1.3660 e - 004 1.2996 e - 005 2.3794 e - 004 1.2755 e - 005Figure 4
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on ZDT2 and ZDT6 test instances.
(a)
ZDT2 (b)
ZDT6Figure5 shows boxplots of the metrics for ZDT1. A boxplot is used to show the statistical results of a group data through five numerical data which are the lower bound, lower quartile, median, upper quartile, and upper bound. For GD, SP, and IGD, the five numerical data of SPEA and AOPSEA are less than others. But AOSPEA is slight better than SPEA2, and AOPSEA is steadier than SPEA2 because the difference of lower quartile and upper quartile of AOSPEA is less than SPEA2. AOSPEA has the same performance with SPEA2 for MS, but AOSPEA is steadier. AOPSEA is better than others for HV and shows good robustness.Figure 5
Boxplots of the metrics for ZDT1.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDTable4 and Figure 6 show statistic values and nondominated solutions on DTLZ test instances. These four problems have three objectives. For GD, AOSPEA is optimal for all the test instances but DTLZ1. For SP, AOSPEA is optimal on DTLZ4 and a little worse than the optimal value on the rest test instances. For MS, AOSPEA and SPEA2 are better than NSGA-II, MODEA, and PESA-II. So AOSPEA has a better diversity considering SP and MS. For HV, AOSPEA is the best of all. For IGD, PESA-II is optimal for all the test instances but DTLZ2. The solutions obtained by PESA-II are easily gathered together due to the fact that the MS of PESA-II is small. So the IGD of PESA-II is optimal for DTLZ test instances. It is clear from Figure 3 that AOSPEA performs much better than the others in terms of diversity. Overall, AOSPEA is better than others for DTLZ test instances.Table 4
Mean values and standard deviations of performance indicators on DTLZ test instances.
Problem Algorithm GD SP HV MS IGD DTLZ1 SPEA2 4.8125 e - 006 2.3621 e - 002 7.8824 e - 001 9.9927 e - 001 7.9758 e - 004 6.3254 e - 007 1.1239 e - 002 3.9501 e - 004 4.2361 e - 004 6.2380 e - 005 NSGA-II 5.9303 e - 006 1.2539 e - 002 7.5291 e - 001 9.8246 e - 001 5.9104 e - 004 6.2413 e - 007 2.6354 e - 002 9.8541 e - 004 5.2146 e - 004 5.6941 e - 005 PESA-II 3.7277 e - 008 1.1629 e - 002 7.3672 e - 001 8.6170 e - 001 4.0547 e - 004 5.4261 e - 009 2.5461 e - 002 8.5421 e - 004 4.8521 e - 004 6.3214 e - 005 MODEA 5.4140 e - 006 1.8241 e - 002 7.8104 e - 001 9.9834 e - 001 6.5028 e - 004 6.2031 e - 007 2.3425 e - 002 9.7452 e - 004 5.7523 e - 004 5.2507 e - 005 AOSPEA 8.6914 e - 007 1.3913 e - 002 7.8933 e - 001 9.9988 e - 001 6.4388 e - 004 3.2262 e - 007 1.8606 e - 002 4.4794 e - 004 8.5999 e - 004 1.8286 e - 005  DTLZ2 SPEA2 5.1666 e - 006 1.2948 e - 002 4.0465 e - 001 9.9997 e - 001 1.0390 e - 003 5.6241 e - 007 3.2154 e - 003 2.1245 e - 003 5.6297 e - 004 8.2415 e - 005 NSGA-II 4.9925 e - 005 4.2959 e - 002 3.7997 e - 001 9.9897 e - 001 1.3961 e - 003 3.5462 e - 006 1.0241 e - 002 6.2584 e - 003 3.4564 e - 004 5.0195 e - 004 PESA-II 7.3671 e - 005 1.9045 e - 002 2.4641 e - 001 6.2671 e - 001 1.4426 e - 003 3.6259 e - 006 2.3124 e - 002 5.3654 e - 003 3.2654 e - 003 4.2381 e - 004 MODEA 4.3248 e - 005 2.8483 e - 002 3.8018 e - 001 9.9899 e - 001 1.1582 e - 003 3.3756 e - 006 1.2531 e - 002 6.3741 e - 003 3.5765 e - 004 5.6021 e - 004 AOSPEA 7.1591 e - 007 1.3037 e - 002 4.1406 e - 001 9.9936 e - 001 6.4520 e - 004 6.9969 e - 007 7.6431 e - 004 1.1547 e - 003 7.3505 e - 004 3.7002 e - 005  DTLZ3 SPEA2 2.1735 e - 005 1.3862 e - 002 4.0516 e - 001 9.9648 e - 001 1.2801 e - 003 2.0841 e - 006 1.2541 e - 003 3.2610 e - 004 3.0214 e - 004 9.0250 e - 004 NSGA-II 1.0351 e - 005 4.1432 e - 002 3.7923 e - 001 9.9911 e - 001 6.8628 e - 004 5.6210 e - 006 3.2514 e - 003 5.2601 e - 003 3.0981 e - 004 8.0214 e - 005 PESA-II 1.8136 e - 005 2.4120 e - 002 1.5832 e - 001 5.0406 e - 001 4.9005 e - 004 2.9015 e - 006 2.3694 e - 003 2.3654 e - 003 3.5089 e - 002 2.3456 e - 005 MODEA 1.6241 e - 005 2.2543 e - 002 3.9348 e - 001 9.9885 e - 001 6.9379 e - 004 5.9015 e - 006 3.5263 e - 003 5.2173 e - 003 3.1092 e - 004 8.5231 e - 005 AOSPEA 1.4928 e - 006 1.5251 e - 002 4.1376 e - 001 9.9914 e - 001 6.2648 e - 004 3.9654 e - 007 1.9804 e - 003 2.1354 e - 004 8.0265 e - 004 5.2245 e - 004  DTLZ4 SPEA2 3.9576 e - 005 1.2211 e - 002 4.0063 e - 001 9.9953 e - 001 1.5867 e - 003 1.2309 e - 006 2.5364 e - 003 4.0167 e - 004 5.0234 e - 004 5.2347 e - 004 NSGA-II 5.4451 e - 005 4.5550 e - 002 3.7327 e - 001 9.9925 e - 001 1.3183 e - 003 1.2354 e - 005 1.2107 e - 002 7.1234 e - 004 1.2547 e - 004 5.6362 e - 004 PESA-II 5.6680 e - 005 4.2256 e - 002 3.2743 e - 001 9.8605 e - 001 9.7414 e - 004 5.4231 e - 006 2.3154 e - 002 2.1563 e - 003 5.2147 e - 003 5.2134 e - 005 MODEA 5.9832 e - 005 3.2566 e - 002 3.9563 e - 001 9.9836 e - 001 1.4924 e - 003 1.3643 e - 005 1.6123 e - 002 7.3201 e - 004 1.8563 e - 004 5.3747 e - 004 AOSPEA 1.4634 e - 005 1.0901 e - 002 4.0934 e - 001 9.9936 e - 001 1.0468 e - 003 5.6842 e - 006 9.2014 e - 004 2.1325 e - 004 9.1231 e - 004 6.9821 e - 004Figure 6
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on DTLZ test instances.
(a)
DTLZ1 (b)
DTLZ4Figure7 shows boxplots of the metrics for DTLZ4. The lower quartile, median quartile, and upper quartile of AOSPEA are less than others for GD, but SPEA is steadier than SPEA2. AOSPEA performs the best for SP and HV and shows better steady. PESA-II has the best value for IGD, but the MS performs the worst. For the value of MS and IGD, AOSPEA shows slighter worse than the best.Figure 7
Boxplots of the metrics for DTLZ4.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDTable5 and Figure 8 show statistic values, nondominated solutions, and boxplots on LZ09 test instances. These eight problems have two objectives except F6 has three objectives. For GD, AOSPEA is optimal on LZ09_F1 and LZ09_F2, PESA-II is optimal on LZ09_F4, LZ09_F5, and LZ09_F9, SPEA2 is optimal on LZ09_F6, and MODEA is optimal on LZ09_F7. AOSPEA is a little worse than the optimal on LZ09_F3, LZ09_F5, LZ09_F6, and LZ09_F9. For SP, AOSPEA is optimal on LZ09_F1 and LZ09_F7, PESA-II is optimal on LZ09_F2, LZ09_F3, LZ09_F6, and LZ09_F9, SPEA2 is optimal on LZ09_F4, and NSGA-II is optimal on LZ09_F5. AOSPEA is a little worse than the optimal on LZ09_F2, LZ09_F3, LZ09_F4, LZ09_F5, and LZ09_F6. For MS, AOSPEA is optimal for all the test instances but LZ09_F1 and LZ09_F7. AOSPEA has the best diversity considering SP and MS. PESA-II has a good SP, but its MS is the worst. For HV, AOSPEA is optimal for all the test instances but LZ09_F7. For IGD, AOSPEA is optimal on LZ09_F1, SPEA2 is optimal on LZ09_F6 and LZ09_F7, and PESA-II is optimal for the rest of test instances. AOPSEA is slightly worse than the optimal for LZ09_F2, LZ09_F5, LZ09_F6, LZ09_F7, and LZ09_F9. Figure 4 shows that AOSPEA have better spread and it is hard to converge for all the algorithms on LZ09_F7 and LZ09_F9. Overall, AOPSEA is better than other algorithms for most of LZ09 test instances.Table 5
Mean values and standard deviations of performance indicators on LZ09 test instances.
Problem Algorithm GD SP HV MS IGD LZ09_F1 SPEA2 3.7556 e - 003 3.5552 e - 002 3.6424 e + 000 9.9340 e - 001 7.7606 e - 003 1.8319 e - 003 3.0150 e - 002 2.0262 e - 002 9.4758 e - 003 4.5673 e - 003 NSGA-II 2.7616 e - 003 8.5761 e - 003 3.6499 e + 000 9.9960 e - 001 3.3906 e - 003 2.1032 e - 003 2.3946 e - 003 2.4461 e - 003 7.7068 e - 004 3.0904 e - 003 PESA-II 2.4732 e - 003 1.4495 e - 002 3.6381 e + 000 9.9267 e - 001 3.2740 e - 003 1.2440 e - 003 7.6753 e - 003 9.0751 e - 003 6.9128 e - 003 2.3093 e - 003 MODEA 1.5258 e - 003 4.4632 e - 003 3.6487 e + 000 9.9326 e - 001 3.7104 e - 003 2.1412 e - 003 2.5382 e - 003 2.5572 e - 003 7.9718 e - 004 3.5101 e - 003 AOSPEA 3.3856 e - 004 2.1617 e - 003 3.6591 e + 000 9.9899 e - 001 3.3817 e - 004 3.8197 e - 005 2.5993 e - 004 3.5637 e - 004 1.1890 e - 003 2.6264 e - 005  LZ09_F2 SPEA2 1.9169 e - 003 1.6310 e - 002 3.3038 e + 000 6.7685 e - 001 1.5532 e - 003 3.3207 e - 003 3.4150 e - 002 1.1211 e - 001 1.5286 e - 001 2.7729 e - 003 NSGA-II 3.2721 e - 003 5.8267 e - 003 3.4290 e + 000 8.8184 e - 001 1.6837 e - 003 2.7291 e - 003 9.4258 e - 003 4.7836 e - 002 1.3044 e - 001 1.4259 e - 003 PESA-II 1.0923 e - 003 8.6235 e - 004 3.1987 e + 000 5.4580 e - 001 5.3251 e - 004 9.0903 e - 004 1.1030 e - 003 1.7616 e - 001 1.5717 e - 001 5.9315 e - 004 MODEA 2.0361 e - 003 5.8738 e - 003 3.4388 e + 000 8.9295 e - 001 1.0004 e - 003 1.9983 e - 003 9.7413 e - 003 4.5487 e - 002 1.5504 e - 001 1.0635 e - 003 AOSPEA 1.5443 e - 003 5.5098 e - 003 3.5931 e + 000 9.3087 e - 001 9.1089 e - 004 4.1867 e - 004 6.8755 e - 003 8.5929 e - 003 4.5133 e - 002 3.0157 e - 004  LZ09_F3 SPEA2 3.3606 e - 003 7.3026 e - 003 3.3997 e + 000 8.1966 e - 001 2.6561 e - 003 3.4579 e - 004 4.9259 e - 003 1.0650 e - 001 1.5015 e - 001 3.1125 e - 004 NSGA-II 4.3339 e - 003 9.8427 e - 003 3.5319 e + 000 9.6780 e - 001 3.5023 e - 003 2.4645 e - 004 6.7163 e - 003 3.6437 e - 002 1.7952 e - 002 3.3908 e - 004 PESA-II 2.6867 e - 003 5.4008 e - 003 3.3372 e + 000 7.4076 e - 001 1.9135 e - 003 7.3607 e - 004 1.7362 e - 003 1.8021 e - 001 2.0984 e - 001 6.7320 e - 004 MODEA 5.0573 e - 003 6.8359 e - 003 3.5621 e + 000 9.7804 e - 001 3.0103 e - 003 2.4645 e - 004 6.4528 e - 003 3.8457 e - 002 13608 e - 002 3.9184 e - 004 AOSPEA 3.1731 e - 003 7.0248 e - 003 3.6167 e + 000 9.9442 e - 001 2.8883 e - 003 2.6854 e - 004 2.6986 e - 003 1.0643 e - 002 5.6899 e - 003 6.4646 e - 004  LZ09_F4 SPEA2 4.0761 e - 003 6.4456 e - 003 3.4087 e + 000 8.4116 e - 001 3.3267 e - 003 6.9912 e - 004 1.5510 e - 003 1.9678 e - 002 4.7887 e - 002 6.2428 e - 004 NSGA-II 3.7630 e - 003 7.3996 e - 003 3.4417 e + 000 8.4098 e - 001 2.9932 e - 003 5.2942 e - 004 2.5646 e - 003 2.7276 e - 002 5.5535 e - 002 4.8189 e - 004 PESA-II 3.6948 e - 003 7.8493 e - 003 3.3937 e + 000 7.7238 e - 001 2.8426 e - 003 9.0100 e - 004 1.0287 e - 003 2.8955 e - 002 3.8750 e - 002 7.6701 e - 004 MODEA 3.8743 e - 003 7.0885 e - 003 3.5228 e + 000 9.4187 e - 001 3.1143 e - 003 5.3053 e - 004 2.6757 e - 003 2.8387 e - 002 5.6646 e - 002 4.9298 e - 004 AOSPEA 4.5735 e - 003 6.6016 e - 006 3.6236 e + 000 9.9572 e - 001 3.2898 e - 003 1.7735 e - 003 2.1646 e - 006 1.1086 e - 002 3.6365 e - 003 4.8174 e - 003  LZ09_F5 SPEA2 4.2443 e - 003 7.6946 e - 003 3.5087 e + 000 9.3333 e - 001 3.9660 e - 003 9.0707 e - 004 5.4273 e - 003 5.0148 e - 002 7.5440 e - 002 1.1625 e - 003 NSGA-II 3.9777 e - 003 5.8253 e - 003 3.5712 e + 000 9.8091 e - 001 3.4926 e - 003 4.9673 e - 004 2.2365 e - 003 2.1052 e - 002 1.6274 e - 002 2.5889 e - 004 PESA-II 2.5690 e - 003 1.4395 e - 002 3.4477 e + 000 8.3870 e - 001 1.8529 e - 003 5.4005 e - 004 1.8361 e - 002 5.7840 e - 002 9.7133 e - 002 4.8959 e - 004 MODEA 2.9658 e - 003 9.9364 e - 003 3.5832 e + 000 9.9562 e - 001 3.5047 e - 003 4.8584 e - 004 2.6534 e - 003 2.2602 e - 002 1.5383 e - 002 2.8994 e - 004 AOSPEA 2.6175 e - 003 6.8127 e - 003 3.6261 e + 000 9.9676 e - 001 3.0101 e - 003 7.1940 e - 004 2.1710 e - 003 6.0387 e - 003 4.6184 e - 003 2.0291 e - 003  LZ09_F6 SPEA2 1.0019 e - 003 1.2787 e - 001 2.4692 e - 001 9.9883 e - 001 7.2812 e - 002 5.5156 e - 004 4.2707 e - 002 8.5666 e - 003 1.1774 e - 004 2.0840 e - 002 NSGA-II 7.0744 e - 003 2.2985 e - 001 1.5436 e - 001 9.7899 e + 000 1.6556 e - 001 8.7776 e - 003 1.9554 e - 001 6.5348 e - 002 7.7052 e - 006 8.6470 e - 002 PESA-II 3.0472 e - 002 1.0007 e - 001 9.1255 e - 002 6.6200 e - 001 2.1902 e - 001 2.0434 e - 002 1.1519 e - 001 1.2405 e - 001 1.7424 e - 001 1.6415 e - 001 MODEA 5.3345 e - 003 2.1874 e - 001 1.5456 e - 001 9.8768 e + 000 1.7667 e - 001 8.5666 e - 003 1.3448 e - 001 6.7324 e - 002 7.1618 e - 006 8.9635 e - 002 AOSPEA 4.2271 e - 003 1.2543 e - 001 2.9381 e - 001 9.9923 e - 001 1.5651 e - 001 8.3194 e - 003 1.4478 e - 001 5.9100 e - 002 1.2849 e - 003 1.6190 e - 001  LZ09_F7 SPEA2 2.7152 e - 003 1.8610 e - 002 2.7996 e + 000 2.6474 e - 001 1.6641 e - 003 3.2924 e - 003 2.7461 e - 002 1.7878 e - 001 2.8438 e - 001 1.6817 e - 003 NSGA-II 1.4830 e - 002 1.1319 e - 003 3.0175 e + 000 5.5930 e - 001 1.3810 e - 002 1.5153 e - 002 1.4869 e - 003 2.3518 e - 001 1.9580 e - 001 1.5221 e - 002 PESA-II 8.6571 e - 003 6.3791 e - 003 2.7293 e + 000 3.1134 e - 001 6.9771 e - 003 9.2704 e - 003 8.2636 e - 003 2.0280 e - 001 1.9539 e - 001 7.7519 e - 003 MODEA 1.9428 e - 003 1.8242 e - 003 2.8634 e + 000 3.4062 e - 001 1.0021 e - 002 1.2626 e - 003 1.5976 e - 003 2.9264 e - 001 1.9748 e - 001 1.2336 e - 002 AOSPEA 3.0445 e - 003 5.0273 e - 004 2.9012 e + 000 3.4429 e - 001 2.5283 e - 003 4.2071 e - 003 6.3906 e - 004 2.2058 e - 001 2.7334 e - 001 3.2431 e - 003  LZ09_F9 SPEA2 1.3536 e - 003 2.5205 e - 003 3.1197 e + 000 9.5827 e - 001 9.9841 e - 004 1.0519 e - 003 1.3774 e - 003 9.1038 e - 002 6.1881 e - 002 1.0710 e - 003 NSGA-II 3.5979 e - 003 7.1248 e - 003 3.0928 e + 000 9.4306 e - 001 1.7312 e - 003 5.1786 e - 003 8.3145 e - 003 7.2511 e - 002 5.6148 e - 002 2.2128 e - 003 PESA-II 2.0336 e - 004 8.4083 e - 004 2.7822 e + 000 7.3696 e - 001 1.5132 e - 004 6.1281 e - 005 2.6371 e - 004 2.4980 e - 001 2.0321 e - 001 3.1092 e - 005 MODEA 2.1416 e - 003 6.7310 e - 003 3.1039 e + 000 9.6328 e - 001 1.1324 e - 003 5.7982 e - 003 8.6524 e - 003 7.2263 e - 002 5.7305 e - 002 2.9323 e - 003 AOSPEA 5.5511 e - 004 4.2319 e - 003 3.2355 e + 000 9.7243 e - 001 3.1984 e - 004 1.9785 e - 004 6.7590 e - 003 1.0563 e - 001 5.9679 e - 002 9.0466 e - 005Figure 8
Nondominated solutions obtained by SPEA2 (left), NSGA-II (second from left), PESA-II (third from left), MODEA (forth from left), and AOSPEA (right) on LZ09 test instances.
(a)
LZ09_F2 (b)
LZ09_F4 (c)
LZ09_F5 (d)Figure9 shows boxplots of the metrics for LA09_F1. The lower quartile, median quartile, and upper quartile of AOSPEA perform the best for GD, SP, HV, and IGD and show the best robustness at the same time. AOSPEA performs slighter worse than NSGA-II and NSGA-II obtains the best maximum spread. AOSPEA shows the best convergence and diversity on LA09_F1.Figure 9
Boxplots of the metrics for LA09_F1.
(a)
GD (b)
SP (c)
HV (d)
MS (e)
IGDFor LZ problems, AOSPEA was compared with other four typical MOEAS which are SPEA2, NSGA-II, PESA-II, and MODEA. For NSGA-II, it adopts the operation-based representation to encode a chromosome. The POX crossover method and bit-flip mutation are used as reproduction operators. The probability of crossover and mutation are set to 0.5 and 0.1, respectively. The population size is set to 30. The other settings of the above algorithms keep consistent with the proposed algorithm. Each instance is executed by SPEA2, NSGA-II, PESA-II, and MODEA for 20 times independently, respectively. Table6 reports the computational results obtained by SPEA2, NSGA-II, PESA-II, and MODEA. Table 6 includes problem name (Instances) and problem size (Dimension). The results of the mean relative error (MRE, MRE=100×(MRE-BKS(orUB))/BKS(orUB)) and the running time (CPU times) of AOSPEA, SPEA2, NSGA-II, PESA-II, and MODEA. The graphical representation in Figure 10 shows the comparison of benchmark standard problems results obtained from AOSPEA with SPEA2, NSGA-II, PESA-II, and MODEA. From Table 5, we know that the results obtained by the proposed algorithms are better than these four typical algorithms. Although AOSPEA does not obtain the best known solutions in the number of generations for large problems, the evolutionary trend of the population does not stagnate. That is to say, AOSPEA can further optimize obtaining the better solution. Meanwhile, the CPU time of all the compared algorithms is provided in Figure 11; it can be seen that the running time of AOSPEA is also superior to other algorithms. The population size of SPEA2, NSGA-II, PESA-II, and MODEA must keep a certain scale; otherwise they are easily trapped in local optimum, but the large population will increase the running time. AOSPEA has strong disturbance capacity, so even if the population is relatively small, it can boost the searching and readily escape the local optimum.Table 6
Results using AGS_PAES for MK problems.
Instance Dimension AOSPEA SPEA2 NSGA-II PESA-II MODEA MRE CPU times MRE CPU times MRE CPU times MRE CPU times MRE CPU times ZDT1 30 4.003 735.1 4.591 839.6 4.612 856.9 5.317 857.5 5.401 858.9 ZDT2 30 4.892 725.9 4.445 841.5 4.961 837.7 5.116 848.3 5.921 849.7 ZDT3 30 5.129 100.3 5.312 150.3 5.378 125.4 5.865 126.6 5.977 127.3 ZDT4 10 5.549 273.3 6.068 378.1 6.543 405.1 6.651 415.7 7.076 417.1 ZDT6 10 6.002 479.5 6.132 592.1 6.298 601.3 6.769 621.9 8.012 633.3 DTLZ1 7 4.198 279.1 4.226 399.8 4.331 400.9 4.821 401.5 5.086 412.9 DTLZ2 12 5.012 434.8 5.203 531.1 5.302 556.6 5.825 557.2 6.325 568.6 DTLZ3 12 3.471 499.2 3.821 645.1 4.828 621.0 5.336 621.6 6.253 633.1 DTLZ4 12 4.021 619.6 4.325 778.9 5.952 781.4 5.409 812.9 6.612 824.3 LZ09_F1 10 5.887 647.3 6.208 751.2 6.802 789.1 7.337 829.7 8.389 831.1 LZ09_F2 30 9.021 1415.1 9.101 1781.2 9.199 1576.9 9.657 1597.5 10.897 1618.9 LZ09_F3 30 7.312 1268 7.625 1459.9 7.883 1469.8 8.331 1480.4 9.441 1501.8 LZ09_F4 30 8.872 1199.8 9.105 1410.1 9.919 1461.6 9.664 1472.2 9.982 1483.6 LZ09_F5 30 5.885 1170.3 6.115 1312.9 6.231 1332.1 6.723 1362.7 6.905 1399.1 LZ09_F6 10 9.002 1149.7 9.205 1341.1 9.902 1361.5 10.008 1392.1 12.911 1419.5 LZ09_F7 10 8.884 1074.4 9.012 1231.1 9.218 1236.2 9.733 1266.8 10.023 1289.2 LZ09_F9 30 5.768 1141.9 6.003 1366.5 6.177 1399.7 6.691 1430.3 7.116 1459.7 MRE — 7.395 — 7.552 — 7.629 — 7.895 — 8.915 —Figure 10
MRE of AOSPEA algorithm compared with SPEA2, NSGA-II, PESA-II, and MODEA.Figure 11
CPU time of AOSPEA compared with SPEA2, NSGA-II, PESA-II, and MODEA.


## 5. Conclusion and Future Work

In this paper, an improved SPEA2 algorithm with adaptive selection of evolutionary operators is proposed. Various evolutionary operators and hybrid evolutionary methods are employed, which can greatly improve the searching ability. The adaptive scheme can select the corresponding operators according to their contribution to the external archive in the whole evolutionary process. This kind of selective way can make sure the proposed algorithm achieves the optimal values as soon as possible. Meanwhile, a minimum selection probability is also set to avoid some operators which would have strong search ability in the remaining process of the algorithm. The experimental results verify these points.In spite of good results which are achieved, there are some shortcomings related the proposed algorithm. The strength of the AOSPEA is not quite obvious while optimizing the instances with high dimensions. Besides, there is no reliable method to set the value of minimum selection probability.Further research will be conducted in following directions. Firstly, we will consist in improving the performance of AOSPEA by making use of the adaptive scheme to mutation operator and verifying its efficiency through a comparison with other types of MOEAs. Secondly, more than two objectives in the MOPs will be studied. Finally, the improved AOSPEA will be utilized to solve the multiobjective job shop and flow shop scheduling problems.



---

*Source: 8010346-2016-11-29.xml*