How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms
This provides a rigorous and intuitive answer to a fundamental debate in evolutionary computation, though it is incremental as it builds on existing theoretical frameworks.
The paper tackles the long-standing question of crossover effectiveness in Genetic Algorithms by rigorously analyzing its impact on building-block assembly, showing that crossover makes every (μ+λ) Genetic Algorithm at least twice as fast as mutation-only algorithms on OneMax, with an optimal mutation rate shift from 1/n to approximately 1.618/n.
We re-investigate a fundamental question: how effective is crossover in Genetic Algorithms in combining building blocks of good solutions? Although this has been discussed 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 at least 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 algorithms, this makes multi-bit mutations more useful. Introducing crossover changes the optimal mutation rate on OneMax from $1/n$ to $(1+\sqrt{5})/2 \cdot 1/n \approx 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.