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].
Benjamin Doerr, Martin S. Krejca, Andre Opris· Proceedings of the Genetic a...· 0 citations
The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(nk+d/2 +μn ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size μ ∈ 2O(n) is at least (2n/d + 1)d/2. Notably, NSGA-III is faster than NSGA-II by a factor of μ/nd/2 for some μ ∈ ω(nd/2). We also show that a stochastic population update, proposed by Bian et al. [1], provably guarantees a speedup of order Θ((k/b)k-1) in the runtime where b > 0 is a constant. Besides [15], this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved. This Hot-off-the-Press paper summarises the work Andre Opris. 2025. A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, Article No.: 990, Pages 8903 - 8911, 2025 [9].
Andre Opris· Proceedings of the Genetic a...· 11 citations
This paper introduces the bi-objective problem class CLIMB and analyzes the runtime of GSEMO and the widely used NSGA-II on this problem, and proves that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes, can find the Pareto front of CLIMB in expected fitness evaluations.