The toolbox module is intended to contain the operators that you need in your evolutionary algorithms, from initialisation to evaluation. It is always possible to use directly the operators from this module but the toolbox does also contain the default values of the different parameters for each method. More over, it makes your algorithms easier to understand and modify, since once an oprerator is set, it can be reused with a simple keyword that contains all its arguments. Plus, every keyword or argument can be overriden at all time.
The toolbox is also used in predefined algorithms from the algorithms module.
A toolbox for evolution that contains the evolutionary operators. At first the toolbox contains two simple methods. The first method clone() duplicates any element it is passed as argument, this method defaults to the copy.deepcopy() function. The second method map() applies the function given as first argument to every items of the iterables given as next arguments, this method defaults to the map() function. You may populate the toolbox with any other function by using the register() method.
Register a method in the toolbox under the name methodname. You may provide default arguments that will be passed automaticaly when calling the registered method.
Keyworded arguments content_init and size_init may be used to simulate iterable initializers. For example, when building objects deriving from list, the content argument will provide to the built list its initial content. Depending on what is given to content_init and size_init the initialization is different. If content_init is an iterable, then the iterable is consumed enterily to intialize each object, in that case size_init is not used. Otherwise, content_init may be a simple function that will be repeated size_init times in order to fill the object.
Unregister methodname from the toolbox.
Decorate methodname with the specified decorators, methodname has to be a registered function in the current toolbox. Decorate uses the signature preserving decoration function decorate().
This module contains the operators for an evolutionary algorithm. They are used to modify, select and move the individuals in their environment. A good set of operators should allow to move from an initial population of good solutions, equivalent to random sampling, to excellent configurations optimizing the studied problem.
Note
The responsibility of making offspring(s) independent of their parent(s) and invalidating the fitness is left to the user and is generally fulfilled in the algorithms by calling toolbox.clone on an individuals to duplicate it and del on the values attribute of the individual’s fitness.
Changed in version 0.6: In earlier versions, the resposability of cloning the individuals was left to the operator that wanted to modify an individuals. The new offsprings were returned via a tuple and the parents were left intact. In version 0.6, cloning is made prior to the operation on the individuals and the operators can now modify the individuals directly. At a user level, this may not affect your evolution if you were using the algorithms, but if you developped your own algorithms, you better take a look at the changes made in the algorithms source code.
Execute a two points crossover on the input individuals. The two individuals are modified in place. This operation apply on an individual composed of a list of attributes and act as follow
>>> ind1 = [A(1), ..., A(i), ..., A(j), ..., A(m)]
>>> ind2 = [B(1), ..., B(i), ..., B(j), ..., B(k)]
>>> # Crossover with mating points 1 < i < j <= min(m, k) + 1
>>> cxTwoPoints(ind1, ind2)
>>> print ind1, len(ind1)
[A(1), ..., B(i), ..., B(j-1), A(j), ..., A(m)], m
>>> print ind2, len(ind2)
[B(1), ..., A(i), ..., A(j-1), B(j), ..., B(k)], k
This function use the randint() function from the python base random module.
Execute a one point crossover on the input individuals. The two individuals are modified in place. This operation apply on an individual composed of a list of attributes and act as follow
>>> ind1 = [A(1), ..., A(n), ..., A(m)]
>>> ind2 = [B(1), ..., B(n), ..., B(k)]
>>> # Crossover with mating point i, 1 < i <= min(m, k)
>>> cxOnePoint(ind1, ind2)
>>> print ind1, len(ind1)
[A(1), ..., B(i), ..., B(k)], k
>>> print ind2, len(ind2)
[B(1), ..., A(i), ..., A(m)], m
This function use the randint() function from the python base random module.
Execute a uniform crossover that modify in place the two individuals. The genes are swapped according to the indpb probability.
This function use the random() function from the python base random module.
Execute a partialy matched crossover (PMX) on the input indviduals. The two individuals are modified in place. This crossover expect iterable individuals of indices, the result for any other type of individuals is unpredictable.
Moreover, this crossover consists of generating two children by matching pairs of values in a certain range of the two parents and swaping the values of those indexes. For more details see Goldberg and Lingel, “Alleles, loci, and the traveling salesman problem”, 1985.
For example, the following parents will produce the two following children when mated with crossover points a = 2 and b = 4.
>>> ind1 = [0, 1, 2, 3, 4]
>>> ind2 = [1, 2, 3, 4, 0]
>>> cxPartialyMatched(ind1, ind2)
>>> print ind1
[0, 2, 3, 1, 4]
>>> print ind2
[2, 3, 1, 4, 0]
This function use the randint() function from the python base random module.
Execute a uniform partialy matched crossover (UPMX) on the input indviduals. The two individuals are modified in place. This crossover expect iterable individuals of indices, the result for any other type of individuals is unpredictable.
Moreover, this crossover consists of generating two children by matching pairs of values chosen at random with a probability of indpb in the two parents and swaping the values of those indexes. For more details see Cicirello and Smith, “Modeling GA performance for control parameter optimization”, 2000.
For example, the following parents will produce the two following children when mated with the chosen points [0, 1, 0, 0, 1].
>>> ind1 = [0, 1, 2, 3, 4]
>>> ind2 = [1, 2, 3, 4, 0]
>>> cxUniformPartialyMatched(ind1, ind2)
>>> print ind1
[4, 2, 1, 3, 0]
>>> print ind2
[2, 1, 3, 0, 4]
This function use the random() and randint() functions from the python base random module.
Executes a blend crossover that modify inplace the input individuals. The blend crossover expect individuals formed of a list of floating point numbers.
This function use the random() function from the python base random module.
Execute a blend crossover on both, the individual and the strategy. minstrategy defaults to None so that if it is not present, the minimal strategy will be minus infinity.
Execute a classical two points crossover on both the individual and its strategy. The crossover points for the individual and the strategy are the same.
Executes a simulated binary crossover that modify inplace the input individuals. The simulated binary crossover expect individuals formed of a list of floating point numbers.
This function use the random() function from the python base random module.
Execute a one point crossover will mostly change the individuals size. This operation apply on an Individual composed of a list of attributes and act as follow
>>> ind1 = [A(1), ..., A(i), ..., A(m)]
>>> ind2 = [B(1), ..., B(j), ..., B(n)]
>>> # Crossover with mating points i, j, 1 <= i <= m, 1 <= j <= n
>>> cxMessyOnePoint(ind1, ind2)
>>> print ind1, len(ind1)
[A(1), ..., A(i - 1), B(j), ..., B(n)], n + j - i
>>> print ind2, len(ind2)
[B(1), ..., B(j - 1), A(i), ..., A(m)], m + i - j
This function use the randint() function from the python base random module.
Randomly select in each individual and exchange each subtree with the point as root between each individual.
Randomly select in each individual and exchange each subtree with the point as root between each individual. Since the node are strongly typed, the operator then make sure the type of second node correspond to the type of the first node. If it doesn’t, it randomly selects another point in the second individual and try again. It tries up to 5 times before giving up on the crossover.
Note
This crossover is subject to change for a more effective method of selecting the crossover points.
This function applies a gaussian mutation of mean mu and standard deviation sigma on the input individual and returns the mutant. The individual is left intact and the mutant is an independant copy. This mutation expects an iterable individual composed of real valued attributes. The mutIndxPb argument is the probability of each attribute to be mutated.
Note
The mutation is not responsible for constraints checking, because there is too many possibilities for resetting the values. Wich way is closer to the representation used is up to you.
One easy way to add cronstraint checking to an operator is to use the function decoration in the toolbox. See the multi-objective example (moga_kursawefct.py) for an explicit example.
This function uses the random() and gauss() functions from the python base random module.
Shuffle the attributes of the input individual and return the mutant. The individual is left intact and the mutant is an independant copy. The individual is expected to be iterable. The shuffleIndxPb argument is the probability of each attribute to be moved.
This function uses the random() and randint() functions from the python base random module.
Flip the value of the attributes of the input individual and return the mutant. The individual is left intact and the mutant is an independant copy. The individual is expected to be iterable and the values of the attributes shall stay valid after the not operator is called on them. The flipIndxPb argument is the probability of each attribute to be flipped.
This function uses the random() function from the python base random module.
Mutate an evolution strategy according to its strategy attribute. minstrategy defaults to None so that if it is not present, the minimal strategy will be minus infinity. The strategy shall be the same size as the individual. This is subject to change.
Randomly select a point in the Tree, then replace the subtree with the point as a root by a randomly generated expression. The expression is generated using the method expr.
The mutation of strongly typed GP expression is pretty easy. First, it finds a subtree. Second, it has to identify the return type of the root of this subtree. Third, it generates a new subtree with a root’s type corresponding to the original subtree root’s type. Finally, the old subtree is replaced by the new subtree.
This operator mutates the individual individual that are subjected to it. The operator randomly chooses a primitive in the individual and replaces it with a randomly selected primitive in pset that takes the same number of arguments.
This operator works on strongly typed trees as on normal GP trees.
This operator works on the constants of the tree ind. In mode "one", it will change the value of one of the individual ephemeral constants by calling its generator function. In mode "all", it will change the value of all the ephemeral constants.
This operator works on strongly typed trees as on normal GP trees.
This operator shrinks the individual individual that are subjected to it. The operator randomly chooses a branch in the individual and replaces it with one of the branch’s arguments (also randomly chosen).
This operator is not usable with STGP.
This operator mutate the GP tree of the individual passed and the primitive set expr, by inserting a new branch at a random position in a tree, using the original subtree at this position as one argument, and if necessary randomly selecting terminal primitives to complete the arguments of the inserted node. Note that the original subtree will become one of the children of the new primitive inserted, but not perforce the first (its position is randomly selected if the new primitive has more than one child)
This operator works on strongly typed trees as on normal GP trees.
Select n individuals from the input individuals using n tournaments of tournSize individuals. The list returned contains references to the input individuals.
This function uses the choice() function from the python base random module.
Select n individuals from the input individuals using n spins of a roulette. The selection is made by looking only at the first objective of each individual. The list returned contains references to the input individuals.
This function uses the random() function from the python base random module.
Apply NSGA-II selection operator on the individuals. Usually, the size of individuals will be larger than n because any individual present in individuals will appear in the returned list at most once. Having the size of individuals equals to n will have no effect other than sorting the population according to a non-domination sheme. The list returned contains references to the input individuals.
For more details on the NSGA-II operator see Deb, Pratab, Agarwal, and Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II”, 2002.
Apply SPEA-II selection operator on the individuals. Usually, the size of individuals will be larger than n because any individual present in individuals will appear in the returned list at most once. Having the size of individuals equals to n will have no effect other than sorting the population according to a strength pareto sheme. The list returned contains references to the input individuals.
For more details on the SPEA-II operator see Zitzler, Laumanns and Thiele, “SPEA 2: Improving the strength pareto evolutionary algorithm”, 2001.
Select n individuals at random from the input individuals. The list returned contains references to the input individuals.
This function uses the choice() function from the python base random module.
Select the n best individuals among the input individuals. The list returned contains references to the input individuals.
Select the n worst individuals among the input individuals. The list returned contains references to the input individuals.
Perform a ring migration between the populations. The migration first select n emigrants from each population using the specified selection operator and then replace n individuals from the associated population in the migarray by the emigrants. If no replacement operator is specified, the immigrants will replace the emigrants of the population, otherwise, the immigrants will replace the individuals selected by the replacement operator. The migration array, if provided, shall contain each population’s index once and only once. If no migration array is provided, it defaults to a serial ring migration (1 – 2 – ... – n – 1). You may pass keyworded arguments to the two selection operators by giving a dictionary to sel_kargs and repl_kargs.
Decorate a function preserving its signature. There is two way of using this function, first as a decorator passing the decorator to use as argument, for example
@decorate(a_decorator)
def myFunc(arg1, arg2, arg3="default"):
do_some_work()
return "some_result"
Or as a decorator
@decorate
def myDecorator(func):
def wrapFunc(*args, **kargs):
decoration_work()
return func(*args, **kargs)
return wrapFunc
@myDecorator
def myFunc(arg1, arg2, arg3="default"):
do_some_work()
return "some_result"
Using the inspect module, we can retreive the signature of the decorated function, what is not possible when not using this method.
print inspect.getargspec(myFunc)
It shall return something like
(["arg1", "arg2", "arg3"], None, None, ("default",))