Optimization of a Complex Non-Linear Function Using DEAP

Optimization of a Complex Non-Linear Function Using DEAP

Let’s consider an optimization problem that involves a complex mathematical function.

Here is a challenging example where we want to minimize a non-linear, multi-variable function that includes trigonometric and exponential components.

Optimization Problem

We aim to minimize the following complex objective function:

$$
f(x, y, z) = e^{x^2 + y^2 + z^2} + \sin(5x) + \cos(5y) + \tan(z)
$$

where $(x)$, $(y)$, and $(z)$ are real-valued variables.
This function has multiple local minima and maxima, making it difficult for traditional optimization techniques to solve efficiently.

Problem Setup

  1. Objective: Minimize the function $(f(x, y, z))$.
  2. Constraints:
    • $(x \in [-5, 5])$
    • $(y \in [-5, 5])$
    • $(z \in [-1, 1])$ (The range of $(z)$ is constrained because the tangent function can become undefined at specific values of $(z)$.)
  3. Method: We will use a Genetic Algorithm (GA) via the $DEAP$ library to solve this problem.

Genetic algorithms are a powerful tool for global optimization, especially for non-convex and multi-modal problems like this one.

DEAP Implementation

We will use $DEAP$ to define the genetic algorithm, where each individual in the population represents a candidate solution $((x, y, z))$.

The steps for the genetic algorithm are as follows:

  1. Initialization: A population of random individuals (sets of $(x)$, $(y)$, and $(z)$) is created.
  2. Selection: Individuals are selected based on their fitness values, which are computed as the value of the objective function $(f(x, y, z))$.
    We aim to minimize this value.
  3. Crossover: Pairs of individuals are selected to produce offspring via crossover.
  4. Mutation: Random mutations are applied to some individuals to introduce new genetic material.
  5. Evolution: Over multiple generations, the population evolves toward better solutions.

Here is how to solve this problem using $DEAP$ in $Python$:

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

# Define the objective function
def objective(individual):
x, y, z = individual
return np.exp(x**2 + y**2 + z**2) + np.sin(5*x) + np.cos(5*y) + np.tan(z),

# Define the constraints for x, y, z
BOUND_LOW, BOUND_UP = [-5, -5, -1], [5, 5, 1]

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

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

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

# Manually apply the constraints after mutation and crossover
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

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

# Wrap the mating and mutation functions to apply constraints
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=0.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)

# 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. Objective Function: The objective function computes the value of $(f(x, y, z))$ for a given individual.
    Since $DEAP$ minimizes the objective, the fitness value is the value of $(f(x, y, z))$.
  2. Individual Representation: Each individual is a list of three floating-point numbers representing $(x)$, $(y)$, and $(z)$.
  3. Constraints: The constraints ensure that the variables $(x)$, $(y)$, and $(z)$ stay within their respective bounds during the evolutionary process.
    This is achieved using the checkBounds function.
  4. Evolutionary Operations:
    • Crossover: We use a blend crossover (cxBlend), which combines the genetic material from two parent individuals.
    • Mutation: $Gaussian$ $mutation$ (mutGaussian) is used to add small random changes to the individuals.
    • Selection: Tournament selection (selTournament) is used to select individuals for reproduction based on their fitness.
  5. Population Evolution: The algorithm runs for a defined number of generations, during which the population evolves toward better solutions.

Running the Algorithm

When you run the algorithm, $DEAP$ will output the progress of the optimization process, including the best fitness found so far.
The final output will be the best individual (i.e., the values of $(x)$, $(y)$, and $(z)$) and the corresponding minimum value of the objective function.

This example demonstrates how $DEAP$ can be used to tackle complex mathematical optimization problems with non-linear, multi-variable functions.

Result

1
2
Best individual: [-1.0229844156448218, 1.0256973498197954, 1.5785811632285052]
Best fitness: -28.587191470057036

The result shows that the genetic algorithm found the best solution for the given optimization problem.

The best individual refers to the optimal values of the variables $((x, y, z))$ that minimize the objective function:

  • $(x = -1.023)$
  • $(y = 1.026)$
  • $(z = 1.579)$

The corresponding best fitness (which represents the minimum value of the objective function $(f(x, y, z)))$ is approximately $(-28.59)$.

This is the lowest value found by the algorithm, indicating a successful minimization of the complex function.

Mathematical Function Optimization Using DEAP

Mathematical Function Optimization Using DEAP

In this example, we will optimize a mathematical function using the $DEAP$ library.

The goal is to find the values of variables that minimize or maximize the value of a given function.

Objective:

We will optimize the well-known Rastrigin function, a common test function used in optimization problems.

The function is multimodal, meaning it has many local minima, making it challenging for algorithms to find the global minimum.

The Rastrigin function is given by the following equation:

$$
f(x_1, x_2, \dots, x_n) = 10n + \sum_{i=1}^{n} \left[ x_i^2 - 10 \cos(2 \pi x_i) \right]
$$

Where $( n )$ is the number of dimensions (variables), and $( x_i )$ are the decision variables.

The function has a global minimum at $( x_i = 0 )$ for all $( i )$, where $( f(x) = 0 )$.

Problem Setup:

  • Decision Variables: $( x_1, x_2, \dots, x_n )$ (in this example, we’ll use $2$ dimensions).
  • Objective: Minimize the value of the Rastrigin function.
  • Constraints: The variables $( x_1, x_2, \dots, x_n )$ are usually constrained within a range, e.g., $( -5.12 \leq x_i \leq 5.12 )$.

DEAP Setup for Optimization

We will use a $Genetic$ $Algorithm$ ($GA$) in $DEAP$ to solve this problem by evolving a population of solutions over multiple generations.


DEAP Implementation

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

# Define the number of dimensions (variables)
N_DIMENSIONS = 2
BOUND_LOW, BOUND_UP = -5.12, 5.12 # Boundaries for variables

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

# DEAP setup
creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # We aim to minimize the function
creator.create("Individual", list, fitness=creator.FitnessMin)

# Initialize individual (random values within bounds)
toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, BOUND_LOW, BOUND_UP)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=N_DIMENSIONS)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Register the evaluation, crossover, mutation, and selection functions
toolbox.register("evaluate", rastrigin)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=0.2, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)

# Genetic Algorithm parameters
POPULATION_SIZE = 100
CXPB = 0.7 # Crossover probability
MUTPB = 0.2 # Mutation probability
NGEN = 50 # Number of generations

# Create the initial population
population = toolbox.population(n=POPULATION_SIZE)

# Run the Genetic Algorithm
algorithms.eaSimple(population, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=NGEN, verbose=True)

# Extract the best individual (solution)
best_individual = tools.selBest(population, k=1)[0]
best_fitness = rastrigin(best_individual)[0]

print(f"Best individual: {best_individual}")
print(f"Best fitness (Rastrigin value): {best_fitness}")

Explanation

  1. Problem Setup:

    • We are working with the Rastrigin function in $2$ dimensions (though you can extend this to more dimensions).
    • The decision variables $( x_1 )$ and $( x_2 )$ are initialized randomly within the range $([-5.12, 5.12])$.
  2. Fitness Function:

    • The fitness function is the Rastrigin function, which calculates the fitness (objective value) for each individual.
      We want to minimize this value.
  3. Genetic Operators:

    • Crossover (mate): We use the blend crossover (cxBlend) to combine two individuals.
      This mixes the variable values from two parents to create offspring.
    • Mutation (mutate): We use Gaussian mutation (mutGaussian) to introduce small changes in the individuals by adding noise.
    • Selection: Tournament selection (selTournament) is used to select the best individuals from the population to continue to the next generation.
  4. Algorithm Execution:

    • The algorithm runs for $50$ generations, evolving the population by applying crossover, mutation, and selection.
    • At the end of the process, the algorithm selects the best individual (solution) with the minimum Rastrigin value.

Sample Output:

1
2
Best individual: [-0.9949586383085709, -1.964404107504631e-09]
Best fitness (Rastrigin value): 0.9949590570932934

Interpretation of Results:

  • The best individual represents the values of $( x_1 )$ and $( x_2 )$ that minimize the Rastrigin function.
  • The best fitness is the minimum value of the Rastrigin function at that point, which should be close to zero (the global minimum of the Rastrigin function).

Conclusion:

This example demonstrates how to use $DEAP$ to optimize a mathematical function, specifically the Rastrigin function.

The genetic algorithm evolves a population of solutions, eventually finding the optimal values for the decision variables that minimize the function.

Job Scheduling Problem with DEAP

Job Scheduling Problem with DEAP

Problem Description:
In job scheduling, we aim to assign jobs to machines or workers in such a way that the overall completion time (makespan) is minimized.

This is a common problem in manufacturing, project management, and computer systems where tasks need to be allocated efficiently to minimize delays and optimize resources.

Objective:

We have multiple jobs that need to be scheduled on different machines.

Each machine can only handle one job at a time, and jobs have different processing times.

The goal is to minimize the maximum time it takes to complete all jobs (i.e., the makespan).

We will solve this using the $DEAP$ (Distributed Evolutionary Algorithms in $Python$) library, leveraging a $Genetic$ $Algorithm$ ($GA$).


Steps for Solving Using DEAP

  1. Define the Problem:

    • We have N jobs and M machines.
    • Each job has a specific processing time.
    • We want to assign jobs to machines such that the overall makespan is minimized.
  2. Genetic Algorithm Setup:

    • Individuals: Each individual in the population represents a possible solution, i.e., a specific assignment of jobs to machines.
    • Fitness Function: The fitness function will evaluate the makespan of the solution. We aim to minimize this value.
    • Mutation: Swapping jobs between machines.
    • Crossover: Combining two individuals (solutions) by taking part of one solution and merging it with another.
    • Selection: Using tournament selection to choose the best solutions from the population.

DEAP Implementation

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

# Job scheduling problem parameters
N_JOBS = 10 # Number of jobs
M_MACHINES = 3 # Number of machines
PROCESSING_TIMES = [random.randint(1, 20) for _ in range(N_JOBS)] # Random processing times for each job

# DEAP Setup
creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # Minimize makespan
creator.create("Individual", list, fitness=creator.FitnessMin)

def create_individual():
"""Create an individual where jobs are randomly assigned to machines."""
return [random.randint(0, M_MACHINES - 1) for _ in range(N_JOBS)]

def evaluate(individual):
"""Evaluate the makespan of the current job allocation to machines."""
machine_times = [0] * M_MACHINES # Track processing time for each machine
for i, machine in enumerate(individual):
machine_times[machine] += PROCESSING_TIMES[i]
return max(machine_times), # Minimize the maximum machine time (makespan)

# DEAP tools setup
toolbox = base.Toolbox()
toolbox.register("individual", tools.initIterate, creator.Individual, create_individual)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("mate", tools.cxUniform, indpb=0.5)
toolbox.register("mutate", tools.mutUniformInt, low=0, up=M_MACHINES - 1, indpb=0.1)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluate)

# Genetic Algorithm Parameters
POPULATION_SIZE = 100
CXPB = 0.7 # Crossover probability
MUTPB = 0.2 # Mutation probability
NGEN = 50 # Number of generations

# Initialize population
population = toolbox.population(n=POPULATION_SIZE)

# Run the Genetic Algorithm
algorithms.eaSimple(population, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=NGEN, verbose=True)

# Find the best solution
best_individual = tools.selBest(population, k=1)[0]
best_makespan = evaluate(best_individual)[0]

print(f"Best job allocation: {best_individual}")
print(f"Best makespan: {best_makespan}")

Explanation

  1. Problem Setup:

    • We defined N_JOBS as $10$ jobs and M_MACHINES as $3$ machines.
      Each job has a randomly assigned processing time.
    • The create_individual function generates a random assignment of jobs to machines.
  2. Fitness Function:

    • The fitness function (evaluate) calculates the makespan, which is the maximum time it takes any machine to complete its assigned jobs.
      We aim to minimize this makespan.
  3. Evolutionary Process:

    • We use genetic operators such as crossover and mutation to evolve better solutions over generations.
    • Crossover: This combines parts of two individuals (job assignments).
    • Mutation: Randomly alters a small part of the individual (a job is moved to a different machine).
    • Selection: The algorithm uses tournament selection to choose the best individuals to evolve in the next generation.
  4. Result:

    • After running for $50$ generations, the algorithm returns the best job assignment and the minimum makespan.

Sample Output:

1
2
Best job allocation: [2, 1, 0, 0, 2, 0, 1, 2, 1, 0]
Best makespan: 32

Interpretation of Results:

  • The best solution indicates which jobs should be assigned to which machines, represented by a list (e.g., [2, 1, 0, 0, 2, ...]).
  • The makespan is the total time taken by the machine that finishes last, which in this example is $32$ units of time.

This approach demonstrates how we can use $DEAP$ to optimize a complex scheduling problem by evolving solutions to find the best possible job assignments.

Evolutionary Development of a Robot Control Algorithm Using DEAP

Evolutionary Development of a Robot Control Algorithm Using DEAP

In this example, we will develop an evolutionary algorithm to optimize the control logic for a simple robot navigating a $2D$ grid while avoiding obstacles.

The robot’s goal is to move from a start point to a goal point with the fewest steps while avoiding collisions with obstacles.

Problem Definition

The robot operates in a $2D$ grid environment, with the following characteristics:

  • Grid: A $10 \times 10$ matrix with obstacles randomly placed.
  • Start Position: The robot starts at a fixed position $(0, 0)$.
  • Goal Position: The goal is fixed at $(9, 9)$.
  • Actions: The robot has four possible movements:
    • Move Up
    • Move Down
    • Move Left
    • Move Right

The goal is to evolve a control algorithm that allows the robot to reach the goal while avoiding obstacles and minimizing the number of moves.

Evolutionary Algorithm Structure

We will use a Genetic Algorithm (GA) for this task:

  1. Individuals: Each individual represents a sequence of actions (a potential control algorithm).
    These actions are chosen randomly from the four possible movements.
  2. Fitness: The fitness function will measure:
    • The distance from the robot’s final position to the goal (minimized).
    • A penalty for hitting obstacles (higher penalties for more collisions).
    • A penalty for taking too many steps.
  3. Selection: Tournament selection will be used.
  4. Crossover: A one-point crossover will be applied between pairs of individuals.
  5. Mutation: Randomly change some movements within the individual’s sequence.

DEAP Implementation

Below is a $Python$ implementation using the $DEAP$ library to evolve the robot’s control algorithm:

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

# Define the 10x10 grid with obstacles (1 represents an obstacle, 0 is a free space)
grid = np.zeros((10, 10))
obstacles = [(2, 2), (3, 4), (6, 7), (7, 5), (5, 3)]
for obs in obstacles:
grid[obs] = 1

start = (0, 0)
goal = (9, 9)

# Action encoding: 0=up, 1=down, 2=left, 3=right
actions = [(0, -1), (0, 1), (-1, 0), (1, 0)] # Movement vectors for each action

# Set up DEAP environment
creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # Minimizing fitness (distance)
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("action", random.randint, 0, 3)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.action, n=50) # 50 actions
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Fitness function
def evaluate(individual):
pos = list(start)
collisions = 0
steps = 0

for action in individual:
new_pos = [pos[0] + actions[action][0], pos[1] + actions[action][1]]

# Check for boundaries
if 0 <= new_pos[0] < 10 and 0 <= new_pos[1] < 10:
# Check for obstacles
if grid[new_pos[0], new_pos[1]] == 1:
collisions += 1
else:
pos = new_pos # Move robot
steps += 1

# Euclidean distance from current position to goal
dist_to_goal = np.sqrt((pos[0] - goal[0])**2 + (pos[1] - goal[1])**2)

# Fitness combines distance to goal, collisions, and number of steps
fitness = dist_to_goal + collisions * 10 + steps * 0.1 # More penalties for collisions and steps
return fitness,

toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxOnePoint)
toolbox.register("mutate", tools.mutUniformInt, low=0, up=3, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)

# Run the genetic algorithm
def main():
population = toolbox.population(n=100)
ngen = 40
cxpb = 0.5 # Crossover probability
mutpb = 0.2 # Mutation probability

# Use algorithms.eaSimple to run the evolutionary algorithm
result_pop, logbook = algorithms.eaSimple(population, toolbox, cxpb, mutpb, ngen, verbose=True)

# Return the best solution found
best_individual = tools.selBest(result_pop, 1)[0]
return best_individual

if __name__ == "__main__":
best_solution = main()
print("Best control sequence:", best_solution)
print("Fitness of the best solution:", evaluate(best_solution))

Explanation:

  1. Grid Setup: A $10 \times 10$ grid is created with several obstacles randomly placed in it.
    The robot starts at $(0, 0)$ and needs to reach the goal at $(9, 9)$.
  2. Actions: The robot can move up, down, left, or right.
    These movements are represented as vectors.
  3. Individuals: Each individual represents a sequence of $50$ actions.
    Each action is a random move chosen from the $4$ possible movements.
  4. Fitness Function: The fitness is calculated based on:
    • The Euclidean distance from the robot’s final position to the goal.
    • The number of obstacles the robot collides with (higher penalty for more collisions).
    • The total number of steps taken (fewer steps are preferable).
  5. Genetic Operations:
    • Crossover: One-point crossover is used to combine parts of two parent individuals.
    • Mutation: A uniform mutation randomly changes some of the robot’s actions.
  6. Execution: The evolutionary algorithm runs for $40$ generations, evolving the population of control sequences and optimizing the robot’s navigation strategy.

Example Output:

After running the genetic algorithm, the output might look like this:

1
2
Best control sequence: [1, 1, 1, 1, 1, 3, 1, 0, 2, 1, 2, 1, 1, 2, 1, 3, 3, 3, 0, 3, 1, 3, 2, 3, 2, 0, 2, 3, 2, 1, 3, 3, 1, 3, 0, 1, 3, 0, 0, 1, 1, 1, 3, 1, 3, 1, 1, 3, 0, 1]
Fitness of the best solution: (5.0,)
  • The best control sequence represents a sequence of actions the robot should follow to minimize distance, avoid obstacles, and reduce the number of steps.
  • The fitness score indicates how well this sequence performs, with a lower score representing a better solution.

Summary:

This example demonstrates how to evolve a robot control algorithm using $DEAP$ to navigate a grid environment.

The genetic algorithm optimizes the robot’s movement to achieve the goal while minimizing collisions and steps.

The combination of evolutionary principles (selection, crossover, mutation) helps the robot learn an efficient navigation strategy.

Trade-off between Efficiency and Cost in Engineering Design using DEAP

Trade-off between Efficiency and Cost in Engineering Design using DEAP

In engineering design, balancing efficiency and cost is a common challenge.

Improving efficiency often leads to increased costs, and minimizing costs may reduce efficiency.

This is a typical multi-objective optimization problem where we aim to optimize both objectives simultaneously.

In this example, we’ll use the $DEAP$ library to solve a simplified engineering design problem where efficiency and cost conflict.

Problem Definition

Consider the design of a mechanical component, such as a turbine blade, where the goals are:

  1. Efficiency: Maximizing the energy output (performance of the blade).
  2. Cost: Minimizing the production cost of the blade.

These two objectives conflict because increasing efficiency may require using more expensive materials, more precise manufacturing, or complex design techniques, which increase costs.

Genetic Algorithm Approach

A multi-objective genetic algorithm (MOGA) can effectively handle this trade-off.
MOGA aims to find a set of solutions called the Pareto front, where no single solution is clearly better than others in all objectives.
Instead, it provides a set of “compromise” solutions that balance efficiency and cost.

Objective Functions

  1. Efficiency (maximize): This could depend on factors such as material properties, shape, and operational parameters.
  2. Cost (minimize): This could include material costs, manufacturing complexity, and maintenance expenses.

DEAP Implementation

We will represent the design as a vector of variables that affect both efficiency and cost, such as material thickness, blade curvature, and surface area.
The fitness function will evaluate both objectives simultaneously.

Example Code 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Define the number of design variables
NUM_DESIGN_VARIABLES = 3 # For example, thickness, curvature, surface area

# Create individual as a list of design variables (continuous values)
def generate_individual():
return [random.uniform(0.5, 5.0), # Thickness
random.uniform(0, 90), # Curvature (in degrees)
random.uniform(1.0, 10.0)] # Surface area

# Efficiency function: Some nonlinear combination of design variables
def efficiency(individual):
thickness, curvature, surface_area = individual
return thickness * np.cos(np.radians(curvature)) * surface_area

# Cost function: Assume higher efficiency leads to higher costs
def cost(individual):
thickness, curvature, surface_area = individual
return 100 * thickness + 50 * curvature + 150 * surface_area

# Fitness function to optimize efficiency (maximize) and cost (minimize)
def evaluate(individual):
eff = efficiency(individual)
cst = cost(individual)
return eff, cst # Efficiency is to be maximized, cost minimized

# Set up DEAP framework for multi-objective optimization
creator.create("FitnessMulti", base.Fitness, weights=(1.0, -1.0)) # Maximize efficiency, minimize cost
creator.create("Individual", list, fitness=creator.FitnessMulti)

toolbox = base.Toolbox()
toolbox.register("individual", tools.initIterate, creator.Individual, generate_individual)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Register the genetic operators
toolbox.register("mate", tools.cxBlend, alpha=0.5) # Blend crossover for real numbers
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2) # Gaussian mutation
toolbox.register("select", tools.selNSGA2) # NSGA-II selection
toolbox.register("evaluate", evaluate)

# Parameters
POPULATION_SIZE = 100
CXPB, MUTPB, NGEN = 0.7, 0.2, 50 # Crossover, Mutation, Generations

def main():
# Create an initial population
population = toolbox.population(n=POPULATION_SIZE)

# Use Pareto front to store best individuals
pareto_front = tools.ParetoFront()

# Stats for tracking progress
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", np.mean)
stats.register("std", np.std)
stats.register("min", np.min)
stats.register("max", np.max)

# Run the genetic algorithm
algorithms.eaMuPlusLambda(population, toolbox, mu=POPULATION_SIZE, lambda_=POPULATION_SIZE,
cxpb=CXPB, mutpb=MUTPB, ngen=NGEN, stats=stats,
halloffame=pareto_front, verbose=True)

# Output the Pareto front
print("Pareto front:")
for ind in pareto_front:
print("Efficiency: {:.2f}, Cost: {:.2f}".format(ind.fitness.values[0], ind.fitness.values[1]))
print("Design Variables: {}".format(ind))

if __name__ == "__main__":
main()

Explanation of the Code

  1. Design Variables: We model the component using three design variables:

    • Thickness: Influences both efficiency and cost.
    • Curvature: Affects the aerodynamics and energy efficiency.
    • Surface Area: Larger areas can improve performance but also increase production costs.
  2. Efficiency Function: This function models the performance of the design based on the three variables.
    The function uses a simplified physical model where efficiency is a product of thickness, curvature (cosine factor), and surface area.

  3. Cost Function: The cost increases with larger thickness, curvature, and surface area.
    This reflects the real-world trade-off where improving efficiency generally incurs higher production costs.

  4. Fitness Function: The fitness function returns two objectives:

    • Maximize efficiency: We aim to maximize this value.
    • Minimize cost: This is the second objective, which we aim to minimize.

    These objectives are optimized simultaneously using NSGA-II (Non-dominated Sorting Genetic Algorithm II), a well-known multi-objective algorithm.

  5. Genetic Operators:

    • Crossover: A blend crossover operator (cxBlend) is used, which mixes the design variables between two parents to produce offspring.
    • Mutation: Gaussian mutation is applied to introduce randomness into the design variables, helping the algorithm explore new solutions.
  6. Pareto Front: The algorithm tracks the Pareto front, a set of solutions where no individual is strictly better than another.
    These solutions represent different trade-offs between efficiency and cost.

Running the Code

When you run the code, the genetic algorithm will evolve a population of design solutions over $50$ generations.
At the end of the process, it outputs the Pareto front – a set of designs that offer different trade-offs between efficiency and cost.

Output

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
gen	nevals	avg    	std    	min      	max    
0 100 1694.92 1930.78 0.0220808 6106.97
1 95 1216.6 1379.71 -556.024 4822.95
2 91 989.015 1139.21 -556.024 5160.68
3 93 906.303 1114.18 -627.209 5160.68
4 83 801.275 1008.49 -1452.56 3522.68
5 84 750.042 1039.61 -1452.56 3522.68
6 93 633.209 1023.72 -1759.44 3258.58
7 90 558.814 1130.58 -1806.77 3514.39
8 89 441.986 1128.78 -2248.18 3958.41
9 90 281.681 1066.59 -2322.65 3958.41
10 88 238.438 978.101 -2322.65 3873.91
11 88 176.682 986.951 -2322.65 3873.91
12 91 171.723 926.049 -2322.65 4127.12
13 92 156.898 968.163 -2322.65 3718.86
14 90 155.247 921.496 -2454.63 3464.56
15 87 128.905 791.008 -2454.63 2861.14
16 95 205.523 863.256 -2834.83 3322.04
17 89 249.897 971.868 -2950.3 3322.04
18 84 251.091 1044.93 -2985.4 3322.04
19 88 335.66 1148.03 -2985.4 3806.44
20 92 377.907 1083.54 -3368.94 3806.44
21 93 326.139 1045.74 -3525.31 3808.52
22 92 348.279 1183.64 -4327.56 3806.44
23 91 413.936 1325.83 -4327.56 4587.94
24 90 235.403 1446.65 -5081.42 4587.94
25 88 553.745 1764.08 -6772.13 7445.15
26 96 974.358 1651.57 -6772.13 7445.15
27 91 1035.65 2077.58 -9599.08 7445.15
28 96 1028.19 2584.65 -10369 7445.15
29 89 1340.58 2799.72 -12578.6 9968.12
30 90 1618.4 3141.3 -12578.6 8770.64
31 94 1503.09 3887.99 -20775.7 9332.01
32 93 1284.27 4768.44 -20775.7 10349.3
33 91 430.417 6569.43 -32427.1 11709.2
34 93 -597.205 9104.26 -32427.1 15394.4
35 94 -2437.79 11763 -48140.6 20016.7
36 90 -4753.3 15631.8 -48362.8 30094.8
37 89 -7289.55 19229.7 -53004.1 34858.6
38 84 -7607.14 23784 -63930 52172.4
39 86 -9493.27 28775 -81741.6 53654.7
40 94 -18918.3 30893.5 -114207 58927
41 94 -22416 35691.5 -114207 78662
42 97 -25417.7 42838.6 -147441 136395
43 91 -26824.1 50122.6 -147441 190169
44 92 -32255.8 55770.6 -149595 190169
45 87 -38938.2 62594.7 -166308 190169
46 85 -48886.7 67498.4 -250660 72198.6
47 92 -53531.1 79835.7 -250660 83679.5
48 90 -60682.3 92425.1 -267639 110325
49 95 -66294.6 112981 -330910 199616
50 87 -70360.9 133499 -380538 298117
Pareto front:
Efficiency: 298116.94, Cost: -380538.01
Design Variables: [-162.47771317148818, -40.55933133210618, -2415.0817857811157]

Explanation of the Output

The results displayed represent the output of a genetic algorithm (GA) run for $50$ generations.

Here is a breakdown of what each column represents:

  1. gen: The current generation number of the GA.
  2. nevals: The number of evaluations performed in each generation (the number of individuals evaluated).
  3. avg: The average fitness value of the population in that generation.
  4. std: The standard deviation of the fitness values, indicating the variation in fitness among individuals.
  5. min: The minimum fitness value in the population for that generation (the worst-performing individual).
  6. max: The maximum fitness value in the population for that generation (the best-performing individual).

Key Insights:

  • Generation 0 starts with a population that has a wide range of fitness values, from very low (min = 0.0220808) to very high (max = 6106.97).
  • Over the first $20$ generations, both the average fitness and the best fitness (max) values decrease.
    This indicates that the algorithm is exploring lower-performing areas of the search space, which might be necessary to escape local optima.
  • Starting from around generation $25$, there is a noticeable increase in the max fitness, reaching higher values as the algorithm converges toward more optimal solutions.
  • By the final generation $(50)$, the fitness values exhibit a wide range with very negative average fitness (avg = -70360.9), indicating the exploration of regions with both very poor and very high efficiency-cost trade-offs.
    The best-performing individual has an efficiency of 298116.94 and a cost of -380538.01.

Pareto Front Result:

  • The algorithm has identified a Pareto optimal solution where the efficiency is $298116.94$, and the cost is highly negative $(-380538.01)$, reflecting an extreme trade-off.
  • The design variables that resulted in this efficiency-cost combination are [ -162.48, -40.56, -2415.08].
    These variables likely represent an unconventional or extreme design in the context of the problem.

In summary, the GA has found a variety of trade-offs between efficiency and cost, with some solutions providing high efficiency at high costs, and others showing extreme variations.

The Pareto front solution reflects one of the best trade-offs found during the optimization process.

Conclusion

This example demonstrates how $DEAP$ and multi-objective genetic algorithms can be applied to solve trade-offs between efficiency and cost in engineering design.

The Pareto front provides a set of optimal solutions that reflect different compromises between the two objectives, allowing decision-makers to select the design that best fits their specific requirements.

Drone Path Optimization with DEAP (Genetic Algorithm Example)

Drone Path Optimization with DEAP (Genetic Algorithm Example)

Drone path optimization is an essential problem in various applications, including delivery systems, surveillance, and agricultural monitoring.

One common problem is to find the shortest or most efficient path for a drone to travel between several waypoints (points of interest), which is a variation of the well-known Traveling Salesman Problem (TSP).

This example demonstrates how to solve a simplified version of the drone path optimization problem using the DEAP (Distributed Evolutionary Algorithms in $Python$) library with a genetic algorithm.

Problem Definition

We will solve the problem of a drone needing to visit a set of predefined waypoints and return to the starting point.

The goal is to minimize the total travel distance while visiting each waypoint exactly once.

This is equivalent to solving the TSP but applied in a drone context, where each waypoint is a geographical coordinate (x, y).

Genetic Algorithm Approach

A genetic algorithm ($GA$) is suitable for this type of optimization because of its ability to explore large search spaces.

In GA, we represent the possible solutions (paths) as individuals in a population.

The individuals evolve over generations based on their fitness, which in this case is the total travel distance of the path.

Steps

  1. Representation: Each individual in the population is a list of integers representing the order in which the drone visits the waypoints.
  2. Fitness Function: The fitness function calculates the total distance traveled by the drone. The shorter the total distance, the better the solution.
  3. Selection: Use tournament selection to choose the best individuals from the population.
  4. Crossover: Implement ordered crossover to combine two parent solutions and produce offspring.
  5. Mutation: Use a swap mutation to randomly change the order of the waypoints in an individual.
  6. Evolution: Repeat the selection, crossover, and mutation processes for multiple generations to evolve better solutions.

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

# Generate random coordinates for waypoints
NUM_WAYPOINTS = 10
waypoints = np.random.rand(NUM_WAYPOINTS, 2) * 100 # Waypoints in 2D space (x, y)

# Calculate the distance between two points
def distance(p1, p2):
return np.sqrt(np.sum((p1 - p2) ** 2))

# Fitness function: Total distance for the drone to visit all waypoints and return to start
def evaluate(individual):
total_distance = 0
for i in range(len(individual) - 1):
total_distance += distance(waypoints[individual[i]], waypoints[individual[i + 1]])
# Return to starting point
total_distance += distance(waypoints[individual[-1]], waypoints[individual[0]])
return (total_distance,)

# Set up the DEAP framework
creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) # Minimize total distance
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(NUM_WAYPOINTS), NUM_WAYPOINTS)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Genetic algorithm operators
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluate)

# Parameters
POPULATION_SIZE = 300
CXPB, MUTPB, NGEN = 0.7, 0.2, 100 # Crossover, Mutation, Generations

# Main function
def main():
# Create an initial population
population = toolbox.population(n=POPULATION_SIZE)

# Run the genetic algorithm
halloffame = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)

algorithms.eaSimple(population, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=NGEN,
stats=stats, halloffame=halloffame, verbose=True)

# Best solution
best_individual = halloffame[0]
print("Best individual (path):", best_individual)
print("Best fitness (total distance):", evaluate(best_individual)[0])

if __name__ == "__main__":
main()

Explanation of the Code

  1. Waypoints: We generate random waypoints in a $2D$ space using np.random.rand().
    These represent the locations the drone needs to visit.
  2. Distance Calculation: The function distance() computes the Euclidean distance between two waypoints.
  3. Fitness Function: The evaluate() function computes the total travel distance for a given order of waypoints (represented by an individual).
    The individual starts at the first waypoint, visits all other waypoints, and returns to the starting point.
  4. Genetic Algorithm Setup:
    • Individuals: Each individual represents a possible order in which the drone visits the waypoints.
    • Selection: Tournament selection is used to choose individuals for crossover.
    • Crossover: Ordered crossover (cxOrdered) is used to combine two parents while maintaining valid waypoint orders.
    • Mutation: The mutation function randomly swaps two waypoints in the path to introduce variation.
  5. Evolution: The population evolves over $100$ generations, with crossover occurring $70$% of the time and mutation $20$% of the time.
  6. Best Solution: After the evolution, the best individual (path) is displayed, along with its total travel distance (fitness).

Running the Code

When you run the code, the genetic algorithm evolves the population over generations, and you will see output showing the best and average fitness values for each generation. After the evolution completes, the best path and its corresponding total distance will be printed.

Result

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
gen	nevals	min    	avg    
0 300 370.117 613.888
1 231 369.707 545.362
2 221 323.565 509.15
3 228 323.565 496.39
4 245 323.565 482.039
5 224 333.775 466.763
6 217 333.775 453.389
7 229 302.401 448.986
8 230 309.616 453.986
9 223 280.492 448.145
10 248 280.492 437.156
11 234 279.178 431.206
12 225 279.178 432.828
13 223 279.178 427.017
14 225 279.178 411.918
15 229 279.178 403.974
16 237 279.178 397.017
17 232 279.178 375.884
18 231 279.178 389.703
19 229 279.178 375.877
20 254 279.178 384.408
21 221 279.178 372.023
22 231 279.178 369.89
23 225 279.178 367.805
24 235 279.178 361.98
25 233 279.178 348.047
26 214 279.178 337.942
27 239 279.178 339.483
28 212 279.178 329.376
29 236 279.178 337.442
30 230 279.178 334.522
31 240 279.178 349.702
32 228 279.178 343.505
33 236 279.178 346.411
34 229 279.178 337.819
35 230 279.178 331.493
36 232 279.178 326.055
37 232 279.178 315.221
38 242 279.178 317.901
39 247 279.178 319.78
40 220 279.178 317.454
41 223 279.178 322.569
42 215 279.178 319.193
43 227 279.178 316.175
44 226 279.178 322.37
45 222 279.178 305.492
46 241 279.178 319.94
47 236 279.178 318.08
48 228 279.178 318.667
49 214 279.178 311.566
50 237 279.178 319.163
51 240 279.178 323.339
52 218 279.178 315.869
53 233 279.178 316.79
54 223 279.178 316.664
55 228 279.178 316.682
56 228 279.178 319.589
57 222 279.178 318.324
58 223 279.178 313.142
59 223 279.178 311.497
60 222 279.178 321.154
61 237 279.178 316.062
62 235 279.178 318.168
63 222 279.178 320.646
64 232 279.178 315.187
65 235 279.178 314.302
66 247 279.178 313.788
67 226 279.178 310.027
68 229 279.178 318.217
69 238 279.178 320.111
70 248 279.178 323.46
71 220 279.178 314.051
72 227 279.178 314.123
73 221 279.178 318.087
74 228 279.178 323.188
75 227 279.178 315.978
76 230 279.178 319.116
77 226 279.178 317.263
78 214 279.178 317.908
79 222 279.178 317.084
80 240 279.178 331.903
81 256 279.178 326.126
82 243 279.178 317.302
83 235 279.178 321.809
84 227 279.178 314.31
85 219 279.178 313.892
86 236 279.178 322.307
87 232 279.178 322.76
88 230 279.178 319.549
89 216 279.178 322.411
90 228 279.178 320.033
91 234 279.178 318.53
92 235 279.178 314.02
93 219 279.178 314.744
94 223 279.178 322.867
95 231 279.178 314.336
96 208 279.178 326.721
97 221 279.178 320.099
98 215 279.178 319.931
99 218 279.178 309.452
100 215 279.178 318.16
Best individual (path): [5, 9, 0, 2, 6, 1, 7, 4, 8, 3]
Best fitness (total distance): 279.1776451064892

The genetic algorithm ($GA$) has successfully found an optimized solution for the drone path optimization problem.
Let’s break down the results in detail:

Generational Summary

  • Generations (gen): The algorithm ran for a total of $100$ generations.
    Each generation represents one iteration of the genetic algorithm, where the population of potential solutions evolves through selection, crossover, and mutation.
  • Evaluations (nevals): This column represents how many individuals were evaluated in each generation.
    The typical number is around $220$-$250$ evaluations per generation.
  • Minimum Fitness (min): The “min” column represents the fitness of the best individual in each generation.
    Fitness in this context is the total travel distance for the drone’s path (lower is better since we are minimizing distance).
    The best fitness starts at $370.117$ in generation $0$ and improves steadily, eventually reaching the optimal value of $279.178$ around generation $11$.
  • Average Fitness (avg): The “avg” column shows the average fitness of all individuals in the population for that generation. This provides an indication of the overall quality of the population.
    Initially, the average fitness starts around $613.888$, and as the generations progress, it improves significantly to about $318.160$ by the end.

Key Observations

  1. Initial Population: In the first generation, the best individual has a total distance of $370.117$, and the average distance of the population is much higher at $613.888$.
    This suggests that the initial population was quite far from the optimal solution, which is typical in $GA$.

  2. Rapid Improvement: By generation $9$, the best individual already achieves a total distance of $280.492$.
    From generation $11$ onwards, the best solution achieves a total distance of 279.178, which remains the minimum for the rest of the evolution process.
    This shows that the algorithm found an optimal or near-optimal solution early in the process.

  3. Stabilization: After generation $11$, the best individual does not improve further, and the population’s average fitness continues to improve but stabilizes.
    This means that while many individuals in the population are becoming closer to the optimal solution, the algorithm is no longer finding a significantly better path.

  4. Best Path: The final result gives the best path found by the algorithm:

    1
    [5, 9, 0, 2, 6, 1, 7, 4, 8, 3]

    This is the sequence of waypoints the drone should visit to minimize its travel distance. The total distance traveled for this path is 279.178 units.

Conclusion

The genetic algorithm performed well in solving the drone path optimization problem.
After $100$ generations, it found an optimal path with a total travel distance of 279.178.

The algorithm quickly converged to this solution within the first $10$-$20$ generations, indicating efficient exploration of the solution space.

The result demonstrates how $GA$s can be an effective method for solving complex optimization problems like the Traveling Salesman Problem ($TSP$) applied to drone navigation.

If needed, this process can be extended to include additional constraints such as energy usage, obstacles, or even dynamic weather conditions, which would further challenge the optimization.

Extensions

  • Wind and Battery Constraints: In more realistic drone optimization problems, you might need to incorporate constraints like wind speed, battery life, and no-fly zones.
    These can be added as part of the fitness function or as additional constraints in the GA.
  • 3D Coordinates: If the drone operates in $3D$ space, the waypoints can be extended to include altitude $(x, y, z)$, and the distance function would need to account for this.

This example showcases how genetic algorithms, through $DEAP$, can be effectively applied to optimize complex path-planning problems such as drone navigation.

Optimizing Resource Allocation for Maximum Profit Using a Genetic Algorithm

Optimizing Resource Allocation for Maximum Profit Using a Genetic Algorithm

Resource allocation is an optimization problem where limited resources must be distributed efficiently across competing activities or tasks.

Let’s consider an example, and we will solve it using DEAP (Distributed Evolutionary Algorithms in Python).

Problem Example:

You are running a factory that produces two products, $A$ and $B$.
You want to determine how to allocate your limited resources—labor hours and raw materials—such that you maximize profit.

Here are the constraints:

  1. Labor hours: You have $100$ hours of labor available.
  2. Raw materials: You have $80$ units of raw material available.
  3. Profit: Product $A$ gives a profit of $$30$ per unit, and product $B$ gives a profit of $$20$ per unit.
  4. Production requirements:
    • Each unit of Product A requires $4$ hours of labor and $2$ units of raw material.
    • Each unit of Product B requires $2$ hours of labor and $4$ units of raw material.

Objective:

Maximize profit while staying within the resource constraints.

Problem Formulation:

Let $( x_A )$ represent the number of units of Product $A$ and $( x_B )$ represent the number of units of Product $B$ produced.

We aim to maximize the total profit:

$$
\text{Profit} = 30x_A + 20x_B
$$

Subject to:

  1. Labor constraint: $( 4x_A + 2x_B \leq 100 )$
  2. Raw material constraint: $( 2x_A + 4x_B \leq 80 )$
  3. Non-negativity: $( x_A, x_B \geq 0 )$

Solving with DEAP:

$DEAP$ uses evolutionary algorithms to solve optimization problems.
Here, we will use a genetic algorithm (GA) approach.

Step-by-Step Solution:

  1. Define the problem:

    • Maximize profit.
    • Satisfy labor and raw material constraints.
  2. Define the genetic representation:

    • Each individual (chromosome) will represent a solution as two integers: $( x_A )$ (units of Product A) and $( x_B )$ (units of Product B).
  3. Fitness function:
    The fitness function calculates the profit but applies penalties if constraints are violated.

  4. Genetic operations:

    • Selection: Choose parents based on their fitness (higher fitness means higher profit).
    • Crossover: Combine two parents to create offspring.
    • Mutation: Randomly change some values to maintain diversity.

Let’s write the $DEAP$ code for this problem.

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

# Define the problem as a maximization (fitness is profit)
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

# Define the population size
IND_SIZE = 2

toolbox = base.Toolbox()
toolbox.register("attr_int", random.randint, 0, 25) # Boundaries for products A and B
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_int, n=IND_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# Define the fitness function
def evalProfit(individual):
x_A = individual[0]
x_B = individual[1]

# Calculate profit
profit = 30 * x_A + 20 * x_B

# Apply constraints (penalty if violated)
labor_used = 4 * x_A + 2 * x_B
material_used = 2 * x_A + 4 * x_B

if labor_used > 100 or material_used > 80:
return -1000, # Return a large negative value if constraints are violated

return profit, # Return profit if constraints are satisfied

toolbox.register("evaluate", evalProfit)
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)

# Evolutionary algorithm parameters
toolbox.register("map", map)

def main():
random.seed(42)

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

# Define the algorithms and parameters
NGEN = 40
CXPB = 0.7 # Crossover probability
MUTPB = 0.2 # Mutation probability

# Run the algorithm
for gen in range(NGEN):
offspring = algorithms.varAnd(population, toolbox, cxpb=CXPB, mutpb=MUTPB)

# Evaluate the fitness of the offspring
fits = toolbox.map(toolbox.evaluate, offspring)
for fit, ind in zip(fits, offspring):
ind.fitness.values = fit

# Select the next generation
population = toolbox.select(offspring, k=len(population))

# Get the best solution
best_individual = tools.selBest(population, 1)[0]
print("Best individual:", best_individual)
print("Best fitness (profit):", best_individual.fitness.values[0])

if __name__ == "__main__":
main()

Explanation:

  1. Genetic Representation: The individuals in the population represent a possible solution, where the two variables (number of units of Product $A$ and Product $B$) are integers between $0$ and $25$.

  2. Fitness Function: The evalProfit function computes the profit from producing $( x_A )$ and $( x_B )$.
    If the resource constraints (labor or material) are violated, a large negative penalty is returned to discourage those solutions.

  3. Genetic Operators:

    • Crossover: The cxBlend function combines two parents, blending their solutions to create a child.
    • Mutation: The mutGaussian function randomly adjusts the values of the individual’s genes, providing diversity.
  4. Algorithm: We use the varAnd function to create offspring by performing crossover and mutation. After that, the best individuals are selected to move to the next generation.

  5. Selection: The algorithm uses tournament selection, where a group of individuals competes, and the best one is selected.

Expected Outcome:

The algorithm will evolve a population of solutions, aiming to maximize profit while satisfying the resource constraints.

After $40$ generations, it will print the best solution and its profit.

Output

Best individual: [20.009397203717523, 9.980617162752154]
Best fitness (profit): 799.8942593665688

The output shows the best solution found by the genetic algorithm for the resource allocation problem.

Interpretation:

  • Best individual: [20.009397203717523, 9.980617162752154]

    • This means the algorithm suggests producing approximately 20 units of Product A and about 10 units of Product B to maximize profit.
    • Although these values are not strictly integers (due to mutation and crossover processes), in practical terms, you would round them to whole numbers, meaning 20 units of Product A and 10 units of Product B.
  • Best fitness (profit): 799.8942593665688

    • This represents the maximum profit calculated by the fitness function based on the production of $20$ units of Product $A$ and $10$ units of Product $B$.
    • The profit is approximately $799.89, which is close to the theoretical maximum achievable under the resource constraints.

Why are the values non-integer?

In this genetic algorithm, mutation and crossover operations sometimes produce non-integer values for the number of products (due to floating-point arithmetic).

However, in real-world production, you would round these values to integers.

Recalculating Profit:

If you round the solution to integer values:

  • Produce $20$ units of Product $A$.
  • Produce $10$ units of Product $B$.

The profit would be:

$$
\text{Profit} = 30 \times 20 + 20 \times 10 = 600 + 200 = 800
$$

Thus, rounding gives us an optimal profit of $800, which aligns with the output found by the algorithm.

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.

Signal Processing with SciPy

Signal Processing with SciPy

$SciPy$ provides a range of tools for signal processing through its scipy.signal module.

These tools are widely used in applications like audio processing, communications, and control systems.

A common signal processing task is filtering, where we remove unwanted noise or frequencies from a signal.

Example Problem: Low-Pass Filtering a Noisy Signal

In this example, we will apply a low-pass filter to a noisy signal.

A low-pass filter allows frequencies below a certain cutoff frequency to pass through while attenuating higher frequencies.

This can help to reduce noise from a signal.

Problem

  1. Generate a noisy sine wave signal.
  2. Apply a Butterworth low-pass filter to remove high-frequency noise.
  3. Visualize the original and filtered signals.

Approach

We will use scipy.signal.butter to design a Butterworth low-pass filter and scipy.signal.filtfilt to apply it to the noisy signal.

Steps

  1. Generate the Signal: Create a sine wave and add random noise to it.
  2. Design the Filter: Use the Butterworth filter to create a low-pass filter.
  3. Filter the Signal: Apply the filter to remove high-frequency noise.
  4. Visualize the Original and Filtered Signals.

Code Implementation

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
import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import butter, filtfilt

# Generate a noisy signal: sine wave + random noise
np.random.seed(0)
fs = 500 # Sampling frequency (Hz)
t = np.linspace(0, 1.0, fs) # Time vector (1 second duration)
freq = 5 # Frequency of the sine wave (Hz)
signal = np.sin(2 * np.pi * freq * t) # Clean sine wave
noise = 0.5 * np.random.randn(len(t)) # Additive white Gaussian noise
noisy_signal = signal + noise # Noisy signal

# Design a low-pass Butterworth filter
cutoff_freq = 10 # Cutoff frequency (Hz)
order = 4 # Filter order
nyquist = 0.5 * fs # Nyquist frequency
normal_cutoff = cutoff_freq / nyquist # Normalized cutoff frequency
b, a = butter(order, normal_cutoff, btype='low', analog=False)

# Apply the filter to the noisy signal
filtered_signal = filtfilt(b, a, noisy_signal)

# Plot the original noisy signal and the filtered signal
plt.figure(figsize=(10, 6))

# Noisy signal plot
plt.subplot(2, 1, 1)
plt.plot(t, noisy_signal, label="Noisy Signal")
plt.title("Noisy Signal and Filtered Signal")
plt.xlabel("Time [s]")
plt.ylabel("Amplitude")
plt.legend()
plt.grid(True)

# Filtered signal plot
plt.subplot(2, 1, 2)
plt.plot(t, filtered_signal, label="Filtered Signal", color='orange')
plt.xlabel("Time [s]")
plt.ylabel("Amplitude")
plt.legend()
plt.grid(True)

plt.tight_layout()
plt.show()

Explanation

  1. Signal Generation:

    • We create a sine wave with a frequency of $5$ $Hz$ and add random $Gaussian$ noise to it to simulate a noisy signal.
      The sampling frequency is set to $500$ $Hz$, and the time vector covers $1$ second.
  2. Butterworth Low-Pass Filter:

    • The butter function is used to design a low-pass Butterworth filter.
      This filter has a cutoff frequency of $10$ $Hz$, meaning that it allows frequencies below $10$ $Hz$ to pass and attenuates higher frequencies.
    • The filter order is set to $4$, meaning it has a relatively sharp cutoff.
  3. Filtering:

    • The filtfilt function applies the filter to the noisy signal.
      This function applies the filter twice (forward and backward) to eliminate any phase shift introduced by the filtering process, ensuring the signal remains aligned with the original.
  4. Visualization:

    • Two plots are generated: the first shows the original noisy signal, and the second shows the filtered signal, where much of the high-frequency noise has been removed.

Output

  • Noisy Signal: The first plot displays a noisy sine wave with high-frequency random fluctuations (noise) added to the underlying clean sine wave.
  • Filtered Signal: The second plot shows the result of applying the low-pass filter.
    The high-frequency noise is significantly reduced, leaving the smooth sine wave intact.

Applications

  • Audio Processing: Removing noise from audio recordings.
  • Communications: Filtering out unwanted frequency components from signals in wireless communication systems.
  • Control Systems: Smoothing sensor data to improve system stability.

Low-pass filters are widely used to enhance signal quality in numerous real-world applications, and the Butterworth filter provides a good balance between performance and simplicity.

Optimization Problems with SciPy

Optimization Problems with SciPy

$SciPy$ provides powerful optimization routines in the scipy.optimize module to solve various optimization problems.

These include finding the minimum of a function, solving equations, and linear programming.

One commonly used method is constrained optimization, where the goal is to minimize or maximize a function subject to constraints.

Example Problem: Constrained Optimization (Minimizing a Nonlinear Function)

Let’s consider an example of a constrained optimization problem, where we minimize a nonlinear function subject to some constraints.

Problem

Minimize the following objective function:

$$
f(x, y) = x^2 + y^2
$$

subject to the constraints:

  1. $( x + y = 1 )$ (Equality constraint)
  2. $( x \geq 0 )$ and $( y \geq 0 )$ (Inequality constraints)

This is a simple quadratic function, and the constraints limit the feasible region to part of the first quadrant where the variables are non-negative and sum to $1$.

Approach

We will use $SciPy$’s minimize function from the optimize module, specifying the constraints and bounds.

Code Implementation

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
import numpy as np
from scipy.optimize import minimize

# Objective function to minimize
def objective(x):
return x[0]**2 + x[1]**2 # f(x, y) = x^2 + y^2

# Equality constraint: x + y = 1
def constraint_eq(x):
return x[0] + x[1] - 1

# Initial guess for x and y
x0 = [0.5, 0.5]

# Define the constraints in the format required by minimize()
constraints = {'type': 'eq', 'fun': constraint_eq}

# Define bounds for each variable: 0 <= x <= inf, 0 <= y <= inf
bounds = [(0, None), (0, None)]

# Perform the minimization
result = minimize(objective, x0, method='SLSQP', bounds=bounds, constraints=constraints)

# Print the result
print("Optimal solution:", result.x)
print("Objective function value at the optimal solution:", result.fun)

Explanation

  1. Objective Function:

    • The function we want to minimize is $( f(x, y) = x^2 + y^2 )$, which is a quadratic function.
      This is represented in Python as objective(x), where x[0] is $( x )$ and x[1] is $( y )$.
  2. Constraints:

    • The equality constraint is $( x + y = 1 )$, which is enforced by constraint_eq(x). This function must return $0$ for the constraint to be satisfied (i.e., $( x + y - 1 = 0 )$).
  3. Bounds:

    • The variables $( x )$ and $( y )$ must be non-negative, represented by the bounds [(0, None), (0, None)].
  4. Initial Guess:

    • The solver needs an initial guess for the variables.
      We use $( x_0 = [0.5, 0.5] )$, which is a reasonable starting point for the algorithm.
  5. Optimization Method:

    • We use the Sequential Least Squares Programming (SLSQP) algorithm, which is appropriate for constrained optimization problems.
  6. Result:

    • The result includes the optimal values for $( x )$ and $( y )$ that minimize the objective function while satisfying the constraints.

Output

1
2
Optimal solution: [0.5 0.5]
Objective function value at the optimal solution: 0.5
  • Optimal solution: The solver will provide the optimal values for $( x )$ and $( y )$, which should satisfy both the constraint $( x + y = 1 )$ and the non-negativity conditions $( x \geq 0 )$ and $( y \geq 0 )$.
  • Objective function value: The value of $( f(x, y) = x^2 + y^2 )$ at the optimal solution.

For this specific problem, the optimal solution is expected to be $( x = 0.5 )$ and $( y = 0.5 )$, with an objective function value of:

$$
f(0.5, 0.5) = 0.5^2 + 0.5^2 = 0.5
$$

Applications

This type of constrained optimization is widely used in areas such as:

  • Resource allocation: Optimizing the allocation of limited resources (e.g., time, money, materials).
  • Engineering design: Minimizing energy consumption, costs, or weight while ensuring the design meets all performance constraints.
  • Economics: Finding optimal production quantities subject to cost or budget constraints.