Non-linear great deluge with reinforcement learning for university course timetabling

Obit, Joe Henry; Landa-Silva, Dario; Sevaux, Marc; Ouelhadj, Djamila

Abstract

This paper describes a non-linear great deluge hyper-heuristic incorporating a reinforcement learning mechanism for the selection of low-level heuristics and a non-linear great deluge acceptance criterion. The proposed hyper-heuristic deals with complete solutions, i.e. it is a solution improvement approach not a constructive one. Two types of reinforcement learning are investigated: learning with static memory length and learning with dynamic memory length. The performance of the proposed algorithm is assessed using eleven test instances of the university course timetabling problem. The experimental results show that the non-linear great deluge hyper-heuristic performs better when using static memory than when using dynamic memory. Furthermore, the algorithm with static memory produced new best results for ?ve of the test instances while the algorithm with dynamic memory produced four best results compared to the best known results from the literature.

Citation

Obit, J. H., Landa-Silva, D., Sevaux, M., & Ouelhadj, D. (2011). Non-linear great deluge with reinforcement learning for university course timetabling. In M. Caserta, & S. Voss (Eds.), Metaheuristics: intelligent decision making. Springer

• Publication Date: Jan 1, 2011
• Deposit Date: Apr 4, 2016
• Peer Reviewed: Peer Reviewed
• Issue: 50
• Series Title: Operations research/computer science interfaces series
• Book Title: Metaheuristics: intelligent decision making
• ISBN: 9781441979728
• Keywords: Great deluge, scheduling and timetabling, course timetabling, adaptive algorithms, heuristics metaheuristics, local search
• Public URL: https://nottingham-repository.worktribe.com/output/1011135