Ross, Peter, Hart, Emma and Corne, Dave (1997) Some observations about GA based timetabling. In: Proceedings of Practical Applications of Automated Timetabling. Lecture Notes in Computer Science, 1408/1 . Springer Berlin, pp. 115-129. ISBN 978-3-540-64979-3
Restricted to Registered users only
Available under License Creative Commons Attribution Non-commercial.
Download (812kB) | Request a copy
Although many people have tried using genetic algorithms (GAs) for exam timetabling, far fewer have done systematic investigations to try to determine whether a GA is a good choice of method or not. We have extensively studied GAs that use one particular kind of direct encoding for exam timetabling. Perhaps not surprisingly, it emerges that this approach is not very good, but it is instructive to see why. In the course of this investigation we discovered a class of solvable problems with interesting properties: our GAs would sometimes fail to solve some of the moderately-constrained problems, but could solve all of the lightly-constrained ones and all of the highly-constrained ones. This is despite the fact that they form a hierarchy: those erratically-solved problems are subproblems of the easily-solved but highly-constrained ones. Moreover, some other non-evolutionary approaches also failed on precisely the same sets. This, together with some observations about much simpler graph-colouring methods based on the Brelaz algorithm, suggest some future directions for GA-based methods.
|Item Type:||Book Section|
|Uncontrolled Keywords:||genetic algorithms; exam timetabling; direct encoding; moderately-constrained problems; lightly-constrained; highly-constrained;|
|University Divisions/Research Centres:||Faculty of Engineering, Computing and Creative Industries > School of Computing|
|Dewey Decimal Subjects:||000 Computer science, information & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science|
|Library of Congress Subjects:||Q Science > QA Mathematics > QA75 Electronic computers. Computer science|
|Depositing User:||Computing Research|
|Date Deposited:||28 Jul 2010 11:38|
|Last Modified:||12 Jan 2011 04:52|
Actions (login required)