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

Class UniformPrecedencePreservativeCrossover

java.lang.Object
org.cicirello.search.operators.permutations.UniformPrecedencePreservativeCrossover
All Implemented Interfaces:
PermutationBinaryOperator, Splittable<CrossoverOperator<Permutation>>, CrossoverOperator<Permutation>
public final class UniformPrecedencePreservativeCrossover extends Object implements CrossoverOperator<Permutation>, PermutationBinaryOperator
Implementation of Precedence Preservative Crossover (PPX), the uniform version. The paper by Bierwirth et al, which introduced PPX, described two versions of the operator, including the uniform version that is implemented by this class, and a two-point version implemented by the PrecedencePreservativeCrossover 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 uniform version of PPX, we begin with a random array of booleans the same length as the parent permutations. In the Bierwirth et al paper, it was described with a random array of 1s and 2s, but this is clearly equivalent to booleans. In our implementation, we use a parameter U as the probability of a true. The Bierwirth et al paper didn't specify, implying equally likely or 0.5. One of this class's constructors defaults U = 0.5 for this reason. Each index of the boolean array controls whether the corresponding index of a child permutation c1 comes from parent p1 or parent p2. If true, the next element of child c1 is the first element left-to-right from parent p1 that is not yet in c1; and if false, the next element of child c1 is the first element left-to-right from parent p2 that is not yet in c1. Likewise, if true, the next element of child c2 is the first element left-to-right from parent p2 that is not yet in c2; and if false, the next element of child c2 is the first element left-to-right from parent p1 that is not yet in c2.

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]. Without loss of generality, we'll use 0s and 1s for our example boolean array: [0, 1, 0, 0, 0, 1, 0, 1]. Child c1 gets its first element from p2, beginning with c1 = [0]. The next element of the boolean array is 1, so c1 gets its next element from p1 for c1 = [0, 7]. The next 3 elements of the boolean array are 0s, so c1 gets its next 3 elements from p2 for c1 = [0, 7, 1, 2, 3, 6]. It then gets its next element from p1 because of the 1 in the next spot of the boolean array. The next element comes from p2 for c1 = [0, 7, 1, 2, 3, 6, 4]. And the final element comes from p1, although since there is only 1 unused element it doesn't really matter. The final c1 = [0, 7, 1, 2, 3, 6, 4, 5]. We can form c2 in a similar way, but the meaning of the 0s and 1s in the boolean array is flipped. The result is c2 = [7, 0, 6, 5, 4, 1, 3, 2].

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

    • UniformPrecedencePreservativeCrossover

      public UniformPrecedencePreservativeCrossover()
      Constructs an instance of the uniform version of the precedence preservative crossover (PPX) operator, with a default value of u = 0.5.

    • UniformPrecedencePreservativeCrossover

      public UniformPrecedencePreservativeCrossover(double u)
      Constructs an instance of the uniform version of the precedence preservative crossover (PPX) operator.
      Parameters:
      u - The probability of an index being among the cross points.
      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 UniformPrecedencePreservativeCrossover 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.