The $DEAP (Distributed Evolutionary Algorithms in Python)$ library is a powerful and flexible library used for implementing evolutionary algorithms.
It is widely used for optimization tasks, particularly in the fields of genetic algorithms, genetic programming, and other evolutionary strategies.
Steps to Use DEAP Library in Python
Installation
You can install $DEAP$ using pip:1
pip install deap
Basic Structure of a $DEAP$ Program
A typical $DEAP$ program involves the following steps:- Importing $DEAP$ modules
- Defining the problem (fitness function)
- Creating individuals and population
- Defining the evolutionary operators (selection, mutation, crossover)
- Setting up the algorithm flow
- Running the algorithm
Example: Simple Genetic Algorithm
Below is an example of a simple genetic algorithm using $DEAP$ to maximize the function
f(x) = x^2, wherexis an integer.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71import random
from deap import base, creator, tools, algorithms
# Step 1: Define the problem (Fitness Function)
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
# Step 2: Define the individual and population
toolbox = base.Toolbox()
toolbox.register("attr_int", random.randint, 0, 100)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_int, 10)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# Step 3: Define the fitness function
def evalOneMax(individual):
return sum(individual), # Summing all values in the individual
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
# Step 4: Set up the evolutionary algorithm
def main():
population = toolbox.population(n=300)
NGEN = 40
CXPB = 0.7
MUTPB = 0.2
# Evaluate the entire population
fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
ind.fitness.values = fit
# Step 5: Run the algorithm
for gen in range(NGEN):
offspring = toolbox.select(population, len(population))
offspring = list(map(toolbox.clone, offspring))
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CXPB:
toolbox.mate(child1, child2)
del child1.fitness.values
del child2.fitness.values
for mutant in offspring:
if random.random() < MUTPB:
toolbox.mutate(mutant)
del mutant.fitness.values
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
population[:] = offspring
fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print(f"Gen {gen}: Min {min(fits)} Max {max(fits)} Avg {mean} Std {std}")
best_ind = tools.selBest(population, 1)[0]
print("Best individual is:", best_ind, best_ind.fitness.values)
if __name__ == "__main__":
main()
Explanation
- Problem Definition: The fitness function (
evalOneMax) is defined to maximizex^2. - Individual and Population: An individual is a list of integers, and the population is a list of individuals.
- Evolutionary Operators:
mate: Uses two-point crossover.mutate: Uses bit flip mutation with a small probability.select: Uses tournament selection.
- Algorithm Flow: The algorithm runs for a specified number of generations (
NGEN), performing selection, crossover, mutation, and evaluation in each generation. - Output: The algorithm prints the minimum, maximum, average, and standard deviation of fitness values at each generation and finally outputs the best individual found.
Output
1 | Gen 0: Min 309.0 Max 787.0 Avg 562.7166666666667 Std 85.22716540060568 |
The output represents the results of an evolutionary algorithm running for $40$ generations.
Here’s a breakdown of what each part of the output means:
Generations (Gen 0, Gen 1, etc.):
- Each “Gen” line corresponds to a generation in the evolutionary process. The algorithm starts at Gen 0 and evolves through to Gen $39$.
Min, Max, Avg, Std:
- Min: The minimum fitness value in the population for that generation.
- Max: The maximum fitness value in the population for that generation.
- Avg: The average fitness value across the entire population for that generation.
- Std: The standard deviation of fitness values in the population, indicating how spread out the fitness values are.
Trends over Generations:
- Min: The minimum fitness value generally increases over time, suggesting that the worst-performing individuals are improving.
- Max: The maximum fitness value also increases, indicating that the best individuals are becoming fitter.
- Avg: The average fitness steadily rises, showing that the overall population is improving.
- Std: The standard deviation decreases over time, meaning the population is becoming more homogenous, with individuals having similar fitness values.
Final Generation (Gen 39):
- Min 691.0, Max 988.0, Avg 981.0266666666666, Std 32.25077707935549: By the final generation, the population has a high average fitness, with the best individual achieving a fitness of $988.0$.
Best Individual:
- The best individual found during the evolutionary process is
[98, 100, 100, 97, 94, 99, 100, 100, 100, 100]with a fitness value of988.0. This individual likely represents an optimal or near-optimal solution to the problem.
- The best individual found during the evolutionary process is
In summary, the algorithm successfully evolves a population over $40$ generations, improving the fitness of individuals, and converging towards an optimal solution, as indicated by the high average and maximum fitness values in the later generations.
Customizing DEAP
- Custom Fitness Functions: You can create custom fitness functions based on the problem at hand.
- Custom Selection, Crossover, and Mutation: $DEAP$ allows you to define and use custom operators.
- Multi-Objective Optimization: $DEAP$ also supports multi-objective optimization, where the fitness function can return multiple values (e.g., minimizing both time and cost).
This example demonstrates how to set up and run a basic genetic algorithm using $DEAP$.
You can extend it by adjusting the problem, operators, and parameters to suit different optimization tasks.
