Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal
Files
(Published version)
Date
2025
Authors
Krejca, M.S.
Neumann, F.
Witt, C.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 18th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2025), 2025, pp.142-153
Statement of Responsibility
Martin S. Krejca, Frank Neumann, Carsten Witt
Conference Name
18th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA) (27 Aug 2025 - 29 Aug 2025 : Leiden, The Netherlands)
Abstract
Populations play a key role in the area of evolutionary computation to tackle complex optimization problems. Nevertheless, it is hard to understand the underlying population dynamics from a theoretical perspective, and only a limited number of theoretical results for population-based algorithms are available even for simple benchmark functions. In this paper, we study the classic (𝜇+1) EA on the benchmark problem BinVal, which allows for exponentially many function values. Previous methods for the analysis, based on fitness levels and multiplicative drift analysis, lead to runtime bounds for this function of size 𝑛 that include an additive term of Θ(𝑛2). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size 𝜇 and do not include this additive term. In particular, we prove bounds on the expected runtime that are𝑂(𝜇5𝑛 log(𝑛/𝜇4)) for standard bit mutation, which is𝑂(𝑛 log𝑛) for constant 𝜇. Our analysis considers the population dynamics of the (𝜇+1) EA more closely, proving that copies created by mutation lead to a low diversity in short blocks of bits across all individuals. We extend this method to mutation operators that cannot create duplicates, and prove bounds similar to standard bit mutation.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2025 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution 4.0 International License.