Finding feasible timetables using group-based operators.

Lewis, Rhydian M R; Paechter, Ben

Abstract

This paper describes the applicability of the so-called "grouping genetic algorithm" to a well-known version of the university course timetabling problem. We note that there are, in fact, various scaling up issues surrounding this sort of algorithm and, in particular, see that it behaves in quite different ways with different sized problem instances. As a by-product of these investigations, we introduce a method for measuring population diversities and distances between individuals with the grouping representation. We also look at how such an algorithm might be improved: first, through the introduction of a number of different fitness functions and, second, through the use of an additional stochastic local-search operator (making in effect a grouping memetic algorithm). In many cases, we notice that the best results are actually returned when the grouping genetic operators are removed altogether, thus highlighting many of the issues that are raised in the study

Citation

Lewis, R. M. R., & Paechter, B. (2007). Finding feasible timetables using group-based operators. IEEE Transactions on Evolutionary Computation, 11, 397-413. https://doi.org/10.1109/TEVC.2006.885162

• Journal Article Type: Article
• Publication Date: Jun 1, 2007
• Deposit Date: May 26, 2008
• Publicly Available Date: May 16, 2017
• Print ISSN: 1089-778X
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 11
• Pages: 397-413
• DOI: https://doi.org/10.1109/TEVC.2006.885162
• Keywords: Group theory; Grouping problems; Fitness functions; Genetic algorithms; Case study; Education; University course timetables
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/1749
• Publisher URL: http://dx.doi.org/10.1109/TEVC.2006.885162