Solving the Examination Timetabling Problem with the Shuffled Frog-leaping Algorithm

Nuno Leite, Fernando Melício, Agostinho Rosa

2013

Abstract

Shuffled Frog-Leaping Algorithm (SFLA) is a recently proposed memetic meta-heuristic algorithm for solving combinatorial optimisation problems. SFLA has both global and local search capabilities, and great convergence speed towards the global optimum. Compared to a genetic algorithm, the experimental results show an effective reduction of the number of evaluations required to find the global optimal solution. The Examination Timetabling Problem (ETTP) is a complex combinatorial optimisation problem faced by schools and universities every epoch. In this work, we apply the Shuffled Frog-Leaping Algorithm to solve the ETTP. The evolution step of the algorithm, specifically the local exploration in the submemeplex is carefully adapted based on the prototype SFLA. The algorithm was evaluated on the standard Toronto benchmark instances, and the preliminary experimental results obtained are comparable to those produced by state of art algorithms while requiring much less time.

Paper Citation

in Harvard Style

Leite N., Melício F. and Rosa A. (2013). Solving the Examination Timetabling Problem with the Shuffled Frog-leaping Algorithm . In Proceedings of the 5th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2013) ISBN 978-989-8565-77-8, pages 175-180. DOI: 10.5220/0004636001750180

in Bibtex Style

@conference{ecta13,
author={Nuno Leite and Fernando Melício and Agostinho Rosa},
title={Solving the Examination Timetabling Problem with the Shuffled Frog-leaping Algorithm},
booktitle={Proceedings of the 5th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2013)},
year={2013},
pages={175-180},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004636001750180},
isbn={978-989-8565-77-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Joint Conference on Computational Intelligence - Volume 1: ECTA, (IJCCI 2013)
TI - Solving the Examination Timetabling Problem with the Shuffled Frog-leaping Algorithm
SN - 978-989-8565-77-8
AU - Leite N.
AU - Melício F.
AU - Rosa A.
PY - 2013
SP - 175
EP - 180
DO - 10.5220/0004636001750180