In computer science and operations research, a genetic algorithm (GA) is a meta-heuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). ~ Wikipedia
Most GA techniques are inspired on biologic phenomenons, such as mutation, crossover and natural selection. These types of algorithms can be used to generate high-quality solutions to optimisation and search problems. In contrast with other types of algorithms, instead of trying to improve 1 solution, a whole set of solutions is generated to then compare these new solutions.
To use GA's, a problem must be condensed to a form where the solution's properties can be altered and mutated. This condensed/encoded version also has to be easy to evaluate. The standard way of doing this is by representing the solutions as strings of 0s and 1s, but other encodings are also allowed.
The first generation of solutions is randomly generated. These solutions are referred to as individuals. Then the fittest individuals are stochastically selected. These fit individuals then fall subject to crossover and the next generation is generated with some random mutation mixed in.
The nurse scheduling/rostering problem (NSP/NRP) is a scheduling problem where nurses have to be assigned shifts and holidays. This comes with a lot of extra constraints. Each nurse has their own wishes and restrictions and so does the hospital.
The problem is fully described in the official paper of the Second International Nurse Rostering Competition (INRC2). Due to the extent of the problem, certain constraints were ignored. The ones that were applied can be found below.
There are two hard constraints:
- all demanded shifts must be assigned to a nurse;
- a nurse can only work one shift per day, i.e. no two shifts can be assigned to the same nurse on a day. A feasible solution is a solution that does not violate any of those two constraints.
- certain shifts cannot follow each other and are defined in the Scenario file
- Insufficient staffing for optimal coverage (30)
- Min and Max number of consecutive assignments (15/30)
- each extra/missing assigment * weight (shift/day)
- Min and Max number of consecutive free days (30)
- Complete weekends off/on (30)
- Total number of assignments in contract (20)
- Total number of working weekends <= max (30)
First the rules must be read. The organisers of the INRC2 provide a dataset from which the participants can start. This dataset consists of 3 types of files: history files, scenario files and week data files.
A randomly generated first generation forms the base for the solution. This generation exists of n randomly generated BitSchedules. BitSchedules contain encoded forms of schedules (See diagram 1).
From every generation the fittest individuals/schedules are selected according to the cost function (mistakes against constraints). The 2 fittest are set as "mother" and "father" of the next generation. This generation is generated by randomly choosing the bits from the mother or the father. To ensure more diverse generations, a chance of mutation is added. For every 1 or 0 in the newly generated code, there is a small chance that the bit gets flipped.
This process can be repeated till an optimal solution gets found or a plateau is reached.
Genetic Algorithms (Wikipedia)
Nurse Scheduling Problem (Wikipedia)
Nurse Rostering Competition I (2010)
Nurse Rostering Competition II (2014)