Crossover (genetic algorithm): Difference between revisions

Content deleted Content added

Inline

Revision as of 13:58, 30 May 2018

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

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

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.

Two-point and k-point crossover

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.

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

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

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]

partially matched crossover (PMX)
cycle crossover (CX)
order crossover operator (OX1)
order-based crossover operator (OX2)
position-based crossover operator (POS)
voting recombination crossover operator (VR)
alternating-position crossover operator (AP)
sequential constructive crossover operator (SCX)^[2]

Other possible methods include the edge recombination operator.

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.

^ 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
^ 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

Newsgroup: comp.ai.genetic FAQ - see section on crossover (also known as recombination).

[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>.

[1]

[2]

@@ Line 1: / Line 1: @@
-In [[genetic algorithm]]s, '''crossover''' is a [[genetic operator]] used to vary the programming of a chromosome or [[chromosome (genetic algorithm)|chromosomes]] from one generation to the next. It is analogous to [[reproduction]] and [[chromosomal crossover|biological crossover]], upon which genetic algorithms are based. Crossover is a process of taking more than one parent solution and producing a child solution from them. There are methods for selection of the chromosomes. Those are also given below.
+In [[genetic algorithm|genetic algorithms]] and [[evolutionary computation]], '''crossover''', also called recombination, is a [[genetic operator]] used to combine the [[chromosome (genetic algorithm)|genetic information]] of two parents to generate new offspring. It is one way to [[stochastic|stochastically]] generate new [[candidate solution|solutions]] from an existing population, and analogous to the [[chromosomal crossover|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 [[mutation (genetic algorithm)|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 structure|data structures]] that can be recombined with crossover are [[bit array|bit arrays]], vectors of real numbers, or [[tree (data structure)|trees]].
-==Methods of selection of chromosomes==
-*'''[[Fitness proportionate selection]]''' (SCX) The individual is selected on the basis of fitness. The probability of an individual to be selected increases with the fitness of the individual greater or less than its competitor's fitness.
-*'''Simplex Crossover (SPX)''' <ref>Claudio Comis Da Ronco, Ernesto Benini, GeDEA-II: a simplex-crossover based multi objective evolutionary algorithm including the genetic diversity as objective, GECCO’12 Companion, July 7–11, 2012, Philadelphia, PA, USA. ACM 978-1-4503-1178-6/12/07 https://www.lri.fr/~hansen/proceedings/2012/GECCO/companion/p619.pdf</ref>
-*'''Boltzmann selection'''
-*'''[[Tournament selection]]'''
-*'''Rank selection'''
-*'''Steady state selection'''
-*'''[[Truncation selection]]'''
-*'''Local selection'''
-*'''Fitness uniform selection'''
-==Techniques==
+==Examples==
+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.
-Many crossover techniques exist for organisms which use different data structures to store themselves.
-===Single-point===
+===Single-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:
+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.
 [[File:OnePointCrossover.svg]]
-===Two-point===
+===Two-point and k-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:
+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.
 [[File:TwoPointCrossover.svg|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 and half uniform ===
-The uniform crossover uses a fixed mixing ratio between two parents. Unlike single- and two-point crossover, the uniform crossover enables the parent chromosomes to contribute the gene level rather than the segment level.
+=== Uniform crossover===
-If the mixing ratio is 0.5, the offspring has approximately half of the genes from first parent and the other half from second parent, although cross over points can be randomly chosen as seen below:
+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.
-[[File:UniformCrossover.png]]
+=== Crossover for ordered lists ===
-The uniform crossover evaluates each bit in the parent strings for exchange with a probability of 0.5. Empirical evidence suggest that it is a more exploratory approach to crossover than the traditional exploitative approach that maintains longer schemata. This results in a more complete search of the design space with maintaining the exchange of good information. Unfortunately, no satisfactory theory exists to explain the discrepancies between the uniform crossover and the traditional approaches.
+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.
-<ref>{{cite book|last=(eds.)|first=P.K. Chawdhry ...|title=Soft computing in engineering design and manufacturing|year=1998|publisher=Springer|location=London|isbn=3-540-76214-0|pages=164|url=https://books.google.com/books?id=mxcP1mSjOlsC}}</ref>
+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:<ref>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</ref>
-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.
+# partially matched crossover (PMX)
+# cycle crossover (CX)
-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.
+# order crossover operator (OX1)
-=== Three parent ===
-{{Expand section|date=June 2013}}
-In this technique, the child is derived from three randomly chosen parents. Each bit of the first parent is compared with the same bit of the second parent. When these bits are the same it is used in the offspring, otherwise the bit from the third parent is used in the offspring. For example, the following three parents:
-'''p<sub>1</sub>''' 110100010<br />
-'''p<sub>2</sub>''' 011001001<br />
-'''p<sub>3</sub>''' 110110101
-will produce the following offspring:
-'''o<sub>p<sub>1</sub>p<sub>2</sub>p<sub>3</sub></sub>''' 110100001<ref>Introduction to genetic algorithms By S. N. Sivanandam, S. N. Deepa</ref>
-=== 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 of the cities to be travelled for the [[traveling salesman problem]]. There are many crossover methods for ordered chromosomes. The already mentioned N-point crossover can be applied for ordered chromosomes also, but this always needs a corresponding repair process, actually, some ordered crossover methods are derived from the idea. However, sometimes a crossover of chromosomes produces recombinations which violate the constraint of ordering and thus need to be repaired. Several examples for crossover operators (also mutation operator) preserving a given order are given in:<ref>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</ref>
-# partially matched crossover (PMX): In this method, two crossover points are selected at random and PMX proceeds by position wise exchanges. The two crossover points give matching selection. It affects cross by position-by-position exchange operations. In this method parents are mapped to each other, hence we can also call it partially mapped crossover.<ref>Introduction to genetic algorithms By S. N. Sivanandam, S. N. Deepa</ref>
-# cycle crossover (CX): Beginning at any gene <math>i</math> in parent 1, the <math>i</math>-th gene in parent 2 becomes replaced by it. The same is repeated for the displaced gene until the gene which is equal to the first inserted gene becomes replaced (cycle).
-# order crossover operator (OX1): A portion of one parent is mapped to a portion of the other parent. From the replaced portion on, the rest is filled up by the remaining genes, where already present genes are omitted and the order is preserved.
 # order-based crossover operator (OX2)
 # position-based crossover operator (POS)
@@ Line 62: / Line 36: @@
 # sequential constructive crossover operator (SCX)<ref>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>.</ref>
 Other possible methods include the [[edge recombination operator]].
-== 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 which might be disrupted by a non-respectful crossover operator.
 == See also ==
+* [[Evolutionary computation]]
+* [[Genetic algorithm]]
 * [[Chromosome (genetic algorithm)]]
+* [[Mutation (genetic algorithm)]]
 * [[Fitness approximation]]
 * [[Fitness function]]
-* [[Mutation (genetic algorithm)]]
+* [[Selection (genetic algorithm)]]
 == References ==