pg.evolution.recombinators¶

Common recombinators for evolutionary algorithms.

Types of recombinators¶

This file implements 3 types of recombinators: point-wise, segment-wise and permutation.

Point-wise recombinators¶

A point-wise recombinator works for an arbitrary number of parents, it crossovers the parents’ DNA into offspring’s DNA point-by-point. For example, Uniform takes a random parent’s decisions per decision point, Sample samples one of the parents’ decision with probabilities computed from a weighting function provided by the user, and Average works for float decision points by averaging parents’ values into the child’s. When dealing with categorical decision points (e.g. pg.oneof, pg.manyof), Sample can be very sample efficient when the decision points are orthgonal to each other.

Segment-wise recombinators¶

A segment-wise recombinator works on 2 parents, it cuts the parents’ DNA into multiple segments, and chooses alternating semgents from the parents. For example, if the i’th segment of one parent is taken as the i’th segment of a child, the (i + 1)’th segment of the child will be taken from another parent. Each recombination produces 2 children which start with a segment from different parents. For example:

parent 1:   1  2  | 3  4  5  6  | 7  8  9
parent 2:   10 20 | 30 40 50 60 | 70 80 90

child 1:    1  2  | 30 40 50 60 | 7  8  9
child 2:    10 20 | 3  4  5  6  | 70 80 90

Well-known segment-wise recombinators are single-point crossover (SPX), two-point crossover (TPX), K-point crossover and more generally, the segmented crossover. While each of the former three chooses a fixed number of cutting points randomly, the segmented crossover allows the user to specify a function to produce the cutting points, which can be done dynamically based on the global state and step. Also the customized cutting point can be effective when the user knows how the search space should be partitioned based on the application.

Permutations¶

A permutation recombinator works on 2 parents by permutating the order of the subchoices of multi-choice decision points, which can be useful in applications in which the order of choices matters (e.g. the traveling salesman problem). Well-know permutation crossovers are partially mapped crossover (PMX), order crossover (OX) and cycle crossover (CX).

Which recombinators to use?¶

Semantics on hyper primitves¶

		# parents	floatv	oneof	manyof sorted Y \| sorted N distinct \| distinct Y \| N \| Y \| N
Point-wise	Uniform	> 0	X	X	X	X	X	X
	Sample	> 0	X	X	X	X	X	X
	Average	> 0	X
	W-Average	> 0	X
Segment-wise	KPoint	2	X	X	X (treated as a single decision			X
	Segmented	2	X	X	point)			X
Permutation	PMX	2					X
	Order	2					X
	Cycle	2					X

A blank cell means the recombinator works as a no-op on the hyper primitive.

Disruptiveness of recombinations¶

A recombinator is more disruptive if it produces children that has more differences from the parents. In that regard, Uniform is more disruptive than Sample when a fitness-based weighting function i used. KPoint with a larger K is more disruptive than with a smaller K.

The more disruptive an operation is, the more diversity the operation produces. Historically studies shows that with small populations, more disruptive recombination such as Uniform or K-Point (k >> 2) may yield better results because they help overcome the limited information capacity of smaller populations and the tendency for more homogencity. With larger populations, less disruptive recombinations like 2-point are more likely to work better. (Reference: Holland, John H. (1975). Adaptation in Natural and Artificial Systems, The University of Michigan Press.)

When we need faster convergence, Sample with a fitness-based weighting function will be very effective, which can be used to implement a point-wise greedy strategy.

On recombination for float values¶

Adding an Average or WeightedAverage when you have float decision points in the search space (created by pg.floatv). It is a no-op when there is no float decision points in the space.