Crossover

Crossovers are HeuristicLab 3.3 operators that implement the ICrossover interface. Crossover operators for different encodings have already been implemented, such as:

---

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.

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

---

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

---

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

---

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.

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)

---

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.