Operators and Algorithms¶

This section describes the operators and algorithms that are available in the deap_er.tools module. For all subsequent examples, assume we have two individuals available as defined below:

from deap_er import Fitness, Toolbox, creator, tools
import random

IND_SIZE = 5

creator.create_type("FitnessMin", Fitness, weights=(-1.0, -1.0))
creator.create_type("Individual", list, fitness=creator.FitnessMin)

toolbox = Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.init_repeat,
                 container=creator.Individual,
                 func=toolbox.attr_float,
                 size=IND_SIZE)

ind1 = toolbox.individual()
ind2 = toolbox.individual()

Operators¶

Evaluation¶

Evaluation operators are responsible for generating fitness values from the solution values of an individual. This is the only operator that the user has to implement themselves, as it's specific to each optimization problem. A typical evaluation function takes an individual as the only argument and returns its fitness value(s) as a tuple of floats. Please refer to Creating Individuals for information about Fitness.

The following example evaluates the previously created individual ind1 and assigns the resulting fitness values to the fitness.values attribute of the individual:

def evaluate(individual) -> tuple[float]:  # Must be a tuple of float(s)
    # Compute the fitness value(s)
    return fit1, fit2

print(ind1.fitness.is_valid())  # False
print(ind1.fitness.values)      # ()

ind1.fitness.values = evaluate(ind1)

print(ind1.fitness.is_valid())  # True
print(ind1.fitness.values)      # (float, float)

Attention

All evaluation functions must return a tuple of float(s) for all types of fitness objectives.

Register evaluate_batch when a whole generation should be scored in one call. The builtin loops (ea_simple, ea_mu_plus_lambda, ea_mu_comma_lambda, ea_map_elites, ea_generate_update, step_islands, and harm) use it in place of map + evaluate. See Multiprocessing.

Mutation¶

Mutation operators are responsible for mutating the solution values of an individual. There are a variety of mutation operators available in the deap_er.tools module, including bounded Gaussian (mut_gaussian_bounded), per-gene heterogeneous mutation (mut_heterogeneous), and a DE/rand/1/bin trial (mut_de). Each mutation operator has its own characteristics and therefore it's recommended to read their documentation before use to avoid undesirable behavior. See the Operators reference.

In the following example, the original individual is cloned and the clone is mutated. This can be done to preserve the original individual if needed, as mutation operators directly modify the input individuals. After mutation, the fitness values of the mutant must be deleted, because they are no longer relevant to the solution values of the mutant.

toolbox.register("clone", tools.clone_individual)
clone = toolbox.clone(ind1)
tools.mut_flip_bit(clone, mut_prob=0.2)
del clone.fitness.values

Crossover¶

Crossover operators are responsible for mating the solution values of two or more individuals. There are a variety of crossover operators available in the deap_er.tools module. Each crossover operator has its own characteristics and therefore it's recommended to read their documentation before use to avoid undesirable behavior. See the Operators reference.

In the following example, the original individuals are cloned and the clones are mated with each other. This can be done to preserve the original individuals if needed, as crossover operators directly modify the input individuals. After mating, the fitness values of the offsprings must be deleted, because they are no longer relevant to the solution values of the offspring.

clone1 = toolbox.clone(ind1)
clone2 = toolbox.clone(ind2)
tools.cx_blend(clone1, clone2, alpha=0.5)
del clone1.fitness.values
del clone2.fitness.values

A mixed encoding (bits, ints, and boxed reals in one individual) registers cx_heterogeneous instead of a one-off mate(). Pass one (v1, v2) -> (v1', v2') callable per gene, or (slice, cx_*) pairs so an existing operator runs on a block. See the mixed-encoding example.

Selection¶

Selection operators are responsible for selecting individuals for subsequent evolution processes. There are a variety of selection operators available in the deap_er.tools module. Besides the usual tournament, roulette, and best/worst helpers, that module also ships the multi-objective selectors (SPEA-II, NSGA-II, NSGA-III, SMS-EMOA, MOEA/D, AGE-MOEA-II), case-structured lexicase variants (including batch ε-lexicase, sel_tournament_cases, and dynamic ε via mode= on sel_epsilon_lexicase), program-team selection (sel_team, sel_team_archive on occupied MAP-Elites cells), novelty selection for MAP-Elites archives (sel_novelty), iso+line mutation (mut_iso_line), and Deb constraint-dominance (constraint_dominates, optional on NSGA-II). Each selection operator has its own characteristics and therefore it's recommended to read their documentation before use to avoid undesirable behavior. See the Operators reference.

In the following example, 10 individuals are selected from a population. The selected individuals can be cloned after selection if needed, to preserve the original individuals for other processing. Please refer to Creating Individuals to learn more about populations.

selected = tools.sel_best(population, sel_count=10)
selected = [toolbox.clone(ind) for ind in selected]

Variation¶

Variation functions are building blocks of evolution algorithms, which alter the application of crossover and mutation operators depending on the given probabilities. To use a variation function, a mate and mutate aliases must be registered into the toolbox with the necessary crossover and mutation operators. See the Algorithms reference.

toolbox.register("mate", tools.cx_two_point)
toolbox.register("mutate", tools.mut_flip_bit, mut_prob=0.05)

offsprings = tools.var_and(toolbox, selected, CX_PROB, MUT_PROB)

Algorithms¶

Evolutionary algorithms are the main workhorses of computational evolution, which alter the individuals of the input population with the operators of a toolbox to solve optimization problems.

A few generic evolutionary algorithms have been built into this library, which can be used for various different optimization problems and can accept any kind of individuals and operators as input. Besides ea_simple, ea_mu_plus_lambda, and ea_mu_comma_lambda, the module includes ea_generate_update / ea_generate_update_restarts for CMA, ea_map_elites for quality-diversity, and step_islands for deme ecology (mig_ring, mig_fully_connected, mig_random, and island_eval_keys). The generational loops accept an optional n_evals= budget. Wrap evaluate with EvalCache when the same expression should not be scored twice:

def evaluate(individual):
    return (sum(individual),)

cache = tools.EvalCache(evaluate)
toolbox.register("evaluate", cache.evaluate)

pop, log = tools.ea_simple(
    toolbox, pop, generations=200, cx_prob=0.5, mut_prob=0.2,
    n_evals=2_000, hof=hof, stats=stats,
)
print(len(cache), log.select("gen")[-1])

n_evals still counts every fitness assignment, including cache hits. The wrapped callable runs only on a miss. A complete script is the evaluation budget example.

For noisy fitness, repeat draws with resample and pair each draw with noisy_draw_key when the scorer is cached:

cache = tools.EvalCache(evaluate)
tools.resample(ind, evaluate, n=5, cache=cache, key="expr")

race_stop adds one resample per survivor per round and drops challengers whose rank on the first objective is still unstable. race_eval_charge counts evaluate units toward n_evals=.

See the Algorithms reference. The following examples demonstrate the most basic ways of solving optimization problems:

Using a builtin algorithm

# toolbox and population setup is omitted for brevity

pop, log = tools.ea_simple(
    toolbox=toolbox,
    population=pop,
    generations=500,
    cx_prob=0.5,
    mut_prob=0.2,
    hof=hof,
    stats=stats,
    log_time=True,
    n_evals=50_000,
)

ea_policy is the same loop plus one observe → decide → apply_policy_action step per generation. Pass a decide callable; fitness stays on the toolbox. When an exam pool is given, selection is lexicase on the current cases= subset. Policy-action evaluations count toward n_evals and the generation nevals. When a policy step meets or exceeds that budget, the generation is recorded without variation.

pop, log = tools.ea_policy(
    toolbox,
    pop,
    decide,
    generations=40,
    cx_prob=0.5,
    mut_prob=0.2,
    exams=pool,
    hof=hof,
    stats=stats,
)

Using a variation function

# toolbox and population setup is omitted for brevity

for gen in range(GENS):
    selection = toolbox.select(pop, len(pop))
    # var_and clones the pool; do not map toolbox.clone first
    offspring = tools.var_and(toolbox, selection, CX_PROB, MUT_PROB)
    tools.evaluate_invalid(toolbox, offspring)
    pop[:] = offspring

Using custom crossover and mutation

# toolbox and population setup is omitted for brevity

for gen in range(GENS):
    offspring = [toolbox.clone(ind) for ind in toolbox.select(pop, len(pop))]

    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if tools.rng.random() < CX_PROB:
            toolbox.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values
    for mutant in offspring:
        if tools.rng.random() < MUT_PROB:
            toolbox.mutate(mutant)
            del mutant.fitness.values

    tools.evaluate_invalid(toolbox, offspring)
    pop[:] = offspring