next up previous

4.2.3 Population Recombination     continued...

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.