SPEA is not one my favorite meta-heuristic algorithms but it's intresting in its own way.
First, it was introduced by Eckart Zitzler et Lothar Thiele (1999) in "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach" and later refined into SPEA-II in 2001.
The algorithm was developed to improve the performance of evolutionary algorithms in finding Pareto-optimal solutions.
This algorithm follows simples rules:
- Strength-based Fitness Assignment: Each individual is assigned a fitness value based on the number of solutions it dominates.
- External Archive: Maintains an archive of non-dominated solutions. This archive is used for selection in the next generation.
- Elitism: Ensures the best solutions are preserved across generations.
- Nearest Neighbor-based Truncation: If the archive becomes too large, solutions are removed based on proximity to others (to maintain diversity).
SPEA has several weaknesses such as: weak density estimation, making it less effective in maintaining diversity. And, struggles with convergence speed in complex problems.
Later in 2001, Zitzler, Laumanns, et Thiele improved SPEA-I and introduced SPEA-II in their research work "SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization".
This algorithm has several key improvemnets for SPEA-i that can be listed as below:
- Refined Fitness Assignment: Combines dominance strength and density information to improve selection.
- Improved Density Estimation: Uses the k-th nearest neighbor approach to enhance solution spread.
- Better Archive Management: Ensures a fixed archive size with controlled diversity.
- Better Handling of Constrained Problems: More effective in problems with many conflicting objectives.
These improvments helped SPEA-II to:
- Faster convergence to Pareto-optimal solutions.
- Better spread of solutions.
- More robust selection and diversity maintenance.