Module org.cicirello.chips_n_salsa
Package org.cicirello.search.operators.permutations

Class OrderCrossoverTwo

java.lang.Object
org.cicirello.search.operators.permutations.OrderCrossoverTwo
All Implemented Interfaces:
PermutationFullBinaryOperator, Splittable<CrossoverOperator<Permutation>>, CrossoverOperator<Permutation>
public final class OrderCrossoverTwo extends Object implements CrossoverOperator<Permutation>, PermutationFullBinaryOperator
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 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 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 69-76, 1991.

  • 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

      public void cross(Permutation c1, Permutation c2)
      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 interface CrossoverOperator<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

      public OrderCrossoverTwo 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 the Copyable 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 interface Splittable<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.

    • apply

      public void apply(int[] raw1, int[] raw2, Permutation p1, Permutation p2)
      See PermutationFullBinaryOperator for 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.
      Specified by:
      apply in interface PermutationFullBinaryOperator
      Parameters:
      raw1 - The raw representation of the first permutation.
      raw2 - The raw representation of the second permutation.
      p1 - The first permutation.
      p2 - The second permutation.