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.