Genetic Algorithms - Crossover
In this chapter, we will discuss about what a Crossover Operator is along with its other modules, their uses and benefits.
Introduction to Crossover
The crossover operator is analogous to reproduction and biological crossover. In this more than one parent is selected and one or more off-springs are produced using the genetic material of the parents. Crossover is usually applied in a GA with a high probability – pc .
Crossover Operators
In this section we will discuss some of the most popularly used crossover operators. It is to be noted that these crossover operators are very generic and the GA Designer might choose to implement a problem-specific crossover operator as well.
One Point Crossover
In this one-point crossover, a random crossover point is selected and the tails of its two parents are swapped to get new off-springs.
Multi Point Crossover
Multi point crossover is a generalization of the one-point crossover wherein alternating segments are swapped to get new off-springs.
Uniform Crossover
In a uniform crossover, we don’t divide the chromosome into segments, rather we treat each gene separately. In this, we essentially flip a coin for each chromosome to decide whether or not it’ll be included in the off-spring. We can also bias the coin to one parent, to have more genetic material in the child from that parent.
Whole Arithmetic Recombination
This is commonly used for integer representations and works by taking the weighted average of the two parents by using the following formulae −
- Child1 = α.x + (1-α).y
- Child2 = α.x + (1-α).y
Obviously, if α = 0.5, then both the children will be identical as shown in the following image.
Davis’ Order Crossover (OX1)
OX1 is used for permutation based crossovers with the intention of transmitting information about relative ordering to the off-springs. It works as follows −
Create two random crossover points in the parent and copy the segment between them from the first parent to the first offspring.
Now, starting from the second crossover point in the second parent, copy the remaining unused numbers from the second parent to the first child, wrapping around the list.
Repeat for the second child with the parent’s role reversed.
There exist a lot of other crossovers like Partially Mapped Crossover (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, etc.
