How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms∗

We re-investigate a fundamental question: how effective is crossover in Genetic Algo-rithms in combining building blocks of good solutions? Although this has been dis-cussed controversially for decades, we are still lacking a rigorous and intuitive answer. We provide such answers for royal road functions and ONEMAX, where every bit is a building block. For the latter we show that using crossover makes every (µ+λ) Genetic Algorithm twice as fast as the fastest evolutionary algorithm using only standard bit mutation, up to small-order terms and for moderate µ and λ. Crossover is beneficial because it effectively turns fitness-neutral mutations into improvements by combining the right building blocks at a later stage. Compared to mutation-based evolutionary al-gorithms, this makes multi-bit mutations more useful. Introducing crossover changes the optimal mutation rate on ONEMAX from 1/n to (1 + 5)/2 · 1/n ≈ 1.618/n. This holds both for uniform crossover and k-point crossover. Experiments and statistical tests confirm that our findings apply to a broad class of building-block functions