SPEA2: Improving the Strength ParetoEvolutionary AlgorithmEckart Zitzler, Marco Laumanns, and Lothar ThieleComputer Engineering and Networks Laboratory (TIK)Department of Electrical EngineeringSwiss Federal Institute of Technology (ETH) ZurichETH Zentrum, Gloriastrasse 35, CH-8092 Zurich, Switzerland{zitzler,laumanns,thiele}@tik.ee.ethz.chTIK-Report 103May 2001(Errata added Sept 27, 2001)AbstractThe Strength Pareto Evolutionary Algorithm (SPEA) (Zitzler and Thiele 1999)is a relatively recent technique for finding or approximating the Pareto-optimal setfor multiobjective optimization problems. In different studies (Zitzler and Thiele1999; Zitzler, Deb, and Thiele 2000) SPEA has shown very good performance incomparison to other multiobjective evolutionary algorithms, and therefore it hasbeen a point of reference in various recent investigations, e.g., (Corne, Knowles,and Oates 2000). Furthermore, it has been used in different applications, e.g., (La-hanas, Milickovic, Baltas, and Zamboglou 2001). In this paper, an improved ver-sion, namely SPEA2, is proposed, which incorporates in contrast to its predecessora fine-grained fitness assignment strategy, a density estimation technique, and anenhanced archive truncation method. The comparison of SPEA2 with SPEA andtwo other modern elitist methods, PESA and NSGA-II, on different test problemsyields promising results.1 IntroductionAfter the first studies on evolutionary multiobjective optimization (EMO) in the mid-1980s, a number of Pareto-based techniques were proposed in 1993 and 1994, e.g.,MOGA (Fonseca and Fleming 1993), NPGA (Horn, Nafpliotis, and Goldberg 1994),and NSGA (Srinivas and Deb 1994), which demonstrated the capability of EMO algo-rithms to approximate the set of optimal trade-offs in a single optimization run. Theseapproaches did not incorporate elitism explicitly, but a few years later the importance1of this concept in multiobjective search was recognized and supported experimentally(Parks and Miller 1998; Zitzler, Deb, and Thiele 2000). A couple of elitist multi-objective evolutionary algorithms were presented at this time, e.g., SPEA (Zitzler andThiele 1998; Zitzler and Thiele 1999) and PAES (Knowles and Corne 1999). SPEA, anacronym for Strength Pareto Evolutionary Algorithm, was among the first techniquesthat were extensively compared to several existing evolution-based methods (Zitzlerand Thiele 1999; Zitzler, Deb, and Thiele 2000). As it clearly outperformed the (non-elitist) alternative approaches under consideration, it has been used as a point of refer-ence by various researchers, e.g., (Corne, Knowles, and Oates 2000; Jaszkiewicz 2000;Tan, Lee, and Khor 2001). Meanwhile further progress has been made and recentlyproposed methods, for instance NSGA-II (Deb, Agrawal, Pratap, and Meyarivan 2000)and PESA (Corne, Knowles, and Oates 2000), were shown to outperform SPEA oncertain test problems. Furthermore, new insights into the behavior of EMO algorithmsimproved our knowledge about the basic principles and the main factors of success inEMO (Laumanns, Zitzler, and Thiele 2000; Laumanns, Zitzler, and Thiele 2001).In this paper, SPEA2 is presented, for which we tried to eliminate the potentialweaknesses of its predecessor and to incorporate most recent results in order to de-sign a powerful and up-to-date EMO algorithm. The main differences of SPEA2 incomparison to SPEA are:• An improved fitness assignment scheme is used, which takes for each individualinto account how many individuals it dominates and it is dominated by.• A nearest neighbor density estimation technique is incorporated which allows amore precise guidance of the search process.• A new archive truncation methods guarantees the preservation of boundary so-lutions.As will be shown in this study, the proposed algorithm provides good performance interms of convergence and diversity, outperforms SPEA, and compares well to PESAand NSGA-II on various, well-known test problems.2 Background2.1 Issues in Evolutionary Multiobjective OptimizationThe approximation of the Pareto-optimal set involves itself two (possibly conflicting)objectives: the distance to the optimal front is to be minimized and the diversity of thegenerated solutions is to be maximized (in terms of objective or parameter values). Inthis context, there are two fundamental issues when designing a multiobjective evo-lutionary algorithm: mating selection and environmental selection. The first issue isdirectly related to the question of how to guide the search towards the Pareto-optimalfront. Given a pool of individuals, fitness values have to be assigned on the basis ofwhich individuals for offspring production are selected. The procedure to fill the mat-ing pool is usually randomized. The second issue addresses the question of which2individuals to keep during the evolution process. Due to limited time and storage re-sources, only a certain fraction of the individuals in a specific generation can be copiedto the pool of the next generation. It is common practice to use a deterministic selectionhere.In most modern EMO algorithms these two concepts are realized in the followingway although the details may be different:Environmental selection: Besides the population, an archive is maintained whichcontains a representation of the nondominated front among all solutions con-sidered so far. A member of the archive is only removed if i) a solution has beenfound that dominates it or ii) the maximum archive size is exceeded and the por-tion of the front where the archive member is located is overcrowded. Usually,being copied to the archive is the only way how an individual can survive sev-eral generations in addition to pure reproduction which may occur by chance.This technique is incorporated in order not to lose certain portions of the currentnondominated front due to random effects.Mating selection: The pool of individuals at each generation is evaluated in a twostage process. First all individuals are compared on the basis of the Pareto dom-inance relation, which defines a partial order on this multi-set. Basically, theinformation which individuals each individual dominates, is dominated by or isindifferent to is used to define a ranking on the generation pool. Afterwards,this ranking is refined by the incorporation of density information. Various den-sity estimation techniques are used to measure the size of the niche in which aspecific individual is located.In principle, both selection schemes are