A Genetic Programming Approach to the Generation of Hyper-Heuristics for the Uncapacitated Examination Timetabling Problem
A Genetic Programming Approach to the Generation of Hyper-Heuristics for the Uncapacitated Examination Timetabling Problem
复制标题
DOI：
10.1007/978-3-540-77002-2_19
复制
发表时间：
2007-12
期刊：
影响因子：
--
通讯作者：
N. Pillay;W. Banzhaf
中科院分区：
文献类型：
--
作者：
N. Pillay;W. Banzhaf
考试排课领域的研究有两个发展方向。第一个着眼于应用各种方法来制定考试时间表。第二种方法采用间接的方法来解决问题，并研究在构建考试时间表时要使用的启发式或启发式组合的生成，即超启发式。本文的研究主要集中在后一领域。本文首次尝试将遗传编程用于求解无能力考试排课问题的超启发式进化算法。该系统已经在9个基准考试排课问题上进行了测试。所有9个问题都找到了无冲突的时间表。此外，遗传编程系统的性能与用于进化这一组问题的超启发式算法的其他搜索算法相比，在许多情况下产生了更高质量的时间表。
Research in the field of examination timetabling has developed in two directions. The first looks at applying various methodologies to induce examination timetables. The second takes an indirect approach to the problem and examines the generation of heuristics or combinations of heuristics, i.e. hyper-heuristics, to be used in the construction of examination timetables. The study presented in this paper focuses on the latter area. This paper presents a first attempt at using genetic programming for the evolution of hyper-heuristics for the uncapacitated examination timetabling problem. The system has been tested on 9 benchmark examination timetabling problems. Clash-free timetables were found for all 9 nine problems. Furthermore, the performance of the genetic programming system is comparable to, and in a number of cases has produced better quality timetables, than other search algorithms used to evolve hyper-heuristics for this set of problems.