Hyper-heuristics for grouping problems

Grouping problems are hard to solve combinatorial optimization problems which require partitioning of objects into a minimum number of subsets while another additional objective is simultaneously optimized. Considerable research e ort has recently been directed towards automated problem-independent reusable heuristic search methodologies such as hyper-heuristics, which operate on a space formed by a set of low level heuristics rather than solutions, directly. Hyper-heuristics are commonly split into two main categories: selection hyper-heuristics, which are the focus of the work presented in this thesis, and generation hyper-heuristics. 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. At each step, a new solution is produced after a selected heuristic is applied to the solution at hand and then the move acceptance method is used to decide whether the resultant solution replaces the current one or not. This thesis presents a novel generic single point-based selection hyper-heuristic search framework, referred to as grouping hyper-heuristic framework. The proposed framework deals with one solution at any given decision point during the search process and embeds axed set of reusable standard low level heuristics specifically designed for the grouping problems. The use of standard heuristics enables the re-usability of the whole framework across different grouping problem domains with less development effort. The proposed grouping hyper-heuristic framework is based on a bi-objective formulation of any given grouping problem. Inspired from multi-objective optimization, a set of high quality solutions is maintained during the search process, capturing the trade-of between the number of groups and the additional objective for the given grouping problem. Moreover, the grouping framework includes a special two-phased acceptance mechanism that use the traditional move acceptance method only to make a preliminary decision regarding whether to consider the new solution for acceptance or not. The performance of different selection hyper-heuristics combining different components, implemented based on the proposed framework is investigated on a range of sample grouping problem domains, including graph coloring, exam timetabling and data clustering domains. Additionally, the selection hyper-heuristics performing the best on each domain are compared to the previously proposed problem-specific algorithms from the scientific literature. The empirical results shows that the grouping hyper-heuristics built based on the proposed framework are not only sufficiently general, but also able to obtain high quality solutions, competitive to some previously proposed approaches. The selection hyper-heuristic employing the 'reinforcement learning' heuristic selection method and embedding the 'iteration limited threshold accepting' move acceptance method performs the best in the overall across those grouping problem domains