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:
- Labor hours: You have $100$ hours of labor available.
- Raw materials: You have $80$ units of raw material available.
- Profit: Product $A$ gives a profit of $$30$ per unit, and product $B$ gives a profit of $$20$ per unit.
- 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:
- Labor constraint: $( 4x_A + 2x_B \leq 100 )$
- Raw material constraint: $( 2x_A + 4x_B \leq 80 )$
- 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:
Define the problem:
- Maximize profit.
- Satisfy labor and raw material constraints.
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).
Fitness function:
The fitness function calculates the profit but applies penalties if constraints are violated.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 | import random |
Explanation:
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$.
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.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.
- Crossover: The
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.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.