Change search
ReferencesLink to record
Permanent link

Direct link
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
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2016 (English)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)
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-186364OAI: diva2:927039
Available from: 2016-05-12 Created: 2016-05-10 Last updated: 2016-05-12Bibliographically approved

Open Access in DiVA

fulltext(1239 kB)79 downloads
File information
File name FULLTEXT01.pdfFile size 1239 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 79 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 507 hits
ReferencesLink to record
Permanent link

Direct link