Effective learning hyper-heuristics for the course timetabling problem |
| |
Authors: | Jorge A Soria-Alcaraz Gabriela Ochoa Jerry Swan Martin Carpio Hector Puga Edmund K Burke |
| |
Institution: | 1. Instituto Tecnológico de León, Doctorado interinstitucional en Ciencias en Computación, División de Estudios de Posgrado e Investigación, León, Guanajuato, Mexico;2. Computing Science and Mathematics, University of Stirling, Stirling, Scotland, UK |
| |
Abstract: | Course timetabling is an important and recurring administrative activity in most educational institutions. This article combines a general modeling methodology with effective learning hyper-heuristics to solve this problem. The proposed hyper-heuristics are based on an iterated local search procedure that autonomously combines a set of move operators. Two types of learning for operator selection are contrasted: a static (offline) approach, with a clear distinction between training and execution phases; and a dynamic approach that learns on the fly. The resulting algorithms are tested over the set of real-world instances collected by the first and second International Timetabling competitions. The dynamic scheme statistically outperforms the static counterpart, and produces competitive results when compared to the state-of-the-art, even producing a new best-known solution. Importantly, our study illustrates that algorithms with increased autonomy and generality can outperform human designed problem-specific algorithms. |
| |
Keywords: | Timetabling Hyper-heuristics Heuristics Metaheuristics Combinatorial optimization |
本文献已被 ScienceDirect 等数据库收录! |
|