Crossover (genetic algorithm)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population, and analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

Different algorithms in evolutionary computation may use different data structures to store genetic information, and each genetic representation can be recombined with different crossover operators. Typical data structures that can be recombined with crossover are bit arrays, vectors of real numbers, or trees.

Examples[edit]

Traditional genetic algorithms store genetic information in a chromosome represented by a bit array. Crossover methods for bit arrays are popular and an illustrative example of genetic recombination.

Single-point crossover[edit]

A point on both parents' chromosomes is picked randomly, and designated a 'crossover point'. Bits to the right of that point are swapped between the two parent chromosomes. This results in two offspring, each carrying some genetic information from both parents.

OnePointCrossover.svg

Two-point and k-point crossover[edit]

In two-point crossover, two crossover points are picked randomly from the parent chromosomes. The bits in between the two points are swapped between the parent organisms.

TwoPointCrossover.svg

Two-point crossover is equivalent to performing two single-point crossovers with different crossover points. This strategy can be generalized to k-point crossover for any positive integer k, picking k crossover points.

Uniform crossover[edit]

In uniform crossover, each bit from the offspring's genome is independently chosen from the two parents according to a given distribution. In contrast to k-point crossover, uniform crossover exchanges individual bits and not segments of the bit array. This eliminates positional bias of inheritance, where bits that are close together on the chromosome are more likely to be inherited together, which is unwanted for some algorithms. An analogous positional bias exists in biology and is called genetic linkage.

Typically, each bit is chosen from either parent with equal probability. Other mixing ratios are sometimes used, resulting in offspring which inherit more genetic information from one parent than the other. There exist other variants of uniform crossover, such as half uniform crossover, which uniformly exchanges exactly half of the bits which are unequal between the two parents.

Crossover for ordered lists[edit]

In some genetic algorithms, not all possible chromosomes represent valid solutions. In some cases, it is possible to use specialized crossover and mutation operators that are designed to avoid violating the constraints of the problem.

For example, a genetic algorithm solving the travelling salesman problem may use an ordered list of cities to represent a solution path. Such a chromosome only represents a valid solution if the list contains all the cities that the salesman must visit. Using the above crossovers will often result in chromosomes that violate that constraint. Genetic algorithms optimizing the ordering of a given list thus require different crossover operators that will avoid generating invalid solutions. Many such crossovers have been published:[1]

  1. partially matched crossover (PMX)
  2. cycle crossover (CX)
  3. order crossover operator (OX1)
  4. order-based crossover operator (OX2)
  5. position-based crossover operator (POS)
  6. voting recombination crossover operator (VR)
  7. alternating-position crossover operator (AP)
  8. sequential constructive crossover operator (SCX)[2]

Other possible methods include the edge recombination operator.

See also[edit]

References[edit]

  • 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.
  1. ^ Pedro Larrañaga et al., "Learning Bayesian Network Structures by searching for the best ordering with genetic algorithms", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996
  2. ^ Ahmed, Zakir H. "Genetic Algorithm for the Traveling Salesman Problem Using Sequential Constructive Crossover Operator." International Journal of Biometric and Bioinformatics 3.6 (2010). Computer Science Journals. Web. <https://pdfs.semanticscholar.org/a1e6/50daed4ed9c6a403b08e5d50b3ea9f3b5de4.pdf>.

External links[edit]