Whatever selection procedure is
used, it does not, of course, introduce any new solutions. Solutions
which survive do so in order to serve as progenitors (breeding
stock) for a new generation. It is in the recombination phase that
the algorithm attempts to create new, improved solutions. The key
procedure is that of *crossover*, in which the GA seeks to construct
better solutions by combining the features of good existing ones.

In the simplest form of crossover *(one point crossover)* proceeds as
follows. First, the entire population is paired off at random to
give sets of potential parents. Second, pairs of solutions are
chosen to undergo crossover with probability . If the simulated
weighted coin toss rejects crossover for a pair, then both solutions
remain in the population unchanged. However, if it is approved, then
two new solutions are created by exchanging all the bits following a
randomly selected locus on the strings. For example, if crossover
after position 5 is proposed between solutions

`1 0 0 1 1 1 0 1`

and

`1 1 1 1 0 0 0 0,`

the resulting offspring are

`1 0 0 1 1 0 0 0`

and

`1 1 1 1 0 1 0 1`

which replace their parents in the population.

A slightly more complex operator, first proposed by Cavicchio
[8], is *two point crossover*
in which two crossover points are randomly
selected and the substrings between (and including) those positions
are exchanged. If necessary, strings are treated as continuous
rings. Thus, if crossover between points 6 (selected first) and 2 is
proposed for strings

`1 0 0 1 1 1 0 1`

and

`1 1 1 1 0 0 0 0,`

the resulting offspring are

`1 1 0 1 1 0 0 0`

and

`1 0 1 1 0 1 0 1.`

Whereas, if crossover is between points 2 (selected first) and 6, the offspring are

`1 1 1 1 0 0 0 1`

and

`1 0 0 1 1 1 0 0.`

The even-handedness of two point crossover is appealing. There is no intuitive reason why right-hand bits should be exchanged more frequently than left-hand ones, unless the string represents the binary coding of a single integer or continuous variable, in which case, of course, the significance of individual bits decreases from left to right.

De Jong [15] tested multiple point crossover
operators, which exchange more than one substring, and found that
performance is degraded as more substrings are swapped. Although it
is essential to introduce some changes in order to make progress,
too many alterations make the probability of destroying the good
features of a solution unacceptably high. An effective GA search
requires a balance between *exploitation* (of good features in
existing solutions) and *exploration* - introducing new (combinations
of) features.

The performance of the recombination phase of a GA can also be improved by requiring that crossover introduce variation whenever possible. For instance, if the strings

`1 0 1 0 1 0 1 1`

and

`1 1 0 1 1 0 1 1.`

are chosen partners, then only exchanges
involving bits 2, 3 or 4 will result in offspring differing from
their parents. Booker [5] suggested that a general solution to this
problem is to perform crossover between points in the parents'
*reduced surrogates*, which contain just the nonmatching bits.

For many real applications, problem-specific solution representations and crossover operators have been developed. This flexibility is one of the attractions of GAs - it is very easy to introduce heuristic operators, which can substantially improve algorithm performance. The state of the art has been well reviewed recently by Davis [13].