Genetic operators

Starndard Population Initializers

These are two population initializers that work across all representations:

StandardInitializer

class geneticengine.algorithms.gp.operators.initializers.StandardInitializer

All individuals are created with full trees (maximum depth in all branches).

How to inject pre-existing programs into the initial population.

The InjectInitialPopulationWrapper class allows you to pass a list of programs to include in the initial population. The remainder of the initial population will be selected via a backup initializer.

Selection operators

Tournament Selection

class geneticengine.algorithms.gp.operators.selection.TournamentSelection(tournament_size, with_replacement=False)

TournamentSelection represents a tournament selection algorithm, where tournament_size individuals are selected at random, and only the best passes to the next generation.

Parameters:

  • tournament_size (int) – number of individuals from the population that will be randomly selected

  • with_replacement (bool) – whether the selected individuals can appear again in another tournament (default: False)

Lexicase Selection

This function generates a selection operator that uses Lexicase Selection [1]

class geneticengine.algorithms.gp.operators.selection.LexicaseSelection(epsilon=False)

Implements Lexicase Selection (http://williamlacava.com/research/lexicase/).

Parameters:

epsilon (bool) – if True, espilon-lexicase is performed. We use the method given by equation 5 in https://dl.acm.org/doi/pdf/10.1145/2908812.2908898.

Elitism and Novelty

Elitism

class geneticengine.algorithms.gp.operators.elitism.ElitismStep

Selects the best individuals from the population.

Novelty

class geneticengine.algorithms.gp.operators.novelty.NoveltyStep

Creates new individuals for the population.

Mutation and Crossover

Mutation

class geneticengine.algorithms.gp.operators.mutation.GenericMutationStep(probability=1)

Applies a mutation to individuals with a given probability.

Parameters:

probability (float)

Note that the operator parameter allows different representations to introduce their own custom mutators.

Crossover

class geneticengine.algorithms.gp.operators.crossover.GenericCrossoverStep(probability=1)

Changes the population by crossing individuals two-by-two together, according to a given probability.

Parameters:

probability (float)

Note that the operator parameter allows different representations to introduce their own custom crossover operators.

Combinators

Combinators allow you to design your own evolutionary algorithms. When they are created, they are agnostic to the population size, so they can be used inside other combinator steps (like SequenceStep or ParallelStep).

In the following example, we are defining a Genetic Programming step that can be used in the Genetic Programming algorithm.

default_generic_programming_step = ParallelStep([
        ElitismStep(),
        NoveltyStep()
        SequenceStep(
            TournamentSelection(tournament_size=5),
            GenericCrossoverStep(probability=0.01),
            GenericMutationStep(probability=0.9),
        )
    ], weights=[.05, .05, .90])
)

In that case, and according to the ParallelStep, a new generation with population size 1000 will have:

  1. the best 50 individuals of the previous generation (5% of elistim);

  2. 50 new individuals (5% of novelty); and

  3. 900 individuals that are create as follows (90% according to the Sequence Step weight):

    • First, 900 individuals will be selected using a tournament each. For each tournament, 5 individuals are chosen at random from the original population, and the best will pass to the next step.

    • The 900 individuals selected via tournament have a 1% probability of being crossover with another individual. Otherwise they will remain to the next step.

    • The 900 individuals that went through crossover or not are not mutated with 90% of probability.

class geneticengine.algorithms.gp.operators.combinators.SequenceStep(*steps)

Applies multiple steps in order, passing the output population of one step to the input population of the next step.

Parameters:

steps (geneticengine.algorithms.gp.structure.GeneticStep)

class geneticengine.algorithms.gp.operators.combinators.ParallelStep(steps, weights=None)

Creates a new population, using different steps for different slices of the target population. The input population for each parallel step is always the complete input population. The output/target population is the one that is split across all of the slices. The size of each slice is given by the proportion of the weight of that particular weight, compared to the sum of all weights.

Consider the example:

another_step = ParallelStep([AStep(), BStep()], weights=[2,3])

In this example, the first 2/5 of the next population will be generated using AStep(), and the next 3/5 will be generated using BStep.

Parameters:
class geneticengine.algorithms.gp.operators.combinators.ExclusiveParallelStep(steps, weights=None)

A version of ParallelStep, where each parallel step receives a portion of the input population equal to the target population of each slice.

Parameters:

References