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 (1/ (n n) ), which is slow but prevents genetic drift, and an aggressive one with large step sizes (1/ 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 (n 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 (n²), since genetic drift can only be avoided with smaller step sizes of O (1/n). We complement our theoretical results with simulations.