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

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

doi:10.24963/ijcai.2025/982

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

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

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8833-8841.

https://doi.org/10.24963/ijcai.2025/982

Keywords

Search: S: Evolutionary computation

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.

Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah. 2025. Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8833–8841. https://doi.org/10.24963/ijcai.2025/982

@inproceedings{ijcai2025p982,
  title     = {Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II},
  author    = {Alghouass, Yasser and Doerr, Benjamin and Krejca, Martin S. and Lagmah, Mohammed},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {8833--8841},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/982},
  url       = {https://doi.org/10.24963/ijcai.2025/982},
}

TY  - CPAPER
TI  - Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II
AU  - Alghouass, Yasser
AU  - Doerr, Benjamin
AU  - Krejca, Martin S.
AU  - Lagmah, Mohammed
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 8833
EP  - 8841
DO  - 10.24963/ijcai.2025/982
UR  - https://doi.org/10.24963/ijcai.2025/982
ER  -