Hybridizing Genetic Algorithm with Biased Chance Local Search

Authors: Mehdi Basikhasteh, Mohamad A. Movafaghpour

Abstract:

This paper explores university course timetabling problem. There are several characteristics that make scheduling and timetabling problems particularly difficult to solve: they have huge search spaces, they are often highly constrained, they require sophisticated solution representation schemes, and they usually require very time-consuming fitness evaluation routines. Thus standard evolutionary algorithms lack of efficiency to deal with them. In this paper we have proposed a memetic algorithm that incorporates the problem specific knowledge such that most of chromosomes generated are decoded into feasible solutions. Generating vast amount of feasible chromosomes makes the progress of search process possible in a time efficient manner. Experimental results exhibit the advantages of the developed Hybrid Genetic Algorithm than the standard Genetic Algorithm.

Keywords: University Course Timetabling, Memetic Algorithm, Biased Chance Assignment, Optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059775

References:

[1] Abdullah S. and H. Turabieh, (2008). Generating University Course Timetable Using Genetic Algorithms and Local Search. Third 2008 International Conference on Convergence and Hybrid Information Technology.
[2] Abdullah, S., E. K. Burke, B. McCollum, (2005). An Investigation of Variable Neighborhood Search for Course Timetabling. In: The Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2005), New York, USA, July 18 -21, pp. 413-427.
[3] Abdullah, S., E. K. Burke, B. McCollum, (2007). A hybrid evolutionary approach to the university course timetabling problem. IEEE congress on evolutionary computation 2007, pp. 1764-1768, Singapore.
[4] Al-Betar, M. A. and A. T. Khader, (2010). A harmony search algorithm for university course timetabling. Annals of Operations Research, In press.
[5] Aubin, J. and J. A. Ferland, (1989). A Large Scale Timetabling Problem. Computers and Operational Research 16(1): 67-77.
[6] Balakrishnan, N., Lucena, A., Wong, R.T., (1992). Scheduling examinations to reduce second-order conflicts. Computers and Operations Research 19, 353-361.
[7] Brailsford, S. C., C. N. Potts, B. M. Smith, (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research 119, 557-581.
[8] Burke E. K. and J. D. Landa Silva, (2005). The Design of Memetic Algorithms for Scheduling and Timetabling Problems, in "Recent Advances in Memetic Algorithms", Springer Berlin / Heidelberg, 289- 311.
[9] Burke E. K. and J. P. Newall, (1999). A Multi-Stage Evolutionary Algorithm for Timetable Problem, IEEE Transactions in Evolutionary Computation 3(1), 63-74.
[10] Burke, E. K. and S. Petrovic, (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2): 266-280.
[11] Carter, M. W. and G. Laporte, (1998). Recent developments in practical course timetabling. Proc of the 2nd Int Conf on Practice and Theory of Automated Timetabling, LNCS 1408, pp. 3-19.
[12] Carter, M. W., (1986). A survey of practical applications of examination timetabling algorithms. Operations Research 34, 193-202.
[13] de Werra, D., (1985). An introduction to timetabling. European Journal of Operational Research 19, 151-162.
[14] Eiselt, H. A. and G. Laporte, (1987). Combinatorial Optimization Problems with Soft and Hard Requirements. Journal of the Operational Research Society 38: 785-795.
[15] Even, S., A. Itai, and A. Shamir, (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691-703.
[16] Hart, W. E., N. Krasnogor and J. E. Smith, (2004). Memetic Evolutionary Algorithms, Recent Advances in Memetic Algorithms: Studies in Fuzziness and Soft Computing, Springer-Verlag, 3-27.
[17] Jat, S. N. and S. Yang, (2008). A Memetic Algorithm for the University Course Timetabling Problem. 20th IEEE International Conference on Tools with Artificial Intelligence.
[18] Krasnogor N., (2002). Studies on the theory and design space of memetic algorithms. PhD thesis, Faculty of computing, engineering and mathematical sciences, University of the West of England, UK.
[19] Rossi-Doria O., M. Sampels, M. Birattari, M. Chiarandini, M. Dorigo, L. Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L. Paquete, and T. Stutzle, (2002). A comparison of the performance of different metaheuristics on the timetabling problem. Lecture Notes in Computer Science 2740, pp. 329-351.
[20] Talbi, E. G., (2002). A Taxonomy of hybrid metaheuristics. Journal of heuristics, 8, 541-564.