Project Homepage3. Algorithms¶
The algorithms module is intended to contain some specific algorithms
in order to execute very common evolutionary algorithms. The method used here
are more for convenience than reference as the implementation of every
evolutionary algorithm may vary infinitely. Most of the algorithms in this
module use operators registered in the toolbox. Generaly, the keyword used are
mate() for crossover, mutate() for mutation, select()
for selection and evaluate() for evaluation.
You are encouraged to write your own algorithms in order to make them do what you really want them to do.
3.1. Complete Algorithms¶
These are complete boxed algorithms that are somewhat limited to the very
basic evolutionary computation concepts. All algorithms accept, in addition to
their arguments, an initialized Statistics object to
maintain stats of the evolution, an initialized
HallOfFame to hold the best individual(s) to appear in
the population, and a boolean verbose to specify wether to
log what is happening during the evolution or not.
-
deap.algorithms.eaSimple(population, toolbox, cxpb, mutpb, ngen[, stats, halloffame, verbose])¶ This algorithm reproduce the simplest evolutionary algorithm as presented in chapter 7 of [Back2000].
Parameters: - population – A list of individuals.
- toolbox – A
Toolboxthat contains the evolution operators. - cxpb – The probability of mating two individuals.
- mutpb – The probability of mutating an individual.
- ngen – The number of generation.
- stats – A
Statisticsobject that is updated inplace, optional. - halloffame – A
HallOfFameobject that will contain the best individuals, optional. - verbose – Whether or not to log the statistics.
Returns: The final population.
It uses
and goes as follow. It first initializes the population ( ) by evaluating every individual presenting an invalid fitness. Then, it enters the evolution loop that begins by the selection of the population. Then the crossover operator is applied on a proportion of according to the cxpb probability, the resulting and the untouched individuals are placed in . Thereafter, a proportion of , determined by mutpb, is mutated and placed in , the untouched individuals are transferred . Finally, those new individuals are evaluated and the evolution loop continues until ngen generations are completed. Briefly, the operators are applied in the following orderevaluate(population) for i in range(ngen): offspring = select(population) offspring = mate(offspring) offspring = mutate(offspring) evaluate(offspring) population = offspring
This function expects
toolbox.mate(),toolbox.mutate(),toolbox.select()andtoolbox.evaluate()aliases to be registered in the toolbox.[Back2000] Back, Fogel and Michalewicz, “Evolutionary Computation 1 : Basic Algorithms and Operators”, 2000.
-
deap.algorithms.eaMuPlusLambda(population, toolbox, mu, lambda_, cxpb, mutpb, ngen[, stats, halloffame, verbose])¶ This is the
evolutionary algorithm.Parameters: - population – A list of individuals.
- toolbox – A
Toolboxthat contains the evolution operators. - mu – The number of individuals to select for the next generation.
- lambda_ – The number of children to produce at each generation.
- cxpb – The probability that an offspring is produced by crossover.
- mutpb – The probability that an offspring is produced by mutation.
- ngen – The number of generation.
- stats – A
Statisticsobject that is updated inplace, optional. - halloffame – A
HallOfFameobject that will contain the best individuals, optional. - verbose – Whether or not to log the statistics.
Returns: The final population.
First, the individuals having an invalid fitness are evaluated. Then, the evolutionary loop begins by producing lambda_ offspring from the population, the offspring are generated by a crossover, a mutation or a reproduction proportionally to the probabilities cxpb, mutpb and 1 - (cxpb + mutpb). The offspring are then evaluated and the next generation population is selected from both the offspring and the population. Briefly, the operators are applied as following
evaluate(population) for i in range(ngen): offspring = varOr(population, toolbox, lambda_, cxpb, mutpb) evaluate(offspring) population = select(population + offspring, mu)
This function expects
toolbox.mate(),toolbox.mutate(),toolbox.select()andtoolbox.evaluate()aliases to be registered in the toolbox. This algorithm uses thevarOr()variation.
-
deap.algorithms.eaMuCommaLambda(population, toolbox, mu, lambda_, cxpb, mutpb, ngen[, stats, halloffame, verbose])¶ This is the
evolutionary algorithm.Parameters: - population – A list of individuals.
- toolbox – A
Toolboxthat contains the evolution operators. - mu – The number of individuals to select for the next generation.
- lambda_ – The number of children to produce at each generation.
- cxpb – The probability that an offspring is produced by crossover.
- mutpb – The probability that an offspring is produced by mutation.
- ngen – The number of generation.
- stats – A
Statisticsobject that is updated inplace, optional. - halloffame – A
HallOfFameobject that will contain the best individuals, optional. - verbose – Whether or not to log the statistics.
Returns: The final population.
First, the individuals having an invalid fitness are evaluated. Then, the evolutionary loop begins by producing lambda_ offspring from the population, the offspring are generated by a crossover, a mutation or a reproduction proportionally to the probabilities cxpb, mutpb and 1 - (cxpb + mutpb). The offspring are then evaluated and the next generation population is selected only from the offspring. Briefly, the operators are applied as following
evaluate(population) for i in range(ngen): offspring = varOr(population, toolbox, lambda_, cxpb, mutpb) evaluate(offspring) population = select(offspring, mu)
This function expects
toolbox.mate(),toolbox.mutate(),toolbox.select()andtoolbox.evaluate()aliases to be registered in the toolbox. This algorithm uses thevarOr()variation.
-
deap.algorithms.eaGenerateUpdate(toolbox, ngen[, stats, halloffame, verbose])¶ This is algorithm implements the ask-tell model proposed in [Colette2010], where ask is called generate and tell is called update.
Parameters: - toolbox – A
Toolboxthat contains the evolution operators. - ngen – The number of generation.
- stats – A
Statisticsobject that is updated inplace, optional. - halloffame – A
HallOfFameobject that will contain the best individuals, optional. - verbose – Whether or not to log the statistics.
Returns: The final population.
The toolbox should contain a reference to the generate and the update method of the chosen strategy.
[Colette2010] Collette, Y., N. Hansen, G. Pujol, D. Salazar Aponte and R. Le Riche (2010). On Object-Oriented Programming of Optimizers - Examples in Scilab. In P. Breitkopf and R. F. Coelho, eds.: Multidisciplinary Design Optimization in Computational Mechanics, Wiley, pp. 527-565; - toolbox – A
3.2. Variations¶
Variations are smaller parts of the algorithms that can be used separately to build more complex algorithms.
-
deap.algorithms.varAnd(population, toolbox, cxpb, mutpb)¶ Part of an evolutionary algorithm applying only the variation part (crossover and mutation). The modified individuals have their fitness invalidated. The individuals are cloned so returned population is independent of the input population.
Parameters: - population – A list of individuals to variate.
- toolbox – A
Toolboxthat contains the evolution operators. - cxpb – The probability of mating two individuals.
- mutpb – The probability of mutating an individual.
Returns: A list of varied individuals that are independent of their parents.
The variator goes as follow. First, the parental population
is duplicated using thetoolbox.clone()method and the result is put into the offspring population . A first loop over is executed to mate consecutive individuals. According to the crossover probability cxpb, the individuals and are mated using thetoolbox.mate()method. The resulting children and replace their respective parents in . A second loop over the resulting is executed to mutate every individual with a probability mutpb. When an individual is mutated it replaces its not mutated version in . The resulting is returned.This variation is named And beceause of its propention to apply both crossover and mutation on the individuals. Note that both operators are not applied systematicaly, the resulting individuals can be generated from crossover only, mutation only, crossover and mutation, and reproduction according to the given probabilities. Both probabilities should be in
.
-
deap.algorithms.varOr(population, toolbox, lambda_, cxpb, mutpb)¶ Part of an evolutionary algorithm applying only the variation part (crossover, mutation or reproduction). The modified individuals have their fitness invalidated. The individuals are cloned so returned population is independent of the input population.
Parameters: - population – A list of individuals to variate.
- toolbox – A
Toolboxthat contains the evolution operators. - lambda_ – The number of children to produce
- cxpb – The probability of mating two individuals.
- mutpb – The probability of mutating an individual.
Returns: A list of varied individuals that are independent of their parents.
The variator goes as follow. On each of the lambda_ iteration, it selects one of the three operations; crossover, mutation or reproduction. In the case of a crossover, two individuals are selected at random from the parental population
, those individuals are cloned using thetoolbox.clone()method and then mated using thetoolbox.mate()method. Only the first child is appended to the offspring population , the second child is discarded. In the case of a mutation, one individual is selected at random from , it is cloned and then mutated using using thetoolbox.mutate()method. The resulting mutant is appended to . In the case of a reproduction, one individual is selected at random from , cloned and appended to .This variation is named Or beceause an offspring will never result from both operations crossover and mutation. The sum of both probabilities shall be in
, the reproduction probability is 1 - cxpb - mutpb.
4. Covariance Matrix Adaptation Evolution Strategy¶
A module that provides support for the Covariance Matrix Adaptation Evolution Strategy.
-
class
deap.cma.Strategy(centroid, sigma[, **kargs])¶ A strategy that will keep track of the basic parameters of the CMA-ES algorithm.
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, Nis the individual’s size (integer).muint(lambda_ / 2)The number of parents to keep from the lambda children (integer). cmatrixidentity(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. damps1 + 2 * max(0, sqrt(( mueff - 1) / (N + 1)) - 1) + csDamping for step-size. ccum4 / (N + 4)Cumulation constant for covariance matrix. ccov12 / ((N + 1.3)^2 + mueff)Learning rate for rank-one update. ccovmu2 * (mueff - 2 + 1 / mueff) / ((N + 2)^2 + mueff)Learning rate for rank-mu update. -
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 from the current strategy using the centroid individual as parent.
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.StrategyOnePlusLambda(parent, sigma[, **kargs])¶ A CMA-ES strategy that uses the
paradigme.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.
- parameter – One or more parameter to pass to the strategy as described in the following table, optional.
-
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 from the current strategy using the centroid individual as parent.
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.