The SPEA2 and the NSGA-II are two of the most widely used dominance-based multi-objective evolutionary algorithms (MOEAs). While prior theoretical work established similar runtime guarantees for both, the differences in their selection mechanisms were not well understood from an approximation perspective. We provide the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability. Specifically, the steady-state SPEA2 computes an optimal spread of the OneMinMax Pareto front in O(μ2n log(μ;) log(n)) expected function evaluations. In contrast, the steady-state NSGA-II, when started near an optimal spread with just two sub-optimal gaps, fails to achieve optimality within polynomial time with overwhelming probability. This is the first result showing a provable qualitative gap between the approximation abilities of these two algorithms. This paper summarizes the work Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. International Joint Conference on Artificial Intelligence, IJCAI 2025. [1].
Yasser Alghouass, Benjamin Doerr, Martin S. Krejca et al.· Proceedings of the Genetic a...· 0 citations
Recent breakthroughs in the analysis of multi-objective evolutionary algorithms (MOEAs) are mathematical runtime analyses of those algorithms which are intensively used in practice. So far, most of these results show the same performance as previously known for simpler algorithms like the GSEMO. The few results indicating advantages of the popular MOEAs share the same shortages: They only consider the problem of computing the full Pareto front, sometimes of algorithms enriched with newly invented mechanisms, and this on newly designed benchmarks. In this work, we overcome these shortcomings by analyzing how existing popular MOEAs approximate the Pareto front of the established LargeFront benchmark. We prove that several popular MOEAs, including NSGA-II (with current crowding distance), NSGA-III, SMS-EMOA, and SPEA2, only need an expected time of O(n2 log n) fitness evaluations to compute an additive ε-approximation of the Pareto front of the LargeFront benchmark. This contrasts with the already proven exponential runtime (with high probability) of the GSEMO on the same task. Our result is the first mathematical runtime analysis showing and explaining the superiority of popular MOEAs over simple ones like the GSEMO for the central task of computing good approximations to the Pareto front. This paper summarizes the work Mingfeng Li, Qiang Zhang, Weijie Zheng and Benjamin Doerr: Why Popular MOEAs Are Popular: Proven Advantages in Approximating the Pareto Front. Advances in Neural Information Processing Systems, NeurIPS 2025. [15].
Mingfeng Li, Qiang Zhang, Weijie Zheng et al.· Proceedings of the Genetic a...· 0 citations
This first complete mathematical runtime analysis for the MOEA/D using the original weighted-sum decomposition shows that this variant of the algorithm solves the classic OneMinMax benchmark considerably faster than both the MOEA/D with Tchebycheff decomposition and many other classic algorithms such as the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2.
Danyang Zhang, Zerong Zhong, Weijie Zheng et al.· Proceedings of the Genetic a...· 0 citations