A Simple Genetic Algorithm from Scratch in Python
Using a Genetic Algorithm for Optimizing A Staff Planning
Genetic Algorithms
Genetic Algorithms are optimization algorithms that mimic the process of natural selection. Rather than using “mathematical tricks”, they simply copy a logic of which we know that it works.
Natural Selection in Genetic Algorithms
This process of natural selection is founded on the Survival of the Fittest: the process in nature that makes the best individuals (animals, plants, or other) survive. Those fittest individuals then mate with each other, giving rise to a new generation. Nature also adds a bit of randomness in the form of mutations to the genome.
The new generation is a mix of good and bad individuals, but here again, the good ones will survive, then mate and then give rise to a new generation.
The result is a consistent improvement from generation to generation.
Genetic Algorithms for Staff Planning
Staff Planning is a topic of optimization research that comes back in many companies. As soon as a company has many employees, it becomes hard to find planning that suits the business needs while respecting certain constraints. Genetic Algorithms are one optimization method to solve this, among other existing solutions.
Python Implementation
In a previous article, I have shown how to use the DEAP library in Python for out-of-the-box Genetic Algorithms. In this article, I am going more into the specifics to show how to understand the different parts of the genetic algorithm.
The below code is a simplified version of what a production code for a genetic algorithm could look like. It is optimized for a better understanding of the example rather than for speed and reusability. It contains each of the listed steps, applied to example data.
Genetic Algorithm Code Walkthrough in 6 steps
The steps of the Genetic Algorithm:
- How to encode the data for the Genetic Algorithm?
- How to evaluate the Genetic Algorithm’s solution?
- How to code Mating (Cross-Over) for the Genetic Algorithm?
- How to code Mutations for the genetic algorithm?
- How to define Selection for the Genetic Algorithm?
- How to define iterations and stopping for the Genetic Algorithm?
If you want to follow along with the notebook, you can download it here.
Step 1 — How to encode the data for the Genetic Algorithm?
The Input Data — Two Types of Plannings
In this code, we will be working with two different shapes of the same staff planning.
Type 1 Planning — Per Employee
The first shape will be the staff planning for employees, the detailed view. This total weekly planning is a list that contains a list per day (5 days in our case). Each daily list contains a list of shifts (11 shifts for the employees in our case). Each shift is a list of an employee id (from 0 to 11, just for information), a start time (between 0 and 24 o’clock), and a shift duration (between 0 and 10 hours).
This type of planning will be needed for our employees to know when they work.
Type 2 Planning — Totals Per Hour
The second type of planning is the total number of employees that have been staffed per hour. This planning will be used by the shop owner to decide whether the planning corresponds to the estimated needs of the shop.
Step 2 — How to evaluate the Genetic Algorithm’s solution?
In order to evaluate an hourly staff planning, we need to have defined a goal situation. Defining this goal is not a part of the optimization: it would be a question for another project.
We do need to define how to evaluate the differences between the planning proposed and the goal planning. This will be done based on the hourly planning, by summing the total number of employee-hours too much and the number of employee-hours missing. This will be a cost function, that we need to minimize.
We could add weights for overstaffing or understaffing, but in this example I made them weigh equally.
Step 3 — How to code Mating (Cross-Over) for the Genetic Algorithm?
There are two key steps in the Genetic Algorithm: mating (also cross-over or recombination) and mutation.
In the Mating step, the new generation is formed from the offspring of individuals of the parent population, as it is in natural selection.
To apply this to our example, consider that later on, we will be generating many not so good staff plannings and trying to combine the best ones together. So we need to define a way to “mix” two individuals (staff plannings) with each other.
In this example, I have decided to code this as follows:
- Choose a random mom from the population
- Choose a random dad from the population
- Create a child as the same size as a parent, but randomly filled with zeroes and ones.
- The positions where the child has ones, we take the data from his father, and the positions where the child has zeroes, we take the data from his mother.
- We repeat this for each child (the number of children is equal to the population size)
This is one way to do it, and there are many other approaches possible. In order for the genetic algorithm to work, it is important to have randomness in the combination code. Of course the combination must fit with the data structure that you chose in step 1.
Step 4 — How to code Mutations for the genetic algorithm?
The second important step in the Genetic Algorithm is Mutation. It consists of adding a completely random change to the new generation. This random change allow to add a new value to the population that was not present anymore.
For example, consider a case where the algorithm has done a few iterations, and due to randomness in the selection and combination process, it has deselected all starting times before 10 am. Without mutation, the algorithm would never be able to get this value back, while it may be actually giving a better solution later on.
The random insertion of (a very small number of) new values helps the algorithm to escape from such situations.
It is coded here as adding replacing either a shift duration or a starting time of one shift by a random value between 0 and 10. This can be repeated if we specify an n_mutations value.
Step 5 — How to define Selection for the Genetic Algorithm?
The selection process is quite simple:
- First, select all feasible solutions: remove those in which employees work more than 10 hours.
- Then, apply the evaluation function to each individual (ie each staff planning) and select the best individuals. The number of selected individuals is kept variable in the code.
Step 6 — How to define iterations and stopping for the Genetic Algorithm?
The last part of the code is to add all the previous building blocks into an overall code that iterates.
Optimization Parameter Tuning
To make the Genetic Algorithm work perfectly, it is important to select the right parameters: generation_size, n_mutations, and n_best are important in this.
Tuning those three would allow for finding the best combination that both:
- converges to a solution (rather than turning around randomly without improving)
- avoids getting stuck in a local optimum
If after this tuning your algorithm still gets stuck, another axis of improvement would be to adapt the mating and mutation functions and see what happens then.
As the goal of this article was to have a simple and applied Genetic Algorithm from scratch, I will not go into the specifics of how to find those best parameters: that will require another article.
Thank you for reading. Don’t hesitate to stay tuned for more!
