5.2.3 Population Recombination



next up previous
Next: 5.2.4 Population Mutation Up: 5.2 Genetic Algorithms Previous: 5.2.2 Population Selection

5.2.3 Population Recombination

 

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].



next up previous
Next: 5.2.4 Population Mutation Up: 5.2 Genetic Algorithms Previous: 5.2.2 Population Selection



verena@csep1.phy.ornl.gov