The analysis of evolutionary algorithms – A proof that crossover really can help

Evolutionary algorithms are randomized search heuristics that were invented in the sixties and have been intensively applied and studied since the eighties. Since then there have been only a few theoretical investigations and no sound theoretical foundation. One of the main sources of difficulty for theoretical analyses is the crossover operator. It can be useful only if the current population of strings has a certain diversity. Here it is proved that an evolutionary algorithm can produce enough diversity such that the use of crossover can speed up the expected optimization time from superpolynomial to a polynomial of small degree.