Hot of the Press: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
TL;DR
This work significantly enhance the understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark, and proves a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years.
Abstract
The global simple evolutionary multi-objective optimizer (GSEMO) is a simple, yet often effective multi-objective evolutionary algorithm (MOEA). By only maintaining non-dominated solutions, it has a variable population size that automatically adjusts to the needs of the optimization process. The downside of the dynamic population size is that the population dynamics of this algorithm are harder to understand, resulting, e.g., in only sporadic tight runtime analyses existing. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros benchmark. From this, we prove a lower bound of order Ω(n2 log n), for the first time matching the seminal upper bounds known for over twenty years. We also show that the GSEMO finds any constant fraction of the Pareto front in time O(n2), improving over the previous estimate of O(n2 log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω(nk+1) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ {2, 3}. We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs. This paper summarizes the work Benjamin Doerr, Martin S. Krejca, and Andre Opris: Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm. International Joint Conference on Artificial Intelligence, IJCAI 2025. ijcai.org, 8876–8884. [6].