Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II
Authors: Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, Mohammed Lagmah
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 One Min Max benchmark in polynomial time. |
| Researcher Affiliation | Academia | 1 Ecole Polytechnique, Institut Polytechnique de Paris 2Laboratoire d Informatique (LIX), CNRS, Ecole Polytechnique, Institut Polytechnique de Paris {firstname.lastname}@polytechnique.edu |
| Pseudocode | Yes | Algorithm 1: The strength Pareto evolutionary algorithm 2 [Zitzler et al., 2001] (SPEA2) and Algorithm 2: The non-dominated sorting genetic algorithm II [Deb et al., 2002] (NSGA-II) |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology described, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper analyzes the One Min Max (OMM) benchmark, which is a bi-objective function defined mathematically for theoretical analysis, not an empirical dataset. The paper states: 'The One Min Max (OMM) benchmark, introduced by [Giel and Lehre, 2010], is a bi-objective function that aims at maximizing the number of ones and the number of zeros of an individual. Formally, for all x {0, 1}n, we have OMM(x) = P i [n] xi, P i [n](1 xi) .' |
| Dataset Splits | No | The paper focuses on theoretical analysis of algorithms on a mathematically defined benchmark (One Min Max function) rather than empirical experiments with datasets, thus dataset splits are not applicable or mentioned. |
| Hardware Specification | No | The paper focuses on theoretical proofs and runtime analysis of algorithms and does not describe any experimental setup that would involve specific hardware. |
| Software Dependencies | No | The paper is a theoretical work providing mathematical proofs and runtime analysis. It does not describe any software implementation or list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper presents theoretical results and mathematical proofs. It does not describe an experimental setup, hyperparameters, or system-level training settings for empirical evaluation. |