Algorithms

Complete Algorithms

These are complete boxed algorithms that are somewhat limited to the very basic evolutionary computation concepts.

class deap.algorithms.GenerationalAlgorithm(population, toolbox, cxpb, mutpb)

Algorithm based on a generational process.

Each iteration, the parental population is selected from the population for reproduction. It is advised to use a selection with replacement as N individuals will be selected from a population of size N. The parents get to reproduce using the and_variation().

Parameters:

• population (list) – Initial population for the evolution.
• toolbox (deap.base.Toolbox) – Toolbox containing a mate, mutate, select and evaluate method.
• cxpb (float) – Probability to apply crossover on every pair of individuals.
• mutpb (float) – Probability to apply mutation on every individual.

Yields:

self

population

The population updated every generation.

nevals

The number of evaluations in the last generation.

toolbox

cxpb

mutpb

Examples

This algorithm can continue the optimization indefinetely util stopped. Each iteration it yields itself to give access to its internal parameters. It can be used as follow:

for state in GenerationAlgorithm(pop, toolbox, CXPB, MUTPB):
    if min(state.population, key=lambda ind: ind.fitness.values) < 1e-6:
        break

Any attribute can be changed during evolution. For example, to change the population, directly use the state

for state in GenerationAlgorithm(pop, toolbox, CXPB, MUTPB):
    state.population = new_population()

class deap.algorithms.MuLambdaAlgorithm(population, toolbox, selection_type, lambda_, cxpb, mutpb)

\((\mu~\begin{smallmatrix}+ \\ ,\end{smallmatrix}~\lambda)\) evolutionary algorithm.

Each iteration, lambda_ individuals are produced by the or_variation(). The individuals are then evaluated and selection is made from the parents and offspring (“+”) or only from the offspring (“,”) depending on the input selection_type.

Parameters:

• population (list) – Initial population for the evolution.
• toolbox (deap.base.Toolbox) – Toolbox containing a mate, mutate, select and evaluate method.
• selection_type (str) – One of “+”, “plus”, “,”, or “comma” specifying if the selection is made from the parents and the offspring (“+”) or only from the offspring (“,”).
• lambda (int) – Number of individual so produce each generation.
• cxpb (float) – Probability to apply crossover on every pair of individuals.
• mutpb (float) – Probability to apply mutation on every individual.

Yields:

self

population

The population updated every generation.

nevals

The number of evaluations in the last generation.

toolbox

selection_type

lambda_

cxpb

mutpb

Examples

This algorithm can continue the optimization indefinetely util stopped. Each iteration it yields itself to give access to its internal parameters. It can be used as follow:

for state in MuLambdaAlgorithm(pop, toolbox, "+", 50, CXPB, MUTPB):
    if min(state.population, key=lambda ind: ind.fitness.values) < 1e-6:
        break

Any attribute can be changed during evolution. For example, to change the population, directly use the state

for state in MuLambdaAlgorithm(pop, toolbox, "+", 50, CXPB, MUTPB):
    state.population = new_population()

class deap.algorithms.GenerateUpdateAlgorithm(toolbox)

Two step evolutionary algorithm – generate/update.

Each iteration, individuals are produced using the toolbox’s generate method. These individuals are evaluted and passed to the toolbox’s update method.

Parameters:toolbox (deap.base.Toolbox) – Toolbox containing the generate and update methods. Yields:self

population

The population updated every generation.

nevals

The number of evaluations in the last generation.

toolbox

Examples

This algorithm can continue the optimization indefinetely util stopped. Each iteration it yields itself to give access to its internal parameters. It can be used as follow:

for state in GenerateUpdateAlgorithm(toolbox):
    if min(state.population, key=lambda ind: ind.fitness.values) < 1e-6:
        break

Any attribute can be changed during evolution. For example, to change the generation method at some point in the evolution, use the state

for g, state in enumerate(GenerateUpdateAlgorithm(toolbox)):
    if g > 50:
        state.toolbox = new_toolbox()

Variations

Variations are smaller parts of the algorithms that can be used separately to build more complex algorithms.

deap.algorithms.and_variation(population, toolbox, cxpb, mutpb)

Vary the individuals of a population using the operators in the toolbox.

Iterator that generates new individuals by varying consecutive pairs of two individuals from the population. The variation first deepcopies the individuals and then applies crossover and mutation with probability cxpb and mutpb on each of them. Both probabilities should be in [0, 1]. The offspring are returned one after an other. If more individuals than the size of the population are requested, the population is cycled over.

Parameters:

• population (Iterable) – The individuals to vary.
• toolbox (base.Toolbox) – The toolbox containing a mate and mutate method to variate the individuals.
• cxpb (float) – Probability to apply crossover on every pair of individuals.
• mutpb (float) – Probability to apply mutation on every individual.

Yields:

individual – Offspring produced by the variation.

Example

The variation can generates new offspring indefinitely if required. To generate a given number of individual:

>>> offspring = take(
...     50,
...     and_variation(population, toolbox, 0.6, 0.3)
... )       

deap.algorithms.or_variation(population, toolbox, cxpb, mutpb)

Vary the individuals of a population using the operators in the toolbox.

Generates new offspring by varying the individuals of a population. At first, the variation selects if a crossover, a mutation or a copy should be used according to the given probabilities. Then, it samples randomly the appropriate number of individuals, 2 for crossover and 1 for mutation and copy, and deepcopies them before applying the operator and yields the result. cxpb and mutpb shoudn’t sum above 1.

Parameters:

• population (iterable) – The individuals to vary.
• toolbox (base.Toolbox) – The toolbox containing a mate and mutate method to variate the individuals.
• cxpb (float) – Probability to apply crossover on every pair of individuals.
• mutpb (float) – Probability to apply mutation on every individual.

Yields:

individual – Offspring produced by the variation.

Example

The variation can generates new offspring indefinitely if required. To generate a given number of individual:

>>> offspring = take(
...     50,
...     or_variation(population, toolbox, 0.6, 0.3)
... )       

Utils

deap.algorithms.evaluate_invalids(individuals, eval_func, map=<built-in function map>)

Evaluate all individuals marked invalid.

Parameters:

• individuals (iterable) – Individuals to evaluate, they must have a fitness attribute. Only those with an invalid fitness will get evaluates.
• eval_func (callable) – The evaluation to use on each individual. The function should take the individual as single argument.
• map (callable) – Functiona that applies the evaluation function to each item in the invalid individuals iterable.

Returns:

The number of individuals evaluated.

Return type:

int

deap.algorithms.take(n, iterable)

Return first n items of an iterable as a list.

This function is taken from Python stdlib itertools.

Covariance Matrix Adaptation Evolution Strategy

Provides support for the Covariance Matrix Adaptation Evolution Strategy.

deap.cma.BasicStrategy	A strategy that will keep track of the basic parameters of the CMA-ES algorithm ([Hansen2001]).
deap.cma.OnePlusLambdaStrategy	A CMA-ES strategy that uses the \(1 + \lambda\) paradigm ([Igel2007]).
deap.cma.ActiveOnePlusLambdaStrategy	A CMA-ES strategy that combines the \((1 + \lambda)\) paradigm [Igel2007], the mixed integer modification [Hansen2011], active covariance update [Arnold2010] and constraint handling [Arnold2012].
deap.cma.MultiObjectiveStrategy	Multiobjective CMA-ES strategy based on the paper [Voss2010].

class deap.cma.BasicStrategy(centroid, sigma[, **kargs])

A strategy that will keep track of the basic parameters of the CMA-ES algorithm ([Hansen2001]).

Parameters:

• centroid – An iterable object that indicates where to start the evolution.
• sigma – The initial standard deviation of the distribution.
• parameter – One or more parameter to pass to the strategy as described in the following table, optional.

Parameter	Default	Details
lambda_	int(4 + 3 * log(N))	Number of children to produce at each generation, N is the individual’s size (integer).
mu	int(lambda_ / 2)	The number of parents to keep from the lambda children (integer).
cmatrix	identity(N)	The initial covariance matrix of the distribution that will be sampled.
weights	"superlinear"	Decrease speed, can be "superlinear", "linear" or "equal".
cs	(mueff + 2) / (N + mueff + 3)	Cumulation constant for step-size.
damps	1 + 2 * max(0, sqrt(( mueff - 1) / (N + 1)) - 1) + cs	Damping for step-size.
ccum	4 / (N + 4)	Cumulation constant for covariance matrix.
ccov1	2 / ((N + 1.3)^2 + mueff)	Learning rate for rank-one update.
ccovmu	2 * (mueff - 2 + 1 / mueff) / ((N + 2)^2 + mueff)	Learning rate for rank-mu update.

[Hansen2001]

(1, 2) Hansen and Ostermeier, 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation

computeParams(params)

Computes the parameters depending on \(\lambda\). It needs to be called again if \(\lambda\) changes during evolution.

Parameters:params – A dictionary of the manually set parameters.

generate(ind_init)

Generate a population of \(\lambda\) individuals of type ind_init from the current strategy.

Parameters:ind_init – A function object that is able to initialize an individual from a list. Returns:A list of individuals.

update(population)

Update the current covariance matrix strategy from the population.

Parameters:population – A list of individuals from which to update the parameters.

class deap.cma.OnePlusLambdaStrategy(parent, sigma[, **kargs])

A CMA-ES strategy that uses the \(1 + \lambda\) paradigm ([Igel2007]).

Parameters:

• parent – An iterable object that indicates where to start the evolution. The parent requires a fitness attribute.
• sigma – The initial standard deviation of the distribution.
• lambda – Number of offspring to produce from the parent. (optional, defaults to 1)
• parameter – One or more parameter to pass to the strategy as described in the following table. (optional)

Other parameters can be provided as described in the next table

Parameter	Default	Details
d	1.0 + N / (2.0 * lambda_)	Damping for step-size.
ptarg	1.0 / (5 + sqrt(lambda_) / 2.0)	Taget success rate.
cp	ptarg * lambda_ / (2.0 + ptarg * lambda_)	Step size learning rate.
cc	2.0 / (N + 2.0)	Cumulation time horizon.
ccov	2.0 / (N**2 + 6.0)	Covariance matrix learning rate.
pthresh	0.44	Threshold success rate.

[Igel2007]

Igel, Hansen, Roth, 2007. Covariance matrix adaptation for

multi-objective optimization. Evolutionary Computation Spring;15(1):1-28

computeParams(params)

Computes the parameters depending on \(\lambda\). It needs to be called again if \(\lambda\) changes during evolution.

Parameters:params – A dictionary of the manually set parameters.

generate(ind_init)

Generate a population of \(\lambda\) individuals of type ind_init from the current strategy.

Parameters:ind_init – A function object that is able to initialize an individual from a list. Returns:A list of individuals.

update(population)

Update the current covariance matrix strategy from the population.

Parameters:population – A list of individuals from which to update the parameters.

class deap.cma.ActiveOnePlusLambdaStrategy(parent, sigma[, **kargs])

A CMA-ES strategy that combines the \((1 + \lambda)\) paradigm [Igel2007], the mixed integer modification [Hansen2011], active covariance update [Arnold2010] and constraint handling [Arnold2012].

This version of CMA-ES requires the random vector and the mutation that created each individual. The vector and mutation are stored in each individual as _z and _y respectively. Updating with individuals not containing these attributes will result in an AttributeError.

Notes

When using this strategy (especially when using constraints) you should monitor the strategy condition_number. If it goes above a given threshold (say \(10^{12}\)), you should think of restarting the optimization as the covariance matrix is going degenerate. See the constrained active CMA-ES example for a simple example of restart.

Parameters:

• parent – An iterable object that indicates where to start the evolution. The parent requires a fitness attribute.
• sigma – The initial standard deviation of the distribution.
• step – The minimal step size for each dimension. Use 0 for continuous dimensions.
• lambda – Number of offspring to produce from the parent. (optional, defaults to 1)
• **kwargs –

  One or more parameter to pass to the strategy as described in the following table. (optional)

Parameter	Default	Details
d	1.0 + N / (2.0 * lambda_)	Damping for step-size.
ptarg	1.0 / (5 + sqrt(lambda_) / 2.0)	Taget success rate (from 1 + lambda algorithm).
cp	ptarg * lambda_ / (2.0 + ptarg * lambda_)	Step size learning rate.
cc	2.0 / (N + 2.0)	Cumulation time horizon.
ccov	2.0 / (N**2 + 6.0)	Covariance matrix learning rate.
ccovn	0.4 / (N**1.6 + 1.0)	Covariance matrix negative learning rate.
cconst	1.0 / (N + 2.0)	Constraint vectors learning rate.
beta	``0.1 / (lambda_ * (N + 2.0))``	Covariance matrix learning rate for constraints.
pthresh	0.44	Threshold success rate.

[Igel2007]

Igel, Hansen and Roth. Covariance matrix adaptation for multi-objective optimization. 2007

[Arnold2010]

(1, 2) Arnold and Hansen. Active covariance matrix adaptation for the (1+1)-CMA-ES. 2010.

[Hansen2011]

(1, 2) Hansen. A CMA-ES for Mixed-Integer Nonlinear Optimization. Research Report] RR-7751, INRIA. 2011

[Arnold2012]

(1, 2) Arnold and Hansen. A (1+1)-CMA-ES for Constrained Optimisation. 2012

generate(ind_init)

Generate a population of \(\lambda\) individuals of type ind_init from the current strategy.

Parameters:ind_init – A function object that is able to initialize an individual from a list. Returns:A list of individuals.

update(population)

Update the current covariance matrix strategy from the population.

Parameters:population – A list of individuals from which to update the parameters.

class deap.cma.MultiObjectiveStrategy(population, sigma[, **kargs])

Multiobjective CMA-ES strategy based on the paper [Voss2010]. It is used similarly as the standard CMA-ES strategy with a generate-update scheme.

Parameters:

• population – An initial population of individual.
• sigma – The initial step size of the complete system.
• mu – The number of parents to use in the evolution. When not provided it defaults to the length of population. (optional)
• lambda – The number of offspring to produce at each generation. (optional, defaults to 1)
• indicator – The indicator function to use. (optional, default to hypervolume())

Other parameters can be provided as described in the next table

Parameter	Default	Details
d	1.0 + N / 2.0	Damping for step-size.
ptarg	1.0 / (5 + 1.0 / 2.0)	Taget success rate.
cp	ptarg / (2.0 + ptarg)	Step size learning rate.
cc	2.0 / (N + 2.0)	Cumulation time horizon.
ccov	2.0 / (N**2 + 6.0)	Covariance matrix learning rate.
pthresh	0.44	Threshold success rate.

[Voss2010]

(1, 2) Voss, Hansen, Igel, “Improved Step Size Adaptation for the MO-CMA-ES”, 2010.

generate(ind_init)

Generate a population of \(\lambda\) individuals of type ind_init from the current strategy.

Parameters:ind_init – A function object that is able to initialize an individual from a list. Returns:A list of individuals with a private attribute _ps. This last attribute is essential to the update function, it indicates that the individual is an offspring and the index of its parent.

update(population)

Update the current covariance matrix strategies from the population.

Parameters:population – A list of individuals from which to update the parameters.