SPEA2

SPEA2, or the Strength Pareto Evolutionary Algorithm 2, is a multi-objective evolutionary algorithm designed to approximate the Pareto front of conflicting objectives. It was introduced by Eckart Zitzler, Lucia Laumanns, and Lothar Thiele in 2001 as an improvement over the original SPEA. The algorithm is widely used for problems where trade-offs between objectives must be explored, such as engineering design, optimization, and control.

A defining feature of SPEA2 is its use of an external archive to store non-dominated solutions found during the search. The archive has a fixed size, and its contents are intended to represent diverse, high-quality trade-offs. Each individual in the population and the archive is assigned a fitness value that combines two components: strength and density. The strength of an individual is the number of solutions it dominates. The density term estimates how crowded the solution is in objective space, typically using a k-nearest neighbor distance. The overall fitness is the sum of the strength and the density, promoting both convergence toward the Pareto front and dispersion along it.

During evolution, the population is updated through environmental selection that prioritizes individuals with better fitness while maintaining diversity. If the archive exceeds its capacity, pruning is performed using the density measure to remove solutions from crowded regions. SPEA2 often combines the current population with the archive to form a larger pool from which the next generation is selected, and new offspring are produced via standard operators such as selection, crossover, and mutation.

SPEA2 is valued for its robust performance across diverse problems, its explicit preservation of an elitist archive, and its explicit mechanism for maintaining diversity, making it a widely cited method in the field of multi-objective optimization.