Evolutionary Trait Optimization Using DEAP

Evolutionary Trait Optimization Using DEAP

Let’s explore an optimization problem inspired by biological evolution, specifically survival of the fittest in an ecosystem.

In this example, different species of organisms are competing for resources, and the goal is to optimize their fitness over time by evolving traits that help them survive and reproduce.

Biological Evolution Optimization Problem

Consider a simplified model where organisms have three key traits:

  1. Speed: Affects the ability to escape predators.
  2. Strength: Affects the ability to hunt and gather resources.
  3. Intelligence: Affects the ability to adapt to environmental changes.

The goal is to evolve a population of organisms to maximize their overall fitness, which is a function of these traits.

The fitness function is given as:

$$
f(\text{speed}, \text{strength}, \text{intelligence}) = \text{speed} \times \text{strength} + \text{intelligence}^2 - \frac{(\text{speed} + \text{strength} + \text{intelligence})^2}{10}
$$

where the three traits $( \text{speed}, \text{strength}, \text{intelligence} )$ are real-valued variables ranging between $0$ and $10$.

Problem Setup

  1. Objective: Maximize the fitness function, which simulates the survival advantage of organisms.
  2. Constraints:
    • Each trait (speed, strength, intelligence) must be within the range $([0, 10])$.
  3. Evolutionary Method: We will use a Genetic Algorithm (GA) via $DEAP$ to simulate the evolutionary process and optimize the population’s traits.

DEAP Implementation

The Genetic Algorithm will evolve a population of organisms, each represented by three variables (speed, strength, intelligence).

Over generations, the traits that provide higher fitness will propagate through the population.

Step-by-Step Process:

  1. Initialization: A random population of organisms (each with speed, strength, and intelligence) is generated.
  2. Selection: The fittest organisms are selected to reproduce, passing on their traits to the next generation.
  3. Crossover: Traits are combined from two parent organisms to produce offspring.
  4. Mutation: Random mutations introduce variations in traits, simulating biological mutations.
  5. Evolution: Over generations, the population evolves towards higher fitness.

Here is how we can implement this in $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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Define the fitness function (maximize fitness)
def fitness_function(individual):
    speed, strength, intelligence = individual
    return (speed * strength + intelligence**2 
            - (speed + strength + intelligence)**2 / 10,)

# Set bounds for speed, strength, intelligence
BOUND_LOW, BOUND_UP = [0, 0, 0], [10, 10, 10]

# Create the DEAP environment
creator.create("FitnessMax", base.Fitness, weights=(1.0,))  # Maximizing fitness
creator.create("Individual", list, fitness=creator.FitnessMax)

toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, 0, 10)
toolbox.register("individual", tools.initRepeat, creator.Individual, 
                 toolbox.attr_float, n=3)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("evaluate", fitness_function)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)

# Check if individuals stay within the bounds
def checkBounds(individual):
    for i in range(len(individual)):
        if individual[i] < BOUND_LOW[i]:
            individual[i] = BOUND_LOW[i]
        elif individual[i] > BOUND_UP[i]:
            individual[i] = BOUND_UP[i]
    return individual

# Custom mating and mutation functions to enforce bounds
def mate_and_checkBounds(ind1, ind2):
    tools.cxBlend(ind1, ind2, alpha=0.5)
    checkBounds(ind1)
    checkBounds(ind2)
    return ind1, ind2

def mutate_and_checkBounds(ind):
    tools.mutGaussian(ind, mu=0, sigma=1, indpb=0.2)
    checkBounds(ind)
    return ind,

toolbox.register("mate", mate_and_checkBounds)
toolbox.register("mutate", mutate_and_checkBounds)

# Algorithm parameters
population_size = 100
generations = 200
cx_prob = 0.5  # Crossover probability
mut_prob = 0.2  # Mutation probability

# Run the Genetic Algorithm
def main():
    pop = toolbox.population(n=population_size)
    hof = tools.HallOfFame(1)  # Keep track of the best individual

    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("min", np.min)
    stats.register("max", np.max)
    
    # Run the GA
    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=cx_prob, mutpb=mut_prob, 
                                   ngen=generations, stats=stats, 
                                   halloffame=hof, verbose=True)

    # Output the best solution
    best_ind = hof[0]
    print(f"Best individual: {best_ind}")
    print(f"Best fitness: {best_ind.fitness.values[0]}")
    
if __name__ == "__main__":
    main()

Explanation of the Code

  1. Fitness Function: The fitness_function simulates the organism’s fitness based on speed, strength, and intelligence.
    It rewards combinations of traits that lead to better survival while penalizing extreme values that might be biologically impractical (e.g., overly strong or fast organisms that exhaust themselves quickly).
  2. Bounds: We impose bounds on the traits to ensure that they stay within biologically plausible ranges ($0$ to $10$).
  3. Mating and Mutation:
    • Mating: cxBlend combines the traits of two parent organisms.
      We ensure the offspring traits remain within bounds.
    • Mutation: mutGaussian introduces random mutations to the traits.
      After mutation, we apply the bounds to keep the traits within the valid range.
  4. Population Evolution: The algorithm evolves the population over $200$ generations.
    During each generation, selection, crossover, and mutation are applied to produce new offspring, simulating biological evolution.

Running the Algorithm

When you run the genetic algorithm, it will evolve the population over time.

$DEAP$ will track the best individual (the organism with the highest fitness) and the average fitness in the population across generations.

The final result will show the traits of the fittest individual and their fitness score.

Biological Insights

This example mimics the evolutionary process, where organisms with the best combination of traits survive and reproduce.

The fitness landscape is non-linear, with trade-offs between speed, strength, and intelligence.

The genetic algorithm simulates how populations can optimize their traits over time to maximize survival.

This example showcases how $DEAP$ can be used to model and solve optimization problems inspired by biological evolution.

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
gen	nevals	avg    	min     	max    
0  	100   	30.2031	-4.58459	84.9431
1  	57    	45.4312	-1.22051	98.6147
2  	52    	60.872 	19.0426 	96.3292
3  	55    	73.3576	32.0905 	102.15 
4  	65    	83.0544	56.0338 	104.981
5  	45    	90.9604	70.2838 	109.471
6  	59    	96.4952	64.7244 	109.471
7  	63    	101.721	87.239  	109.868
        (details omitted)
194	69    	109.899	103.538 	110    
195	64    	109.94 	106.832 	110    
196	57    	109.635	99.4751 	110    
197	57    	109.624	94.0766 	110    
198	70    	109.483	101.174 	110    
199	70    	109.393	80.3783 	110    
200	65    	109.685	94.4924 	110    
Best individual: [10, 10.0, 10]
Best fitness: 110.0

This table shows the results of a genetic algorithm run over $200$ generations.

Here’s a simple breakdown of the columns:

  1. gen: The generation number, starting from $0$ up to $200$.
  2. nevals: Number of evaluations (solutions checked) in each generation.
  3. avg: The average fitness (quality of solutions) in that generation.
  4. min: The minimum fitness in that generation (worst solution).
  5. max: The maximum fitness in that generation (best solution).

The goal of the algorithm is to maximize fitness.

As we can see, the maximum fitness steadily improves across generations, starting from $84.94$ in generation $0$, and reaching the maximum of 110 by the end.

The best individual (solution) found is [10, 10.0, 10] with a fitness value of 110.0.
This shows the algorithm successfully found an optimal or near-optimal solution.