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.
Mutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some explicitly defined fitness functions f"n: 0,1 ^n->R that a genetic algorithm with crossover can optimize f"n in expected polynomial time while all evolution strategies based only on mutation (and selection) need expected exponential time. Here such functions and proofs are presented for a genetic algorithm without any idealization. For some functions one-point crossover is appropriate while for others uniform crossover is the right choice.  Evolutionary and genetic algorithms (EAs and GAs) are quite successful randomized function optimizers. This success is mainly based on the interaction of different operators like selection, mutation, and crossover. Since this interaction is still not well understood, one is interested in the analysis of the single operators. Jansen and Wegener [Proceedings of GECCO'2001, 2001, pp. 375-382] have described so-called real royal road functions where simple steady-state GAs have a polynomial expected optimization time while the success probability of mutation-based EAs is exponentially small even after an exponential number of steps. This success of the GA is based on the crossover operator and a population whose size is moderately increasing with the dimension of the search space. Here new real royal road functions are presented where crossover leads to a small optimization time, although the GA works with the smallest possible population size--namely 2.