Class OrderCrossoverTwo
 All Implemented Interfaces:
Splittable<CrossoverOperator<Permutation>>
,CrossoverOperator<Permutation>
Implementation of the crossover operator for permutations that is often referred to as Order Crossover 2 (OX2). It is
rather different in function than the original Order Crossover (OX), implemented in class OrderCrossover
. OX2, which
was introduced by Syswerda (see reference below), is very nearly identical to Uniform Order Based Crossover (UOBX) also
introduced by Syswerda in the same paper. UOBX is implemented in the UniformOrderBasedCrossover
class. Each child
produced by OX2 from a given pair of parents can be produced by UOBX from
the same pair of parents. Likewise each child produced by UOBX from a given pair of parents can be produced by OX2 from the
same pair of parents. However, the pair of children produced by OX2 from a given pair of parents will typically differ from
the pair of children produced by UOBX and vice versa. Therefore, OX2 and UOBX are not exactly equivalent. However, it is not
clear whether there is ever an occasion when either one will lead to significantly different performance relative to the other.
The ChipsnSalsa library includes both operators in the interest of comprehensiveness with respect to commonly encountered
permutation crossover operators.
OX2 begins by selecting a random set of indexes. The original description implied each index equally likely chosen as not chosen. However, in our implementation, we provide a parameter u, which is the probability that an index is chosen, much like the parameter of a uniform crossover for bitstrings. We provide a constructor with a default of u=0.5. The elements at those indexes in parent p2 are found in parent p1. Child c1 is then a copy of p1 but with those elements rearranged into the relative order from p2. In a similar way, the elements at the chosen indexes in parent p1 are found in parent p2. Child c2 is then a copy of p2 but with those elements rearranged into the relative order from p1.
Consider this example. Let p1 = [1, 0, 3, 2, 5, 4, 7, 6] and p2 = [6, 7, 4, 5, 2, 3, 0, 1]. Let the random indexes include: 1, 2, 6, and 7. The elements at those indexes in p2, ordered as in p2, are: 7, 4, 0, 1. These are therefore rearranged within p1 to produce c1 = [7, 4, 3, 2, 5, 0, 1, 6]. The elements at the random indexes in p1, ordered as in p1, are: 0, 3, 7, 6. These are therefore rearranged within p2 to produce c2 = [0, 3, 4, 5, 2, 7, 6, 1].
The worst case runtime of a call to cross
is O(n), where n is the length of the
permutations.
OX2 was introduced in the following paper:
Syswerda, G. Schedule Optimization using Genetic Algorithms. Handbook of Genetic Algorithms, 1991.
Although it got its name Order Crossover 2 (OX2) from others in order to distinguish it from
the original OX, such as this paper:
T. Starkweather, S McDaniel, K Mathias, D Whitley, and C Whitley. A Comparison of Genetic Sequencing Operators.
Proceedings of the Fourth International Conference on Genetic Algorithms, pages 6976, 1991.

Constructor Summary
ConstructorDescriptionConstructs Syswerda's order crossover operator, often referred to as OX2.OrderCrossoverTwo
(double u) Constructs Syswerda's order crossover operator, often referred to as OX2. 
Method Summary
Modifier and TypeMethodDescriptionvoid
cross
(Permutation c1, Permutation c2) Performs a crossover for an evolutionary algorithm, such that crossover forms two children from two parents.split()
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.

Constructor Details

OrderCrossoverTwo
public OrderCrossoverTwo()Constructs Syswerda's order crossover operator, often referred to as OX2. Uses a default U=0.5. 
OrderCrossoverTwo
public OrderCrossoverTwo(double u) Constructs Syswerda's order crossover operator, often referred to as OX2. Parameters:
u
 The probability of selecting an index. Throws:
IllegalArgumentException
 if u is less than or equal to 0.0, or if u is greater than or equal to 1.0.


Method Details

cross
Description copied from interface:CrossoverOperator
Performs a crossover for an evolutionary algorithm, such that crossover forms two children from two parents. Implementations of this method modify the parameters, transforming the parents into the children. Specified by:
cross
in interfaceCrossoverOperator<Permutation>
 Parameters:
c1
 A candidate solution subject to the crossover. This method changes the state of c1.c2
 A candidate solution subject to the crossover. This method changes the state of c2.

split
Description copied from interface:Splittable
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of theCopyable
interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state. Specified by:
split
in interfaceSplittable<CrossoverOperator<Permutation>>
 Returns:
 A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.
