EUVIMEDEUVIMED entdecken
Crossref

Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer

Benjamin Doerr, Martin S. Krejca, Milan Stanković

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →