What is a Genetic Algorithm?
A Genetic Algorithm (GA) is a method for solving optimization problems by mimicking natural selection.
Solutions to the problem are treated as individuals in a population. Over generations, these individuals evolve
through selection, crossover (reproduction), and mutation, gradually improving the solutions.
Why and When to Use Genetic Algorithms
We use Genetic Algorithms when:
● The problem has a large, complex solution space.
● Traditional methods like brute force or dynamic programming are inefficient.
● We need to optimize multiple objectives or find a "good enough" solution
quickly rather than an exact one.
Examples of real-world applications include:
● Route optimization (e.g., traveling salesman problem).
● Task scheduling (e.g., job-shop scheduling).
● Evolving neural networks or machine learning models.
What is the Task Scheduling Problem?
Task scheduling involves assigning tasks to a group of workers or machines,
where each task has a certain duration. The goal is to distribute tasks in such a
way that no individual is overloaded, minimizing the maximum workload.
How GA Solves Task Scheduling
Steps involved in solving task scheduling with GA:
1. Initial Population: Generate random task assignments for each individual in the
population.
2. Fitness Calculation: For each individual, compute the fitness by calculating the
maximum workload among employees.
3. Selection: Choose the best individuals based on fitness to reproduce.
4. Crossover: Combine the task assignments of two parents to create a child.
5. Mutation: Randomly change the assignment of one or more tasks.
6. Repeat: Continue evolving over several generations until a good solution is found.
Complete Dry Run Example
Let's go through a dry run of solving a task scheduling problem using a Genetic Algorithm.
Problem: Task Scheduling
We have 5 employees and 10 tasks, each with different durations, and we want to minimize the
maximum workload on any one employee.
● Task Durations: [30, 45, 20, 55, 40, 25, 60, 35, 50, 30] (minutes)
● Number of Employees: 5
● Initial Population Size: 5 individuals
● Generations: 3 generations
● Mutation Rate: 20%
Initial Population
Each individual represents a different way to assign tasks to the 5 employees. For example:
● Individual 1: [0, 1, 2, 3, 4, 0, 1, 2, 3, 4] (Task 1 → Employee 0, Task 2 → Employee 1, Task 3
→ Employee 2, ...)
● Individual 2: [4, 3, 2, 1, 0, 4, 3, 2, 1, 0]
● Individual 3: [1, 0, 4, 3, 2, 1, 0, 4, 3, 2]
● Individual 4: [3, 2, 1, 0, 4, 3, 2, 1, 0, 4]
● Individual 5: [0, 2, 1, 3, 4, 0, 1, 3, 4, 0]
Fitness Calculation for Each Individual (Generation 1)
We calculate the total workload for each employee and determine the maximum workload (fitness).
Here’s how it works for each individual:
● Example (Individual 1):[0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
○ Employee 0: Task 1 + Task 6 = 30 + 25 = 55 mins
○ Employee 1: Task 2 + Task 7 = 45 + 60 = 105 mins
○ Employee 2: Task 3 + Task 8 = 20 + 35 = 55 mins
○ Employee 3: Task 4 + Task 9 = 55 + 50 = 105 mins
○ Employee 4: Task 5 + Task 10 = 40 + 30 = 70 mins
Fitness = Max(55, 105, 55, 105, 70) = 105 mins.
Example (Individual 5): [0, 2, 1, 3, 4, 0, 1, 3, 4, 0]
● Employee 0: Task 1 (30) + Task 6 (25) + Task 10 (30) = 85 mins
● Employee 1: Task 3 (20) + Task 7 (60) = 80 mins
● Employee 2: Task 2 (45) = 45 mins
● Employee 3: Task 4 (55) + Task 8 (35) = 90 mins
● Employee 4: Task 5 (40) + Task 9 (50) = 90 mins
Fitness = Max(85, 80, 45, 90, 90) = 90 mins
Selection of Parents
Based on fitness values, we select the two best-performing individuals (with the lowest fitness) to
become parents.
● Best Individual: Individual 5 (Fitness = 90 mins)
● Second Best Individual: Individual 1 (Fitness = 105 mins)
Crossover
We combine the selected parents to create a child by splitting their task assignments at a random
crossover point.
● Parent 1 (Individual 5): [0, 2, 1, 3, 4, 0, 1, 3, 4, 0]
● Parent 2 (Individual 1): [0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
Let’s say the crossover point is 5. The child will take the first 5 tasks from Parent 1 and the rest
from Parent 2.
● Child: [0, 2, 1, 3, 4, 0, 1, 2, 3, 4]
Mutation
We apply a 20% mutation rate. There is a chance that one or more of the tasks will be randomly
reassigned to another employee.
Let’s say Task 3 is mutated, and it is reassigned to Employee 2.
● Mutated Child: [0, 2, 2, 3, 4, 0, 1, 2, 3, 4]
Fitness Calculation After Mutation
We calculate the fitness for the mutated child:
● Employee 0: Task 1 (30) + Task 6 (25) = 55 mins
● Employee 1: Task 7 (60) = 60 mins
● Employee 2: Task 2 (45) + Task 3 (20) + Task 8 (35) = 100 mins
● Employee 3: Task 4 (55) + Task 9 (50) = 105 mins
● Employee 4: Task 5 (40) + Task 10 (30) = 70 mins
Fitness = Max(55, 60, 100, 105, 70) = 105 mins
Repeat the Process
The GA will continue this process of selection, crossover, mutation, and fitness calculation over
several generations to find a better solution. Each generation should improve the fitne
