Putting the “Genetics” back into Genetic Algorithms (Reconsidering the Role of Crossover in Hybrid Operators)

Abstract

The original analysis of genetic algorithms presents combination to be the primary mechanism of crossover. Although good solutions can be found by combination, they are often not locally optimal. Thus, a popular technique is to locally optimize each crossover solution before adding it to the population. In these "hybrid" operators, crossover can be viewed as a means of restarting the local optimizer. Unfortunately, if crossover does little more than combine random parts of two parent solutions, the performance of the resulting hybrid operator may not be significantly different from random restart of the local optimizer. The design of the crossover operator affects the efficiency and effectiveness of hybrid operators. A new analysis presents preserving common schemata as an important design consideration for crossover.