Adaptive randomized descent algorithm for solving course timetabling problems

作者：Abuhamdah Anmar^*; Ayob Masri

来源：International Journal of Physical Sciences, 2010, 5(16): 2516-2522.

• Course timetabling problems
• late acceptance strategy hill climbing

This work proposes an Adaptive Randomized Descent Algorithm (ARDA) for solving university course timetabling problems. The work aims is to produce an adaptive algorithm that can produce good quality timetable by assigning a set of courses (events) and students to a fixed number of timeslots and rooms subject to a set of constraints. ARDA delays the comparison between the quality of the candidate solution and the current solution. ARDA use a threshold value (that is calculated based on the average quality of some recently accepted solution) as an acceptance criterion. ARDA can adaptively manage to escape from local optima by intelligently changing the threshold value when the search is trap in local optima. This is done by estimating an appropriate threshold value based on the history of the search. Results tested on the Socha's benchmark datasets showed that, ARDA produces significantly good quality solutions when compared with late acceptance strategy in hill climbing, average late randomized descent within a reasonable time and comparable to other approaches tested on Socha's dataset.

• 出版日期2010-12-4