[[PageOutline]] = Crossover = Crossovers are HeuristicLab 3.3 operators that implement the `ICrossover` interface. Crossover operators for different encodings have already been implemented, such as: ---- [=#Binary] == Crossover for !BinaryVectorEncoding == '''Common Operator Parameters:''' The following paramters are present for all Crossover operators that can be applied to binary vector encoded solutions: ||= Parameter =||= Description =|| || Child || The child vector resulting from the crossover. || || Parents || The parent vectors which should be crossed. || || Random || The pseudo random number generator which should be used for stochastic crossover operators. || === !MultiBinaryVectorCrossover === Randomly selects and applies one of its crossovers every time it is called. [[Image(MultiBinaryVectorCrossover_Parameters.png)]] '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || 0-2 || 3 Crossover Operators || || Probabilities || The array of relative probabilities for each operator (Default: Uniform {{{[1,1,1]}}}) || === NPointCrossover === N point crossover for binary vectors. It is implemented as described in (Eiben and Smith 2003). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || N || Number of crossover points (Default: 2) || === !MultiBinaryVectorCrossover === Randomly selects and applies one of its crossovers every time it is called. === !SinglePointCrossover === Single point crossover for binary vectors. It is implemented based on the NPointCrossover. === !UniformCrossover === Uniform crossover for binary vectors. It is implemented as described in (Eiben and Smith 2003). ---- [=#Integer] == Crossover for !IntegerVectorEncoding == '''Common Operator Parameters:''' The following paramters are present for all Crossover operators that can be applied to integer vector encoded solutions: ||= Parameter =||= Description =|| || Child || The child vector resulting from the crossover. || || Parents || The parent vectors which should be crossed. || || Random || The pseudo random number generator which should be used for stochastic crossover operators. || === !DiscreteCrossover === Discrete crossover for integer vectors. It is implemented as described in (Gwiazda 2006, p. 17). === !MultiIntegerVectorCrossover === Randomly selects and applies one of its crossovers every time it is called. '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || 0-1 || 2 Crossover Operators || || Probabilities || The array of relative probabilities for each operator (Default: Uniform {{{[1,1]}}}) || === !SinglePointCrossover === Single point crossover for integer vectors. It is implemented as described in (Michalewicz 1999). ---- [=#Permutation] == Crossover for !PermutationEncoding == '''Common Operator Parameters:''' The following paramters are present for all Crossover operators that can be applied to binary vector encoded solutions: ||= Parameter =||= Description =|| || Child || The child vector resulting from the crossover. || || Parents || The parent vectors which should be crossed. || || Random || The pseudo random number generator which should be used for stochastic crossover operators. || === !CosaCrossover === An operator which performs the crossover described in the COSA optimization method. It is implemented as described in (Wendt 1994). === !CyclicCrossover === An operator which performs the cyclic crossover on two permutations. It is implemented as described in (Eiben and Smith 2003). === !CyclicCrossover2 === An operator which performs the cyclic crossover on two permutations. It is implemented as described in (Affenzeller et al. 2009, p. 136) === !EdgeRecombinationCrossover === An operator which performs the edge recombination crossover on two permutations. It is implemented as described in (Whitley et al. 1991). === !MaximalPreservativeCrossover === An operator which performs the maximal preservative crossover on two permutations. It is implemented as described in (Mühlenbein 1991). === !MultiPermutationCrossover === Randomly selects and applies one of its crossovers every time it is called. '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || 0-9 || 10 Crossover Operators || || Probabilities || The array of relative probabilities for each operator (Default: Uniform {{{[1,1,1,1,1,1,1,1,1,1]}}}) || === !OrderBasedCrossover === An operator which performs an order based crossover of two permutations. It is implemented as described in (Syswerda 1991). === !OrderCrossover === An operator which performs an order crossover of two permutations. It is implemented as described in (Eiben and Smith 2003). === !OrderCrossover2 === An operator which performs an order crossover of two permutations. It is implemented as described in (Affenzeller et al. 2009, p. 135). === !PartiallyMatchedCrossover === An operator which performs the partially matched crossover on two permutations. It is implemented as described in (Fogel 1988). === !PositionBasedCrossover === An operator which performs the position based crossover on two permutations. It is implemented as described in (Syswerda 1991). ---- [=#Real] == Crossover for !RealVectorEncoding == '''Common Operator Parameters:''' The following paramters are present for all Crossover operators that can be applied to real vector encoded solutions: ||= Parameter =||= Description =|| || Bounds || The lower and upper bounds of the real vector. || || Child || The child vector resulting from the crossover. || || Parents || The parent vectors which should be crossed. || || Random || The pseudo random number generator which should be used for stochastic crossover operators. || === !AverageCrossover === The average crossover (intermediate recombination) produces a new offspring by calculating in each position the average of a number of parents. It is implemented as described by (Beyer and Schwefel 2002). === !BlendAlphaBetaCrossover === The blend alpha beta crossover (BLX-a-b) for real vectors is similar to the blend alpha crossover (BLX-a), but distinguishes between the better and worse of the parents. The interval from which to choose the new offspring can be extended more around the better parent by specifying a higher alpha value. It is implemented as described in (Takahashi and Kita 2001). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Alpha || The value for alpha (Default: 0.75) || || Beta || The value for alpha (Default: 0.25) || || Maximization || Whether the problem is a maximization problem or not. || || Quality || The quality values of the parents. || === !BlendAlphaCrossover === The blend alpha crossover (BLX-a) for real vectors creates new offspring by sampling a new value in the range [min_i - d * alpha, max_i + d * alpha) at each position i. Here min_i and max_i are the smaller and larger value of the two parents at position i and d is max_i - min_i. It is implemented as described in (Takahashi and Kita 2001). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Alpha || The value for alpha (Default: 0.5) || === !DiscreteCrossover === Discrete crossover for real vectors: Creates a new offspring by combining the alleles in the parents such that each allele is randomly selected from one parent. It is implemented as described in (Beyer and Schwefel 2002). === !HeuristicCrossover === The heuristic crossover produces offspring that extend the better parent in direction from the worse to the better parent. It is implemented as described in (Wright 1994). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Maximization || Whether the problem is a maximization problem or not. || || Quality || The quality values of the parents. || === !LocalCrossover === The local crossover is similar to the arithmetic all positions crossover, but uses a random alpha for each position x = alpha * p1 + (1-alpha) * p2. It is implemented as described in (Dumitrescu et al. 2000, p. 194). === !MultiRealVectorCrossover === Randomly selects and applies one of its crossovers every time it is called. [[Image(MultiRealVectorCrossover_Parameters.png)]] '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || 0-10 || 11 Crossover Operators || || Quality || The quality values of the parents. || || Probabilities || The array of relative probabilities for each operator (Default: Uniform {{{[1,1,1,1,1,1,1,1,1,1,1]}}}) || === !RandomConvexCrossover === The random convex crossover acts like the local crossover, but with just one randomly chosen alpha for all crossed positions. It is implementes as described in (Dumitrescu et al. 2000, pp. 193 - 194). === !SimulatedBinaryCrossover === The simulated binary crossover (SBX) is implemented as described in (Deb and Agrawal 1995). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Contiguity || Specifies whether the crossover should produce very different (small value) or very similar (large value) children. Valid values must be greater or equal to 0 (Default: 2). || === !SinglePointCrossover === Breaks both parent chromosomes at a randomly chosen point and assembles a child by taking one part of the first parent and the other part of the second pard. It is implemented as described in (Michalewicz 1999). === !UniformAllPositionsArithmeticCrossover === The uniform all positions arithmetic crossover constructs an offspring by calculating x = alpha * p1 + (1-alpha) * p2 for every position x in the vector. Note that for alpha = 0.5 it is the same as the !AverageCrossover. It is implemented as described in (Michalewicz 1999). '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Alpha || The alpha value in the range [0;1] (Default: 0.33) || === !UniformSomePositionsArithmeticCrossover === The uniform some positions arithmetic crossover (continuous recombination) constructs an offspring by calculating x = alpha * p1 + (1-alpha) * p2 for a position x in the vector with a given probability (otherwise p1 is taken at this position). It is implemented as described in (Dumitrescu et al. 2000, p. 191). Note that Dumitrescu et al. specify the alpha to be 0.5. '''Additional Operator Parameters:''' ||= Parameter =||= Description =|| || Alpha || The alpha value in the range [0;1] (Default: 0.5) || || Probability || The probability for crossing a position in the range [0;1] (Default: 0.5) || ---- [=#Trees] == Crossover for !SymbolicExpressionTreeEncoding == === !SubTreeCrossover === An operator which performs subtree swapping crossover. '''Operator Parameters:''' ||= Parameter =||= Description =|| || Child || The child vector resulting from the crossover. || || !FailedCrossoverEvents || The number of failed crossover events (child is an exact copy of a parent) (Default: 0) || || !InternalCrossoverPointProbability || The probability to select an internal crossover point (instead of a leaf node). (Default: 90%) || || !MaxTreeHeight || The maximal height of the symbolic expression tree (a tree with one node has height = 0). || || !MaxTreeSize || The maximal size (number of nodes) of the symbolic expression tree. || || Parents || The parent vectors which should be crossed. || || Random || The pseudo random number generator which should be used for stochastic crossover operators. || || !SymbolicExpressionGrammar || The grammar that defines the allowed symbols and syntax of the symbolic expression trees. || ---- == References == * Affenzeller, M. et al. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press. * Beyer, H.-G. and Schwefel, H.-P. 2002. Evolution Strategies - A Comprehensive Introduction Natural Computing, 1, pp. 3-52. * Deb, K. and Agrawal, R. B. 1995. Simulated binary crossover for continuous search space. Complex Systems, 9, pp. 115-148. * Dumitrescu, D. et al. 2000. Evolutionary computation. CRC Press. Boca Raton. FL. * Eiben, A.E. and Smith, J.E. 2003. Introduction to Evolutionary Computation. Natural Computing Series, Springer-Verlag Berlin Heidelberg. * Fogel, D.B. 1988. An Evolutionary Approach to the Traveling Salesman Problem. Biological Cybernetics, 60, pp. 139-144, Springer-Verlag. * Gwiazda, T.D. 2006. Genetic algorithms reference Volume I Crossover for single-objective numerical optimization problems. * Michalewicz, Z. 1999. Genetic Algorithms + Data Structures = Evolution Programs. Third, Revised and Extended Edition, Springer-Verlag Berlin Heidelberg. * Mühlenbein, H. 1991. Evolution in time and space - the parallel genetic algorithm. FOUNDATIONS OF GENETIC ALGORITHMS. Morgan Kaufmann. pp. 316-337. * Syswerda, G. 1991. Schedule Optimization Using Genetic Algorithms. In Davis, L. (Ed.) Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, pp. 332-349. * Takahashi, M. and Kita, H. 2001. A crossover operator using independent component analysis for real-coded genetic algorithms Proceedings of the 2001 Congress on Evolutionary Computation, pp. 643-649. * Wendt, O. 1994. COSA: COoperative Simulated Annealing - Integration von Genetischen Algorithmen und Simulated Annealing am Beispiel der Tourenplanung. Dissertation Thesis. IWI Frankfurt. * Whitley et.al. 1991, The Traveling Salesman and Sequence Scheduling, in Davis, L. (Ed.), Handbook of Genetic Algorithms, New York. pp. 350-372 * Wright, A.H. 1994. Genetic algorithms for real parameter optimization, Foundations of Genetic Algorithms. G.J.E. Rawlins (Ed.). Morgan Kaufmann. San Mateo. CA. pp. 205-218.