Analyzing an Electrical Circuit with NetworkX

Analyzing an Electrical Circuit with NetworkX

In Electrical Circuit Analysis, components such as resistors, capacitors, and inductors are connected in a network to control the flow of electrical current.

This network can be modeled using a graph, where the nodes represent connection points (or junctions), and the edges represent the components (resistors, capacitors, etc.) between the junctions.

Problem Definition

We are given a simple circuit with the following components and connections:

  • Nodes represent junctions where multiple components are connected.
  • Edges represent electrical components (resistors) with specified resistance values.

Objective:

  1. Build a circuit graph where nodes represent junctions and edges represent resistors.
  2. Calculate the equivalent resistance between two points using series and parallel combinations of resistors.
  3. Visualize the circuit using $NetworkX$.

Circuit Layout:

  • Node $1$ connects to Node $2$ through a $5$-ohm resistor.
  • Node $2$ connects to Node $3$ through a $10$-ohm resistor.
  • Node $3$ connects to Node $4$ through a $20$-ohm resistor.
  • Node $2$ connects to Node $4$ through a parallel path with a $15$-ohm resistor.

Approach

We’ll use $NetworkX$ to model this electrical circuit and calculate the equivalent resistance between Node $1$ and Node $4$.

Python 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
import networkx as nx
import matplotlib.pyplot as plt

# Create a graph for the electrical circuit
G = nx.Graph()

# Add edges with resistance values (resistors between nodes)
G.add_edge(1, 2, resistance=5)  # 5 ohms between Node 1 and Node 2
G.add_edge(2, 3, resistance=10)  # 10 ohms between Node 2 and Node 3
G.add_edge(3, 4, resistance=20)  # 20 ohms between Node 3 and Node 4
G.add_edge(2, 4, resistance=15)  # 15 ohms between Node 2 and Node 4 (parallel path)

# Visualize the circuit
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightgreen', edge_color='blue', node_size=2000, font_size=12, font_weight='bold')
labels = nx.get_edge_attributes(G, 'resistance')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.title("Electrical Circuit Graph")
plt.show()

# Calculate the equivalent resistance using series and parallel rules
# Helper function to compute equivalent resistance in parallel
def parallel_resistance(*resistances):
    return 1 / sum(1 / r for r in resistances)

# Step-by-step calculation of the equivalent resistance
R_23 = G[2][3]['resistance']  # Resistor between Node 2 and 3 (10 ohms)
R_34 = G[3][4]['resistance']  # Resistor between Node 3 and 4 (20 ohms)
R_24 = G[2][4]['resistance']  # Resistor between Node 2 and 4 (15 ohms)

# Resistors R_34 and R_24 are in parallel
R_parallel = parallel_resistance(R_34, R_24)

# The equivalent resistance from Node 1 to Node 4 is the series combination
R_12 = G[1][2]['resistance']  # Resistor between Node 1 and 2 (5 ohms)
R_eq = R_12 + R_parallel  # Series combination

# Output the equivalent resistance
print(f"Equivalent resistance between Node 1 and Node 4: {R_eq:.2f} ohms")

Explanation of the Code

  1. Graph Construction:

    • Each node represents a junction in the circuit.
    • Each edge represents a resistor, with the resistance stored as an edge attribute.

  2. Visualization:

    • We use nx.spring_layout() to visually represent the circuit graph, showing the connections between nodes and labeling each edge with its resistance value.

  3. Resistance Calculations:

    • For resistors in series, the total resistance is the sum of individual resistances.
    • For resistors in parallel, we use the formula $( R_{eq} = \frac{1}{\frac{1}{R_1} + \frac{1}{R_2} + \dots} )$.
    • In this case, the resistors between Nodes $2$ and $4$ ($20$ ohms and $15$ ohms) are in parallel, so we calculate their equivalent resistance first, then add it to the resistance between Nodes $1$ and $2$ ($5$ ohms) to get the total resistance.

Explanation of Results

  • The visualization shows the circuit with its components labeled by resistance values.
  • The equivalent resistance is calculated step by step:
    • The parallel combination of the $20$-ohm and $15$-ohm resistors gives:
      $$
      R_{parallel} = \frac{1}{\frac{1}{20} + \frac{1}{15}} \approx 8.57 , \text{ohms}
      $$
    • The total resistance between Node $1$ and Node $4$ is:
      $$
      R_{eq} = 5 , \text{ohms (series with the parallel combination)} + 8.57 , \text{ohms} = 13.57 , \text{ohms}
      $$
  • Therefore, the equivalent resistance between Node 1 and Node 4 is approximately 13.57 ohms.

Example Output

Electrical Relevance

In real-world electrical circuits, it is important to calculate the equivalent resistance to determine the total current flow and the voltage distribution in the circuit.

$NetworkX$ provides an excellent tool for modeling and analyzing such circuits by treating them as graphs, where components (like resistors) can be easily analyzed for their contributions to the overall circuit behavior.

Conclusion

This example demonstrates how to use $NetworkX$ to model and analyze an electrical circuit.

The approach can be extended to more complex circuits involving capacitors, inductors, and more intricate resistor networks.

This graph-based method provides a flexible and scalable way to understand and compute circuit properties, such as equivalent resistance.

Protein-Protein Interaction (PPI) Network Analysis

Protein-Protein Interaction (PPI) Network Analysis

Biological Network Analysis is a powerful method used to understand the relationships and interactions among biological entities.

One common example is the Protein-Protein Interaction (PPI) Network, where proteins interact with each other to carry out various biological functions.

Problem Definition

We are given a set of proteins and their known interactions. The goal is to:

  1. Identify important proteins (hubs) in the network.
  2. Find clusters of proteins that work together in specific biological pathways.
  3. Detect the shortest interaction paths between two proteins, which can indicate how quickly biological signals can propagate between them.

Approach

We will use NetworkX to:

  1. Build a graph where nodes represent proteins, and edges represent interactions between them.
  2. Analyze the network to find important proteins using centrality measures.
  3. Cluster the network using community detection to find groups of proteins working together.
  4. Find the shortest path between two proteins to understand how they communicate.

Python 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
import networkx as nx
import matplotlib.pyplot as plt

# Sample data: protein-protein interactions
ppi_data = [
    ('ProteinA', 'ProteinB'),
    ('ProteinA', 'ProteinC'),
    ('ProteinB', 'ProteinD'),
    ('ProteinC', 'ProteinE'),
    ('ProteinD', 'ProteinE'),
    ('ProteinE', 'ProteinF'),
    ('ProteinF', 'ProteinG'),
    ('ProteinG', 'ProteinH'),
    ('ProteinH', 'ProteinA'),
    ('ProteinD', 'ProteinF')
]

# Create a graph representing the PPI network
G = nx.Graph()

# Add edges (protein-protein interactions)
G.add_edges_from(ppi_data)

# 1. Visualize the network
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='lightblue', edge_color='gray', node_size=2000, font_size=10, font_weight='bold')
plt.title("Protein-Protein Interaction Network")
plt.show()

# 2. Find the most important proteins (based on degree centrality)
degree_centrality = nx.degree_centrality(G)
most_important_proteins = sorted(degree_centrality, key=degree_centrality.get, reverse=True)
print("Proteins ranked by importance (degree centrality):")
for protein in most_important_proteins:
    print(f"{protein}: {degree_centrality[protein]:.2f}")

# 3. Community detection (finding clusters of proteins)
from networkx.algorithms.community import greedy_modularity_communities

communities = list(greedy_modularity_communities(G))
print("\nCommunities (clusters of interacting proteins):")
for i, community in enumerate(communities, 1):
    print(f"Community {i}: {sorted(community)}")

# 4. Shortest path between two proteins
protein_start = 'ProteinA'
protein_end = 'ProteinF'
shortest_path = nx.shortest_path(G, source=protein_start, target=protein_end)
print(f"\nShortest path from {protein_start} to {protein_end}: {shortest_path}")

Explanation

  1. Graph Construction:

    • We create a graph where each node represents a protein, and each edge represents an interaction between two proteins.
    • The edges indicate that two proteins interact and may participate in the same biological function.

  2. Visualizing the Network:

    • We use $NetworkX$’s draw() function to visualize the network of proteins.
      This gives us a clear overview of how proteins are connected.
    • Proteins that are highly connected (with many edges) may play more important roles in the biological system.

  3. Finding Important Proteins:

    • We compute degree centrality, which measures the number of direct connections a protein has.
      Proteins with higher centrality scores are likely to be hubs and may be crucial for the biological processes.
    • In this example, proteins like ProteinE, ProteinD, and ProteinF might be highly connected and thus important for signal transduction.

  4. Community Detection:

    • Using greedy modularity communities, we group proteins into clusters.
      These clusters represent proteins that are more likely to be involved in the same biological processes or pathways.
    • For example, ProteinA, ProteinB, and ProteinC might belong to the same functional pathway.

  5. Shortest Path Between Proteins:

    • We use the shortest path algorithm to find the shortest sequence of interactions between two proteins.
      This can represent how a biological signal propagates through the network.
    • For example, the shortest path from ProteinA to ProteinF might reveal how a signal passes through a series of interactions from one protein to another.

Example Output

The output shows the results of a Protein-Protein Interaction (PPI) Network Analysis using $NetworkX$. Here’s a summary of the results:

1. Protein-Protein Interaction Network Visualization:

  • The network graph shows proteins (ProteinA, ProteinB, etc.) as nodes, and their interactions as edges (lines between nodes).
    This represents how different proteins interact with one another in a biological system.

2. Proteins Ranked by Importance (Degree Centrality):

  • The ranking of proteins is based on their degree centrality, which indicates how many other proteins they interact with:
    • ProteinA, ProteinD, and ProteinF have the highest centrality ($0.43$), meaning they are highly connected and likely important in the network.
    • ProteinB, ProteinC, ProteinG, and ProteinH have lower centrality scores ($0.29$), indicating fewer connections.

3. Communities of Interacting Proteins:

  • The network is divided into three clusters (or communities):
    • Community 1: ProteinC, ProteinD, ProteinE, ProteinF, and ProteinA, suggesting these proteins interact closely and may participate in a common biological function.
    • Community 2: ProteinA and ProteinB, indicating that these two proteins have a special relationship or function.
    • Community 3: ProteinG and ProteinH, forming another distinct interaction pair.

4. Shortest Path from ProteinA to ProteinF:

  • The shortest interaction path between ProteinA and ProteinF is: ['ProteinA', 'ProteinB', 'ProteinD', 'ProteinF'].
  • This indicates how signals or interactions might propagate through the network between these two proteins.

In conclusion, this analysis identifies important proteins, clusters of interacting proteins, and the shortest path between specific proteins, providing valuable insights into the structure and function of the biological network.

Biological Relevance

  • In a real-world PPI network, discovering central proteins (hubs) is crucial because they may be involved in key biological processes such as signal transduction, cellular regulation, or metabolism.
  • Community detection is useful for identifying groups of proteins that are likely to function together in pathways or biological modules.
  • Shortest path analysis helps biologists understand how proteins communicate or influence each other, which is important for designing experiments or drugs that target specific pathways.

Conclusion

This example demonstrates how to analyze a protein-protein interaction network using $NetworkX$.

The analysis helps in identifying important proteins, detecting functional clusters, and understanding the propagation of biological signals between proteins.

Such an approach is widely used in computational biology to study disease mechanisms, drug targets, and cellular functions.

Building a Recommendation System Using NetworkX

Building a Recommendation System Using NetworkX

Let’s create a recommendation system that suggests new products to users based on their past interactions with products and the preferences of other similar users.

This type of system can be found in e-commerce platforms like Amazon or content platforms like Netflix.

Problem Definition

Imagine a small e-commerce platform where users have purchased or liked certain products.
We want to recommend new products to a user based on:

  1. Products that similar users liked or purchased.
  2. Products that are connected to the user through a series of recommendations or interactions.

We will model the system as a bipartite graph where:

  • One set of nodes represents users.
  • The other set of nodes represents products.
  • An edge between a user and a product indicates that the user has purchased or liked that product.

Objective

Our goal is to recommend new products to a user by:

  1. Identifying users who are similar in behavior to the target user.
  2. Finding products that the similar users have interacted with, but the target user has not yet interacted with.

Graph Model

  • Nodes: Users and products.
  • Edges: A connection between a user and a product (representing an interaction such as a purchase or a like).

Approach

We will use NetworkX to create the bipartite graph and implement a recommendation system using a simple collaborative filtering approach:

  1. Build a bipartite graph of users and products.
  2. Compute neighbors of the target user (users who interacted with similar products).
  3. Recommend products that are liked by those similar users but not yet interacted with by the target user.

Python 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 networkx as nx
from networkx.algorithms import bipartite

# Sample data: Users and their interactions with products (edges between users and products)
user_product_interactions = [
    ('User1', 'Product1'), ('User1', 'Product2'),
    ('User2', 'Product1'), ('User2', 'Product3'),
    ('User3', 'Product2'), ('User3', 'Product3'), ('User3', 'Product4'),
    ('User4', 'Product3'), ('User4', 'Product5'),
    ('User5', 'Product1'), ('User5', 'Product5'),
]

# Create a bipartite graph
B = nx.Graph()
# Add edges (user-product interactions)
B.add_edges_from(user_product_interactions)

# Set of users and products
users = {n for n in B if n.startswith('User')}
products = set(B) - users

# Function to recommend products for a specific user based on similar users
def recommend_products(target_user, B, users, products):
    # Find the neighbors of the target user (i.e., products they interacted with)
    target_user_products = set(B.neighbors(target_user))
    
    # Find users who have interacted with the same products
    similar_users = set()
    for product in target_user_products:
        similar_users.update(B.neighbors(product))
    similar_users.discard(target_user)  # Remove the target user from the list
    
    # Find products that these similar users interacted with, but the target user hasn't
    recommended_products = set()
    for similar_user in similar_users:
        similar_user_products = set(B.neighbors(similar_user))
        recommended_products.update(similar_user_products - target_user_products)
    
    return recommended_products

# Example: Recommend products for User1
target_user = 'User1'
recommended_products = recommend_products(target_user, B, users, products)

print(f"Recommended products for {target_user}: {recommended_products}")

Explanation

  1. Data Structure:

    • We model the system as a bipartite graph where users are connected to the products they have interacted with.
    • The interactions are represented as edges between the user and product nodes.

  2. Recommendation Algorithm:

    • First, we find all the products that the target user has already interacted with.
    • Then, we identify similar users by finding those who have interacted with the same products.
    • Finally, we recommend the products that these similar users have interacted with but the target user has not.

Example Output

Let’s say we want to recommend products to User1. The code will output:

1
Recommended products for User1: {'Product3', 'Product5', 'Product4'}

This means that User1 hasn’t interacted with Product3, Product4, or Product5, but similar users (such as User2 and User3) have, so these products are good candidates for recommendation.

Explanation of Results

  • User1 has interacted with Product1 and Product2.
  • User2 also interacted with Product1 and liked Product3, making Product3 a candidate for recommendation.
  • User3 liked Product2 (which User1 also interacted with), but User3 also interacted with Product4, which could be recommended to User1.
  • User4 interacted with Product3 and Product5, further suggesting that Product3 and Product5 are good recommendations for User1.

Enhancements

This is a basic collaborative filtering approach. More advanced techniques can be used to:

  • Weight recommendations: Products that multiple similar users interacted with should have higher priority.
  • Use rating or feedback: If users provide ratings or reviews, this information can further refine the recommendation.
  • Matrix factorization: Use machine learning techniques like matrix factorization to improve recommendations by discovering latent factors.

Real-World Application

Recommendation systems like this are commonly used in:

  • E-commerce platforms: Amazon, Alibaba, etc., to recommend products to users based on the preferences of other users.
  • Streaming services: Netflix, YouTube, to suggest videos or movies based on user viewing history.
  • Social networks: Facebook, Twitter, to recommend friends, pages, or groups.

Conclusion

This example demonstrates how to build a basic recommendation system using $NetworkX$.

The system leverages user-product interactions to suggest new products for a given user based on the behavior of other similar users.

$NetworkX$’s ability to model and analyze complex graphs makes it a valuable tool for implementing such systems in various domains like e-commerce, social networks, and media platforms.

Solving Electromagnetic Wave Modes in a Rectangular Cavity

Solving Electromagnetic Wave Modes in a Rectangular Cavity

Let’s consider a different advanced physics problem: solving Maxwell’s equations for electromagnetic wave propagation in a cavity using $Python$.

Problem: Solving Maxwell’s Equations for Electromagnetic Waves in a Rectangular Cavity

Maxwell’s equations describe the behavior of electric and magnetic fields.

In this problem, we will focus on the propagation of electromagnetic waves in a rectangular cavity.

These cavities are important in applications like microwave ovens, waveguides, and resonant cavities used in particle accelerators.

Maxwell’s Equations

Maxwell’s equations in free space (with no charges or currents) are:

  1. $( \nabla \cdot \mathbf{E} = 0 )$
  2. $( \nabla \cdot \mathbf{B} = 0 )$
  3. $( \nabla \times \mathbf{E} = -\frac{\partial \mathbf{B}}{\partial t} )$
  4. $( \nabla \times \mathbf{B} = \mu_0 \epsilon_0 \frac{\partial \mathbf{E}}{\partial t} )$

Where:

  • $( \mathbf{E} )$ is the electric field.
  • $( \mathbf{B} )$ is the magnetic field.
  • $( \mu_0 )$ is the permeability of free space.
  • $( \epsilon_0 )$ is the permittivity of free space.

Problem Definition

We want to find the electric and magnetic field modes inside a rectangular cavity with perfectly conducting walls.
The boundary conditions for a perfectly conducting cavity are:

  • The tangential electric field $( \mathbf{E}_t )$ at the walls must be zero.

The solution to Maxwell’s equations in a rectangular cavity can be written as standing wave solutions, and we are interested in finding the resonant modes (frequencies) and the corresponding field distributions.

For a rectangular cavity with dimensions $( a \times b \times d )$, the resonant frequencies $( f_{m,n,p} )$ are given by:

$$
f_{m,n,p} = \frac{c}{2} \sqrt{\left(\frac{m}{a}\right)^2 + \left(\frac{n}{b}\right)^2 + \left(\frac{p}{d}\right)^2}
$$

Where:

  • $( m, n, p )$ are the mode numbers (positive integers).
  • $( c )$ is the speed of light.
  • $( a, b, d )$ are the cavity dimensions.

Objective

  1. Find the resonant frequencies $( f_{m,n,p} )$ for a rectangular cavity with given dimensions.
  2. Visualize the electric field distribution for some of the modes.

Python Code Implementation

We will use $Python$ to calculate the resonant frequencies for different modes and visualize the electric field distribution for the fundamental mode.

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
import numpy as np
import matplotlib.pyplot as plt

# Constants
c = 3.0e8  # Speed of light in vacuum (m/s)

# Cavity dimensions (in meters)
a = 0.1  # Length in x-direction
b = 0.05  # Length in y-direction
d = 0.02  # Length in z-direction

# Function to compute the resonant frequency for a given mode (m, n, p)
def resonant_frequency(m, n, p, a, b, d, c):
    return (c / 2) * np.sqrt((m/a)**2 + (n/b)**2 + (p/d)**2)

# Calculate resonant frequencies for a few modes (m, n, p)
modes = [(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1), (2, 1, 0), (1, 2, 1)]
frequencies = [resonant_frequency(m, n, p, a, b, d, c) for m, n, p in modes]

# Print the resonant frequencies
for mode, freq in zip(modes, frequencies):
    print(f"Mode {mode}: Resonant frequency = {freq/1e9:.2f} GHz")

# Visualizing the electric field for the fundamental mode (m=1, n=0, p=0)
# Assuming the electric field is sinusoidal along the x-axis
x = np.linspace(0, a, 100)
y = np.linspace(0, b, 100)
X, Y = np.meshgrid(x, y)

# Electric field distribution for the (1,0,0) mode
E_x = np.sin(np.pi * X / a)

plt.figure(figsize=(8, 6))
plt.contourf(X, Y, E_x, cmap='RdBu', levels=50)
plt.colorbar(label="Electric Field Strength")
plt.title("Electric Field Distribution for Mode (1,0,0)")
plt.xlabel("x (m)")
plt.ylabel("y (m)")
plt.show()

Explanation of the Code

  1. Resonant Frequencies:

    • The function resonant_frequency calculates the resonant frequency for a given mode $( (m, n, p) )$ using the formula for the rectangular cavity.
    • We calculate the resonant frequencies for a few different modes, including the fundamental mode $( (1, 0, 0) )$, where the field is sinusoidal along the $( x )$-axis.

  2. Field Visualization:

    • For the fundamental mode $( (1, 0, 0) )$, we assume the electric field has a sinusoidal variation along the $( x )$-axis.
      The electric field is zero at the conducting walls.
    • We use matplotlib to visualize the field distribution inside the cavity.

Results

  1. Resonant Frequencies:
    The output will show the resonant frequencies for various modes.
    These frequencies are in the GHz range, which is typical for microwave cavities.

    Example output:

  1. Electric Field Distribution:
    The plot shows the electric field distribution for the fundamental mode $( (1, 0, 0) )$, with a sinusoidal variation along the $( x )$-axis.
    The field is zero at the cavity boundaries, as expected for a mode in a perfectly conducting cavity.

Real-World Applications

  1. Microwave Cavities: Resonant cavities are used in microwave ovens and accelerators to confine and amplify electromagnetic waves.
  2. Waveguides: The same principles are used to design waveguides that carry electromagnetic waves over long distances with minimal loss.
  3. Quantum Computing: Superconducting resonant cavities are critical in designing qubits for quantum computers.

Conclusion

This example demonstrates how to solve an advanced physics problem involving Maxwell’s equations for electromagnetic waves in a rectangular cavity.

Using $Python$, we computed the resonant frequencies for different modes and visualized the electric field distribution for the fundamental mode.

This method is essential for understanding and designing resonant cavities used in a wide range of practical applications, from microwave technologies to quantum devices.

Optimizing Building Shape with DEAP

Optimizing Building Shape with DEAP

Let’s tackle an optimization problem where we optimize the shape of a building to balance structural efficiency and aesthetic design using $DEAP$.

This type of problem is known as architectural form optimization and is crucial in fields like sustainable design and engineering.

Problem: Shape Optimization of a Building

The goal is to optimize the shape of a building to minimize the material cost and maximize structural efficiency, while also adhering to aesthetic constraints.

The building’s shape is represented by a set of geometric parameters, such as the dimensions of floors and curvature of the walls.

Objective

We aim to balance the following objectives:

  1. Structural efficiency: The building must be stable, with minimal stress in critical areas.
  2. Material cost: The total amount of building material used should be minimized.
  3. Aesthetic constraints: The building should maintain a desired aesthetic, such as symmetry or a specified curvature.

Problem Definition

We will consider a simple tower with the following shape variables:

  1. Height $( h )$ (ranging between $50$ to $200$ meters).
  2. Base radius $( r_b )$ (ranging between $10$ to $50$ meters).
  3. Top radius $( r_t )$ (ranging between $5$ to $30$ meters).

The building’s structure will be a tapering cylindrical shape, where the top radius might be smaller than the base radius. The cost function incorporates structural stress and material usage.

Total Material Volume (Cost):

The material cost is proportional to the volume of the structure:

$$
V(h, r_b, r_t) = \pi \times h \times \frac{r_b^2 + r_b r_t + r_t^2}{3}
$$

Structural Efficiency:

We define structural efficiency as inversely proportional to the maximum stress in the building.
The stress depends on the height, base, and top radius:

$$
S(h, r_b, r_t) = \frac{h}{r_b + r_t}
$$

The objective is to minimize the material volume while maintaining structural efficiency by ensuring that the stress $( S )$ does not exceed a given threshold.

Aesthetic Constraint:

To maintain symmetry and aesthetic appeal, the base and top radii must be proportionally related, and a penalty is applied if the relationship deviates too much from a desired ratio $( r_b/r_t \approx 2 )$.

Multi-Objective Optimization:

We want to:

  1. Minimize the material volume $( V(h, r_b, r_t) )$,
  2. Maximize the structural efficiency $( \frac{1}{S(h, r_b, r_t)} )$,
  3. Respect the aesthetic constraint $( \frac{r_b}{r_t} \approx 2 )$.

DEAP Implementation

We will use $DEAP$ to solve this multi-objective optimization problem.

Each individual will represent a set of parameters $( (h, r_b, r_t) )$, and $DEAP$ will evolve the population over generations to find the optimal balance between structural efficiency, material cost, and aesthetic constraints.

Here’s how we can model this 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Define the fitness function (multi-objective)
def fitness_function(individual):
    h, r_b, r_t = individual
    # Volume of the building (minimize)
    volume = np.pi * h * (r_b**2 + r_b * r_t + r_t**2) / 3
    # Structural stress (minimize stress, so maximize its inverse)
    stress = h / (r_b + r_t)
    structural_efficiency = 1.0 / stress
    # Aesthetic constraint (penalty for deviation from the ratio r_b/r_t ≈ 2)
    aesthetic_penalty = abs((r_b / r_t) - 2)
    return volume, -structural_efficiency + aesthetic_penalty

# Set bounds for the variables (height, base radius, top radius)
BOUND_LOW = [50, 10, 5]
BOUND_UP = [200, 50, 30]

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

toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, 50, 200)
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=10, indpb=0.2)
toolbox.register("select", tools.selNSGA2)  # Use NSGA-II for multi-objective optimization

# Custom bounds checking function
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]

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

# Apply bounds after crossover and mutation
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)
    
    # Evolutionary algorithm with bounds checking
    for gen in range(generations):
        offspring = toolbox.select(pop, len(pop))
        offspring = list(map(toolbox.clone, offspring))

        # Apply crossover and mutation
        for child1, child2 in zip(offspring[::2], offspring[1::2]):
            if random.random() < cx_prob:
                toolbox.mate(child1, child2)
                checkBounds(child1)
                checkBounds(child2)
                del child1.fitness.values
                del child2.fitness.values

        for mutant in offspring:
            if random.random() < mut_prob:
                toolbox.mutate(mutant)
                checkBounds(mutant)
                del mutant.fitness.values

        # Evaluate individuals with invalid fitness
        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

        # Replace the old population with offspring
        pop[:] = offspring

        # Gather and print statistics
        hof.update(pop)
        record = stats.compile(pop)
        print(f"Generation {gen}: {record}")

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

Explanation of the Code

  1. Fitness Function: We define the fitness function to minimize the building’s material volume and maximize its structural efficiency.
    We also include an aesthetic penalty for deviating from the desired ratio between the base and top radii.
  2. Multi-Objective Optimization: Since this is a multi-objective problem (minimizing volume while maximizing efficiency), we use the NSGA-II algorithm (selNSGA2) to handle the trade-offs between conflicting objectives.
  3. Constraints: Bounds are enforced on the height, base radius, and top radius to ensure the building remains within practical limits.
  4. Crossover and Mutation: The algorithm uses blend crossover (cxBlend) and Gaussian mutation (mutGaussian) to evolve the population.
    These operators modify the building parameters slightly in each generation.
  5. Evolutionary Process: Over $200$ generations, the algorithm evolves the population, selecting individuals based on their fitness in both objectives (volume and structural efficiency).

Running the Algorithm

When you run the genetic algorithm, $DEAP$ will evolve the population of building designs over generations.

The algorithm will return the best-performing design (the individual with the optimal combination of height, base radius, and top radius), balancing material cost, structural efficiency, and aesthetic constraints.

Real-World Applications

  1. Skyscraper Design: Optimizing the structural form of tall buildings for both cost-efficiency and stability.
  2. Sustainable Architecture: Minimizing the environmental impact of construction by reducing material use while maintaining aesthetic integrity.
  3. Bridge Design: Optimizing the shape of bridges to ensure they can support loads efficiently without using excessive materials.

Conclusion

This example demonstrates how $DEAP$ can be used for multi-objective optimization in architectural design, balancing structural efficiency, cost, and aesthetics.

By evolving the shape of the building over generations, the genetic algorithm helps identify an optimal design that satisfies multiple conflicting objectives.

Output

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
8      66        104.533    86.682      110    
9      60        106.674    90.7454     110    
10     64        108.301    102.908     110    
11     62        108.925    92.2664     110    
12     62        109.677    96.9721     110    
13     56        109.771    102.924     110    
14     56        109.285    84.0149     110    
15     65        109.414    90.0117     110    
16     56        109.357    95.1722     110    
17     56        109.342    85.5902     110    
18     58        109.865    105.307     110    
19     53        109.69     88.9731     110    
20     61        109.469    95.8403     110    
21     64        109.958    107.5       110    
22     63        109.67     87.5967     110    
23     56        109.629    92.1763     110    
24     65        109.545    85.6428     110    
25     72        109.739    93.9295     110    
26     53        109.845    102.354     110    
27     56        109.65     100.067     110    
28     68        109.394    85.0092     110    
29     63        109.1      81.3666     110    
30     49        109.887    102.778     110    
31     68        109.54     89.2593     110    
32     67        109.845    100.159     110    
33     59        109.464    88.0685     110    
34     62        109.652    100.051     110    
35     63        109.398    95.8296     110    
36     56        109.734    96.4426     110    
37     62        109.999    109.915     110    
38     63        109.203    78.4034     110    
39     61        109.808    96.6963     110    
40     57        109.668    101.347     110    
41     63        109.872    107.208     110    
42     61        109.653    97.3602     110    
43     54        109.733    97.9184     110    
44     47        109.461    87.6114     110    
45     55        109.545    95.4545     110    
46     49        109.942    106.151     110    
47     60        109.823    98.3643     110    
48     53        109.587    96.8339     110    
49     57        109.353    90.8686     110    
50     64        109.675    93.9186     110    
51     58        109.565    90.6717     110    
52     76        109.601    97.3458     110    
53     53        109.642    91.4243     110    
54     64        109.417    93.5573     110    
55     60        109.766    99.543      110    
56     50        109.572    90.7425     110    
57     65        109.86     98.1754     110    
58     59        109.617    89.4655     110    
59     55        109.805    103.898     110    
60     58        109.668    94.2321     110    
61     57        109.912    101.181     110    
62     64        109.521    97.1337     110    
63     60        109.672    97.3061     110    
64     51        109.646    94.9934     110    
65     62        109.774    97.9661     110    
66     44        109.683    92.1023     110    
67     69        109.404    76.2358     110    
68     62        109.533    80.385      110    
69     45        109.706    100.829     110    
70     62        109.833    102.379     110    
71     51        109.57     86.7019     110    
72     59        109.619    93.0737     110    
73     59        109.696    90.8966     110    
74     57        109.765    92.5364     110    
75     65        109.544    83.7875     110    
76     61        109.884    105.476     110    
77     58        109.503    91.5296     110    
78     57        109.686    95.8519     110    
79     69        109.523    97.5127     110    
80     64        109.629    96.7788     110    
81     63        109.349    85.8037     110    
82     70        109.662    92.9332     110    
83     49        109.545    97.5696     110    
84     60        109.412    94.8316     110    
85     59        109.823    92.2895     110    
86     63        109.833    105.039     110    
87     59        109.535    93.0147     110    
88     60        109.643    96.5255     110    
89     55        109.706    94.9962     110    
90     67        109.206    83.6985     110    
91     48        109.709    98.124      110    
92     58        109.753    101.298     110    
93     61        109.767    101.255     110    
94     64        109.901    105.363     110    
95     56        109.76     98.3865     110    
96     60        109.738    103.642     110    
97     64        109.803    98.8248     110    
98     58        109.666    89.6437     110    
99     54        109.666    95.8321     110    
100    61        109.494    95.486      110    
101    70        109.799    102.967     110    
102    62        109.739    96.9402     110    
103    77        109.744    95.1285     110    
104    55        109.836    102.75      110    
105    57        109.779    99.3039     110    
106    53        109.911    105.227     110    
107    55        109.342    84.6381     110    
108    45        109.846    100.018     110    
109    58        109.971    107.067     110    
110    58        109.298    86.8772     110    
111    56        109.623    100.785     110    
112    53        109.906    105.962     110    
113    54        109.747    100.471     110    
114    66        109.883    98.2764     110    
115    64        109.809    102.77      110    
116    57        109.386    91.1257     110    
117    60        109.796    97.8844     110    
118    59        109.678    86.3709     110    
119    55        109.831    97.5534     110    
120    58        109.741    98.9108     110    
121    57        109.523    99.0968     110    
122    52        109.607    94.825      110    
123    61        109.661    88.0185     110    
124    61        109.837    103.542     110    
125    54        109.643    93.0993     110    
126    59        109.741    99.6697     110    
127    58        109.695    89.2412     110    
128    54        109.622    98.3891     110    
129    49        109.716    97.0653     110    
130    63        109.523    98.014      110    
131    52        109.444    82.8089     110    
132    56        109.718    97.7141     110    
133    73        109.786    105.672     110    
134    59        109.58     94.2797     110    
135    56        109.758    99.9133     110    
136    62        109.707    91.8893     110    
137    68        109.718    97.7743     110    
138    49        109.568    94.7746     110    
139    50        109.557    99.0476     110    
140    63        109.539    97.9216     110    
141    69        109.219    90.5617     110    
142    66        109.706    92.9352     110    
143    48        109.864    103.266     110    
144    65        109.988    108.774     110    
145    49        109.276    92.3438     110    
146    58        109.734    90.2498     110    
147    64        109.842    100.694     110    
148    62        109.648    96.0825     110    
149    56        109.837    103.081     110    
150    56        109.998    109.78      110    
151    55        109.734    93.7204     110    
152    58        109.81     103.322     110    
153    62        109.856    102.386     110    
154    64        109.664    98.9855     110    
155    65        109.701    93.7264     110    
156    70        108.383    82.8439     110    
157    75        109.94     106.813     110    
158    57        109.714    95.7672     110    
159    62        109.714    92.9867     110    
160    66        109.644    100.39      110    
161    54        109.674    96.3835     110    
162    61        109.658    85.0905     110    
163    52        109.751    97.0785     110    
164    55        109.879    102.546     110    
165    67        109.638    91.7032     110    
166    63        109.824    103.369     110    
167    53        109.996    109.668     110    
168    62        109.42     93.4978     110    
169    65        109.597    92.6122     110    
170    60        109.621    98.15       110    
171    68        109.636    87.6776     110    
172    77        109.754    92.5824     110    
173    58        109.789    97.1111     110    
174    62        109.629    100.315     110    
175    54        109.752    100.745     110    
176    62        109.832    103.505     110    
177    57        109.92     106.379     110    
178    59        109.983    108.311     110    
179    61        109.792    103.147     110    
180    56        109.834    103.666     110    
181    59        109.694    96.045      110    
182    67        109.418    93.1862     110    
183    67        109.998    109.839     110    
184    57        109.965    106.474     110    
185    68        109.543    91.7126     110    
186    63        109.413    83.4402     110    
187    65        109.892    104.356     110    
188    60        109.546    92.2867     110    
189    51        109.722    87.5918     110    
190    65        109.593    102.811     110    
191    55        109.83     101.872     110    
192    66        109.792    98.9256     110    
193    47        109.844    103.942     110    
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

The results show the progress of a genetic algorithm over $200$ generations.

Here’s a brief summary:

  • Initial Generation (0): The population starts with an average fitness of around $30.2$, and the best individual has a fitness of about $84.9$.
  • Generation 1-5: The average fitness steadily increases from $45.4$ to $90.9$.
    The maximum fitness improves, reaching values above $100$.
  • Generations 6-20: The average fitness continues to increase and stabilizes around $109$, with the best fitness consistently at $110$.
  • Generations 21-200: The algorithm converges, maintaining a maximum fitness of $110$ in almost every generation.

The best individual found has a fitness of 110.0, indicating an optimal solution in this context.

Solving the Quadratic Assignment Problem with DEAP

Solving the Quadratic Assignment Problem with DEAP

Let’s tackle a challenging combinatorial optimization problem, specifically the Quadratic Assignment Problem ($QAP$).

This is a classic problem in combinatorial optimization, known for its complexity and difficulty.

Problem: Quadratic Assignment Problem (QAP)

The $QAP$ models scenarios where a set of facilities needs to be assigned to a set of locations, and the cost depends on both the flow between facilities and the distance between locations.

The goal is to minimize the total cost of assignment.

Problem Definition

You are given:

  1. n facilities and n locations.
  2. A flow matrix $( F \in \mathbb{R}^{n \times n} )$ where $( F[i][j] )$ is the flow between facility $( i )$ and facility $( j )$.
  3. A distance matrix $( D \in \mathbb{R}^{n \times n} )$ where $( D[i][j] )$ is the distance between location $( i )$ and location $( j )$.

The objective is to find a permutation $( \pi )$ of $( {1, 2, …, n} )$ that assigns each facility to a location such that the total cost is minimized.

The cost function is defined as:

$$
C(\pi) = \sum_{i=1}^{n} \sum_{j=1}^{n} F[i][j] \cdot D[\pi(i)][\pi(j)]
$$

where $( \pi(i) )$ denotes the location assigned to facility $( i )$.

Example Scenario

Imagine you’re optimizing the layout of a factory.

There are multiple machines (facilities) and various spots (locations) where the machines can be placed.

The machines have specific interactions with each other (flow of goods), and the goal is to minimize transportation costs between machines by placing them in optimal spots based on their interactions.

Problem Setup

  1. Objective: Minimize the total cost of assigning facilities to locations.
  2. Constraints:
    • Each facility must be assigned to exactly one location.
    • Each location must host exactly one facility.
  3. Method: Use a Genetic Algorithm (GA) via $DEAP$ to find the optimal assignment of facilities to locations.

DEAP Implementation

We will use $DEAP$ to model this problem as a permutation-based optimization problem, where each individual in the population represents a permutation (assignment of facilities to locations).

Step-by-Step Approach:

  1. Representation: Each individual is a permutation of integers representing the assignment of facilities to locations.
  2. Evaluation: The fitness of an individual is the total cost of the assignment (using the cost function described above).
  3. Crossover and Mutation: Since this is a combinatorial problem, specialized crossover (e.g., partially mapped crossover) and mutation (e.g., swap mutation) operators are used.
  4. Selection: Individuals are selected based on their fitness values for the next generation.

Here’s how to solve the $QAP$ 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
import random
import numpy as np
from deap import base, creator, tools, algorithms

# Define the flow and distance matrices (example with 4 facilities/locations)
flow_matrix = np.array([[0, 3, 2, 2],
                        [3, 0, 1, 4],
                        [2, 1, 0, 5],
                        [2, 4, 5, 0]])

distance_matrix = np.array([[0, 22, 53, 53],
                            [22, 0, 40, 62],
                            [53, 40, 0, 55],
                            [53, 62, 55, 0]])

n = len(flow_matrix)  # Number of facilities and locations

# Define the fitness function (minimize the total cost)
def fitness_function(individual):
    total_cost = 0
    for i in range(n):
        for j in range(n):
            total_cost += flow_matrix[i][j] * distance_matrix[individual[i]][individual[j]]
    return total_cost,

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

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

toolbox.register("evaluate", fitness_function)
toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)

# Algorithm parameters
population_size = 100
generations = 200
cx_prob = 0.7  # 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 (cost): {best_ind.fitness.values[0]}")
    
if __name__ == "__main__":
    main()

Explanation of the Code

  1. Fitness Function: The fitness_function calculates the total cost of assigning facilities to locations based on the flow and distance matrices.
  2. Individual Representation: Each individual is a permutation of the indices $( {0, 1, 2, …, n-1} )$, representing an assignment of facilities to locations.
  3. Crossover: We use partially matched crossover (PMX), which ensures valid permutations after crossover.
  4. Mutation: The mutShuffleIndexes operator randomly swaps the positions of two elements in the permutation, introducing small variations.
  5. Selection: We use tournament selection (selTournament) to select individuals for reproduction.

Running the Algorithm

When you run the genetic algorithm, $DEAP$ will evolve the population over time. The algorithm will keep track of the best solution (the permutation that results in the lowest cost) and report the final best individual and its corresponding cost.

Why This Is Challenging

The Quadratic Assignment Problem is NP-hard, meaning it is computationally difficult to solve optimally for large instances.
The problem’s complexity grows rapidly as the number of facilities increases, due to the factorial number of possible assignments $( n! )$.
This makes it a perfect candidate for metaheuristic approaches like Genetic Algorithms, which can efficiently search large solution spaces.

Real-World Applications

  • Facility Layout Planning: Optimizing the layout of machinery in factories to minimize transportation costs.
  • Data Center Design: Assigning servers to racks in a way that minimizes the cost of communication between servers.
  • Hospital Design: Assigning departments (facilities) to rooms (locations) to minimize the movement of patients, staff, and resources.

This example illustrates how $DEAP$ can be applied to solve complex combinatorial optimization problems using evolutionary algorithms.

Output

gen    nevals    avg        min 
0      100       1611.06    1436
1      73        1582.84    1436
2      85        1546.18    1436
3      64        1501.92    1436
4      71        1476.96    1436
5      79        1467.72    1436
6      81        1463.3     1436
7      70        1441.28    1436
8      75        1451.24    1436
9      70        1454.02    1436
10     64        1449.72    1436
11     79        1464.28    1436
12     68        1457.32    1436
13     73        1464.88    1436
14     69        1451.34    1436
15     69        1450.1     1436
16     76        1458.96    1436
17     79        1457.3     1436
18     78        1456       1436
19     78        1453.9     1436
20     74        1459.32    1436
21     70        1459.76    1436
22     85        1449.28    1436
23     75        1454.76    1436
24     84        1456.92    1436
25     87        1444.84    1436
26     78        1458.72    1436
27     82        1452.36    1436
28     83        1458.68    1436
29     76        1459.28    1436
30     77        1457.08    1436
31     76        1455.68    1436
32     70        1451.78    1436
33     72        1455.36    1436
34     79        1447.14    1436
35     65        1456.52    1436
36     79        1449.48    1436
37     78        1454.12    1436
38     63        1457.16    1436
39     75        1458.6     1436
40     80        1454.94    1436
41     68        1453.44    1436
42     78        1456.34    1436
43     84        1444.42    1436
44     69        1450.64    1436
45     76        1447.82    1436
46     70        1454.64    1436
47     78        1447.74    1436
48     81        1459.22    1436
49     72        1454.06    1436
50     73        1455.82    1436
51     81        1463.56    1436
52     81        1450.4     1436
53     72        1458.44    1436
54     79        1451.44    1436
55     81        1461       1436
56     77        1456.52    1436
57     79        1446.98    1436
58     66        1462.22    1436
59     72        1444.18    1436
60     62        1461.26    1436
61     71        1457.9     1436
62     90        1445.26    1436
63     78        1458.44    1436
64     81        1455.92    1436
65     72        1454.92    1436
66     81        1446.14    1436
67     72        1440.92    1436
68     81        1451.46    1436
69     78        1451.18    1436
70     85        1458.2     1436
71     75        1457       1436
72     74        1452.4     1436
73     77        1456.96    1436
74     71        1445.98    1436
75     83        1457       1436
76     80        1448.7     1436
77     84        1456.38    1436
78     74        1468.24    1436
79     75        1453.36    1436
80     75        1452.34    1436
81     87        1463.12    1436
82     73        1450.84    1436
83     70        1451.94    1436
84     73        1454.76    1436
85     76        1449.5     1436
86     76        1454.96    1436
87     81        1452.58    1436
88     79        1460.16    1436
89     70        1466.76    1436
90     76        1445.5     1436
91     69        1460.82    1436
92     72        1455.46    1436
93     76        1455.96    1436
94     70        1451.98    1436
95     78        1446.96    1436
96     69        1446.6     1436
97     71        1461.48    1436
98     76        1469.44    1436
99     73        1462.18    1436
100    69        1456.28    1436
101    82        1455.74    1436
102    72        1458.5     1436
103    74        1458.44    1436
104    72        1444.3     1436
105    81        1457.88    1436
106    76        1453.9     1436
107    69        1457.82    1436
108    79        1446.86    1436
109    73        1445.1     1436
110    76        1457.14    1436
111    77        1458.52    1436
112    82        1444.12    1436
113    78        1463.36    1436
114    69        1455.58    1436
115    71        1459.42    1436
116    78        1453.62    1436
117    74        1448.24    1436
118    79        1459.58    1436
119    73        1454.62    1436
120    87        1454.76    1436
121    81        1457.76    1436
122    77        1453.88    1436
123    63        1444.22    1436
124    74        1452.24    1436
125    80        1455.92    1436
126    70        1451.1     1436
127    76        1454.48    1436
128    66        1449.18    1436
129    76        1448.24    1436
130    73        1454.5     1436
131    77        1456.12    1436
132    71        1461.96    1436
133    85        1450.24    1436
134    64        1453.94    1436
135    80        1449.18    1436
136    75        1458.52    1436
137    74        1460.74    1436
138    84        1459.9     1436
139    73        1463.12    1436
140    85        1455.72    1436
141    80        1457.12    1436
142    72        1449.9     1436
143    79        1445.54    1436
144    74        1455.94    1436
145    81        1462.96    1436
146    75        1453.94    1436
147    78        1447.94    1436
148    73        1453.86    1436
149    77        1452.66    1436
150    87        1451.82    1436
151    69        1448.36    1436
152    71        1453.52    1436
153    76        1448.16    1436
154    71        1447.4     1436
155    75        1448.06    1436
156    76        1449.04    1436
157    78        1453.22    1436
158    83        1449.98    1436
159    75        1456.72    1436
160    71        1457.84    1436
161    66        1450.36    1436
162    82        1467.6     1436
163    81        1458.16    1436
164    77        1457.58    1436
165    68        1455.12    1436
166    70        1453.78    1436
167    85        1456.32    1436
168    76        1452.36    1436
169    74        1452.36    1436
170    73        1462.48    1436
171    71        1450.2     1436
172    72        1450.98    1436
173    79        1452.08    1436
174    78        1453       1436
175    74        1454.96    1436
176    75        1451.64    1436
177    82        1443.52    1436
178    66        1455.34    1436
179    75        1466.22    1436
180    79        1453.08    1436
181    74        1450.58    1436
182    88        1452.12    1436
183    81        1460.62    1436
184    70        1449.4     1436
185    85        1457.42    1436
186    74        1462.48    1436
187    74        1454.24    1436
188    77        1454.88    1436
189    70        1444.34    1436
190    71        1441       1436
191    76        1454.46    1436
192    70        1453.3     1436
193    81        1452.88    1436
194    77        1445.44    1436
195    69        1450.14    1436
196    78        1462.52    1436
197    72        1460.7     1436
198    61        1449.24    1436
199    69        1449.1     1436
200    76        1455.04    1436
Best individual: [3, 2, 0, 1]
Best fitness (cost): 1436.0

This output represents the progress of the genetic algorithm over $200$ generations as it attempts to solve a combinatorial optimization problem using $DEAP$.

The key columns are:

  • gen: The current generation number.
  • nevals: The number of individuals evaluated in that generation.
  • avg: The average fitness (cost) of the population in that generation.
  • min: The minimum fitness (best solution) found in that generation.

Explanation:

  • The algorithm begins with an initial population, and over time, it refines the solutions.
  • The minimum fitness (cost) starts at 1436 and remains the same throughout the generations, indicating that the optimal solution was found early (possibly in the first generation).
  • The best individual (solution) is [3, 2, 0, 1], with a cost of 1436.

Despite multiple generations and evaluations, no better solution than $1436$ was found after the initial discovery.

The algorithm successfully converged, finding the optimal or near-optimal solution.

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.

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.