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 an analogy to reproduction and biological crossover, upon which genetic algorithms are based.
| Contents |
Crossover techniques
Many crossover techniques exist for organisms which use different data structures to store themselves.
One point crossover
A crossover point on the parent organism string is selected. All data beyond that point in the organism string is swapped between the two parent organisms. The resulting organisms are the children:
Missing image
SinglePointCrossover.png
Image:SinglePointCrossover.png
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:
Missing image
TwoPointCrossover.png
Image:TwoPointCrossover.png
"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.
Missing image
CutSpliceCrossover.png
Image:CutSpliceCrossover.png
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.
See also
External links
- Newsgroup: comp.ai.genetic FAQ (http://www.faqs.org/faqs/ai-faq/genetic/part2/) - see section on crossover (also known as recombination).
References
- John Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Michigan. 1975. ISBN 0262581116.
- 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.