Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm

Benjamin Doerr, Martin S. Krejca, Andre Opris · 2025

Read Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm by Benjamin Doerr, Martin S. Krejca, Andre Opris (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01266.txt.

Introduction

Benjamin Doerr and co-authors pinned down run times for a simple search method in a 2025 paper. The method breeds solutions to problems with two goals at once and keeps only those that no rival beats on both goals. Its pool size grows and shrinks on its own, which suits the task but makes its speed hard to prove.

The team studied how the pool moves over time on a classic test problem that counts ones and zeros in a bit string. That close look let them prove tight bounds on how long the method needs. Such bounds tell users when this simple tool is a sound pick.

Catalog record

CREATORBenjamin Doerr, Martin S. Krejca, Andre Opris
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01266

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm Benjamin Doerr, Martin S. Krejca, Andre Opris 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 the fact that only sporadic tight runtime analyses exist. In this work, we significantly enhance our understanding of the dynamics of the GSEMO, in particular, for the classic CountingOnesCountingZeros (COCZ) benchmark. From this, we prove a lower bound of order Ω ⁡ ( n 2 ​ log ⁡ n ) \Omega(n^{2}\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 ⁡ ( n 2 ) O(n^{2}) , improving over the previous estimate of O ⁡ ( n 2 ​ log ⁡ n ) O(n^{2}\log n) for the time to find the first Pareto optimum. Our methods extend to other classic benchmarks and yield, e.g., the first Ω ⁡ ( n k + 1 ) \Omega(n^{k+1}) lower bound for the OJZJ benchmark in the case that the gap parameter is k ∈ { 2 , 3 } k\in\{2,3\} . We are therefore optimistic that our new methods will be useful in future mathematical analyses of MOEAs. Keywords: Evolutionary algorithms, runtime analysis, GSEMO, COCZ, lower bound. 1 Introduction Many real-world optimization problems are characterized by several, often conflicting objectives. A common solution concept for such multi-objective optimization problems is to compute a diverse set of Pareto optima (solutions which cannot be improved in one objective without compromising in another objective) and let a human decision maker select one of these. Due to their population-based nature, multi-objective evolutionary algorithms (MOEAs) are among the most prominent approaches to such problems and have found applications in numerous subfields of multi-objective optimization Coello et al. (2007) ; Zhou et al. (2011) . The mathematical runtime analysis of MOEAs was started around 20 years ago Laumanns et al. (2002) ; Giel (2003) ; Thierens (2003) . It has gained considerable momentum in the last years, among others, with analyses of classic algorithms such as the NSGA-II, NSGA-III, SMS-EMOA, and SPEA2 Zheng et al. (2022) ; Wietheger and Doerr (2023) ; Bian et al. (2023) ; Ren et al. (2024) ; Opris (2025) ; Opris et al. (2024) or works discussing how MOEAs can solve submodular problems Qian et al. (2019) ; Qian et al. (2020) ; Crawford (2021) ; Do et al. (2023) . The by far dominant algorithm in the rigorous analysis of MOEAs is the global simple evolutionary multi-objective optimizer Giel (2003) (GSEMO). Due to its apparent simplicity, it was the first MOEA for which mathematical runtime analyses were conducted, and it is still often the first algorithm for which new phenomena are discovered, see, e.g., Dinot et al. (2023) ; Dang et al. (2024) for recent examples. At the same time, it is a central algorithm, and many other algorithms, in particular in the area of submodular optimization, build on it. For example, algorithms such as POSS (Pareto Optimization for Subset Selection) Qian et al. (2015) , POMC (Pareto Optimization for Monotone Constraints) Qian et al. (2017) , and POMS (Pareto Optimization for Multiset Selection) Qian et al. (2018) are all variants of the GSEMO applied to a suitable bi-objective formulation of the submodular problem of interest. Despite this impressive body of theoretical works on the GSEMO, a real understanding of the working principles of this algorithm is still missing. This is most visible from the fact that there are almost no lower bounds matching the existing runtime guarantees (see Section 2 for a detailed discussion of this point). The reason is that for matching bounds, a deeper understanding of the population dynamics is necessary. This is particularly crucial for the GSEMO with its dynamic population size (note that the probability to choose a particular individual as parent is the reciprocal of the population size). Our contribution: In this work, we greatly expand our understanding of the population dynamics of the GSEMO. To this end, we study how this algorithm optimizes the classic CountingOnesCountingZeros (COCZ) benchmark. For readers less familiar with the area of runtime analyses, we note that it is the established approach of this field to study how a specific randomized search heuristics solves a well-understood benchmark problem, and from this derive insights into the working principles of the heuristic. All runtime analysis works cited above follow this approach. We give more details on our new understanding of the population dynamics later ( Section 4 ) when we have made precise the GSEMO algorithm and the COCZ benchmark, and now only describe two implications. First, we indeed succeed in proving a lower bound of \Omega(n^{2}\log n) ( Theorem 4 ), which matches the classic upper bound of Laumanns et al. (2002) ; Giel (2003) . This is the first tight lower bound for a benchmark problem in which reaching the Pareto front is non-trivial (as opposed to, e.g., the OneMinMax benchmark, where all solutions are on the Pareto front). Second, we also gain a deeper understanding on how difficult it is to reach the Pareto front. Whereas previously the time to find the first solution on the Pareto front was estimated by O(n^{2}\log n) , we prove that O(n^{2}) iterations suffice with high probability to reach the Pareto front and compute any linear fraction of it ( Corollary 8 ). Our results are made possible by a number of new arguments. The most interesting one is that we add dummy individuals to the population to reach a population size equal to the maximum possible size. If such a dummy individual is chosen as parent, this iteration has no effect (but is counted as iteration). This argument helps overcome the changing population size of the original GSEMO. What is interesting is that this argument, which slows down the original algorithm, can be used to prove lower bounds on the runtime. The reason is that we exploit this argument not to estimate times directly (which is not possibly due to the unclear deceleration from the dummy individuals) but only to understand the shape of the population in the objective space. We are optimistic that this argument, and our other new proof ideas, will be useful in future runtime analyses of MOEAs as well. As a first support for this claim, we show that our methods also give a tight lower bound for the runtime of the GSEMO on the \textsc{OJZJ}_{k} benchmark for all k (where previous works could not analyze the cases k=2 and k=3 ) and that all our results extend to the SEMO algorithm. 2 Previous Works In the interest of space, we concentrate on the previous works most relevant for ours. For a general introduction to MOEAs and their success in applications, we refer to Coello et al. (2007) ; Zhou et al. (2011) .

Read the complete text