A grouping hyper-heuristic framework: application on graph colouring
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 f...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/32183/ |
| _version_ | 1848794351929393152 |
|---|---|
| author | Elhag, Anas Özcan, Ender |
| author_facet | Elhag, Anas Özcan, Ender |
| author_sort | Elhag, Anas |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:14:49Z |
| format | Article |
| id | nottingham-32183 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:14:49Z |
| publishDate | 2015 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-321832020-05-04T17:11:46Z https://eprints.nottingham.ac.uk/32183/ A grouping hyper-heuristic framework: application on graph colouring Elhag, Anas Özcan, Ender 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. Elsevier 2015-08-01 Article PeerReviewed Elhag, Anas and Özcan, Ender (2015) A grouping hyper-heuristic framework: application on graph colouring. Expert Systems with Applications, 42 (13). pp. 5491-5507. ISSN 0957-4174 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-quality solutions; Hyper-heuristics; Timetabling; Tradeoff solution Heuristic methods http://www.sciencedirect.com/science/article/pii/S0957417415000536 doi:10.1016/j.eswa.2015.01.038 doi:10.1016/j.eswa.2015.01.038 |
| spellingShingle | 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-quality solutions; Hyper-heuristics; Timetabling; Tradeoff solution Heuristic methods Elhag, Anas Özcan, Ender A grouping hyper-heuristic framework: application on graph colouring |
| title | A grouping hyper-heuristic framework: application on graph colouring |
| title_full | A grouping hyper-heuristic framework: application on graph colouring |
| title_fullStr | A grouping hyper-heuristic framework: application on graph colouring |
| title_full_unstemmed | A grouping hyper-heuristic framework: application on graph colouring |
| title_short | A grouping hyper-heuristic framework: application on graph colouring |
| title_sort | grouping hyper-heuristic framework: application on graph colouring |
| topic | 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-quality solutions; Hyper-heuristics; Timetabling; Tradeoff solution Heuristic methods |
| url | https://eprints.nottingham.ac.uk/32183/ https://eprints.nottingham.ac.uk/32183/ https://eprints.nottingham.ac.uk/32183/ |