# Multiobjective Differential Evolution Algorithm with Multiple Trial Vectors

Authors: Yuelin Gao; Junmei Liu
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

This paper presents a multiobjective differential evolution algorithm with multiple trial vectors. For each individual in the population, three trial individuals are produced by the mutation operator. The offspring is produced by using the crossover operator on the three trial individuals. Good individuals are selected from the parent and the offspring and then are put in the intermediate population. Finally, the intermediate population is sorted according to the Pareto dominance relations and the crowding distance, and then the outstanding individuals are selected as the next evolutionary population. Comparing with the classical multiobjective optimization algorithm NSGA-II, the proposed algorithm has better convergence, and the obtained Pareto optimal solutions have better diversity.


---

## Body

## 1. Introduction

Multiobjective optimization problems (MOPs) are different from single objective optimization problems (SOPs). For MOPs, the objective functions are often conflict, so the best solution often does not exist. It is difficult to find the optimal solution. The MOPs need to find a noninferior solution set that is called Pareto optimal solution set (or nondominated optimal solution set). The key is to find a solution set which is as close to the Pareto front and uniformly distributed as possible. In the past ten years, evolutionary algorithms have been widely used for solving multiobjective optimization problems. The typical algorithm contains NSGA [1], NSGA-II [2], SPEA [3], SPEA2 [4], and so on.Differential evolution (DE) [5] is an important branch of the evolutionary algorithms. Because of its easiness to use and robustness, it has been widely applied in many fields. The basic DE algorithm is a greedy algorithm and is used to solve the SOPs. The individual choice is based on the objective function value. In solving MOPs, the objective function value is a vector value and the individual choice is based on the vector value. Some scholars have improved DE algorithm to solve MOPs. Abbass et al. [6] proposed a differential evolution algorithm based on the Pareto front’s (PDE) to solve MOPs. Later, the PDE algorithm is improved to an adaptive PDE algorithm (SPDE) [7]. Madavan [8] proposed the differential evolution algorithm based on the Pareto (PDEA). Xue et al. [9] and Robi and Filipi [10] and Qian and Li [11] proposed the different kind of multiobjective differential evolution algorithm. Gong and Cai [12] proposed an improved multiobjective differential evolution based on the Pareto-adaptive ε-dominance and the orthogonal design.Here, a multiobjective differential evolution algorithm with multiple trial vectors (MTVDE) is proposed. In this algorithm, for each individual in the parent, three different mutation operators and a crossover operator are used to produce three trial individuals. First, we compare the three trial individuals. If an individual Pareto-dominate another, the better one is retained. If two individuals do not dominate each other, both two individuals are retained. Secondly, retained trial individuals compare with the parent individual: if an individual Pareto-dominate another, put the nondominated individual in the intermediate population, and if the two individuals do not dominate each other, two individuals are put in the intermediate population. Finally, in the intermediate population, the individuals are sorted according to the Pareto dominance relations and the crowding distance. We eliminate some low-quality individuals from the intermediate population and retain some fine individuals to form the next evolutionary population. The individuals are sorted according to the nondominated relations, and individuals with low ordinal value are better individuals. When individuals are with the same ordinal, the individual of larger crowding distance is better than the individual of smaller crowding distance.


## 2. Multiobjective Optimization Problem and Related Concepts

Below, we give several concepts related to this paper. Because the maximum optimization problems and minimum optimization problem can be transformed into each other, here we only consider the minimum multiobjective optimization problem.Definition 2.1 (multiobjective optimization problems, MOPs).
The MOPs are described as follows:(2.1)min⁡⁡y=f(x)=(f1(x),f2(x),…,fk(x)),s.t.s.g(x)=(g1(x),g2(x),…,gl(x))≤0,s.t.s.s.h(x)=(hl+1(x),hl+2(x),…,hm(x))=0,s.t.s.s.x=(x1,x2,…,xn)∈X,s.t.s.s.y=(y1,y2,…,yk)∈Y,
where y∈Rk indicates the target vector, x∈Rn indicates the decision vector, X indicates decision space of the decision vector x,   Y indicates the target space of the target vector y.Definition 2.2 (the dominance relationship of the target vector).
The target vectoru=(u1,u2,…,uk) is better than v=(v1,v2,…,vk) if and only if for all i∈(1,2,…,k)  ul≤vl and there exists at least one i∈(1,2,…,k) such that ui<vi was established, then the target the vector u Pareto better than v, or v Pareto inferior to u.Definition 2.3 (decision vector relations of domination).
If the decision vectorz=(z1,z2,…,zn) Pareto-dominates w=(w1,w2,…,wn) if and only if f(z) Pareto is superior to f(w), we call the decision vector z Pareto-dominating w or the decision vector w is Pareto dominated by z.Definition 2.4 (Pareto optimal solution).
Decision vectorxu∈F (F is the feasible solution set) is a Pareto optimal solution, if and only if an individual does not exist in the feasible solution set F dominate xu, then xu is called the MOPs’ Pareto optimal solution, or xu is called the MOPs’ nondominated optimal solution. The set of all Pareto optimal solution is known as the MOPs’ Pareto optimal solution set or nondominated optimal solution set.Definition 2.5 (Pareto front).
For given MOPs, Pareto optimal solution set corresponding to the objective function value vector is known as the MOPs’ Pareto front. Therefore, our task is to make the current nondominated optimal solution set as close as possible to the theoretical Pareto optimal solution set, from the view of Pareto front is to ask the Pareto front as possible as close to the theoretical Pareto front and uniformly distributed.Definition 2.6 (individual nondominant relationship sort, INDR).
There aren individuals in the population P. For each individual xi,i=1,2,…,n,  Si represents the set of individuals that are dominated by xi, ni represents the number of individuals dominating the individual xi. Finally, if ni=0, then xi belongs to the first level. The sequence of xi is ranki=1, xi joined to F1 (F1 indicates the individual set of ordinal value is 1). The counter of the initial sequence value rank=1, if Frank≠ϕ, (Frank represents the set of individuals’ sequence value rank=1) each individual xi in Frank, each individual xi,nj=nj-1 in the corresponding Si. Finally, if ni=0, then xj belongs to the rank+1 level. The sequence value of xj is rankj=rank+1. Update sequence value’s counter rank=rank+1, xj joined to Frank. As a result, we can calculate the ordinal value of each individual in the population P.Definition 2.7 (the same level of individuals’ crowding distance) (ICD).
LetI be a set of individuals of a certain grade. All the target m(m=1,2,…) individuals are sorted according to the objective function value in I. The first and the last individuals’ crowding distances are infinite. The other individuals’ crowding distance is calculated as subtract the two neighbor individuals’ objective function and then square it. Then sum the crowding distance on all objective functions as the individuals’ crowding distance. The individuals are sorted according to crowding distance in the same level.


## 3. Multiobjective Differential Evolution Algorithm with Multiple Trial Vectors (MTVDE)

### 3.1. The Mutation Operation

Mutation components are difference vectors of the parent generation. Each vector is generated by the different individuals in the parent population. The mutation operation on the basis of the difference vector and its equation is(3.1)vi1t=xit+F(xr1t-xr2t),vi2t=xr1t+F(xr2t-xr3t),vi3t=xit+F(xr1t-xr2t)+F(xr3t-xr4t),
where vi1t,vi2t,vi3t are the mutated individuals, xit is individual of parent population. xr1t,xr2t,xr3t,xr4t are different from each other, and they are different from xit. F∈(0,2] is the scaling factor. It indicates the influence degree of the difference vector to the offspring. From the mutation operator, each individual in parent population produces three individuals through the mutation operator, which can enhance the diversity of the population.The value ofF has a certain influence on the algorithm performance. If F is too large, the convergence rate slows, and the algorithm runs longer. If F is too small, the diversity of the population decreases, according to experimental tests, and F is often set to 0.5.


### 3.2. Crossover Operator

The mutated individualvi(t+1),(i=i1,i2,i3), and the individual xi(t) in parent population use the crossover operator to generate the trial individual ui(t+1),(i=i1,i2,i3). The crossover operator is expressed as
(3.2)uij(t+1)={vij(t+1),if(rand(0,1)≤CR)or(j=randi(1,D)),xij(t),otherwise,
where rand(0,1) is an uniformly distributed random number between (0,1), randi(1,D) is the integer randomly selected from {1,2,…,D}, which can insure at least one ui(t+1) is from vi(t+1). CR∈[0,1] is the crossover probability. It is used to control the variable in ui(t+1) to be from vi(t+1) or xi(t). If CR=1, then ui(t+1)=vi(t+1).


### 3.3. Selecting Operation

For MOPs, this paper uses the following criteria to select the next evolution population.(1)
For each individual in the parent population, three different mutated operators and a crossover operator are used to produce three trial individuals. For the three trial individuals and the parent individual, the one who Pareto-dominates another is retained in the intermediate population. If the two individuals do not dominate each other, both are retained.(2)
Some low-quality individuals in the intermediate population need elimination. Individuals are sorted in the intermediate population according to the Pareto dominance relations and the crowding distance of individuals. First of all, the individuals are divided into several levels according to the non-dominant relations in the intermediate population. Individuals in the same level are sorted according to the crowding distance. We choose the former NP individuals to form the next evolution population.


### 3.4. MTVDE Description of the Algorithm

Step 1.
Set the basic parameters: the population size NP, the scaling factorF, the maximum evolution generation, and the crossover probability factor CR.Step 2.
Initialize the population.Step 3.
Mutation is according to the mutation operation (3.1) to generate three variation individuals.Step 4.
Crossover is according to the crossover operation (3.2) to generate three test individuals.Step 5.
Select the next evolution population.Step 6.
If the maximum iteration is reached, stop and output optimal solution, otherwise return to Step3.


## 3.1. The Mutation Operation

Mutation components are difference vectors of the parent generation. Each vector is generated by the different individuals in the parent population. The mutation operation on the basis of the difference vector and its equation is(3.1)vi1t=xit+F(xr1t-xr2t),vi2t=xr1t+F(xr2t-xr3t),vi3t=xit+F(xr1t-xr2t)+F(xr3t-xr4t),
where vi1t,vi2t,vi3t are the mutated individuals, xit is individual of parent population. xr1t,xr2t,xr3t,xr4t are different from each other, and they are different from xit. F∈(0,2] is the scaling factor. It indicates the influence degree of the difference vector to the offspring. From the mutation operator, each individual in parent population produces three individuals through the mutation operator, which can enhance the diversity of the population.The value ofF has a certain influence on the algorithm performance. If F is too large, the convergence rate slows, and the algorithm runs longer. If F is too small, the diversity of the population decreases, according to experimental tests, and F is often set to 0.5.


## 3.2. Crossover Operator

The mutated individualvi(t+1),(i=i1,i2,i3), and the individual xi(t) in parent population use the crossover operator to generate the trial individual ui(t+1),(i=i1,i2,i3). The crossover operator is expressed as
(3.2)uij(t+1)={vij(t+1),if(rand(0,1)≤CR)or(j=randi(1,D)),xij(t),otherwise,
where rand(0,1) is an uniformly distributed random number between (0,1), randi(1,D) is the integer randomly selected from {1,2,…,D}, which can insure at least one ui(t+1) is from vi(t+1). CR∈[0,1] is the crossover probability. It is used to control the variable in ui(t+1) to be from vi(t+1) or xi(t). If CR=1, then ui(t+1)=vi(t+1).


## 3.3. Selecting Operation

For MOPs, this paper uses the following criteria to select the next evolution population.(1)
For each individual in the parent population, three different mutated operators and a crossover operator are used to produce three trial individuals. For the three trial individuals and the parent individual, the one who Pareto-dominates another is retained in the intermediate population. If the two individuals do not dominate each other, both are retained.(2)
Some low-quality individuals in the intermediate population need elimination. Individuals are sorted in the intermediate population according to the Pareto dominance relations and the crowding distance of individuals. First of all, the individuals are divided into several levels according to the non-dominant relations in the intermediate population. Individuals in the same level are sorted according to the crowding distance. We choose the former NP individuals to form the next evolution population.


## 3.4. MTVDE Description of the Algorithm

Step 1.
Set the basic parameters: the population size NP, the scaling factorF, the maximum evolution generation, and the crossover probability factor CR.Step 2.
Initialize the population.Step 3.
Mutation is according to the mutation operation (3.1) to generate three variation individuals.Step 4.
Crossover is according to the crossover operation (3.2) to generate three test individuals.Step 5.
Select the next evolution population.Step 6.
If the maximum iteration is reached, stop and output optimal solution, otherwise return to Step3.


## 4. Numerical Experiments

### 4.1. Algorithm Performance Evaluation Criteria

Multiobjective optimization algorithm performance can be evaluated by two criteria.(1)
The obtained nondominated optimal solution set needs to be as close as possible to the true Pareto front.(2)
The obtained nondominated optimal solution set need as possible as uniformly distribute to the true Pareto front.The two indexes are used to test the convergence and distribution of the solution set, respectively. The definitions of the approximation index and the uniformity index are given below.(a) Approximation index is defined as follows:(4.1)γ=∑i=1ndin,
where n is the number of vectors in the set of nondominated solutions found so far, di is the Euclidean distance (measured in objective space) between each of these solutions and the nearest member of the Pareto optimal set. di is calculated as di=min{|Xi-Yj|,j=1,2,…,N}, where N denotes the total number of the true Pareto front vectors, Xi denotes the nondominated optimal solutions set, Yj denotes the true Pareto front, and |·| denotes Euclidean distance. The value of  γ is smaller, the degree of algorithm approximating to  true Pareto front is higher. It is clear that a value γ=0 indicates that all the generated elements are in the Pareto front.(b) The uniformity index is defined as follows:(4.2)Δ=df+dl+∑i=1n-1|di-d-|df+dl+(n-1)d-,
where di is the Euclidean distance between neighboring solutions in the obtained nondominated solutions set and d- is the mean of all di. The parameters df and dl are the Euclidean distances between the extreme solutions and the boundary solutions of the obtained nondominated set. df is calculated as df=|Xf-Yf|, where Xf is the leftmost vector of obtained nondominated optimal target vector, Yf is the leftmost vector of theoretical Pareto front. dl is calculated as dl=|Xl-Yl|, where Xl is the rightmost vector of obtained nondominated optimal target vector, Yf is the rightmost vector of theoretical Pareto front, |·| denotes Euclidean distance. The value of Δ is smaller, the degree of obtained nondominated solutions’ diversity and uniform distribution is better.


### 4.2. Numerical Experiments and Analysis

In order to know how competitive the MTVDE algorithm was, it was compared with NSGA-II. In algorithm NSGA-II,ηc=20, ηm=20 Pool size = 100, Tour size = 2. In MTVDE algorithm, CR = 0.9 except the problem ZDT4 that CR = 0.3. For all test functions, the population size of the two algorithms is taken as 100, and the number of iterations is taken as 250. Figures 1, 2, 3, 4, 5, 6, 7 and 8 show the results of the MTVDE algorithm by testing eight multiobjective functions. It can be seen from the figures the MTVDE algorithm produces a more uniform solution, and the solution quality is better than NSGA-II.Figure 1
ZDT1.Figure 2
ZDT2.Figure 3
ZDT3.Figure 4
ZDT4.Figure 5
ZDT6.Figure 6
SCH.Figure 7
DTLZ1.Figure 8
DTLZ2.From Tables1, 2, 3, 4, 5 and 6 eight testing functions are chosen to test the approximation index, uniformity index (mean value and variance in 10 runs). For the first five functions, the MTVDE algorithm is compared with the five classic algorithms in [8, 9, 11, 12]. For the rest three functions, the MTVDE algorithm is compared with NSGA2.Table 1
Testing result’s statistics of the problem ZDT1.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.033482
±
0.004750
0.390307
±
0.001876
NSGA-II (binary-coded)
0.000894
±
0.000000
0.463292
±
0.041622
SPEA
0.001799
±
0.000001
0.784525
±
0.004440
PAES
0.082085
±
0.008679
1.229794
±
0.000742
PDEA
N/A
0.298567
±
0.000742
MODE
0.005800
±
0.000000
N/A
MTVDE
0.0012
00
±
0.000002
0.5
0
58
00
±
0.0032
00Table 2
Testing result’s statistics of the problem ZDT2.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.072391
±
0.031689
0.430776
±
0.004721
NSGA-II (binary-coded)
0.000824
±
0.000000
0.435112
±
0.024607
SPEA
0.001339
±
0.000000
0.755184
±
0.004521
PAES
0.126276
±
0.036877
1.165942
±
0.007682
PDEA
N/A
0.317958
±
0.001389
MODE
0.005500
±
0.000000
N/A
MTVDE
0.0047
00
±
0.000006
0.6459
00
±
0.002600Table 3
Testing result’s statistics of the problem ZDT3.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.114500
±
0.004940
0.738540
±
0.019706
NSGA-II (binary-coded)
0.043411
±
0.000042
0.575606
±
0.005078
SPEA
0.047517
±
0.000047
0.672938
±
0.003587
PAES
0.023872
±
0.000010
0.789920
±
0.001653
PDEA
N/A
0.623812
±
0.000225
MODE
0.021560
±
0.000000
N/A
MTVDE
0.006000
±
0.000002
0.604400
±
0.000326Table 4
Testing result’s statistics of the problem ZDT4.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.513053
±
0.118460
0.702612
±
0.064648
NSGA-II (binary-coded)
3.227636
±
7.307630
0.479475
±
0.009841
SPEA
7.340299
±
6.572516
0.798463
±
0.014616
PAES
0.854816
±
0.527238
0.870458
±
0.101399
PDEA
N/A
0.840852
±
0.035741
MODE
0.638950
±
0.500200
N/A
MTVDE
0.0052
00
±
0.00000
2
0.7445
00
±
0.0035
00Table 5
Testing result’s statistics of the problem ZDT6.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.296564
±
0.013135
0.668025
±
0.009923
NSGA-II (binary-coded)
7.806798
±
0.001667
0.644477
±
0.035042
SPEA
0.221138
±
0.000449
0.849389
±
0.002713
PAES
0.085469
±
0.006664
1.153052
±
0.003916
PDEA
N/A
0.473074
±
0.021721
MODE
0.026230
±
0.000861
N/A
MTVDE
0
.
000
4
14
±
3.4014
e
-
009
0.9263
00
±
0.000
895Table 6
Testing result’s statistics of the problems SCH, DTLZ1, and DTLZ2.
Problem
Algorithm
Convergence metric
Diversity metric
SCH
NSGA-II
0.0076
±
6.2023
e
-
008
0.8471
±
1.9253
e
-
004
MTVDE
0.008
4
±
1.2296
e
-
007
0.8728
±
8.0547
e
-
005
DTLZ1
NSGA-II
7.4592
00
±
12.42210
1.0205
0
±
0.0059
00
MTVDE
0.023200
±
0.000014
0.7749
00
±
0.0023
00
DTLZ2
NSGA-II
0.6591
00
±
0.0040
00
0.914300
±
0.0027
00
MTVDE
0.5129
00
±
0.0011
00
0.6470
00
±
0.0015
00N/A denotes the algorithm does not calculate the index; the PDEA algorithm in [7] calculates the index GD (generational distance) instead of calculating the index (the convergence metric). The MODE algorithm in [7] did not calculate the index (diversity metric). We can be seen from Tables 1–6 that MTVDE algorithm has better convergence solutions except the problems ZDT1, ZDT2, and SCH.In this paper, the population size is 250. Through experiments, we found that the increasing of population size has no effect on performance of the algorithm but only can increase the running time. In order to detect the impact of the scaling factor and the crossover probability on performance of algorithm, we make 50 times independent experiments for problem SCH. In order to test the impact ofF and CR on the algorithm performance, it can be found that the F and CR have little effect on the algorithm performance by the testing data. Through comparison, F=0.5, CR = 0.9 results are a little better, but the algorithm performance (approximation index and uniformity index) is not particularly sensitive to the values of F and CR (Table 7).Table 7
F
CR
Convergence metric
Diversity metric
0.1
0.9
0.0086
±
1.9976
e
-
007
0.9551
±
1.8152
e
0.3
0.9
0.0090
±
1.4876
e
-
007
0.9361
±
1.6769
e
0.5
0.9
0.0084
±
1.2296
e
-
007
0.8728
±
8.0547
e
0.7
0.9
0.0091
±
1.9254
e
-
007
0.9281
±
1.4343
e
0.9
0.9
0.0088
±
9.4253
e
-
008
0.9276
±
1.9030
e
0.5
0.1
0.0088
±
7.6655
e
-
008
0.9258
±
1.6304
e
0.5
0.3
0.0089
±
1.4744
e
-
007
0.9283
±
2.0532
e
0.5
0.5
0.0091
±
2.8769
e
-
008
0.9327
±
1.1066
e
0.5
0.7
0.0091
±
1.5230
e
-
007
0.9313
±
5.6436
e
0.5
0.9
0.0084
±
1.2296
e
-
007
0.8728
±
8.0547
e


## 4.1. Algorithm Performance Evaluation Criteria

Multiobjective optimization algorithm performance can be evaluated by two criteria.(1)
The obtained nondominated optimal solution set needs to be as close as possible to the true Pareto front.(2)
The obtained nondominated optimal solution set need as possible as uniformly distribute to the true Pareto front.The two indexes are used to test the convergence and distribution of the solution set, respectively. The definitions of the approximation index and the uniformity index are given below.(a) Approximation index is defined as follows:(4.1)γ=∑i=1ndin,
where n is the number of vectors in the set of nondominated solutions found so far, di is the Euclidean distance (measured in objective space) between each of these solutions and the nearest member of the Pareto optimal set. di is calculated as di=min{|Xi-Yj|,j=1,2,…,N}, where N denotes the total number of the true Pareto front vectors, Xi denotes the nondominated optimal solutions set, Yj denotes the true Pareto front, and |·| denotes Euclidean distance. The value of  γ is smaller, the degree of algorithm approximating to  true Pareto front is higher. It is clear that a value γ=0 indicates that all the generated elements are in the Pareto front.(b) The uniformity index is defined as follows:(4.2)Δ=df+dl+∑i=1n-1|di-d-|df+dl+(n-1)d-,
where di is the Euclidean distance between neighboring solutions in the obtained nondominated solutions set and d- is the mean of all di. The parameters df and dl are the Euclidean distances between the extreme solutions and the boundary solutions of the obtained nondominated set. df is calculated as df=|Xf-Yf|, where Xf is the leftmost vector of obtained nondominated optimal target vector, Yf is the leftmost vector of theoretical Pareto front. dl is calculated as dl=|Xl-Yl|, where Xl is the rightmost vector of obtained nondominated optimal target vector, Yf is the rightmost vector of theoretical Pareto front, |·| denotes Euclidean distance. The value of Δ is smaller, the degree of obtained nondominated solutions’ diversity and uniform distribution is better.


## 4.2. Numerical Experiments and Analysis

In order to know how competitive the MTVDE algorithm was, it was compared with NSGA-II. In algorithm NSGA-II,ηc=20, ηm=20 Pool size = 100, Tour size = 2. In MTVDE algorithm, CR = 0.9 except the problem ZDT4 that CR = 0.3. For all test functions, the population size of the two algorithms is taken as 100, and the number of iterations is taken as 250. Figures 1, 2, 3, 4, 5, 6, 7 and 8 show the results of the MTVDE algorithm by testing eight multiobjective functions. It can be seen from the figures the MTVDE algorithm produces a more uniform solution, and the solution quality is better than NSGA-II.Figure 1
ZDT1.Figure 2
ZDT2.Figure 3
ZDT3.Figure 4
ZDT4.Figure 5
ZDT6.Figure 6
SCH.Figure 7
DTLZ1.Figure 8
DTLZ2.From Tables1, 2, 3, 4, 5 and 6 eight testing functions are chosen to test the approximation index, uniformity index (mean value and variance in 10 runs). For the first five functions, the MTVDE algorithm is compared with the five classic algorithms in [8, 9, 11, 12]. For the rest three functions, the MTVDE algorithm is compared with NSGA2.Table 1
Testing result’s statistics of the problem ZDT1.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.033482
±
0.004750
0.390307
±
0.001876
NSGA-II (binary-coded)
0.000894
±
0.000000
0.463292
±
0.041622
SPEA
0.001799
±
0.000001
0.784525
±
0.004440
PAES
0.082085
±
0.008679
1.229794
±
0.000742
PDEA
N/A
0.298567
±
0.000742
MODE
0.005800
±
0.000000
N/A
MTVDE
0.0012
00
±
0.000002
0.5
0
58
00
±
0.0032
00Table 2
Testing result’s statistics of the problem ZDT2.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.072391
±
0.031689
0.430776
±
0.004721
NSGA-II (binary-coded)
0.000824
±
0.000000
0.435112
±
0.024607
SPEA
0.001339
±
0.000000
0.755184
±
0.004521
PAES
0.126276
±
0.036877
1.165942
±
0.007682
PDEA
N/A
0.317958
±
0.001389
MODE
0.005500
±
0.000000
N/A
MTVDE
0.0047
00
±
0.000006
0.6459
00
±
0.002600Table 3
Testing result’s statistics of the problem ZDT3.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.114500
±
0.004940
0.738540
±
0.019706
NSGA-II (binary-coded)
0.043411
±
0.000042
0.575606
±
0.005078
SPEA
0.047517
±
0.000047
0.672938
±
0.003587
PAES
0.023872
±
0.000010
0.789920
±
0.001653
PDEA
N/A
0.623812
±
0.000225
MODE
0.021560
±
0.000000
N/A
MTVDE
0.006000
±
0.000002
0.604400
±
0.000326Table 4
Testing result’s statistics of the problem ZDT4.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.513053
±
0.118460
0.702612
±
0.064648
NSGA-II (binary-coded)
3.227636
±
7.307630
0.479475
±
0.009841
SPEA
7.340299
±
6.572516
0.798463
±
0.014616
PAES
0.854816
±
0.527238
0.870458
±
0.101399
PDEA
N/A
0.840852
±
0.035741
MODE
0.638950
±
0.500200
N/A
MTVDE
0.0052
00
±
0.00000
2
0.7445
00
±
0.0035
00Table 5
Testing result’s statistics of the problem ZDT6.
Algorithm
Convergence metric
Diversity metric
NSGA-II (real-coded)
0.296564
±
0.013135
0.668025
±
0.009923
NSGA-II (binary-coded)
7.806798
±
0.001667
0.644477
±
0.035042
SPEA
0.221138
±
0.000449
0.849389
±
0.002713
PAES
0.085469
±
0.006664
1.153052
±
0.003916
PDEA
N/A
0.473074
±
0.021721
MODE
0.026230
±
0.000861
N/A
MTVDE
0
.
000
4
14
±
3.4014
e
-
009
0.9263
00
±
0.000
895Table 6
Testing result’s statistics of the problems SCH, DTLZ1, and DTLZ2.
Problem
Algorithm
Convergence metric
Diversity metric
SCH
NSGA-II
0.0076
±
6.2023
e
-
008
0.8471
±
1.9253
e
-
004
MTVDE
0.008
4
±
1.2296
e
-
007
0.8728
±
8.0547
e
-
005
DTLZ1
NSGA-II
7.4592
00
±
12.42210
1.0205
0
±
0.0059
00
MTVDE
0.023200
±
0.000014
0.7749
00
±
0.0023
00
DTLZ2
NSGA-II
0.6591
00
±
0.0040
00
0.914300
±
0.0027
00
MTVDE
0.5129
00
±
0.0011
00
0.6470
00
±
0.0015
00N/A denotes the algorithm does not calculate the index; the PDEA algorithm in [7] calculates the index GD (generational distance) instead of calculating the index (the convergence metric). The MODE algorithm in [7] did not calculate the index (diversity metric). We can be seen from Tables 1–6 that MTVDE algorithm has better convergence solutions except the problems ZDT1, ZDT2, and SCH.In this paper, the population size is 250. Through experiments, we found that the increasing of population size has no effect on performance of the algorithm but only can increase the running time. In order to detect the impact of the scaling factor and the crossover probability on performance of algorithm, we make 50 times independent experiments for problem SCH. In order to test the impact ofF and CR on the algorithm performance, it can be found that the F and CR have little effect on the algorithm performance by the testing data. Through comparison, F=0.5, CR = 0.9 results are a little better, but the algorithm performance (approximation index and uniformity index) is not particularly sensitive to the values of F and CR (Table 7).Table 7
F
CR
Convergence metric
Diversity metric
0.1
0.9
0.0086
±
1.9976
e
-
007
0.9551
±
1.8152
e
0.3
0.9
0.0090
±
1.4876
e
-
007
0.9361
±
1.6769
e
0.5
0.9
0.0084
±
1.2296
e
-
007
0.8728
±
8.0547
e
0.7
0.9
0.0091
±
1.9254
e
-
007
0.9281
±
1.4343
e
0.9
0.9
0.0088
±
9.4253
e
-
008
0.9276
±
1.9030
e
0.5
0.1
0.0088
±
7.6655
e
-
008
0.9258
±
1.6304
e
0.5
0.3
0.0089
±
1.4744
e
-
007
0.9283
±
2.0532
e
0.5
0.5
0.0091
±
2.8769
e
-
008
0.9327
±
1.1066
e
0.5
0.7
0.0091
±
1.5230
e
-
007
0.9313
±
5.6436
e
0.5
0.9
0.0084
±
1.2296
e
-
007
0.8728
±
8.0547
e


## 5. Summary

In MTVDE algorithm, the improved DE algorithm is used to solve MOPs. The main difference between MTVDE algorithm and other MOEA algorithms is the three test vectors and the new select method. Eight benchmark functions are used to test the MTVDE algorithm. Experimental results show that MTVDE algorithm is better than most MOEA. In order to find the best solution, different values of crossover probability are tested, the results of ZDT4 are very sensitive to the crossover probability (crossover probability is 0.3 better results). In short, the algorithm in this paper can effectively converge to the Pareto front of the problem and maintain the diversity of the Pareto optimal solution set. It is an effective algorithm for solving multiobjective optimization problems. In the future work, we intend to use MTVDE algorithm or appropriate improved MTVDE algorithms for solving other complex constrained MOPs.



---

*Source: 172041-2012-09-12.xml*