Numerical Optimization Problem with DEAP
DEAP (Distributed Evolutionary Algorithms in Python) is a flexible library for implementing evolutionary algorithms.
It’s widely used for optimization problems, where traditional methods struggle with non-linearity, high dimensionality, or noisy functions.
In this example, we’ll solve a numerical optimization problem using a genetic algorithm (GA) implemented with DEAP.
Specifically, we’ll minimize the Rastrigin function, a common benchmark in optimization problems that is highly multimodal and presents many local minima, making it challenging for classical optimization techniques.
Problem
Minimize the Rastrigin function:
f(x)=10n+n∑i=1[x2i−10cos(2πxi)]
where (n) is the number of dimensions (we’ll use 2 in this example).
The function has a global minimum at (f(0,0,…,0)=0).
Approach
We will:
- Define the problem and the fitness function using DEAP.
- Set up a genetic algorithm with parameters like population size, mutation rate, and crossover rate.
- Run the genetic algorithm to find the minimum of the Rastrigin function.
Steps and Code Implementation
Install DEAP:
First, you need to install the DEAP library if you haven’t already:1
pip install deap
Define the Rastrigin Function and Optimization Problem:
Below is the full Python code to minimize the Rastrigin function using DEAP.
1 | import random |
Explanation
Fitness Function (Rastrigin):
- The
rastrigin
function evaluates the fitness of an individual, which is a vector of decision variables.
The smaller the value of this function, the better the individual (since we are minimizing). - The function returns a tuple because DEAP expects the fitness to be returned in this format.
- The
Individual and Population:
- We define an “Individual” as a list of floats (decision variables).
Each individual has a fitness attribute associated with it. - A “population” is a list of individuals.
- We define an “Individual” as a list of floats (decision variables).
Genetic Operators:
cxBlend
: A blending crossover is used where genes from two parents are combined.mutGaussian
: This applies Gaussian mutation, where a random value sampled from a normal distribution is added to the gene.selTournament
: Tournament selection selects individuals based on their fitness for crossover and mutation.
Genetic Algorithm Parameters:
- Population size: 300 individuals in the population.
- Crossover probability (cxpb): 0.7, meaning 70% of the population undergoes crossover.
- Mutation probability (mutpb): 0.2, meaning 20% of the population undergoes mutation.
- Generations: The algorithm runs for 50 generations.
Algorithm Execution:
algorithms.eaSimple
runs the evolutionary algorithm using simple evolutionary strategies. It returns the final population and the log of evolution.tools.selBest
selects the best individual from the population.
Result:
- The best individual found by the GA and its fitness value are printed.
The fitness value should be close to 0 for the Rastrigin function‘s global minimum.
- The best individual found by the GA and its fitness value are printed.
Output
The genetic algorithm will print the best individual and its corresponding fitness:
1 | Best individual is: [-1.0333568778912494e-09, 1.0226956450775647e-09] |
In this case, the algorithm finds an individual close to the global minimum ([0,0]), with a fitness value near zero, indicating that the solution is very close to the true minimum of the Rastrigin function.
Applications
Genetic algorithms, as implemented in DEAP, are widely used in optimization problems such as:
- Engineering design: Optimizing structures or systems with complex constraints.
- Machine learning: Feature selection, hyperparameter tuning, and architecture search.
- Operations research: Scheduling, resource allocation, and routing problems.
Genetic algorithms are particularly useful in cases where the objective function is non-convex, noisy, or discontinuous, making traditional gradient-based methods less effective.