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

Class PrecedencePreservativeCrossover

java.lang.Object
org.cicirello.search.operators.permutations.PrecedencePreservativeCrossover
All Implemented Interfaces:
PermutationBinaryOperator, Splittable<CrossoverOperator<Permutation>>, CrossoverOperator<Permutation>
public final class PrecedencePreservativeCrossover extends Object implements CrossoverOperator<Permutation>, PermutationBinaryOperator
Implementation of Precedence Preservative Crossover (PPX), the two-point version. The paper by Bierwirth et al, which introduced PPX, described two versions of the operator, including the two-point version that is implemented by this class, and a uniform version, implemented in the UniformPrecedencePreservativeCrossover class. They referred to both simply as PPX in that paper, but these are essentially two very similar, closely related crossover operators.

The paper that originally described PPX described it as producing one child from the cross of two parents. However, our implementation generalizes this in the obvious way to producing two children from two parents. In the two-point version of PPX, a pair of cross points are chosen randomly, similar to a two-point bit-string crossover. The cross points are used in a rather different manner than other operators with cross points. Let's say that the two cross points are i and j, and that i is the lower of the two cross indexes. Child c1 gets everything to the left of i from parent p1, and likewise child c2 gets everything to the left of i from parent p2. Now let k = |i-j| + 1, be the size of the region defined by indexes i and j. Child c1 gets its next k elements from parent p2, specifically the first k elements (left-to-right) from parent p2 that are not yet in child c1. Likewise, child c2 gets its next k elements from parent p1, specifically the first k elements (left-to-right) from parent p1 that are not yet in child c2. The remaining elements of child c1 come from parent p1 in the order they appear in p1; and the remaining elements of child c2 come from parent p2 in the order they appear in p2.

Consider this example with parent p1 = [7, 6, 5, 4, 3, 2, 1, 0] and parent p2 = [0, 1, 2, 3, 4, 5, 6, 7]. Now consider that the random i and j are 3 and 5, which means k = 3. Child c1 gets its first i=3 elements from p1, for example c1 = [7, 6, 5], and likewise c2 begins with the first i=3 elements of p2, such that c2 = [0, 1, 2]. Child c1 gets its next k=3 elements from p2, the first 3 such elements left to right from p2 that are not yet present in c1, which in this case happens to be p2's first 3 elements, leading to c1 = [7, 6, 5, 0, 1, 2]. And in a similar way, c2 is now c2 = [0, 1, 2, 7, 6, 5]. We can now complete c1 taking the remaining elements from p1 that are not yet in c1 in a left-to-right order. The final c1 = [7, 6, 5, 0, 1, 2, 4, 3]. Likewise, the final c2 = [0, 1, 2, 7, 6, 5, 3, 4].

The worst case runtime of a call to cross is O(n), where n is the length of the permutations.

PPX was introduced in the following paper:
Bierwirth, C., Mattfeld, D., and Kopfer, H. On permutation representations for scheduling problems. Proceedings of the International Conference on Parallel Problem Solving from Nature, 1996, pp. 310-318.

  • Constructor Details

    • PrecedencePreservativeCrossover

      public PrecedencePreservativeCrossover()
      Constructs a precedence preservative crossover (PPX) operator.

  • 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 PrecedencePreservativeCrossover 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)
      See PermutationBinaryOperator 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 PermutationBinaryOperator
      Parameters:
      raw1 - The raw representation of the first permutation.
      raw2 - The raw representation of the second permutation.