Evolutionary Operations¶

PyGlove provides a rich set of operations for creating evolutionary algorithms. This notebook explains them through examples. To understand how an evolutionary operation works within an evolutionary algorithm, please see Evolution Algorithm.

!pip install pyglove

import pyglove as pg

Preparation¶

To make examples easy to understand, we use the same DNA list as the input for all operations unless individual cells overrule.

dna_spec = pg.dna_spec(pg.oneof(range(10)))
inputs = [pg.evolution.set_fitness(pg.DNA(i, spec=dna_spec), i) for i in range(10)]
print(inputs)

[DNA(0), DNA(1), DNA(2), DNA(3), DNA(4), DNA(5), DNA(6), DNA(7), DNA(8), DNA(9)]

Generic Operations¶

Generic operations are operations that work with any element types, which can be chained together for representing a complex process.

Pipeline: chains operations together¶

For example, to find the fittest item among the 3 items randomly chosen from the input, we can do:

# Pipeline the randomly selected DNAs to Top1.
(pg.evolution.selectors.Random(3, seed=1) >> pg.evolution.selectors.Top(1))(inputs)

[DNA(4)]

Or:

pg.evolution.Pipeline([
    pg.evolution.selectors.Random(3, seed=1),
    pg.evolution.selectors.Top(1)
])(inputs)

[DNA(4)]

Union: unions the outputs of operations based on the same input¶

For example, find top 1 item unioned with the first 3 items from the input.

(pg.evolution.selectors.Top(1) | pg.evolution.selectors.First(3))(inputs)

[DNA(9), DNA(0), DNA(1), DNA(2)]

Or:

pg.evolution.Union([
    pg.evolution.selectors.Top(1),
    pg.evolution.selectors.First(3)
])(inputs)

[DNA(9), DNA(0), DNA(1), DNA(2)]

Intersection: intersects the outputs of operations based on the same input¶

For example, Find within first 6 items whose fitnesses are among the top 6:

(pg.evolution.selectors.Top(6) & pg.evolution.selectors.First(6))(inputs)

[DNA(5), DNA(4)]

Or:

pg.evolution.Intersection([
    pg.evolution.selectors.Top(6),
    pg.evolution.selectors.First(6)
])(inputs)

[DNA(5), DNA(4)]

Difference: computes the difference between operation outputs¶

For example: Find top 5 items that is not among the first 6 items:

(pg.evolution.selectors.Top(5) - pg.evolution.selectors.First(6))(inputs)

[DNA(9), DNA(8), DNA(7), DNA(6)]

Or:

pg.evolution.Difference([
   pg.evolution.selectors.Top(5),
   pg.evolution.selectors.First(6),
])(inputs)

[DNA(9), DNA(8), DNA(7), DNA(6)]

Symmetric Difference: Computes the items that appear only once among the operation outputs¶

For example, items are either in top 6 or within last 5, but not both:

(pg.evolution.selectors.Top(6) ^ pg.evolution.selectors.Last(5))(inputs)

[DNA(4)]

Or:

pg.evolution.SymmetricDifference([
    pg.evolution.selectors.Top(6),
    pg.evolution.selectors.Last(5)
])(inputs)

[DNA(4)]

Concatenation: Concatenates the outputs of multiple operations¶

For example: the top 5 items and the last 3 items (Items that match both condition will be duplicated):

(pg.evolution.selectors.Top(5) + pg.evolution.selectors.Last(3))(inputs)

[DNA(9), DNA(8), DNA(7), DNA(6), DNA(5), DNA(7), DNA(8), DNA(9)]

Or:

pg.evolution.Concatenation([
  pg.evolution.selectors.Top(5), 
  pg.evolution.selectors.Last(3)
])(inputs)

[DNA(9), DNA(8), DNA(7), DNA(6), DNA(5), DNA(7), DNA(8), DNA(9)]

Repeat: Repeats an operation multiple times on the same input and concatenate the outputs¶

For example, selecting the top 1 candidate and generate 3 children by mutating it.

(pg.evolution.selectors.Top(1) >> pg.evolution.mutators.Uniform(seed=1) * 3)(inputs)

[DNA(9), DNA(4), DNA(7)]

Or:

pg.evolution.Pipeline([
  pg.evolution.selectors.Top(1),
  pg.evolution.Repeat(pg.evolution.mutators.Uniform(seed=1), 3)
])(inputs)

[DNA(9), DNA(4), DNA(7)]

Power: Chains an operation itself multiple times¶

For example, mutate the top 1 DNA 3 times:

(pg.evolution.selectors.Top(1) >> pg.evolution.mutators.Uniform(seed=1) ** 3)(inputs)

[DNA(7)]

Or:

pg.evolution.Pipeline([
  pg.evolution.selectors.Top(1),
  pg.evolution.Power(pg.evolution.mutators.Uniform(seed=1), 3)
])(inputs)

[DNA(7)]

Inversion/Negation: Computes the complementary set of the operation output based on the input¶

For example, items that are not within the top 5:

(~pg.evolution.selectors.Top(5))(inputs)

[DNA(0), DNA(1), DNA(2), DNA(3), DNA(4)]

Or:

(-pg.evolution.selectors.Top(5))(inputs)

[DNA(0), DNA(1), DNA(2), DNA(3), DNA(4)]

which is also equivalent to:

(pg.evolution.Identity() - pg.evolution.selectors.Top(5))(inputs)

[DNA(0), DNA(1), DNA(2), DNA(3), DNA(4)]

Slice: A slice of the input as the output¶

For example, the first 2 elements from 5 random items:

(pg.evolution.selectors.Random(5, seed=1)[:2])(inputs)

[DNA(2), DNA(1)]

Or:

pg.evolution.Slice(
    pg.evolution.selectors.Random(5, seed=1),
    slice(2))(inputs)

[DNA(2), DNA(1)]

Slice can also work with a single integer as the index for requested item, which generates an output list of 1 element.

(pg.evolution.selectors.Random(5, seed=1)[1])(inputs)

[DNA(1)]

Identity: Returns the input as the output¶

For example:

pg.evolution.Identity()(inputs)

[DNA(0),
 DNA(1),
 DNA(2),
 DNA(3),
 DNA(4),
 DNA(5),
 DNA(6),
 DNA(7),
 DNA(8),
 DNA(9)]

Lambda: Wraps a user function into a `Operator`.¶

For example, return all the even-indexed items:

(pg.evolution.Lambda(lambda x: x[::2]))(inputs)

[DNA(0), DNA(2), DNA(4), DNA(6), DNA(8)]

pg.evolution.Lambda is often used when we want to chain multiple user functions together, or combine with built-in operations. For example:

(pg.evolution.Lambda(lambda x: x[::2]).with_prob(0.1, seed=1))(inputs)

[DNA(0),
 DNA(1),
 DNA(2),
 DNA(3),
 DNA(4),
 DNA(5),
 DNA(6),
 DNA(7),
 DNA(8),
 DNA(9)]

Choice: Pipeline a sequence of operations with probabilities.¶

How Choice works is to visit each sub-operation in order, and draw lots (generate a random number within [0, 1]) to determine whether to execute current operation or not. The execution will stop either when all operations have been visited, or the limit of the number of operations to execute is reached.

For example, random select one element or choose the top 1 element with equal probability:

pg.evolution.Choice([
    (pg.evolution.selectors.Random(1, seed=1), 0.5),
    (pg.evolution.selectors.Top(1), 1.0),
], limit=1)(inputs)

[DNA(9)]

If there is no limit, the Top operation will continue to apply on top of Random’s output when the first operation is executed.

Choice also power Operation.with_prob() for chaining the operations:

def with_prob(self, prob):
  return pg.evolution.Choice([
    (self, prob)
  ])

Conditional: Conditional execution based on a predicate.¶

For example, if current step is greater than 10, choose top 3 items, otherwise choose random 5 items:

op = pg.evolution.Conditional(
    lambda xs, step: step > 10,
    pg.evolution.selectors.Top(3),
    pg.evolution.selectors.Random(5, seed=1))
op(inputs, step=4)

[DNA(2), DNA(1), DNA(4), DNA(0), DNA(3)]

op(inputs, step=11)

[DNA(9), DNA(8), DNA(7)]

Conditional also power Operation.if_true() and Operation.if_false():

def if_true(self, predicate):
  return pg.evolution.Conditional(
      predicate,
      self, 
      pg.evolution.Identity())

ElementWise: Perform an operation on each child (which is a list)¶

For example, random select 2 groups from 5 DNA groups, for each selected group, select the top 1 individual:

custom_inputs = [
  [pg.evolution.set_fitness(pg.DNA(i + j), i + j) for i in range(3)]
  for j in range(5)
]
print(custom_inputs)

[[DNA(0), DNA(1), DNA(2)], [DNA(1), DNA(2), DNA(3)], [DNA(2), DNA(3), DNA(4)], [DNA(3), DNA(4), DNA(5)], [DNA(4), DNA(5), DNA(6)]]

(pg.evolution.selectors.Random(2, seed=1)
 >> pg.evolution.ElementWise(pg.evolution.selectors.Top(1)))(custom_inputs)

[[DNA(3)], [DNA(2)]]

This can also be expressed as:

pg.evolution.selectors.Random(2, seed=1).for_each(
    pg.evolution.selectors.Top(1))(custom_inputs)

[[DNA(3)], [DNA(2)]]

Flatten: Flatten nested lists into a flat list¶

For example, to flatten the outputs from previous example, we can do:

(pg.evolution.selectors.Random(2, seed=1) 
 >> pg.evolution.ElementWise(pg.evolution.selectors.Top(1))
 >> pg.evolution.Flatten())(custom_inputs)

[DNA(3), DNA(2)]

Or:

pg.evolution.selectors.Random(2, seed=1).for_each(
    pg.evolution.selectors.Top(1)).flatten()(custom_inputs)

[DNA(3), DNA(2)]

Flatten supports an argument max_level, which specifies the maximum level to flatten, for example:

custom_inputs = [[
    [pg.evolution.set_fitness(pg.DNA(i + j), i + j) for i in range(2)]
    for j in range(2)]
    for k in range(2)]

print(custom_inputs)
print(pg.evolution.Flatten(max_level=1)(custom_inputs))
print(pg.evolution.Flatten(max_level=2)(custom_inputs))

[[[DNA(0), DNA(1)], [DNA(1), DNA(2)]], [[DNA(0), DNA(1)], [DNA(1), DNA(2)]]]
[[DNA(0), DNA(1)], [DNA(1), DNA(2)], [DNA(0), DNA(1)], [DNA(1), DNA(2)]]
[DNA(0), DNA(1), DNA(1), DNA(2), DNA(0), DNA(1), DNA(1), DNA(2)]

UntilChange: Repeat the operation on the input until the output has a difference from its input¶

For example, mutate the input DNA until the output DNA is different from the input:

(pg.evolution.selectors.Top(1) 
 >> pg.evolution.UntilChange(
     pg.evolution.mutators.Uniform(seed=1).with_prob(0.01)))(inputs)

[DNA(4)]

Or:

(pg.evolution.selectors.Top(1) 
 >> pg.evolution.mutators.Uniform(seed=1).with_prob(0.01).until_change())(inputs)

[DNA(4)]

UntilChange also allows the user to specify a max_attempts, for example:

(pg.evolution.selectors.Top(1) 
 >> pg.evolution.mutators.Uniform(seed=1).with_prob(0.01).until_change(
     max_attempts=2))(inputs)

[DNA(9)]

GlobalStateSetter: Set a value to the global state with a key¶

For most common evolutionary algorithms, reproduction is simply a procedure of list processing based on current population. Complex evolutionary algorithms, such as NEAT, NSGA2, however, are based on clusters of individuals, like species, frontiers, etc. In such case, the algorithms need to maintain additional information beyond the population, which should be accessible by all the operations that are involved in the evolution process.

Global state is introduced for this purpose. To understand the design of global state in details, see Evolutionary Algorithm. GlobaStateSetter is the built-in operation for writing global state.

For example: To save the top 5 individuals as a global state associated with key ‘top5’, we can do:

global_state = pg.geno.AttributeDict()
(pg.evolution.selectors.Top(5) >> pg.evolution.GlobalStateSetter('top5'))(
    inputs, global_state=global_state)

[]

Or:

pg.evolution.selectors.Top(5).as_global_state('top5')(
    inputs, global_state=global_state)

[]

We can print the global state:

global_state

{'top5': [DNA(9), DNA(8), DNA(7), DNA(6), DNA(5)]}

We can see GlobalStateSetter returns an empty list. If we want the inputs of global state setter to be returned, we can do the following:

(pg.evolution.selectors.Top(5) >> (
    pg.evolution.GlobalStateSetter('top5')
    + pg.evolution.Identity()))(
        inputs, global_state=global_state)

[DNA(9), DNA(8), DNA(7), DNA(6), DNA(5)]

GlobalStateSetter also supports setting global state with constant values, which is useful when we want to put some flags.

pg.evolution.GlobalStateSetter('sorted', False)(inputs, global_state=global_state)

[]

global_state

{'sorted': False, 'top5': [DNA(9), DNA(8), DNA(7), DNA(6), DNA(5)]}

GlobalStateGetter: Access a value from the global state¶

With global state, an operation can access the values stored in the global state. GlobalStateGetter can be used for such purpose. Instead of consuming the inputs, it does key-value look up from the global state, and use the value as the output.

Disclaimer: It’s up to the user to ensure that the value stored in global state is a list.

pg.evolution.GlobalStateGetter('top5')(inputs, global_state=global_state)

[DNA(9), DNA(8), DNA(7), DNA(6), DNA(5)]

Selectors¶

A selector is an operation that takes a list of items (of any type) as input, and returns a list of selected items as the output.

It’s defined by interface:

class Selector(pg.evolution.Operation):
  """Base class for selectors."""

  @abc.abstractmethod
  def select(
      self,
      inputs: List[Any],
      global_state: pg.geno.AttributeDict,
      step: int) -> List[Any]:

PyGlove provides a list of built-in selectors, which can work with an arbitrary input element type.

First
Last
Top
Bottom
Random
Sample
Proportional

First: Selects the first N items from the input¶

For example, the code below selects the first 3 items:

pg.evolution.selectors.First(3)(inputs)

[DNA(0), DNA(1), DNA(2)]

Last: Selects the last N items from the input¶

For example, the code below selects the last 3 items:

pg.evolution.selectors.Last(3)(inputs)

[DNA(7), DNA(8), DNA(9)]

Top: Selects the top N items from the input¶

By default, selecting the top is based on the fitness, for example:

pg.evolution.selectors.Top(5)(inputs)

[DNA(9), DNA(8), DNA(7), DNA(6), DNA(5)]

Users can also provide a custom ordering key:

pg.evolution.selectors.Top(
    5, key=lambda x: abs(5 - pg.evolution.get_fitness(x)))(inputs)

[DNA(0), DNA(1), DNA(9), DNA(2), DNA(8)]

Bottom: Selects the bottom N items from the input¶

Similarly, Bottom returns the bottom N items:

pg.evolution.selectors.Bottom(5)(inputs)

[DNA(0), DNA(1), DNA(2), DNA(3), DNA(4)]

pg.evolution.selectors.Bottom(
    5, key=lambda x: abs(5 - pg.evolution.get_fitness(x)))(inputs)

[DNA(5), DNA(4), DNA(6), DNA(3), DNA(7)]

Random: Selects N items randomly from the input¶

Randomly select 10 items without replacement:

pg.evolution.selectors.Random(10, seed=1)(inputs)

[DNA(2),
 DNA(1),
 DNA(4),
 DNA(0),
 DNA(3),
 DNA(5),
 DNA(7),
 DNA(9),
 DNA(8),
 DNA(6)]

Randomly select 10 items with replacement:

pg.evolution.selectors.Random(10, replacement=True, seed=1)(inputs)

[DNA(2),
 DNA(9),
 DNA(1),
 DNA(4),
 DNA(1),
 DNA(7),
 DNA(7),
 DNA(7),
 DNA(6),
 DNA(3)]

Sample: Samples items based on sampling weights¶

Sample all items with equal weights:

pg.evolution.selectors.Sample(
    5, weights=lambda xs: [1.0] * len(xs), seed=1)(inputs)

[DNA(1), DNA(8), DNA(7), DNA(2), DNA(4)]

Sample items with exponential increasing weights:

pg.evolution.selectors.Sample(
    5, 
    weights=lambda xs: [1.0 * 2**i for i in range(len(xs))],
    seed=1)(inputs)

[DNA(7), DNA(9), DNA(9), DNA(8), DNA(8)]

Proportional: Selects items from the input proportionally¶

Proportionally selects items from the input based on equal weights:

pg.evolution.selectors.Proportional(
    5, weights=lambda xs: [1.0] * len(xs))(inputs)

[DNA(5), DNA(6), DNA(7), DNA(8), DNA(9)]

Sample items with exponential increasing weights:

pg.evolution.selectors.Proportional(
    5, weights=lambda xs: [1.0 * 2**i for i in range(len(xs))]
    )(inputs)

[DNA(7), DNA(8), DNA(9), DNA(9), DNA(9)]

Recombinators¶

Recombinators are operatons that take a DNA list (length > 1) as the input, and outputs a DNA list. Based on the mechanisms of recombination, there are three types of recombinators:

Point-wise: recombine values at each decision point level.
Segment-wise: recombine DNA sequences
Permutational: change the order of decisions in the DNA sequence.

Point-wise¶

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.

dna_spec = pg.dna_spec(pg.List(
        [pg.oneof(range(10))]
        + [pg.floatv(0.1, 1.)]
        + [pg.manyof(2, range(10), False, False)]))

x = pg.DNA([1, 0.2, [1, 2]], spec=dna_spec)
y = pg.DNA([3, 0.5, [4, 5]], spec=dna_spec)
z = pg.DNA([2, 0.6, [3, 3]], spec=dna_spec)

# Set the fitness of x, y and z.
pg.evolution.set_fitness(x, 0.5)
pg.evolution.set_fitness(y, 0.5)
pg.evolution.set_fitness(z, 0.)

DNA([2, 0.6, [3, 3]])

Uniform Recombinator: Uniformly sample decisions from parents¶

r = pg.evolution.recombinators.Uniform(seed=1)
                         
# For manyof decision points, uniform takes the decisions from one parent
# as a whole.
r([x, y, z])

[DNA([1, 0.6, [3, 3]])]

All point-wise recombinators supports a where argument, which specifies the function that determines what decision should be included for recombination. Excluded decision points will be left in children intact (this means multiple children could be produced, inherting values from their parents), for example:

r = pg.evolution.recombinators.Uniform(
    where=lambda ds: [d for d in ds if not isinstance(d, pg.geno.Float)],
    seed=1)

# Recombining on oneof and manyof, and leave floatv intact.
r([x, y, z])

[DNA([1, 0.5, [4, 3]]), DNA([1, 0.6, [4, 3]]), DNA([1, 0.2, [4, 3]])]

Sample Recombinator: Sample decisions from parents based on a weighting function¶

r = pg.evolution.recombinators.Sample(lambda parents: [0.0, 0.5, 0.5], seed=1)

# Per decision-point sampling with 50% chance from `y` and 50% chance from `z`.
r([x, y, z])

[DNA([3, 0.6, [3, 5]])]

Average Recominbator: Averaging the float decision points from the parents¶

r = pg.evolution.recombinators.Average()

# Per decision-point sampling with 50% chance from `y` and 50% chance from `z`.
r([x, y, z])

[DNA([3, 0.4333333333333333, [4, 5]]),
 DNA([2, 0.4333333333333333, [3, 3]]),
 DNA([1, 0.4333333333333333, [1, 2]])]

WeightedAverage Recombinator: Weighted averaging the float decision points from the parents¶

r = pg.evolution.recombinators.WeightedAverage(lambda parents: [0.0, 0.5, 0.5])

# Weighted averaging float decision point, with weights: [x=0.0, y=0.5, z=0.5].
r([x, y, z])

[DNA([1, 0.55, [1, 2]]), DNA([3, 0.55, [4, 5]]), DNA([2, 0.55, [3, 3]])]

Segment-wise¶

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.

KPoint: Cuts parents into K + 1 segements and alternate the segments¶

K-point crossover is one of the basic crossovers in evolutionary algorithms. It cuts both parents’ DNA at K positions, which forms K + 1 segments. Then it takes the K + 1 segments from both parents in an interleaving manner. For example, a two-point crossover that takes places at cutting points 2 and 5 will result in 2 children as follows::

   Parent 1:   [1,  2,  | 3,  4,  5,  | 6,  7]
   Parent 2:   [10, 20, | 30, 40, 50, | 60, 70]
                        |             |
   Child 1:    [1,  2,  | 30, 40, 50, | 6,  7]
   Child 2:    [10, 20, | 3,  4,  5,  | 60, 70]

2 children as follows: When K=1, we get a single-point crossover. Similarily, when K=2, we get a two-point crossover.

When K equals or is greater than the length of DNA sequence, we get an alternating-position (APX) crossover.

Reference: https://mitpress.mit.edu/books/introduction-genetic-algorithms https://dl.acm.org/doi/abs/10.5555/93126.93134 https://www.intechopen.com/chapters/335

# Single-point recombination
r = pg.evolution.recombinators.KPoint(1, seed=1)

# x = pg.DNA([1, 0.2, [1, 2]], spec=dna_spec)
# y = pg.DNA([3, 0.5, [4, 5]], spec=dna_spec)

# Cut at position 1
print(r([x, y]))

# Cut at position 3
print(r([x, y]))

[DNA([1, 0.5, [4, 5]]), DNA([3, 0.2, [1, 2]])]
[DNA([1, 0.2, [1, 5]]), DNA([3, 0.5, [4, 2]])]

# Two-point recombination
r = pg.evolution.recombinators.KPoint(2, seed=1)

# x = pg.DNA([1, 0.2, [1, 2]], spec=dna_spec)
# y = pg.DNA([3, 0.5, [4, 5]], spec=dna_spec)

# Cut at position 1, 3
print(r([x, y]))

# Cut at position 1, 2
print(r([x, y]))

[DNA([1, 0.5, [4, 2]]), DNA([3, 0.2, [1, 5]])]
[DNA([1, 0.5, [1, 2]]), DNA([3, 0.2, [4, 5]])]

Segmented: Alternating segments with a custom cutting strategy¶

# A fixed single-point crossover at the mid of the chrosome:
r = pg.evolution.recombinators.Segmented(lambda xs: [len(xs) // 2])

# x = pg.DNA([1, 0.2, [1, 2]], spec=dna_spec)
# y = pg.DNA([3, 0.5, [4, 5]], spec=dna_spec)

r([x, y])

[DNA([1, 0.2, [4, 5]]), DNA([3, 0.5, [1, 2]])]

###Permutational

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).

dna_spec = pg.dna_spec(pg.permutate(range(5)))
x = pg.DNA([0, 1, 2, 4, 3], spec=dna_spec)
y = pg.DNA([1, 2, 3, 4, 0], spec=dna_spec)

PMX: Partially mapped crossover¶

The partially mapped crossover (PMX) was proposed by D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” in Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, vol. 1985, pp. 154–159, Los Angeles, USA.

Reference: https://dl.acm.org/doi/10.5555/645511.657095

r = pg.evolution.recombinators.PartiallyMapped(seed=1)
r([x, y])

[DNA([0, 2, 3, 4, 1]), DNA([1, 0, 2, 4, 3])]

OX: Order crossover¶

The order crossover (OX) was proposed by L. Davis, “Applying adaptive algorithms to epistatic domains,” IJCAI, vol. 85, pp. 162–164, 1985.

It builds offspring by choosing a subtour of a parent and preserving the relative order of bits of the other parent.

Reference: https://dl.acm.org/doi/10.5555/1625135.1625164

r = pg.evolution.recombinators.Order(seed=1)
r([x, y])

[DNA([1, 2, 4, 3, 0]), DNA([0, 2, 3, 4, 1])]

CX: Cycle crossover¶

The cycle crossover (CX) operator was first proposed by I. M. Oliver, D. J. d. Smith, and R. C. J. Holland, “Study of permutation crossover operators on the traveling salesman problem,” in Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA, USA, 1987.

Reference: https://dl.acm.org/doi/10.5555/42512.42542.

r = pg.evolution.recombinators.Cycle(seed=1)
r([x, y])

[DNA([1, 2, 3, 4, 0]), DNA([0, 1, 2, 4, 3])]

Semantics with PyGlove hyper primitives¶

		# 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.

Mutators¶

A mutator is an operation that takes a list of DNA as input, and returns a list of DNA by mutating each of them.

Mutators are defined by interface:

class Mutator(DNAOperation):
  """Base class for mutators.

  A mutator performs a mutation, i.e. a random transformation that converts
  a parent DNA to a child DNA. Mutations should reach the full search space
  through composition and should prefer local transformations individually.
  """

  def mutate(
      self,
      dna: pg.DNA,
      global_state: pg.geno.AttributeDict,
      step: int = 0) -> typing.Union[pg.DNA, List[pg.DNA]]:

PyGlove provides a list of mutators:

Uniform
Swap.

dna_spec = pg.dna_spec(pg.List([
    pg.oneof(range(5), name='x'),
    pg.manyof(3, range(4), name='y'),
    pg.floatv(0.0, 1.0, name='z'),
    pg.oneof([
      pg.oneof(range(3)),
      1
    ])
]))

dna = dna_spec.first_dna()
print(dna)

DNA([0, [0, 1, 2], 0.0, (0, 0)])

Uniform Mutator: Select 1 decision point for random mutation¶

Uniform mutator does the following things:

It randomly select one decision point (node) from the search space for mutation.
It then generates a random value for that node, and make necessary adjustment to honor the constraint (e.g. the distinct constraint of pg.manyof). If it mutate a decision point that has child decision points (e.g. nested pg.oneofs), the child desion points will be randomly generated.

m = pg.evolution.mutators.Uniform(seed=1)

# Mutate the first decision of `pg.manyof`.
print(m([dna]))

# Mutate the 3rd decision of `pg.manyof`.
print(m([dna]))

# Mutate the decision of the nested `pg.oneof`.
print(m([dna]))

[DNA([0, [3, 1, 2], 0.0, (0, 0)])]
[DNA([0, [0, 1, 3], 0.0, (0, 0)])]
[DNA([0, [0, 1, 2], 0.0, (0, 1)])]

PyGlove mutators provides a where statement to select applicable nodes. For example, if we want to mutate the pg.floatv from the DNA, we can do:

m = pg.evolution.mutators.Uniform(
    where=lambda d: isinstance(d.spec, pg.geno.Float),
    seed=1)

print(m([dna]))
print(m([dna]))

[DNA([0, [0, 1, 2], 0.5692038748222122, (0, 0)])]
[DNA([0, [0, 1, 2], 0.2550690257394217, (0, 0)])]

We can also filter decision points to mutate by names:

m = pg.evolution.mutators.Uniform(
    where=lambda d: getattr(d.spec, 'name', None) == 'x',
    seed=1)

print(m([dna]))
print(m([dna]))

[DNA([4, [0, 1, 2], 0.0, (0, 0)])]
[DNA([2, [0, 1, 2], 0.0, (0, 0)])]

Swap Mutator: Swap the position of two decisions, applicable only for `pg.manyof`¶

To mutate a permutation, Uniform does not work, since it requires to change the value for at least two decision points. Swap is the mutator to help in this case, which only operates on decision points of pg.manyof.

m = pg.evolution.mutators.Swap(seed=1)

print(m([dna]))
print(m([dna]))
print(m([dna]))

[DNA([0, [2, 1, 0], 0.0, (0, 0)])]
[DNA([0, [1, 0, 2], 0.0, (0, 0)])]
[DNA([0, [0, 2, 1], 0.0, (0, 0)])]