---
title: "Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II"
authors:
  - "Yasser Alghouass"
  - "Benjamin Doerr"
  - "Martin S. Krejca"
  - "Mohammed Lagmah"
doi: "10.24963/ijcai.2025/982"
url: "https://ijcai.org/proceedings/2025/982"
pdf: "https://ijcai.org/proceedings/2025/0982.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8833-8841"
track: "Main Track"
keywords:
  - "Search: S: Evolutionary computation"
---

# Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II

Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8833-8841. DOI: [10.24963/ijcai.2025/982](https://doi.org/10.24963/ijcai.2025/982)

## Abstract

Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of σ-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.