Explaining to what extent the real power of genetic algorithms lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay between mutation and crossover can make genetic algorithms hillclimb faster than their mutation-only counterparts. We devise a Markov Chain framework that allows to rigorously prove an upper bound on the runtime of standard steady state genetic algorithms to hillclimb the OneMax function. The bound establishes that the steady-state genetic algorithms are 25 faster than all standard bit mutation-only evolutionary algorithms with static mutation rate up to lower order terms for moderate population sizes. The analysis also suggests that larger populations may be faster than populations of size 2. We present a lower bound for a greedy (2+1) GA that matches the upper bound for populations larger than 2, rigorously proving that 2 individuals cannot outperform larger population sizes under greedy selection and greedy crossover up to lower order terms. In complementary experiments the best population size is greater than 2 and the greedy genetic algorithms are faster than standard ones, further suggesting that the derived lower bound also holds for the standard steady state (2+1) GA.
The interplay between crossover and mutation may produce a speed-up also in the exploitation phase, for instance when the algorithm is hillclimbing. Research in this direction has recently appeared. The design of the (1+( @math )) GA was theoretically driven to beat the @math lower bound of all unary unbiased black box algorithms. Since the dynamics of the algorithm differ considerably from those of standard GAs, it is difficult to achieve more general conclusions about the performance of GAs from the analysis of the (1+( @math )) GA. From this point of view the work of Sudholt is more revealing when he shows that any standard ( @math ) GA outperforms its standard bit mutation-only counterpart for hillclimbing the function @cite_28 . The only caveat is that the selection stage enforces diversity artificially, similarly to how Jansen and Wegener had enforced diversity for the Real Royal Road function analysis. In this paper we rigorously prove that it is not necessary to enforce diversity artificially for standard-steady state GAs to outperform their standard bit mutation-only counterpart.
@cite_28
2187785713
We reinvestigate 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 + i¾ genetic algorithm at least twice as fast as the fastest evolutionary algorithm using only standard bit mutation, up to small-order terms and for moderatei¾ andi¾ . Crossover is beneficial because it can capitalize on mutations that have both beneficial and disruptive effects on building blocks: crossover is able to repair the disruptive effects of mutation in later generations. Compared to mutation-based evolutionary algorithms, this makes multibit mutations more useful. Introducing crossover changes the optimal mutation rate on OneMax from to . 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.