Crossover

Taking the ieeeXplore database as a first reference we find one first publication between 1983 - 1992, then 79 publications between 1993 - 2002, and finally a little 'boost' with 157 between 2003 and (May) 2012.

(((genetic algorithm) AND crossover) AND "Document Title":crossover) 

2003	2012	157
1993	2002	79
1983	1992	1
1973	1982	0

Here I will present a selection of papers from this data base search. Romaniuk [303], [304] uses crossover within a genetic algorithm to support the evolutionary development of simple neural networks. Romaniuk [303]:718 uses 'reproduction' (selecting half of the population with highest fitness values), crossover (the crossover-point is determined by the relative fitness of the parent chromosomes), and mutation (as factor determines the rate at which a chromosome gene value will be altered). In [304]:751 he distinguishes between simple crossover (single randomly selected crossover-point), weighted crossover (crossover-point as a function of the relative fitness of the parents), and blocked crossover (creating barriers between chunks of genes within a chromosome). He gives no general argument for the crossover operator.

Suzuki [374] tries to describe the behavior of simple genetic algorithms with the aid of Markov chain models. Referring to Goldberg [122] he uses as basic elements of a GA 'selection' (in Goldberg also called 'reproduction'), 'crossover' as well as 'mutation' (p.656). His crossover operator can exchange l-many values randomly. Mutation occurs with some probability $\mu$. Although his theoretical approach allows the definition of some very general properties, he points out to some unsolved problems (p.658).

Yamamura et al. [426] are also investigating the overall effect of crossover within a simple GA according to Goldberg [122] using the operators 'selection', 'crossover' and 'mutation'. Similar to Suzuki they use the formalism of Markov chains to model the behavior of GAs. They compare GAs with only a selection operator and GAs with selection and crossover. They can show that the convergence speed of GAs is increased with crossover. This doesn't tell anything about the overall quality of crossover nor about the interplay between crossover and mutation. Nevertheless this is a stimulating paper (as well the paper of Suzuki before).

Qi et al. [294] investigating in their paper the unique diversification role of the crossover operator in genetic algorithms using a uniform crossover operator in multi-dimensional continuous space. They use the three operators: selection, crossover, and mutation as the 'essential' operators (p.120). They define the selection operator according to the 'Darwinian principle' of 'survival of the fittest'. The other two operators crossover and mutation are designed according to the 'mechanisms' of 'gene mutation' and 'chromosome recombination' found in biological genetics. (p.120). They mention three variants how to use crossover in the literatur: two-point crossover, multi-point crossover, and uniform crossover.(p.120) Mentioning explicitly Hollands Schema-theorem as well as Goldberg's 'Building Block Hypothesis' they describe the goal of their paper as ``The Schema Theorem and the Building Block Hypothesis convey the general sense that the genetic algorithm searches for an optimal solution by allocating increasing numbers of sample points to the hyperplanes with high average fitness that are not easily disrupted by crossover. Unfortunately, the above-mentioned results are largely qualitative in nature. This work attempts to show quantitatively how the crossover operator affects the population distribution by casting it into the formal mathematical framework of stochastic processes, and deriving recursive equations governing the population density under repeated crossover.''(p.120)

To be continued....