Crossover (genetic algorithm)

In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based.

Additional recommended knowledge

Daily Sensitivity Test

How to ensure accurate weighing results every day?

Guide to balance cleaning: 8 simple steps

Crossover techniques

Many crossover techniques exist for organisms which use different data structures to store themselves.

One-point crossover

A single crossover point on both parents' organism strings is selected. All data beyond that point in either organism string is swapped between the two parent organisms. The resulting organisms are the children:

Two-point crossover

Two-point crossover calls for two points to be selected on the parent organism strings. Everything between the two points is swapped between the parent organisms, rendering two child organisms:

"Cut and splice"

Another crossover variant, the "cut and splice" approach, results in a change in length of the children strings. The reason for this difference is that each parent string has a separate choice of crossover point.

Uniform Crossover and Half Uniform Crossover

In both these schemes: the two parents are combined to produce two new offspring.

In the uniform crossover scheme (UX) individual bits in the string are compared between two parents. The bits are swapped with a fixed probability, typically 0.5.

In the half uniform crossover scheme (HUX), exactly half of the nonmatching bits are swapped. Thus first the Hamming distance (the number of differing bits) is calculated. This number is divided by two. The resulting number is how many of the bits that do not match between the two parents will be swapped.

Crossover for Ordered Chromosomes

Depending on how the chromosome represents the solution, a direct swap may not be possible.

One such case is when the chromosome is an ordered list, such as an ordered list the cities to be travelled for the traveling salesman problem. A crossover point is selected on the parents. Since the chromosome is an ordered list, a direct swap would introduce duplicates and remove necessary candidates from the list. Instead, the chromosome up to the crossover point is retained for each parent. The information after the crossover point is ordered as it is ordered in the other parent. For example, if our two parents are ABCDEFGHI and IGAHFDBEC and our crossover point is after the fourth character, then the resulting children would be ABCDIGHFE and IGAHBCDEF.

Other possible methods include the edge recombination operator and partially mapped crossover.

Crossover biases

For crossover operators which exchange contiguous sections of the chromosomes (e.g. k-point) the ordering of the variables may become important. This is particularly true when good solutions contain building blocks which might be disrupted by a non-respectful crossover operator.

See also

• Genetic algorithm
• Mutation (genetic algorithm)
• Chromosome (genetic algorithm)

References

• John Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Michigan. 1975. ISBN 0-262-58111-6.
• Larry J. Eshelman, The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination, in Gregory J. E. Rawlins editor, Proceedings of the First Workshop on Foundations of Genetic Algorithms. pages 265-283. Morgan Kaufmann, 1991. ISBN 1-55860-170-8.
• Tomasz D. Gwiazda, Genetic Algorithms Reference Vol.1 Crossover for single-objective numerical optimization problems, Tomasz Gwiazda, Lomianki, 2006. ISBN 83-923958-3-2.