In this chapter—as promised—the real fun begins! You will be introduced to DEAP—a powerful and flexible evolutionary computation framework capable of solving real-life problems using genetic algorithms. After a brief introduction, you will get acquainted with two of its main modules—the creator and the toolbox—and learn how to create the various components needed for the genetic algorithm flow. We will then write a Python program that solves the OneMax problem—the Hello World of genetic algorithms—using the DEAP framework. This will be followed by a more concise version of the same program—taking advantage of the built-in algorithms of the framework. And we saved the best for the last part of this chapter, where we will be experimenting with various settings of the genetic algorithm we created and...
You're reading from Hands-On Genetic Algorithms with Python
Technical requirements
Recent versions of DEAP can be used with either Python 2 or 3. In this book, we will be using Python 3.7. Python can be downloaded from the Python Software Foundation at this link: https://www.python.org/downloads/. Additional useful instructions can be found here: https://realpython.com/installing-python/.
The recommended ways to install DEAP are using easy_install or pip, for example:
pip install deap
For more information, check this DEAP documentation link: https://deap.readthedocs.io/en/master/installation.html. Conda install is available at this link: https://anaconda.org/conda-forge/deap.
In addition, we will be using various Python packages throughout the book.
For this chapter you will need the following packages:
- NumPy: http://www.numpy.org/
- Matplotlib: https://matplotlib.org/
- Seaborn: https://seaborn.pydata.org/
We are now ready to use DEAP...
Introduction to DEAP
As we have seen in the previous chapters, the basic ideas behind genetic algorithms and the genetic flow are relatively simple, and so are many of the genetic operators. Therefore, developing a program from scratch that implements a genetic algorithm to solve a particular problem is entirely feasible.
However, as is often the case when developing software, using a tried-and-true dedicated library or framework can make our life easier. It helps us create solutions faster and with fewer bugs, and give us many options to choose from (and experiment with) right out of the box, without the need to re-invent the wheel.
Numerous Python frameworks have been created for working with genetic algorithms—GAFT, Pyevolve, and PyGMO, to mention a few. After looking into several options, we chose to use the DEAP framework for this book, thanks to its ease of use and...
Using the creator module
The first powerful tool provided by the DEAP framework is the creator module. The creator module is used as a meta-factory, and it enables us to extend existing classes by augmenting them with new attributes.
For example, suppose we have a class called Employee. Using the creator tool, we can extend the Employee class by creating a Developer class as follows:
from deap import creator
creator.create("Developer", Employee, position = "Developer", programmingLanguages = set)
The first argument passed to the create() function is the desired name for the new class. The second argument is the existing class to be extended. Then, each additional argument defines an attribute for the new class. If the argument is assigned a class (such as a dict or a set), it will be added to the new class as an instant attribute initialized in the constructor...
Using the Toolbox class
The second mechanism offered by the DEAP framework is the base.Toolbox class. The Toolbox is used as a container for functions (or operators), and enables us to create new operators by aliasing and customizing existing functions.
For example, suppose we have a function, sumOfTwo(), defined as follows:
def sumOfTwo(a, b):
return a + b
Using toolbox, we can now create a new operator, incrementByFive(), which customizes the sumOfTwo() function as follows:
from deap import base
toolbox= base.Toolbox()
toolbox.register("incrementByFive", sumOfTwo, b=5)
The first argument passed to the register() toolbox function is the desired name (or alias) for the new operator. The second argument is the existing function to be customized. Then, each additional (optional) argument is automatically passed to the customized function whenever we call the new operator...
The OneMax problem
The OneMax (or One-Max) problem is a simple optimization task that is often used as the Hello World of genetic algorithm frameworks. We will use this problem for the rest of this chapter to demonstrate how DEAP can be used to implement a genetic algorithm.
The OneMax task is to find the binary string of a given length that maximizes the sum of its digits. For example, the OneMax problem of length 5 will consider candidates such as the following:
- 10010 (sum of digits = 2)
- 01110 (sum of digits = 3)
- 11111 (sum of digits = 5)
Obviously (to us), the solution to this problem is always the string that comprises all 1s. But the genetic algorithm does not have this knowledge, and needs to blindly look for this solution using its genetic operators. If the algorithm does its job, it will find this solution, or at least one close to it, within a reasonable amount of time...
Solving the OneMax problem with DEAP
In the previous chapter, we mentioned several choices that need to be made when solving a problem using the genetic algorithm approach. As we tackle the OneMax problem, we will make these choices as a series of steps. In the chapters to follow, we will keep using the same series of steps as we apply the genetic algorithms approach to various types of problems.
Choosing the chromosome
Since the OneMax problem deals with binary strings, the choice of chromosome is easy—each individual will be represented with a binary string that directly represents a candidate solution. In the actual Python implementation, this will be implemented as a list containing integer values of either 0 or...
Using built-in algorithms
The DEAP framework comes with several built-in evolutionary algorithms provided by the algorithms module. One of them, eaSimple, implements the genetic algorithm flow we have been using, and can replace most of the code we earlier had in the main method. Other useful DEAP objects, Statistics and Logbook, can be used for statistics gathering and printing, as we will soon see.
The program described in this section implements the same solution to the OneMax problem as the program discussed in the previous section, but with less code. The only differences are in the main method. We will describe these differences in the following code snippets.
The complete program can be found here:
Experimenting with the algorithm's settings
We can now experiment with the various settings and definitions we placed into the program and observe the changes in the behavior and the results.
In each of the following subsections, we start from the original program settings and make one or more changes. You are encouraged to experiment with making your own modifications, as well as combining several modifications to the same program.
Bear in mind that the effects of changes we make may be specific to the problem at hand, a simple OneMax in our case, and may be different for other types of problems.
Population size and number of generations
We will start our experimentation by making modifications to the population size...
Summary
In this chapter, you were introduced to DEAP—a versatile evolutionary computation framework that will be used in the rest of this book to solve real-life problems using genetic algorithms. You learned about DEAP's creator and toolbox modules, and how to use them to create the various components needed for the genetic algorithm flow. DEAP was then used to write two versions of a Python program that solves the OneMax problem, the first with full implementation of the genetic algorithm flow, and the other—more concise—taking advantage of the built-in algorithms of the framework. A third version of the program introduced the hall-of-fame (HOF) feature offered by DEAP. We then experimented with various settings of the genetic algorithm, and discovered the effects of changing the population size, as well as modifying the selection, crossover, and mutation...
Further reading
For more information, please refer to the following resources:
- DEAP documentation: https://deap.readthedocs.io/en/master/
- DEAP source code on GitHub: https://github.com/DEAP/deap