- All Implemented Interfaces:
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
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
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 SummaryConstructorDescriptionConstructs a precedence preservative crossover (PPX) operator.
Method SummaryModifier and TypeMethodDescription
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.
PrecedencePreservativeCrossoverpublic PrecedencePreservativeCrossover()Constructs a precedence preservative crossover (PPX) operator.
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 PrecedencePreservativeCrossover 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.