An evolutionary algorithm for multiobjective optimization: the strength Pareto approach

Abstract

Evolutionary algorithms (EA) have proved to bewell suited for optimization problems with multiple objectives.Due to their inherent parallelism they are able to capture a number of solutions concurrently in a single run.In this report, we propose a new evolutionary approach to multicriteria optimization, the Strength Pareto Evolutionary Algorithm (SPEA).It combines various features of previous multiobjective EAs in a unique manner and is characterized as follows: a) besides the population a set of individuals is maintained which c o n tains the Pareto-optimal solutions generated so far b) this set is used to evaluate the tness of an individual according to the Pareto dominance relationship c) unlike the commonly-used tness sharing, population diversity is preserved on basis of Pareto dominance rather than distance d) a clustering method is incorporated to reduce the Pareto set without destroying its characteristics.The proof-of-principle results on two problems suggest that SPEA is very e ective in sampling from along the entire Pareto-optimal front and distributing the generated solutions over the tradeo surface.Moreover, we compare SPEA with four other multiobjective EAs as well as a single-objective E A and a random search method in application to an extended 0/1 knapsack problem.Regarding two complementary quantitative measures SPEA outperforms the other approaches at a wide margin on this test problem.Finally, a n umber of suggestions for extension and application of the new algorithm are discussed.