Please use this identifier to cite or link to this item: http://hdl.handle.net/1893/15721
Appears in Collections:Computing Science and Mathematics Journal Articles
Peer Review Status: Refereed
Title: Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems
Author(s): Qu, Rong
Burke, Edmund
McCollum, Barry
Contact Email: e.k.burke@stir.ac.uk
Keywords: Adaptive
Exam timetabling
Graph colouring
Graph colouring heuristics
Hybridisation
Hyper-heuristic
Operations Research/Decision Theory
Organization/Planning
Information retrieval
Computer science
Computer software
Computational complexity
Algorithm Analysis and Problem Complexity
Discrete Mathematics in Computer Science
Issue Date: Oct-2009
Date Deposited: 1-Jul-2013
Citation: Qu R, Burke E & McCollum B (2009) Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems. European Journal of Operational Research, 198 (2), pp. 392-404. https://doi.org/10.1016/j.ejor.2008.10.001
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.
DOI Link: 10.1016/j.ejor.2008.10.001
Rights: The publisher does not allow this work to be made publicly available in this Repository. Please use the Request a Copy feature at the foot of the Repository record to request a copy directly from the author. You can only request a copy if you wish to use this work for your own research or private study.
Licence URL(s): http://www.rioxx.net/licenses/under-embargo-all-rights-reserved

Files in This Item:
File Description SizeFormat 
Adaptive automated construction of hybrid heuristics.pdfFulltext - Published Version493.49 kBAdobe PDFUnder Embargo until 3000-01-01    Request a copy

Note: If any of the files in this item are currently embargoed, you can request a copy directly from the author by clicking the padlock icon above. However, this facility is dependent on the depositor still being contactable at their original email address.



This item is protected by original copyright



Items in the Repository are protected by copyright, with all rights reserved, unless otherwise indicated.

The metadata of the records in the Repository are available under the CC0 public domain dedication: No Rights Reserved https://creativecommons.org/publicdomain/zero/1.0/

If you believe that any material held in STORRE infringes copyright, please contact library@stir.ac.uk providing details and we will remove the Work from public display in STORRE and investigate your claim.