Faster Optimization Through Genetic Drift
<|reference_start|>Faster Optimization Through Genetic Drift: 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 $\Theta(1/(\sqrt{n}\log n))$, which is slow but prevents genetic drift, and an aggressive one with large step sizes $\Theta(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 $\Theta(n\log 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\cdot polylog (n))$. However, the conservative mode becomes substantially slower, yielding a runtime of $\Omega(n^2)$, since genetic drift can only be avoided with smaller step sizes of $O(1/n)$. We complement our theoretical results with simulations.<|reference_end|>
@article{florescu2024faster,
    title={Faster Optimization Through Genetic Drift},
    author={Cella Florescu and Marc Kaufmann and Johannes Lengler and Ulysse
  Schaller},
    journal={arXiv preprint arXiv:2404.12147},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.12147},
    primaryClass={cs.NE math.PR}
}