Strength Pareto Evolutionary Algorithm 2 (SPEA2) in MATLAB

Strength Pareto Evolutionary Algorithm 2 (SPEA2) is an extended version of the SPEA multi-objective evolutionary optimization algorithm. Zitzler and Thiele proposed SPEA in 1999 (paper (opens in a new tab)), and Zitzler, Laumanns and Thiele presented SPEA2 in 2001 in a technical report of ETH Zurich. SPEA2 uses a mechanism similar to k-Nearest Neighbor (kNN) and a specialized ranking system to sort the population. The next generation is selected from the combination of the current population and an archive of the best solutions found so far. SPEA2 is one of the best-known multi-objective optimization algorithms.

The problem

SPEA2 minimizes several conflicting objectives $f_1, \dots, f_M$ at the same time. Solutions are compared with Pareto dominance: $x$ dominates $y$ ($x \prec y$) when $f_i(x) \le f_i(y)$ for every objective $i$ and $f_j(x) < f_j(y)$ for at least one objective $j$. The goal is a set of non-dominated solutions that lies close to the Pareto front and covers it well.

How SPEA2 works

SPEA2 keeps a population $P$ of size $N$ and an archive $\bar{P}$ of size $\bar{N}$. In each generation, every member $i$ of $P \cup \bar{P}$ gets a fitness value in three steps.

The strength $S(i)$ is the number of members that $i$ dominates:

The raw fitness $R(i)$ is the sum of the strengths of all members that dominate $i$. A non-dominated member has $R(i) = 0$, and a member dominated by strong members gets a large value:

The density $D(i)$ comes from the distance $\sigma_i^k$ between member $i$ and its $k$-th nearest neighbor in objective space, with $k = \sqrt{N + \bar{N}}$ rounded to an integer. It is always below 1, so it only separates members with the same raw fitness:

Lower fitness is better. The next archive is filled as follows:

1. All non-dominated members ($R(i) = 0$) are copied to the archive.
2. If there are fewer than $\bar{N}$ of them, the best dominated members by fitness fill the rest.
3. If there are more than $\bar{N}$, the truncation step removes members one at a time. Each time, it removes the member that is closest to its neighbors, so the archive keeps a good spread along the front.

Parents are then chosen from the archive by binary tournament on $F$, and crossover and mutation create the new population.

Implementation in MATLAB

This post shares an open-source implementation of SPEA2 in MATLAB. The code is structured, so if you know MATLAB, you should find it easy to use in your research projects.

The SPEA2 folder holds the main script spea2.m, a one line entry point main.m, and the helper functions Dominates.m, BinaryTournamentSelection.m, Crossover.m, Mutate.m and PlotCosts.m. The default problem is ZDT.m, the ZDT1 test function with two objectives, and MOP2.m is a second test problem.

To run the code, open the SPEA2 folder in MATLAB and run main.m. In each iteration the program prints the number of members on the approximate Pareto front and plots them. At the end it prints the minimum, maximum, range, standard deviation and mean of each objective over the front.

The code uses unifrnd, randsample and pdist2, functions of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox. The distances between members are computed with pdist2 and the standardized Euclidean metric. The archive-truncation code is a simplified implementation and does not recompute the full neighbor-distance ordering after every removal, so it should not be treated as an exact reproduction of the report.

Parameters in the code

The parameters are set at the top of spea2.m:

The rest of the new population (a share of $1 - 0.7$) is created by mutation. To solve your own problem, write a cost function that takes a column vector and returns a column vector of objective values, and set CostFunction, nVar, VarMin and VarMax in spea2.m.

Check the result

Check dominance among the reported objective vectors, confirm decision-variable bounds, and inspect the spread across repeated runs. An archive can include dominated members while it is being filled, so distinguish its contents from the final reported non-dominated subset. Standardized distances need meaningful variation in each objective, and an objective with zero variance needs explicit handling. Use a consistent evaluation budget when comparing with NSGA-II or other methods.

Related posts

NSGA-II, PESA-II, MOEA/D and Multi-Objective PSO are other multi-objective algorithms on Yarpiz, implemented in the same style.

Mostapha Kalami Heris, Strength Pareto Evolutionary Algorithm 2 (SPEA2) in MATLAB (YPEA122), Yarpiz, 2015. https://yarpiz.com/spea2-ypea122

@misc{yarpiz-ypea122,
  author = {{Mostapha Kalami Heris}},
  title = {{Strength Pareto Evolutionary Algorithm 2 (SPEA2) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA122},
  url = {https://yarpiz.com/spea2-ypea122}
}