Skip to main content

Research Repository

Advanced Search

A grouping hyper-heuristic framework: application on graph colouring

Elhag, Anas; �zcan, Ender

A grouping hyper-heuristic framework: application on graph colouring Thumbnail


Authors

Anas Elhag

Profile Image

ENDER OZCAN ender.ozcan@nottingham.ac.uk
Professor of Computer Science and Operational Research



Abstract

Grouping problems are hard to solve combinatorial optimisation problems which require partitioning of objects into a minimum number of subsets while a given objective is simultaneously optimised. Selection hyper-heuristics are high level general purpose search methodologies that operate on a space formed by a set of low level heuristics rather than solutions. Most of the recently proposed selection hyper-heuristics are iterative and make use of two key methods which are employed successively; heuristic selection and move acceptance. In this study, we present a novel generic selection hyper-heuristic framework containing a fixed set of reusable grouping low level heuristics and an unconventional move acceptance mechanism for solving grouping problems. This framework deals with one solution at a time at any given decision point during the search process. Also, a set of high quality solutions, capturing the trade-off between the number of groups and the additional objective for the given grouping problem, is maintained. The move acceptance mechanism embeds a local search approach which is capable of progressing improvements on those trade-off solutions. The performance of different selection hyper-heuristics with various components under the proposed framework is investigated on graph colouring as a representative grouping problem. Then, the top performing hyper-heuristics are applied to a benchmark of examination timetabling instances. The empirical results indicate the effectiveness and generality of the proposed framework enabling grouping hyper-heuristics to achieve high quality solutions in both domains. ©2015 Elsevier Ltd. All rights reserved.

Citation

Elhag, A., & Özcan, E. (2015). A grouping hyper-heuristic framework: application on graph colouring. Expert Systems with Applications, 42(13), https://doi.org/10.1016/j.eswa.2015.01.038

Journal Article Type Article
Publication Date Aug 1, 2015
Deposit Date Mar 10, 2016
Publicly Available Date Mar 29, 2024
Journal Expert Systems with Applications
Print ISSN 0957-4174
Electronic ISSN 0957-4174
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 42
Issue 13
DOI https://doi.org/10.1016/j.eswa.2015.01.038
Keywords Combinatorial optimization; Computer software reusability; Economic and social effects; Graph theory; Iterative methods; Optimization; Problem solving; Scheduling, Examination timetabling; Graph colouring; Grouping problem; Heuristic selections; High-qual
Public URL https://nottingham-repository.worktribe.com/output/755552
Publisher URL http://www.sciencedirect.com/science/article/pii/S0957417415000536

Files





You might also like



Downloadable Citations