This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Deap framework introduction

There are many Python frameworks for genetic algorithms — GAFT, DEAP, Pyevolve, PyGMO, etc. The DEAP (Distributed Evolutionary Algorithms in Python) framework supports rapid solution development using genetic Algorithms and other Evolutionary computing techniques. DEAP provides a variety of data structures and tools that are essential in implementing a variety of genetic algorithm-based solutions.

Creator module

The Creator module can act as a meta-factory, extending existing classes by adding new properties. For example, there is a class named Employee. Using the Creator tool, you can extend the Employee class by creating a Developer class:

import deap import creator
creator.create("Developer",Employee,position="Developer",programmmingLanguage=set)
Copy the code

The first argument passed to create() is the name of the new class. The second parameter is the existing class to be extended, followed by defining the properties of the new class using other parameters. If a class (such as dict or set) is assigned to a parameter, it is added to the new class as an instance attribute initialized in the constructor. If the parameter is not a class (such as a string), add it as a static attribute. Therefore, the Developer class created will extend the Employee class and will have a static property, position, set to “Developer”, and an instance property, programmingLanguages of type set, initialized in the constructor. Thus it is effectively equivalent to:

class Developer(Employee) :
    position = "Developer"
    def __init__(self) :
        self.programmmingLanguage = set(a)Copy the code

This new class exists in the Creator module, so use Creator.Developer when you need to reference it. When using DEAP, the Creator module is typically used to create the Fitness class as well as the Individual class.

Create a fitness class

With DEAP, Fitness is encapsulated in the Fitness class. In the DEAP framework, fitness can have several components, each with its own weights. The combination of these weights defines the behavior or strategy appropriate for a given problem.

Define a fitness strategy

To quickly define Fitness policies, DEAP uses the abstract Base.fitness class, which contains weights tuples to define policies and make the class available. You can do this by creating an extension to the base Fitness class using Creator, similar to creating the Developer class:

creator.create("FitnessMax",base.Fitness,weights=(1.0)),Copy the code

This will produce a creator.FitnessMax class that extends the Base.Fitness class and initializes the weights class attribute to a value of (1.0,). The Note. Weights argument is a tuple. The strategy of the FitnessMax class is to maximize the fitness value of the single-objective solution during the genetic algorithm. Conversely, if you have a single-objective problem that requires a solution that minimizes the fitness value, you can use the following definition to create a minimization strategy:

creator.create("FitnessMin",base.Fitness,weights=(-1.0)),Copy the code

You can also define policies that optimize multiple goals with different importance:

creator.create("FitnessCompound",base.Fitness,weights=(1.0.0.2, -0.5))
Copy the code

This will result in a Creator.FitnessCompound class with three different fitness components. The first part is weighted 1.0, the second part is weighted 0.2, and the third part is weighted -0.5. This tends to maximize the first and second parts (or goals) and minimize the third part (or goals).

Fitness storage mode

Although the weight tuple defines the Fitness policy, a corresponding tuple (called Values) is used to store Fitness values in the Base.fitness class. These values are obtained from a separately defined function, usually called evaluate(). Just like the weights tuple, the VALUES tuple stores each fitness component (object) value. The tuple wVALUES contains the weights obtained by multiplying each component of the VALUES tuple by its corresponding component of the weights tuple. As soon as the fitness value of the instance is obtained, the weighting value is calculated and inserted into Wvalues. These values are used to compare fitness between individuals.

Creating individual classes

A second common use of the Creator tool in DEAP is to define the individuals that make up the genetic algorithm population. Individuals in genetic algorithms are represented by chromosomes that can be manipulated by genetic operators, and “Individual” classes are created by extending the base classes that represent chromosomes. In addition, each individual instance in the DEAP needs to include its fitness function as an attribute. To satisfy these two requirements, use Creator to create the Creator.Individual class:

creator.create("Individual".list,fitness=creator.FitnessMax)
Copy the code

This snippet has the following two effects:

  1. The Individual class created extends Python’slistClass. This means that the chromosomes used are list types.
  2. Each instance of the Individual class created will have the FitnessMax attribute created earlier.

Toolbox classes

The second efficient mechanism for creating genetic algorithms provided by the DEAP framework is the Base.Toolbox class. Toolbox is used as a container for functions (or operations), enabling the creation of new operators through alias mechanisms and customization of existing functions. Suppose we have a function sumOfTwo() :

def sumOfTwo(a,b) :
    return a + b
Copy the code

With the Toolbox, you can create a new operation, incrementByFive(), which is created using the sumOfTwo() function:

import base
toolbox = base.Toolbox()
toolbox.register("incrementByFive",sumOfTwo,b=5)
Copy the code

The first argument passed to the register() function is the name (or alias) required for the new operator. The second argument is the existing function that is being customized. After creation, other arguments are automatically passed to the created function each time a new operator is called, such as:

toolbox.incrementByFive(10)
Copy the code

Equivalent to:

sumOfTwo(10.5)
Copy the code

This is because the argument to B has been defined as 5 by the incrementByFive operator.

Create genetic operator

To quickly build genetic processes, you can use the Toolbox classes to customize existing functions of the Tools module. The Tools module contains many convenient functions, including selection, crossover, and mutation genetic operators, and program initialization. For example, the following code defines three alias functions that are used as genetic operators:

from deap import tools
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.02)
Copy the code

The three alias functions are described in detail:

  1. Select is registered as a Tools functionselTournament()Alias, and tournsize is set to 3. This creates a toolbox.select operator for creating a tournament selection operator of tournament size 3.
  2. Register mate as tools functioncxTwoPoint()The alias. This creates the toolbox.mate operator that performs a two-point crossover.
  3. Mutate is registered as a Tools functionmutFlipBit()Alias, and set the INDPB parameter to 0.02, which creates a bit-flip mutation operator with a probability of flipping each feature of 0.02.

Tools module provides the implementation of various genetic operators, as shown in the following implementation functions of common genetic operators. Selection operators mainly include:

selRoulette() Roulette selection
selStochasticUniversalSampling()# Random Traversal sampling (SUS)
selTournament()# Tournament selection
Copy the code

Crossover operators mainly include:

cxOnePoint()		# Single point crossover
cxUniform()			# Evenly cross
cxOrdered()			# Ordered crossover
cxPartialyMatched()	# implement partial matching crossover
Copy the code

Mutation operators mainly include:

mutFlipBit()	# bit flip mutation
mutGaussian()	# Normal distribution mutation
Copy the code

Create a species

The tool module’s init.py file contains functions to create and initialize the genetic algorithm, including initRepeat(), which takes three arguments:

  1. The type of container to place the result object in
  2. The function used to generate the object to be put into the container
  3. The number of objects to be generated

Such as:

# Generate a list of 30 random numbers between 0 and 1
randomList = tools.initRepeat(list,random.random,30)
Copy the code

In this example, list is the type used to populate the container, random. Random is the generator function, and 30 is the number of times the generator function is called to generate the value to populate the container. If you want to populate the list with integer random numbers of 0 or 1, you can create a function that uses random.radint() to generate random values of 0 or 1, and then use that as a generator function for initRepeat() :

def zeroOrOne() :
    return random.randint(0.1)
randomList = tools.initRepeat(list,zeroOrOne,30)
Copy the code

Alternatively, you can use Toolbox:

# create zeroOrOne operator, call random.radint() with arguments 0, 1
toolbox.register("zeroOrOne",random.randint,0.1)
randomList = tools.initRepeat(list,tools.zeroOrOne,30)
Copy the code

Calculated fitness

Although the Fitness class defines Fitness weights that determine its policies (such as maximize or minimize), the actual Fitness is derived from a separate defined function. This fitness calculation function is usually registered with the Toolbox module using the alias evalidate:

def someFitnessCalculationFunction(individual) :
	"" calculate the fitness of a given individual. ""
    return _some_calculation_of_of_the_fitness(individual)
# will evaluate registered as someFitnessCalculationFunction (alias)
toolbox.register("evaluate",someFitnessCalculationFunction)
Copy the code

Solve OneMax problems using the DEAP framework

Using DEAP framework to realize the genetic algorithm of Hello World — OneMax problem, code link.