Multiobjective Differential Evolution with External Archive and Harmonic Distance-Bad Diversity Measure V. L. Huang, P. N. Suganthan, A. K. Qin and S. Baskar
School of Electrical and Electronic Engineering
Nanyang Technological University
Singapore 639798
{huangling, qinkai}@u.edu.sg, epnsugan@ntu.edu.sg, baskar_
Abstract: This paper prents an approach to incorporate Pareto dominance into the differential evolution (DE) algorithm in order to solve optimization problems with more than one objective by using the DE algorithm. Unlike the existing proposals to extend the DE to solve multiobjective optimization problems, our algorithm us an external archive to store nondominated solutions. In order to generate trial vectors, the current population and the nondominated solutions stored in the external archive are ud. We also propo a new harmonic average distance to measure the crowding degree of the solutions more accurately. Simulation results on nine test problems show that the propod MODE, in most problems, is able to find much better spread of solutions with better approximating the true Pareto-
optimal front compared to three other multiobjective optimization evolutionary algorithms. Further the new crowding degree estimation method improves the diversity of the nondominated solutions along the Pareto front.
Keywords: differential evolution, multiobjective differential evolution, multiobjective evolutionary algorithm, external archive.
1.Introduction
The development of evolutionary algorithms to solve multiobjective optimization problems has attracted much interest recently and a number of multiobjective evolutionary algorithms (MOEAs) have been suggested (Zitzler and Thiele, 1999; Knowles and Corne, 2000; Zitzler, Laumanns and Thiele, 2001; Deb et al., 2002; Coello et al., 2004). While most of the the algorithms were developed taking into consideration two common goals, namely fast convergence to the Pareto-optimal front and good distribution of solutions along the front, each algorithm employs a unique combination of specific techniques to achieve the goals. SPEA (Zitzler and Thiele, 1999) us a condary population to store the nondominated solutions and cluster mechanism to ensure diversity. PAES (Knowles and Corne, 2000) us a histogram-like density measure over a hyper-grid
division of the objective space. NSGA-II (Deb et al., 2002) incorporates elitist and crowding approaches. The main advantage of evolutionary algorithms (EAs) in solving multi-objective optimization problems is their ability to find multiple Pareto-optimal solutions in one single run.
The differential evolution (DE) algorithm has been found to be successful in single objective optimization problems. Recently there are veral attempts to extend the DE to solve multiobjective problems.One approach is prented to optimi train movement by tuning fuzzy membership functions in mass transit systems (Chang et al., 1999). Abbass et al., (2001) introduce a Pareto-frontier Differential Evolution algorithm (PDE) to solve multiobjective problem by incorporating Pareto dominance. This PDE is also extended with lf-adaptive crossover and mutation (Abbass, 2002). Madavan (2002) extended DE to solve multiobjective optimization problems by incorporating a nondominated sorting and ranking lection scheme of NSGA-II. Another approach involves Pareto-bad evaluation to DE for solving multiobjective decision problems and has been applied to an enterpri planning problem with two objectives namely, cycle time and cost (Xue, 2003; Xue et al., 2003). Recently rearchers also have developed parallel multi-population DE algorithm (Parsopoulos et al., 2004) and Kukkonen and Lampinen (2004) propo Generalized Differential Evolution (GDE) for constrained multiobjective algorithm and extend GDE2.
眼镜品牌排行榜
However, none of the existing approaches extend DE to deal with multiobjective optimization problems with an external archive, which is an effective notion of elitism and has been successfully ud in other MOEAs (Zitzler and Thiele, 1999; Knowles and Corne, 2000;
Zitzler, Laumanns and Thiele, 2001; Coello et al., 2004). Further, existing multiobjective DE implementations have not been comprehensively evaluated and compared with the other multiobjective evolutionary algorithms. In this paper, we prent an approach to extend DE algorithm to solve multiobjective optimization problems with an external archive, which we call “multiobjective differential evolution” (MODE). From the simulation results on veral standard test functions, we find that the MODE overall outperforms three highly competitive MOEAs: the nondominated sorting genetic algorithm-II (NSGA-II) (Deb et al ., 2002), the multiobjective particle swarm optimization (MOPSO) (Coello et al., 2004) and Pareto archive evolution strategy (PAES) (Knowles and Corne, 2000). To generate a better distribution of solutions along the front, we propo a new harmonic average distance measure to estimate crowding and incorporate it into the MODE to obtain MODE-II.
land攻击
The remainder of the paper is organized as follows. Section 2 summarizes the differential evolution algorithm. In Section 3, we describe MODE with a standard crowding distance measure and MODE-I
I with harmonic average distance measure. Section 4 prents simulation and comparative results of MODE and three other competitive MOEAs, and also evaluates effectiveness of the harmonic average distance measure. The paper is concluded in Section 5.
2. The Differential Evolution Algorithm
Differential evolution (DE) is a simple population-bad, direct-arch algorithm for global optimization (Storn and Price, 1997). It has demonstrated its robustness and effectiveness in a variety of applications, such as neural network learning (Ilonen et al., 2003), IIR-filter design (Storn, 1996), and the optimization of aerodynamic shapes (Rogalsky et al., 1999). The main features of the DE are summarized below.
Let n电脑进入bios
S ℜ⊂ be the arch space of the problem under consideration. Then, the DE utilizes NP , D –dimensional vectors, {}1,,,, ..., , 1,...,D i G i G i G x x i NP ==X
as a population for each generation of the algorithm. The initial population is chon randomly and should cover the entire parameter space. At each generation, DE employs both mutation and crosso
ver (recombination) to produce one trial vector G i U , for each target vector G i X ,. Then, a lection pha takes place, where each trial vector is compared to the corresponding target
vector, the better one will enter the population of the next generation. For each target vector ,i G X , a mutant vector ,i G V is generated using the following equation (Storn and Price, 1997)
1234,,,,,,()(),i G r G r G r G r G best G F F =+−+−V X X X X X (1)
where, random indexes } , ,2 ,1{ , , , ,54321NP r r r r r K ∈ are mutually different integers and
also different from the current object vector index i . F is a scaling factor ]2 ,0[∈ and ,best G X is the best individual of the population at generation G .
After the mutation pha, the crossover operator is ud to increa the diversity.
()(),,,, if [0, 1) or , otherwi j i G j rand j
i G j i G v rand CR j j u x ⎧≤=⎪=⎨⎪⎩ 1, 2, ... ,D j = (2)
and ()
12,,,,,, ..., D i G i G i G i G u u u =U (3) CR is ur-specified crossover constant ];1 ,0[∈ rand j is a randomly chon index from {1, 2, , }D K , which ensures that the trial vector U i,G will differ from its target X i,G by at least one parameter.
To decide whether the trial vector U i,G should be a member of generation 1+G , it is compared with target vector X i,G .
,,,,1,, if ()() otherwi i G i G i G i G i G
f f +≤=⎧⎪⎨⎪⎩U U X X X (4) With the membership of the next generation thus lected, the evolutionary cycle of the DE repeats until a stoppin
g condition is satisfied.
3. MODE with External Archive碧绿造句
In our work, we propo a novel approach to extend DE to multiobjective optimization problems. The main differences of our approach with respect to the other proposals in the literature are: a. We make u of an external archive to rve three parate purpos. First, it saves and updates well spread nondominated solutions that would be the Pareto optimal solutions when the algorithm conve
rges to the Pareto front. Second, it is ud as an aid to choo between target and trial when they do not dominate each other. This process provides the lection pressure by pushing the archive to retain better solutions. Finally, we u the external archive as a pool to
lect the ,best G X in Equation (1) for the DE. In this way, the propod MODE can converge faster while maintaining a good diversity.
b. We measure the crowding degree of the solutions, which is ud as a criterion to lect less crowded one between nondominated target and trial as the new target for next generation, and delete the crowded archive members when the external archive population has reached its maximum size.
c. We also propo a new harmonic average distance measure to estimate the crowding degree of the solutions more accurately.
d. We compare our MODE with other landmark multiobjective evolution algorithms on convergence and diversity metrics.
The MODE algorithm is described in Table 1.
Table 1: MODE with External Archive
难忘时刻Step1: Set the generation number 0G =, randomly initialize a population of NP individuals {}1,,,...,G G NP G =P X X with {}1,,,, ..., , 1,...,D i G i G i G x x i NP
==X uniformly distributed in the range []min max , X X , where {}1min min min ,...,D x x =X and {}1max max max ,...,D x x =X , and initialize the external archive G G
=A P . Step2: Evaluate the fitness value of each target vector ,i G X .
Step3: WHILE stopping criterion is not satisfied,
DO
Step3.1: Mutation step
FOR i = 1 to NP
Generate a mutated vector {}
论说文范文
1,,,, ..., D i G i G i G v v =V corresponding to the target vector ,i G X via 1234,,,,,,()(),i G best G r G
r G r G r G F F =+−+−V X X X X X (1)
where ,best G X is randomly taken from G A . The indices 1234,,,r r r r are mutually exclusive integers randomly generated within the range []NP ,1, which are also different from the index i .
END FOR
Step3.2: Crossover step
FOR i = 1 to NP
Generate a trail vector {}1,,,, ..., D i G i G i G u u =U for each target vector ,i G X
FOR j = 1 to D
()(){,,,, if [0,1) or , otherwi
j j i G rand j i G i G v rand CR j j u x ≤== (2) randomly lect rand j from {1, 2, , }D K
END FOR
END FOR
战略规划三要素Step3.3: Selection step
FOR i =1 to NP
Evaluate the trial vector ,i G U
If ,G i X dominates ,i G U , ,i G U is rejected青春派观后感
If ,i G U dominates ,G i X , ,,1i G i G +=X U , and update G A with Update_archive in Table 2.
If ,G i X and ,i G U are nondominated with each other, u Update_archive to compare ,i G U with G A
and the less crowded one will be the next generation target vector 1,G i +X .
END FOR
Step3.4: When G A exceeds the maximum size, we lect the less crowded vectors bad on crowding distance to keep the archive size at max N . Step3.5: Increment the generation count G = G + 1. END WHILE
3.1. External Archive
We u an external archive to keep the best nondominated solutions generated so far by the MODE algorithm. Initially, this archive is empty. As the evolution progress, good solutions enter the archive. However, the size of the true nondominated t can be huge. The computational complexity of maintaining the archive increas with the archive size. Moreover, considering the u of an external archive as a pool to lect the G best X ,, the archive size also affects the complexity of lection. Hence, the size of the archive will be restricted to a pre-specified value as many other rearchers have done (Zitzler and Thiele, 1999; Knowles and Corne, 2000; Zitzler et al., 2001; Coello et al., 2004).
Table 2. Update_archive
If ,i G U is dominated by any member of G A , discard ,i G U
El if ,i G U dominates a t of members ,()i G D U from G A
,\()i G G G =A A D U ;{},G G i G =∪A A U
El G A and ,i G U are nondominated, {},G G i G =∪A A U
The trial vectors that are not dominated by the corresponding target vectors obtained at each generation are compared one by one in Step 3.3 (Table 1) with the current archive, which contains the t of nondominated solutions found so far. There are three cas as illustrated in Table 2: 1. If the trial vector is dominated by a member of the external archive, the trial vector is rejected. 2. If the trial vector dominates some member(s) of the archive, then the dominated members in the archive are deleted and the trial vector enters the archive. 3. The trial vector does not dominate any archive members and none of the archive member dominates the solution. This implies that the trial vector belongs to the nondominated front and it enters the archive. Finally,
