Division of Informatics
Forrest Hill & 80 South Bridge
MSc Thesis #94127 | |
|---|---|
| Title: | A Comparison of Ga-Based Methods and Graph-Colouring Methods for Solving Timetabling Problems. |
| Authors: | Marin,HT |
| Date: | 1994 |
| Presented: | |
| Keywords: | |
| Abstract: | Several approaches have been used to solve the timetabling problem. Among those approaches the Genetic Algorithms (GAs) and the conventional graph colouring algorithms are found. This dissertation presents a comparison between the performance of GAs and the conventional algorithms for solving the problem when only edge constraints are considered. The work reported also presents results after comparing the pure genetic algorithm when using several variations in its parameters and other heuristic based on finding the clique of a graph. Finally, other types of constraints, specifically near-clash constraints, are considered in the conventional algorithm using a heuristic for solving the traveling salesman problem (TSP). The criteria for comparison used is the number of constraint checks done in each approach. In general, results show that the conventional algorithms perform better than the genetic algorithm when only edge constraints are considered; the heuristic based on the inclusion of the clique in the genetic algorithm can provide a dramatic reduction in the number of constraint checks; and finally, when other types of constraints are considered the conventional algorithms starts to manifest some problems. |
| Download: | NO ONLINE COPY |
![[Search These Pages]](http://www.dai.ed.ac.uk/icons/dai_search.gif){kind=icon}
![[DAI Home Page]](http://www.dai.ed.ac.uk/icons/dai_home.gif){kind=icon}
![[Comment]](http://www.dai.ed.ac.uk/icons/dai_comment.gif){kind=icon}