A grouping hyper-heuristic framework: Application on graph colouring

作者：Elhag Anas^*; Oezcan Ender

来源：Expert Systems with Applications, 2015, 42(13): 5491-5507.

DOI：10.1016/j.eswa.2015.01.038

• Hyper-heuristics
• Grouping problems
• Graph colouring
• Timetabling

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 hyperheuristics to achieve high quality solutions in both domains.

• 出版日期2015-8-1