Hyper-heuristics using Reinforcement Learning for the Examination Timetabling Problem

Han, Kate; McMullan, Paul

Abstract

Selection Hyper-heuristics as general-purpose search methods controlling a set of low level heuristics have been successfully applied to various problem domains. A key to designing an effective selection Hyper-heuristic is to find the right combination of heuristic selection and move acceptance methods which are invoked successively under an iterative single-point-based search framework. The examination timetabling problem is a well-known challenging real world problem faced recurrently by many educational institutions across the world. In this study, we investigate various reinforcement learning techniques for heuristic selection embedded into a selection Hyper-heuristic using simulated annealing with reheating for examination timetabling. Reinforcement learning maintains a utility score for each low level heuristic. At each iteration, a heuristic is selected based on those adaptively updated utility scores and applied to the solution at hand with the goal of improvement. All selection Hyper-heuristics using different reinforcement learning schemes are tested on the examination timetabling benchmark of ITC 2007. The results show that ε-decay-Greedy reinforcement learning which chooses a low level heuristic with the maximum utility score with a decaying probability rate, otherwise choosing a random low level heuristic performs the best. The proposed tuned approach although does not perform as good as the state-of-the-art, it delivers a better performance than some existing Hyper-heuristics

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 8th Multidisciplinary International Conference on Scheduling: Theory and Applications
• Start Date: Dec 5, 2017
• End Date: Dec 8, 2017
• Online Publication Date: Aug 5, 2018
• Publication Date: Aug 5, 2018
• Deposit Date: Jan 7, 2025
• Pages: 256-268
• Book Title: Proceedings of the 8th Multidisciplinary International Conference on Scheduling: Theory and Applications
• Publisher URL: https://www.inprincipo.nl/file/upload/doc/mista2017.pdf