Strength Pareto Evolutionary Algorithm

The objective of the algorithm is to locate and and maintain a front of non-dominated solutions, ideally a set of Pareto optimal solutions. This is achieved by using an evolutionary process (with surrogate procedures for genetic recombination and mutation) to explore the search space, and a selection process that uses a combination of the degree to which a candidate solution is dominated (strength) and an estimation of density of the Pareto front as an assigned fitness. An archive of the nondominated set is maintained separate from the population of candidate solutions used in the evolutionary process, providing a form of elitism.

The CalculateRawFitness function calculates the raw fitness as the sum of the strength values of the solutions that dominate a given candidate, where strength is the number of solutions that a give solution dominate. The CandidateDensity function estimates the density of an area of the Pareto front as 1/(o^k + 2) where o^k is the Euclidean distance of the objective values between a given solution the kth nearest neighbor of the solution, and k is the square root of the size of the population and archive combined. The PopulateWithRemainingBest function iteratively fills the archive with the remaining candidate solutions in order of fitness. The RemoveMostSimilar function truncates the archive population removing those members with the smallest o^k values as calculated against the archive. The SelectParents function selects parents from a population using a Genetic Algorithm selection method such as binary tournament selection. The CrossoverAndMutation function performs the crossover and mutation genetic operators from the Genetic Algorithm.

SPEA was designed for and is suited to combinatorial and continuous function multiple objective optimization problem instances. A binary representation can be used for continuous function optimization problems in conjunction with classical genetic operators such as one-point crossover and point mutation. A k value of 1 may be used for eciency whilst still providing useful results. The size of the archive is commonly smaller than the size of the population.