Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper conducts a runtime analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) to investigate its handling of dominated solutions, revealing that SPEA2 struggles to efficiently cover the Pareto front in the OneTrapZeroTrap benchmark compared to other algorithms like NSGA-II and NSGA-III. The authors introduce an enhanced version, SPEA2$^+$, which incorporates all pairwise distances in fitness assignment, thereby improving diversity maintenance among dominated individuals. Experimental results corroborate the theoretical findings, demonstrating that SPEA2$^+$ matches the performance of leading algorithms while retaining SPEA2's effectiveness on simpler problems.
SPEA2$^+$ not only matches the performance of leading multi-objective algorithms but also reveals critical limitations in how traditional SPEA2 manages dominated solutions.
The Strength Pareto Evolutionary Algorithm 2 (SPEA2) is a popular and prominent evolutionary algorithm for solving multi-objective optimisation problems. Despite its popularity, theoretical analyses of SPEA2 have only appeared recently. Moreover, these analyses focus exclusively on how SPEA2 handles non-dominated solutions and disregard the algorithmic components responsible for handling dominated solutions. We conduct a first runtime analysis of SPEA2 for which these components are analysed. We prove that, unlike other prominent algorithms, including NSGA-II, NSGA-III and SMS-EMOA under the same setting of constant population size and duplicate elimination, SPEA2 is unable to cover the Pareto front of the OneTrapZeroTrap benchmark efficiently. Our results indicate that using k-th nearest-neighbour distance in the fitness assignment provides an insufficient signal to maintain diversity among dominated individuals. To address this issue, we propose an improved variant, SPEA2$^+$, that considers all pairwise distances. The new algorithm achieves the same performance guarantees as the other prominent algorithms on OneTrapZeroTrap, while matching the performance of the original SPEA2 on simpler problems. Experimental results complement our theoretical findings.