An Empirical Study into the Structure of Heuristic Combinations in an Evolutionary Algorithm Hyper- Heuristic for the Examination Timetabling Problem

摘要

A hyper-heuristic for the examination timetabling problem searches a space of constructive heuristic combinations instead of a space of examination timetables. The most optimal heuristic combination found by the search is used to construct the examination timetable. The focus of a hyper-heuristic is to generalize well rather than producing the best result for one or more problem sets in the domain. A metaheuristic such as evolutionary algorithms is usually employed to explore the heuristic space. This study reports on an empirical investigation conducted to test how the structure of the heuristic combination affects the success of the search of an evolutionary algorithm (EA) hyper-heuristic for the uncapacitated examination timetabling problem. Two structures, namely, one that combines low-level construction heuristics linearly, and applies them sequentially and a second which combines heuristics hierarchically and applies them simultaneously are investigated. The performance of the EA-based hyper-heuristic using both structures is tested on a set of eight uncapacitated examination timetabling problems. The study has revealed that the representation used does have an impact on the success of the evolutionary algorithm. In this domain the linear combination and sequential application of heuristics produced better results. The EAs with both representations were also found to perform better than other hyper-heuristic methods applied to the same problem.