Numerical Optimization Problem with DEAP

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 + \sum_{i=1}^{n} \left[ x_i^2 - 10\cos(2\pi x_i) \right]
$$

where $( n )$ is the number of dimensions (we’ll use $2$ in this example).
The function has a global minimum at $( f(0, 0, \dots, 0) = 0 )$.

Approach

We will:

  1. Define the problem and the fitness function using $DEAP$.
  2. Set up a genetic algorithm with parameters like population size, mutation rate, and crossover rate.
  3. Run the genetic algorithm to find the minimum of the Rastrigin function.

Steps and Code Implementation

  1. Install DEAP:
    First, you need to install the $DEAP$ library if you haven’t already:

    1
    pip install deap

  2. Define the Rastrigin Function and Optimization Problem:
    Below is the full $Python$ code to minimize the Rastrigin function using $DEAP$.

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
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Define the fitness function (Rastrigin function)
def rastrigin(individual):
    n = len(individual)
    return 10 * n + sum([(x**2 - 10 * np.cos(2 * np.pi * x)) for x in individual]),

# Create types for DEAP
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))  # Minimization
creator.create("Individual", list, fitness=creator.FitnessMin)

# Register the genetic operators in the DEAP toolbox
toolbox = base.Toolbox()

# Define the range for each gene (we assume 2-dimensional case here)
BOUND_LOW, BOUND_UP = -5.12, 5.12
NDIM = 2  # Number of dimensions

# Attribute generator (random initialization of each gene)
toolbox.register("attr_float", random.uniform, BOUND_LOW, BOUND_UP)

# Structure initializers
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=NDIM)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Register the evaluation function (fitness function)
toolbox.register("evaluate", rastrigin)

# Register the genetic operators
toolbox.register("mate", tools.cxBlend, alpha=0.5)  # Crossover (blending)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)  # Mutation
toolbox.register("select", tools.selTournament, tournsize=3)  # Selection method

# Genetic Algorithm parameters
toolbox.register("map", map)  # For parallelization (optional)

# Evolutionary Algorithm parameters
population_size = 300
prob_crossover = 0.7  # Crossover probability
prob_mutation = 0.2  # Mutation probability
generations = 50  # Number of generations

# Create the population
population = toolbox.population(n=population_size)

# Run the Genetic Algorithm
result_pop, log = algorithms.eaSimple(population, toolbox, cxpb=prob_crossover, mutpb=prob_mutation,
                                      ngen=generations, verbose=False)

# Get the best individual
best_individual = tools.selBest(result_pop, k=1)[0]
print("Best individual is:", best_individual)
print("Best fitness is:", best_individual.fitness.values[0])

Explanation

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

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

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

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

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

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

Output

The genetic algorithm will print the best individual and its corresponding fitness:

1
2
Best individual is: [-1.0333568778912494e-09, 1.0226956450775647e-09]
Best fitness is: 0.0

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.