A Hybrid Genetic Algorithm for School Timetabling
Wilke P, Gröbner M, Oster N (2002)
Publication Language: English
Publication Type: Conference contribution, Original article
Publication year: 2002
Original Authors: Wilke Peter, Gröbner Matthias, Oster Norbert
Publisher: Springer
Edited Volumes: Lecture Notes in Computer Science
City/Town: Berlin Heidelberg
Book Volume: 2557
Pages Range: 455-464
Conference Proceedings Title: AI 2002: Advances in Artificial Intelligence - 15th Australian Joint Conference on Artificial Intelligence
Event location: Canberra
ISBN: 978-3-540-00197-3
URI: http://www2.informatik.uni-erlangen.de/publication/download/AI02.ps.gz
Abstract
Hybrid Genetic Algorithms apply so called hybrid or repair operators or include problem specific knowledge about the problem domain in their mutation and crossover operators. These operators use local search to repair or avoid illegal or unsuitable assignments or just to improve the quality of the solutions already found.
Those Hybrid Genetic Algorithms have been successfully applied to different constraint satisfaction and timetabling problems such as the travelling salesman problem, scheduling problems, employee timetabling or high school timetabling.
In this paper we describe a Genetic Algorithm for solving the German school timetabling problem. The Genetic Algorithm uses direct representation of the problem and applies an adapted mutation operator as well as several specific repair operators. We redecode the computed improvements to the genotype which establishes a kind of Lamarckian evolution. One of the problems utilising these hybrid operators is how and when to apply them, i.e. how to set the parameters right to achieve the best results. Different approaches have been started to adjust these parameters in an optimal way, but in most cases these adjustments require additional computing time and consequently are quite costly. We tackled this problem by an adaptation mechanism for the repair operators which can be applied without additional computing time. These operators are switched on when the normal Genetic Algorithm does not yield any more improvements. When the Genetic Algorithm then converges again, a reconfiguration step for the operator parameters guides the search out of the local optimum.
Authors with CRIS profile
Peter Wilke
Lehrstuhl für Informatik 2 (Programmiersysteme)
Norbert Oster
Lehrstuhl für Informatik 2 (Programmiersysteme)
How to cite
APA:
Wilke, P., Gröbner, M., & Oster, N. (2002). A Hybrid Genetic Algorithm for School Timetabling. In Mc Kay B., Slaney J. (Eds.), AI 2002: Advances in Artificial Intelligence - 15th Australian Joint Conference on Artificial Intelligence (pp. 455-464). Canberra, AU: Berlin Heidelberg: Springer.
MLA:
Wilke, Peter, Matthias Gröbner, and Norbert Oster. "A Hybrid Genetic Algorithm for School Timetabling." Proceedings of the AI2002 15th Australian Joint Conference on Artificial Intelligence, Canberra Ed. Mc Kay B., Slaney J., Berlin Heidelberg: Springer, 2002. 455-464.
BibTeX: Download