Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2016.
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-186364OAI: oai:DiVA.org:kth-186364DiVA: diva2:927039
Supervisors
Examiners
Available from: 2016-05-12 Created: 2016-05-10 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 428 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

urn-nbn

Altmetric score

urn-nbn
Total: 944 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf