Learning assignment order in an ant colony optimiser for the university course timetabling problem
Sakal, J; Fieldsend, JE; Keedwell, E
Date: 7 July 2021
Publisher
Association for Computing Machinery (ACM)
Publisher DOI
Abstract
Previous studies have employed Ant Colony Optimisation to solve the University Course Timetabling task — which requires the order
of lecture assignments to be defined for its construction graph. Various heuristic or random ordering techniques have been proposed in the literature, but uncertainty remains regarding the best approach for ...
Previous studies have employed Ant Colony Optimisation to solve the University Course Timetabling task — which requires the order
of lecture assignments to be defined for its construction graph. Various heuristic or random ordering techniques have been proposed in the literature, but uncertainty remains regarding the best approach for this. We investigate the effect that permuting assignment order
has on the quality of timetable produced. As part of this we develop a novel MAX-MIN Ant System including dynamic constraint
handling and partial function evaluations. We also explore algorithm variants with and without Local Search and employ a form
of transfer learning to identify appropriate permutations. We find that between smaller problems in the International Timetabling
Competition 2007 benchmark, timetabling performance can be improved using such an approach. However we find that we lose this performance gain when attempting to transfer to considerably larger problems — indicating that similar structures are required
when using a ‘learnt’ permutation approach in such a framework.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0