2024/04/18 by Cella Florescu, Florescu, Cella, Marc Kaufmann +5
Computer Science · #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #FOS: Mathematics #Neural and Evolutionary Computing (cs.NE) #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2404.12147
openalex publication_date 2024/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The compact Genetic Algorithm (cGA), parameterized by its hypothetical population size K, offers a low-memory alternative to evolving a large offspring population of solutions. It evolves a probability distribution, biasing it towards promising samples. For the classical benchmark OneMax, the cGA has to two different modes of operation: a conservative one with small step sizes Θ(1/(√(n)log n)), which is slow but prevents genetic drift, and an aggressive one with large step sizes Θ(1/log n), in which genetic drift leads to wrong decisions, but those are corrected efficiently. On OneMax, an easy hill-climbing problem, both modes lead to optimization times of Θ(nlog n) and are thus equally efficient. In this paper we study how both regimes change when we replace OneMax by the harder hill-climbing problem DynamicBinVal. It turns out that the aggressive mode is not affected and still yields quasi-linear runtime O(n⋅ polylog (n)). However, the conservative mode becomes substantially slower, yielding a runtime of Ω(n2), since genetic drift can only be avoided with smaller step sizes of O(1/n). We complement our theoretical results with simulations.