[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,))

this tell 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. The 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 0 and 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.individual function

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.

The 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.

Examples

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_onemax.py, deap_partition.py, and deap_tsp.py. These should show, how different algorithms can be implemented in the library.