Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems.(Report) Qu, Rong; Burke, Edmund K.; McCollum, Barry

User activity

Share to:
View the summary of this work
Qu, Rong ; Burke, Edmund K. ; McCollum, Barry
Appears In
European Journal of Operational Research
Computer Science; Business, general; Research and Development in the Physical, Engineering, and Life Sciences
Academic; Trade
To link to full-text access for this article, visit this link: Byline: Rong Qu (a), Edmund K. Burke (a), Barry McCollum (b) Keywords: Adaptive; Exam timetabling; Graph colouring; Graph colouring heuristics; Hybridisation; Hyper-heuristic Abstract: In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods. Author Affiliation: (a) Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, University of Nottingham, Wollaton Road, Nottingham NG8 1BB, UK (b) School of Computer Science, Queens University, University Road, Belfast BT7 1NN, N. Ireland, UK Article History: Received 15 August 2006; Accepted 8 October 2008
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users