Sexual Reproduction Can Speed Up Optimisation

Despite reproduction via recombination being at the centre stage in life and much more successful than asexual reproduction in natural evolution, the most successful optimisation heuristics rely on variation operators that resemble or are inspired by asexual evolution. Examples of such heuristics include local search and simulated annealing. We present an analysis of the performance of a standard steady-state genetic algorithm (GA) for the Mastermind problem with two colours, also known as OneMax. We prove that the GA can identify the solution to the problem using fewer guesses than asexual evolution heuristics. By providing bounds on the optimisation time that decrease with the population size, we give an indication of the benefits of evolving a population of solutions via recombination, mutation and selection.