Abstract
Some evolutionary algorithm (EA)/timetabling researchers find benefit from combining an EA with graph-colouring based greedy algorithms, while others opt for a simpler but faster method. We consider a combination of the two approaches, largely retaining the speed of the simpler method while adopting the greedy method to bootstrap the process. In this combination, the initial population is produced by a ‘peckish’ timetable construction algorithm, similar to a greedy algorithm, but less concerned with finding a best timeslot for an event at each step. We find peckish population initialisation more effective than either greedy or random initialisation on non-trivial problems. Peckish initialisation is shown to aid a simple hill-climbing approach in a similar way. Finally, we add to the growing observation that hill-climbing often outperforms an EA on timetabling problems, but that this effect is reversed on problems of particular overconstrainedness or difficulty.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Abramson and J. Abela, ‘A parallel genetic algorithm for solving the school timetabling problem', Technical report, Division of Information Technology, C.S.I.R.O., (April 1991).
Edmund Burke, David Elliman, and Rupert Weare, ‘thm for university timetabling', in AISB Workshop on Evolutionary Computation. Workshop Notes, (1994).
Robert J. Collins and David R. Jefferson, ‘Selection in massively parallel genetic algorithms', in Proceedings of the Fourth International Conference on Genetic Algorithms, eds., R.K. Belew and L.B. Booker, pp. 249–256. San Mateo: Morgan Kaufmann, (1991).
Alberto Colorni, Marco Dorigo, and Vittorio Maniezzo, ‘Genetic algorithms and highly constrained problems: The time-table case', in Parallel Problem Solving from Nature, eds., G. Goos and J. Hartmanis, 55–59, Springer-Verlag, (1990).
Dave Corne, Peter Ross, and Hsiao-Lan Fang, ‘Fast practical evolutionary timetabling', in Proceedings of the AISB Workshop on Evolutionary Computation, ed., Terence C. Fogarty, Springer-Verlag, (1994).
Si-Eng Ling, ‘Intergating genetic algorithms with a Prolog assignment problem as a hybrid solution for a polytechnic timetable problem', in Parallel Problem Solving from Nature II, eds., R. Manner and B. Manderick, 321–329, Elsevier Science Publisher B.V., (1992).
B. Paechter, H. Luchian, A. Gumming, and M. Petruic, ‘An evolutionary approach to the general timetable problem', in Proceedings of the 9th Romanian Symposium on Computer Science, (1993).
B. Paechter, H. Luchian, A. Gumming, and M. Petruic, ‘Two solutions to the general timetable problem using evolutionary methods', in Proceedings of the First IEEE Conference on Evolutionary Computation, pp. 300–305, (1994).
Peter Ross, Dave Corne, and Hsiao-Lan Fang, ‘Improving evolutionary timetabling with delta evaluation and directed mutation', in Parallel Problem Solving from Nature III, ed., Y. Davidor, Springer-Verlag, (1994).
Peter Ross, Dave Corne, and Hsiao-Lan Fang, 'successful lecture timetabling with evolutionary algorithms', in Proceedings of the 11th ECAI Workshop, Springer-Verlag, (1994).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Corne, D., Ross, P. (1996). Peckish initialisation strategies for evolutionary timetabling. In: Burke, E., Ross, P. (eds) Practice and Theory of Automated Timetabling. PATAT 1995. Lecture Notes in Computer Science, vol 1153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61794-9_62
Download citation
DOI: https://doi.org/10.1007/3-540-61794-9_62
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61794-5
Online ISBN: 978-3-540-70682-3
eBook Packages: Springer Book Archive