Investigating a Genetic Algorithm-Simulated Annealing Hybrid Applied to University Course Timetabling Problem: A Comparative Study Between Simulated Annealing Initialized with Genetic Algorithm, Genetic Algorithm and Simulated Annealing
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En Jämförelse Mellan Simulated Annealing Initialiserad med Genetic Algorithm, Genetic Algorithm och Simulated Annealing Applicerat på Universitetsschemaläggningsproblemet (Swedish)
Every semester universities around the world have to create new schedules. This task can be very complex considering that a number of constraints has to be taken into account, e.g. there should not exist any timetable clashes for students and a room cannot be double-booked. This can be very hard and time-consuming for a human to do by hand, which is why methods to automate this problem, the University Course Timetabling Problem, has been researched for many years.
This report investigates the performance of a hybrid consisting of Genetic Algorithm and Simulated Annealing when solving the University Course Timetabling Problem. An implementation by Yamazaki & Pertoft (2014) was used for the Genetic Algorithm. Simulated Annealing used the Genetic Algorithm as base for its implementation. The hybrid runs the Genetic Algorithm until some breakpoint, takes the best timetable and uses it as an initial solution for the Simulated Annealing.
Our results show that our implementation of Simulated Annealing performs better than the hybrid and magnitudes better than the Genetic Algorithm. We believe one reason for this is that the dataset used was too simple, the Genetic Algorithm might scale better as the complexity of the dataset increases.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-186364OAI: oai:DiVA.org:kth-186364DiVA: diva2:927039