Class PrecedencePreservativeCrossover
 All Implemented Interfaces:
Splittable<CrossoverOperator<Permutation>>
,CrossoverOperator<Permutation>
Implementation of Precedence Preservative Crossover (PPX), the twopoint version. The paper
by Bierwirth et al, which introduced PPX, described two versions of the operator, including the
twopoint 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 twopoint version of PPX, a pair of cross points are chosen randomly, similar to a twopoint bitstring 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 = ij + 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 (lefttoright) 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 (lefttoright) 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 lefttoright 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. 310318.

Constructor Summary
ConstructorDescriptionConstructs a precedence preservative crossover (PPX) operator. 
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

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


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.
