Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca · 2025

Read Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark by Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca (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-2501-16250.txt.

Introduction

A simple genetic search method finally gets a proof of how fast it solves a classic test problem. Marcel Chwialkowski, Benjamin Doerr, and Martin Krejca supply that proof in a 2025 paper. The method keeps a probability for each bit and samples new guesses from those odds. The test problem rewards long runs of leading ones.

When the method's single size setting is at least modestly larger than the problem size, the optimum is found fast with high chance. The step count grows near-linearly in problem size and linearly in the size setting. Best settings give the sharpest bounds. Theory users gain a missing benchmark result for one of the simplest search methods in the field.

Catalog record

CREATORMarcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16250

Browse the full library · About the Tower of Babel

Full text

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

Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca Abstract The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA)—another simple EDA—, the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark—one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes . For the cGA’s single parameter—called the hypothetical population size—at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes . Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works. I Introduction Estimation-of-distribution algorithms [ 1 ] (EDAs) constitute a large and important class of general-purpose randomized optimization heuristics (ROHs) [ 2 ] . A key feature of EDAs that clearly separates them from other prominent classes of ROHs, such as evolutionary algorithms [ 3 ] , is that they maintain and evolve a probabilistic model of the search space. This model defines a probability distribution over the search space and aims at giving better solutions a higher probability. Ideally, only global optima in the search space have a positive probability. EDAs iteratively refine their model based on random samples thereof, giving more probability to more promising solutions. This approach has been shown to outperform competing approaches both empirically [ 1 ] as well as theoretically [ 4 ] on numerous occasions. Like other ROHs, EDAs have been subject to mathematical investigations for more than two decades, starting with convergence guarantees [ 4 ] . The first fully rigorous runtime analysis comparable to the current state of the art in this field was carried out by Droste [ 5 ] . In this seminal paper, he analyzed the compact genetic algorithm [ 6 ] (cGA) on the OneMax benchmark. The cGA is a simple EDA that samples the problem variables independently, resulting in a so-called univariate model. It refines this model in each iteration based solely on two independent samples, shifting probability mass in discrete steps of size \frac{1}{\mu} , where \mu is an algorithm-specific parameter called the hypothetical population size . Since the cGA is a simple EDA and since OneMax is the most commonly studied theory benchmark in the field of evolutionary computation [ 7 ] , the result by Droste [ 4 ] served as a logical and strong first runtime contribution in the domain of EDAs. Interestingly, this paper was initially not followed up by a lot of theoretical work. The rigorous investigation of EDAs only gained momentum with the paper by Dang and Lehre [ 8 ] , who analyzed the runtime of the univariate marginal distribution algorithm [ 9 ] (UMDA), which is also a univariate EDA but allows, in contrast to the cGA, for a larger sample size than two. Dang and Lehre considered the OneMax and the LeadingOnes theory benchmarks, covering the two most important theory benchmarks in the field. Since then, numerous theoretical results on EDAs have been published [ 4 ] . Most of these results still only consider the cGA and the UMDA, but they provide us with deep insights into the complex dynamics of updating the algorithms’ probabilistic models. Moreover, they cover more complex benchmarks than OneMax and LeadingOnes , and they also consider more complex scenarios, such as noisy optimization. In Section II , we give more detail about some of these works. Surprisingly, despite this increased theoretical body of literature and the long way that runtime analysis on EDAs has come since the initial paper by Droste [ 4 ] , to this day, the cGA’s runtime performance on the LeadingOnes benchmark has not been rigorously studied. In other words, we are still missing a theoretical result for one of the most studied EDAs on one of the most studied theory benchmarks. In comparison, runtime guarantees for the commonly studied UMDA on LeadingOnes have existed for more than a decade [ 10 ] . Our contribution: We conduct the first runtime analysis of the cGA on LeadingOnes . We consider the parameter regime of the algorithm where it exhibits low genetic drift , that is, the updates of the cGA to its probabilistic model are sufficiently small such that random fluctuations in the update process do not have a strong impact on the overall performance. For a problem size of n , we show that the cGA with \mu=\Omega(n\log^{2}n) samples the optimum of LeadingOnes with high probability after O(\mu n\log n) function evaluations ( Theorem 4 ). This runtime bound is minimized for \mu=\Theta(n\log^{2}n) , resulting in an overall runtime of O(n^{2}\log^{3}n) . This runtime bound is slightly worse, by a factor of O(\log^{3}n) , compared to the common O(n^{2}) bound of many other ROHs on LeadingOnes [ 7 ] , including the best-known runtime bound of the UMDA [ 11 ] . For the generally preferred regime of low genetic drift, the best known runtime bound for the UMDA is \Theta(n^{2}\log n) [ 12 ] , which is only better by a factor of O(\log^{2}n) . These small differences might be a consequence of how the cGA and the UMDA fix certain parts in their probabilistic model. As the UMDA, due to its larger sample size, can apply larger (justified) changes to its model, it can adjust it slightly quicker. We discuss this difference in the optimization behavior of the two algorithms in more detail after Lemma 7 and a second difference at the end of Section IV . We note, though, that we currently have no matching lower bound. Hence we cannot say whether the two algorithms truly have a different asymptotic runtime or the difference in the upper bounds is caused by our upper bound not being absolutely tight. Due to the difficulty of proving lower bounds, we have to leave this an open problem. Outline: We discuss related work in Section II . In Section III , we describe the cGA, the LeadingOnes problem, and the mathematical tools we use for our analysis. We then conduct the runtime analysis of the cGA on LeadingOnes in Section IV . Last, we conclude our paper in Section V . II Related Work We now discuss important runtime results of EDAs that relate to our result. The term runtime refers to the number of function evaluations until a global maximum of the objective function is sampled for the first time. For EDAs, runtime results are often shown to hold with high probability but also regularly in expectation. We do

Read the complete text