On a genetic algorithm, chromosomal crossover is the process of combining two chromosomes into a new one, similarly to what happens in Biology.
There are several ways to implement this, and which one is the best will depend on the use case. Let’s look at some of the most common.
If our chromosomes are arrays of genes, we can define a random index, the crossover point, and combine both arrays with elements from the first one, where index <= crossoverPoint, and the elements of the second one, where index > crossoverPoint.
| g0 | g1 | g2 | g3 | g4 | ||
|---|---|---|---|---|---|---|
| Individual A | 0 | 1 | 0 | 1 | 1 | |
| Individual B | 1 | 0 | 1 | 1 | 0 | |
| Crossover point | ||||||
| Offspring A + B | 0 | 1 | 0 | 1 | 0 |
In this example, the offspring got the genes g0, g1 and g2 from Individual A, and genes g3 and g4 from Individual B.
Single-point crossover may result in greater gene entanglement at the edges of the chromosome, since most of the time they will be inherited together. A variation of the technique introduces multiple crossover points, making for a more uniform randomization.
| g0 | g1 | g2 | g3 | g4 | |||
|---|---|---|---|---|---|---|---|
| Individual A | 0 | 1 | 0 | 1 | 1 | ||
| Individual B | 1 | 0 | 1 | 1 | 0 | ||
| Crossover point | Crossover point | ||||||
| Offspring A + B | 0 | 0 | 1 | 1 | 1 |
With uniform crossover each offspring gene is inherited from either chromosome with equal probability. This approach is most useful when we do not need to preserve the ordering of the genes.
| g0 | g1 | g2 | g3 | g4 | |
|---|---|---|---|---|---|
| Individual A | 0 | 1 | 0 | 1 | 1 |
| Individual B | 1 | 0 | 1 | 1 | 0 |
| Offspring A + B | 0 | 0 | 0 | 1 | 1 |
This also opens the possibility of combining corresponding genes, rather than selecting either one. For example, if we have two genes with continuous values, the combined gene can be given by their average or a randomly weighted mean.
