SPEA2$^+$: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees

The article presents SPEA2$^+$, an enhanced version of the Strength Pareto Evolutionary Algorithm 2 (SPEA2), aimed at improving density estimation in multi-objective optimization. This new variant incorporates pairwise distance calculations for fitness assignment, addressing the limitations of the original SPEA2 in efficiently covering the Pareto front in the OneTrapZeroTrap benchmark. Theoretical analyses and experimental results demonstrate that SPEA2$^+$ matches the performance guarantees of leading algorithms like NSGA-II and NSGA-III while maintaining SPEA2's effectiveness on simpler problems, making it a valuable tool for practitioners in evolutionary algorithm applications.