Automatic Lecture Planner using Genetic Algorithm
Planning Lectures or Creating Timetable is a very tedious thing to do, but a very basic and important task for every Educational Institute and other organizations also. So, there are many ways to do that automatically (using Computers).
There are many way to do that, and we can do it automatically by just providing some inputs to the Timetable generator.
Time Table generation is a NP-Complete problem. It needs to check most of the possibilities to make the best out of all the solutions from the inputs. Scheduling is not easy for our computers also…
Here we are going to start our solution with the most popular approach for this problem. We are going to solve this using Genetic Algorithm.
If you are not familiar with it. Genetic algorithms are based on the ideas of natural selection and genetics.
Head towards this article for understanding the basics of Genetic Algorithms and its variables.
The simple form of algorithm we are going to follow is as follow:
1. First, an initial generation of chromosomes is created randomly and their fitness value is analyzed.2. New generations are created after this. For each generation, it performs the following:
2.1 Preserve few fittest chromosomes from the previous generation as it is.
2.2 Randomly select a pair of chromosomes from previous generation.
2.3 Perform crossover depending on crossover rate.
2.4 perform mutation on the more fit chromosome so obtained depending on mutation rate.3. Analyze the fitness of new generation and order them accordingly to fitness values.4. Repeat creating new generations unless chromosomes of desired fitness value are obtained i.e. fitness = 1. (stopping criteria)
After understanding the basics of Genetic Algorithm and its variables. We should start implementing the approach.
Now you must be thinking of how to implement Chromosomes, Population, Mutation, Crossover etc etc. This looks good in theory… Aaaahhhhhh!!!
Inputs
Batch (Grades) = [6, 7, 8, 9, 10]
Subjects = [‘Math’, ‘Eng’, ‘Physics’, ‘Computer Science’, ‘Chemistry’]
Room Numbers = [1, 2, 3, 4, 5, 6, 7, 8]
Days = 5 (Monday to Friday)
Time periods = [‘10:00–11:00’, ‘11:00–12:00’, ‘1:00–2:00’, ‘2:00–3:00’]
Gene
Consider your Inputs: and now convert them as 4 bit binary string.
eg: ‘Math’ = ‘0000’,
‘Eng’ = ‘0001’ etc.
Do this like for all your input data and store it in variables.
Chromosomes
These genes will help us to form the chromosomes.
Now we can append this gene data within a binary string:
Length depends on your Inputs, here we will form a 20 bits long string for chromosomes because we have 5 * 4 bits long gene.
Length of Chromosome = 5 * 4 = 20
5 is our number of choices for inputs
Chromosome = <batch, subject, room, days, time_period>
eg: 0001 0110 0111 0101 0011
Initial Population
Now when we have created one chromosome, so we can also produce more chromosomes based on random selection from our inputs to form an Initial population.
eg. Initial Population: [ 0001 0110 0111 0101 0011, 0001 0110 0111 0001 0110, …, … ]
Fitness calculation
Fitness calculation is very important to know that our chromosome is doing well when put in the timetable.
Fitness calculation is based on some constraints. eg:.
1. Is there any empty room available for the batch to start the lecture.
2. If the number of students in the batch is greater than the capacity of the room then it is not possible to assign that room to that batch.
3. Same subject should not occur for another batch at the same time same day.
4. Same subject should not have same subject same day twice.
5. There should not be any conflict in two subjects for same batch, same time, same day.etc. you may think of some soft constraints also to implement, feel free to remove any of these and add your constraints if you think that is important.
Fitness is calculated in numbers (increment the number by 1 if the chromosome passed the condition). and after the highest fitness obtaining chromosome will get a chance to reproduce their offspring by getting into crossover and mutation… (Just like the basic: best group survives)
Crossover
Crossover is a method which divides the chromosomes and generate copies of other chromosomes with half-half qualities of both chromosomes.
eg: chromo1 = 1001 0011
chromo2 = 0110 1101after one point crossover (splitting from the half) chromo3 = 1001 1101
chromo4 = 0110 0011so now we have a collection of 4 chromosomes
We have created some chromosomes with the best fitted chromosomes after the fitness calculation.
Mutation is something different than crossover. In mutation we mutate (change) one bit or the gene of the chromosome (in this case).
Now we have all the thing to start with and we can start generating our Time table. we just need to find out how 😜. We know the simple algorithm for that and we can do that step by step following the procedure.
Conclusion
Now we have to calculate fitness of our population and then give the best chromosomes to crossover and mutation until you get the desirable number of chromosomes in your best fitness population.
If you want to give it a try by yourself then you are ready to go…
or you can just head towards our Lecture planner code available on github.
Thanks 💙 to Simran Kaur and Ravi Tej KVNN
