Artificial Intelligence: 4. GA, MA, CSP for Timetable Generation
Code: GitRepo
Genetic Algorithm (GA)
- There is always a sub-optimal solution during the generations in GA and MA. We need not wait for thousands of years just to get to the optimal answer.
- All the timetable algorithms and constraints are developed considering the IIITD timetable and the staff and lecture halls available.
Basic Algorithm Steps:
1. Initialise Population — 100
2. Evaluate Function
3. Repeat while not converged
a. Crossover
b. Mutate
c. Evaluate (pick best 10)
Assumptions and Additional Features:
- The evaluation function takes the top 10 best performing chromosomes
- For better diversity, we can even include a randomly generated chromosome into the population randomly in a random generation with some probability
- Elitism is not used
- [0, 0] is used to denote a free lecture hall where no lecture is happening
- In each generation, the 0,0 block is added into the possibilities to improve the probability of that getting randomly selected
- We can also include few random chromosomes into the population, this is not used as the performance with my current algorithm is satisfactory.
- Lots of Probability is used in many places to decide the mutation rate and crossover rate
Chromosome:
- 3d structure of days, slots and lecture halls
- Days ✕ Slot ✕ Lecture Halls(N) → 5 ✕ 8 ✕ N
Fitness Function and Constraints Handled:
- A lecturer cannot teach when he is currently teaching (same subject or different subject)
- A lecturer should teach only the subject he is assigned to teach.
- A course cannot be held in any other hall if it is currently going on
- A course should satisfy the minimum number of classes required per week
- A course should not exceed maximum class limit per week
- A course once held on a day cannot be held on that day again
- Number of courses can be greater than or less than the number of lecturers
- [0, 0] is an empty block
- If any of the above conditions are not met, there is a penalty added. And fitness can be basically defined as the inverse of that penalty.
- Fitness = 1/(1+errorrate). Here the error rate is the error penalty for all the unsatisfied conditions mentioned above.
Crossover:
- Crossover is done on random-axis.
- Probability is used to select which kind of crossover should be used
Mutation:
- Mutation can be done on any dimension, but it will be of very less use if it is done only on one dimension.
- Probability is used to decide which dimension to be mutated and the number of times to repeat that process (1 or 2).
Observations:
- The performance is very good, but the convergence can take quite a number of generations.
- And after a set of generations, the best collision rate keeps a constant value for quite many generations (e.g., 1)
- The running time is less
- Bit difficult to converge with complex constraints, but will definitely converge after certain generations.
Memetic Algorithm (MA)
MA = GA + Local Hill Climbing
Basic Algorithm Steps:
1. Initialise Population
2. Local Search
3. Evaluate Function
4. Repeat while not converged
a. Crossover
b. Mutate
c. Local Search
d. Evaluate
The main difference between GA and MA is that we try to improve each individual chromosome before evaluation. This additional functionality is called local search (Local Hill Climbing). In this, for each chromosome, we move a bit around in its local search space and see if it is a better state than the previous. If that space is better, we then replace the parent with the generated chromosome.
Local Search:
- Local Search happens in local search space
- Recombine a pair of parents and replace them if the child is better than parents (mentioned in Lecture Slides).
- Take a step in either direction in the search space of each chromosome by changing a gene and replace parent if the child is better
- We can even take multiple steps depending upon our implementation, but the steps should not be too far to save the computational power
Observations and Points to Note:
1. Local search in MA is usually computationally heavy, but it is definitely worth the computation cost.
2. MA converges a lot faster than GA
3. There is a high probability that the best chromosome will be improved in each generation, and there is a huge improvement in the initial generations.
4. Can also solve complex constraints
5. Both GA and MA gives meaning full and evenly distributed results unlike CSP
6. The fitness function, evaluation function, crossover and mutation are same as GA
Performance Evaluation of GA and MA:
Stage 1:
- Random mutation on z-axis (lecture hall) once (on each chromosome)
- Random 1-point crossover on z-axis once
- MA is using positive replacing of parents upon recombination
- The constraints given are very lenient
GA — 2 courses/day
MA — 2 courses/day
MA — 1 course/day
Observations:
- With 2 courses/day GA is able to converge fine.
- MA is able to converge much better
- MA is also able to handle 1 course/day
Stage 2:
- Random mutation on random axis once (on each chromosome)
- Random 1-point crossover on z-axis once
GA — 2 courses/day
Observations:
- The random axis mutation improved the GA for the same constraints in GA.
Stage 3:
- Random mutation on random axis random number of times (1(0.6) or 2(0.4)) (on each chromosome)
- Random 1-point crossover on z-axis once
- MA is using positive replacing of parents upon recombination
GA — 2 courses/day
GA — 1 courses/day
MA — 1 courses/day
Observations:
- With the increase in randomness to the axis in mutation, the performance seems to increase.
- While GA is able to compute well even for stricter constraints (1 course/day). MA is preforming much better
Stage 4:
- Random mutation on random axis random number of times (1(0.6) or 2(0.4)) (on each chromosome)
- Random 1-point crossover on random-axis once
- MA is using positive replacing of parents upon recombination
- MA with different input values
MA — 1 courses/day
Observations:
- Now I tried MA with stricter constraints and was checking how I can improve the performance on the worst conditions.
- I found that implementing randomness on crossover axis seems to help.
- MA converges in reasonable generations
Stage 5:
- Random mutation on random axis random number of times (1(0.6) or 2(0.4)) (on each chromosome)
- Random 1-point crossover on random-axis once
- MA is using positive replacing of parents upon recombination and surrounding check (another Hill Climb) — where we take a step in the local search space on either side a couple number of steps and replace the parent if the child is better.
Observations:
- Now after stage 4, I tried to reduce the number of generations the MA is taking to converge.
- In this Local Search, first I try to wander each chromosome to its surroundings randomly to couple of steps and replace the parent if it is better.
- This reduces the generations by half, as we can observe.
Stage 6:
- Random mutation on random axis random number of times (1(0.6) or 2(0.4))
- Random “random (1 or 2)-point” crossover on random-axis once
- MA is using positive replacing of parents upon recombination and surrounding check
- Stricter Constraints
MA — 2 courses/day
GA — 2 courses/day
GA — 1 course/day
MA — 1 course/day
Observations:
- Now I want to take my algorithm to its max, to generate an actual IIITD timetable. So I gave more constraints and I was trying different ways to improve the performance.
- I found that randomly deciding which crossover to perform is a very good technique.
- Here to make my algorithm simple, if my random variable decided to do a 2-point crossover, I just have to do the 1-point crossover twice.
- In this there is a problem, if the same point of crossover is chosen, then there is a problem that it returns the same parent. So I’m keeping a check if the same random point is chosen, and if it same I return the 1-point crossover chromosome.
Inference:
- The generated timetable is very neatly diverse and follows all constraints. There are free classes at random times which will help students of IIITD to have some leisure time.
- Using this algorithm and implementing some more constraints we can actually use this as a timetable generator.
- I would personally use MA to find a solution faster with huge constraints.
Final Stage:
GA:
Converged in 125 generation
Timetable
Courses per day Error: 0
[[0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1]
[0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0]
[0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 0]
[1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1]
[1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0]]
Course Frequency Error: 0
[2 3 2 2 2 2 2 3 3 2 3 2 2 3 2 2 3 2 2 2]
Lecture Z-Axis Collisions: 0
Total Collisions: 0 Fitness: 1.0
MA
Timetable
Courses per day Error: 0
[[1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0]
[1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1]
[0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0]
[1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1]
[0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0]]
Course Frequency Error: 0
[3 4 4 3 2 2 3 2 3 4 3 2 4 4 4 3 2 2 4 2]
Lecture Z-Axis Collisions: 0
Total Collisions: 0 Fitness: 1.0
Constraint Satisfaction Problem (CSP):
- Basically a DFS on the set of possibilities on our 3D matrix
- The possibilities here are the all possible combinations of lecturer and course. Because a course taught by one professor should not be taught by another professor
- Gives uneven results
- [-1, -1] is an empty slot in the timetable. Starting the matrix with all zero’s
- As this tries to fill the matrix cell by cell, checking if the constraints are met, the data placed are sequential.
- The conditions here are taken the same as GA fitness function
- If it reaches a dead state where the conditions are not met, then we return back to the parent searching for a different combination
- This gives a solution but depends on our necessity if we have to use this.
- Also takes a little computational and space power depending on the type of CSP implemented.
- Becomes heavy depending on the constrains and the search space
- This is not a good approach both in terms of time complexity and space complexity
Inference:
- The timetable generated is very uneven
- The lecture halls are utilized to an extent in the first 3 slots and the rest of the day is totally free.
- If this timetable is used for IIITD, no student will be able to attend classes in the morning
- So I would not prefer this timetable for IIITD, lets go with GA/MA
Timetable Generated:
Constraints:
courses = 10lectureHalls = 3professors = 6minClassCount = 2maxClassCount = 5coursesPerDay = 1
Items in Stack: 271, Cost: 119
Courses per day Error: 0
[[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]
[1 1 1 1 1 1 1 1 1 1]]
Course Frequency Error Max: 0
[5 5 5 5 5 5 5 5 5 5]
Course Frequency Error Min: 0
[5 5 5 5 5 5 5 5 5 5]
Total Collisions: 0
