[EN] Deap Library
Up until now, we used our simple framework for evolutionary algorithms, where we implemented everything from scratch. If you want to use evolutionary algorithms for something more practical, it often helps to use a more advanced library. Today, we will talk about the deap library and how to use it. I will also implement some of the basic assignments in this library.
The following text is basically a summary of the
deap tutorial available at the library webpage.
Fitness and Individual
The first step we need to do when creating a new evolutionary algorithm is to define the individual and fitness. To this end, the deap library contains a
creator module. The
creator.create() function of this module basically defines a new class with a given name that inherits from a given base class and can also specify custom attributes. For example, fitness is stored with individual in
deap as an instance of the
base.Fitness class. The library assumes fitness always returns a tuple of values (
deap is by default multi-objective, although you can have only one objective). By default, individuals are sorted lexicographically according to the fitness values, we can specify the order by specifying positive or negative weights for each of the fitness functions. In order to create a specific class for representing the fitness values, we can call
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
deap to create a class called
FitnessMax that inherits from the
base.Fitness class and sets the weights to
(1.0,) (keep in mind that this is also a tuple of single value). This also means we will be maximizing the fitness (the weight is positive). The length of the weights attribute should be the same as the number of objectives.
In order to create a class for an individual, we can again use the
creator. In most cases, the individual class is inherited from the list class and we only need to specify the attribute for the fitness (in
deap, fitness is stored in each individual). We can do that by calling
creator.create("Individual", list, fitness=creator.FitnessMax).
Genetic Operators and Selection
The creation of an individual and population itself as well as specification of genetic operators is typically handled by a toolbox (an instance of
base.Toolbox). The toolbox contains only one important method -
register method registers a method in the toolbox. It takes a number of arguments, the first one is the name the method should have in the toolbox, the rest are basically given to the
functools.partial function and create the method itself.
Deap contains a number of useful methods that can be used to initialize an individual. Typically, individual initialization is done in two steps - first we create a function that returns a value (or values) for the individual and then we create the full individual. For example, in order to create an individual that contains only 1s and 0s, we can do the following:
toolbox = base.Toolbox() toolbox.register("attr_bool", random.randint, 0, 1) toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, 100)
The first line creates the toolbox itself. The second one defines a function
toolbox.attr_bool that is basically
random.randint with parameters
1. The last line than defines the
toolbox.individual function using the
tools.initRepeat function. This function takes a three arguments - the type of the individual, a function that returns a single value (for a single gene in the individual) and number of values the individual should have (
100 in the example). It basically calls the
toolbox.attr_bool function 100 times and sets the result as the values in the individual.
We can create a population in the same way as individual - we just repeatedly call the
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
Notice that here we did not specify the number of repetitions, the
toolbox.population function will now have a single argument that can be used to specify that.
The most important use of the toolbox is to specify the fitness and genetic operators. Fitness is a function that receives an individual and returns its fitness. For example, for the OneMAX problem, we can use the same fitness as in the first lesson. We just need to return a tuple with a single value instead of only the value (notice the comma at the end of the return statement).
def evalOneMax(individual): return sum(individual),
The algorithms implemented in deap then expect specific functions to be present in the toolbox. For fitness, the function is typically named
evaluate. Genetic operators are often called
mate (crossover) and
mutate (mutation) and selection is called
select. We can register all of them:
toolbox.register("evaluate", evalOneMax) toolbox.register("mate", tools.cxTwoPoint) toolbox.register("mutate", tools.mutFlipBit, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3)
Notice, that we used a number of functions from the
tools module - it contains the implementation of many of the common genetic operators and selections we talked about. Check its documentation for a full list.
Running the Algorithm
With everything specified, we can run our algorithm. Most of the basic algorithms are implemented in the algorithms module. The most basic version we used is called
eaSimple, we can call it simply as
pop = toolbox.population(n=300) pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40)
You can see the algorithm returns the final population and log. The log in this case will be
None, as we did not specify any statistics we want to compute. If we want to log some statistics, we can call the algorithm in a more verbose way:
pop = toolbox.population(n=300)
hof = tools.HallOfFame(1) stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("avg", numpy.mean) stats.register("std", numpy.std) stats.register("min", numpy.min) stats.register("max", numpy.max) pop, log = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40, stats=stats, halloffame=hof, verbose=True)
We used the
tools.Statistics class to record statistics of the run. The function used as parameter in the contructor specifies, what how we should get a value from the individual. The functions specified in the
stats.register specify, what should be done with the values from the whole population.
tools.HallOfFame is basically an archive of best individuals found in the evolution. The number specifies the size of the archive.
Apart from reading this text and the tutorial, I also recommend checking the source codes for the library - the implementations are typically easy to read and understand, once you understand the basics of the library. They can also be simply used as a starting point for your own implementation of different types of evolutionary algorithms.
I prepared three examples that should be roughly equivalent to the default versions for some of the problems we solved in the past. You can find them in the Github repository as
deap_tsp.py. These should show, how different algorithms can be implemented in the library.