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.
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:
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.
See also
