Digitala Vetenskapliga Arkivet

Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A comparative study between a simulated annealing and a genetic algorithm for solving a university timetabling problem
KTH, Skolan för datavetenskap och kommunikation (CSC).
KTH, Skolan för datavetenskap och kommunikation (CSC).
2016 (engelsk)Independent thesis Basic level (degree of Bachelor), 10 poäng / 15 hpOppgaveAlternativ tittel
En jämförande studie mellan en algoritm baserad på simulerad glödgning och en genetisk algoritm för att lösa ett universitetsschemaläggningsproblem (svensk)
Abstract [en]

The university timetabling problem is an NP-complete problem which schools all over the world face every semester. The aim of the problem is to schedule sets of events such as lectures and seminars into certain time slots without violating numerous specified constraints. This study aimed to automate this process with the help of simulated annealing and compare the results with a genetic algorithm. The input data sets were inspired by the Royal Institute of Technology in Stockholm. The results showed a great run time difference between the two algorithms where the simulated annealing performed much better. They also showed that even though the simulated annealing algorithm was better during all stages, the genetic algorithm had a much better performance in early stages than it had in latter. This led to the conclusion that a more optimized, hybrid algorithm could be created from the two algorithms provided that the genetic algorithm could benefit from the improvements suggested in previous research.

Abstract [sv]

Universitetsschemaläggningsproblemet är ett NP-fullständigt problem som skolor över hela världen måste hantera innan varje termin. Syftet med problemet är att schemalägga händelser, såsom föreläsningar och seminarier, utan att bryta flertalet fördefinierade villkor.

Denna studie hade som mål att automatisera denna process med hjälp av algoritmkonstuktionsmetoden simulerad glödgning och sedan jämföra resultatet med en genetisk algoritm. De datamängder som användes är inspirerade av den verkliga situationen på KTH. Resultaten visar stora tidsmässiga skillnader där algoritmen baserad på simulerad glödgning går snabbare. De visar dock också att den genetiska algoritmen har en bättre prestanda i tidigare stadier än i senare. Detta ledde till slutsatsen att en mer optimerad hybridalgoritm kan skapas av de två algoritmerna, förutsatt att den genetiska algoritmen kan dra nytta av förbättringar som föreslagits i tidigare forskning.

sted, utgiver, år, opplag, sider
2016. , s. 45
Emneord [en]
Simulated annealing, Genetic algorithm, University timetabling problem
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-187158OAI: oai:DiVA.org:kth-187158DiVA, id: diva2:929059
Fag / kurs
Computer Science
Utdanningsprogram
Master of Science in Engineering - Computer Science and Technology
Veileder
Examiner
Tilgjengelig fra: 2016-05-18 Laget: 2016-05-17 Sist oppdatert: 2022-06-22bibliografisk kontrollert

Open Access i DiVA

fulltext(728 kB)853 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 728 kBChecksum SHA-512
98dcb99f145935253c2dfdb1a7566e39964956612082502223d5bac47bff5d2323faec379928c4450dfe6e5b32cbc1bd2c0b4c9c7349fd227d666a1e1b5ef383
Type fulltextMimetype application/pdf

Søk i DiVA

Av forfatter/redaktør
Fredrikson, RasmusDahl, Jonas
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 853 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 1250 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf