Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36855-36863
DOI: 10.1609/aaai.v40i43.41012 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Benjamin Doerr und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref).
Abstract (Originalsprache)
Together with the NSGA-II, the SPEA2 is one of the most widely used domination-based multi-objective evolutionary algorithms. For both algorithms, the known runtime guarantees are linear in the population size; for the NSGA-II, matching lower bounds exist. With a careful study of the more complex selection mechanism of the SPEA2, we show that it has very different population dynamics. From these, we prove runtime guarantees for the OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks that depend less on the population size. For example, we show that the SPEA2 with parent population size mu >= n - 2k + 3 and offspring population size lambda computes the Pareto front of the OneJumpZeroJump benchmark with gap size k in an expected number of O((lambda+mu)n + n^(k+1)) function evaluations. This shows that the best runtime guarantee of O(n^(k+1)) is not only achieved for mu = Theta(n) and lambda = O(n) but for arbitrary mu, lambda = O(n^k). Thus, choosing suitable parameters - a key challenge in using heuristic algorithms - is much easier for the SPEA2 than the NSGA-II.
Zitieren
APA
Doerr, B., Krejca, M. S., & Stanković, M. (2026). Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36855-36863. https://doi.org/10.1609/aaai.v40i43.41012
Vancouver
Doerr B, Krejca MS, Stanković M. Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36855-36863. doi:10.1609/aaai.v40i43.41012
BibTeX
@article{Doerr2026,
author = {Doerr, Benjamin and Krejca, Martin S. and Stanković, Milan},
title = {Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36855--36863},
doi = {10.1609/aaai.v40i43.41012}
}
EUVIMED