- All Implemented Interfaces:
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
UniformOrderBasedCrossoverclass. 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 Chips-n-Salsa 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 bit-strings. 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
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 69-76, 1991.
Method SummaryModifier and TypeMethodDescription
PermutationFullBinaryOperatorfor details of this method.
voidPerforms 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.
OrderCrossoverTwopublic OrderCrossoverTwo()Constructs Syswerda's order crossover operator, often referred to as OX2. Uses a default U=0.5.
(double u)Constructs Syswerda's order crossover operator, often referred to as OX2.
u- The probability of selecting an index.
IllegalArgumentException- if u is less than or equal to 0.0, or if u is greater than or equal to 1.0.
crossDescription copied from interface:
CrossoverOperatorPerforms 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.
splitpublic OrderCrossoverTwo split()Description copied from interface:
SplittableGenerates 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 the
Copyableinterface. 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.
PermutationFullBinaryOperatorfor details of this method. This method is not intended for direct usage. Use the
cross(org.cicirello.permutations.Permutation, org.cicirello.permutations.Permutation)method instead.