Intelligent hyper-heuristics: a tool for solving generic optimisation problems

Designing a dedicated search and optimisation algorithm is a time-consuming process requiring an in-depth analysis of the problem. The resulting algorithm is expected to be effective for solving a given set of target problem instances. However, since the algorithm is dedicated, it is hard to adapt and to apply to other problems. Meta-heuristics were brought in to cope with this drawback. Nevertheless, in most of the meta-heuristic studies, the employed meta-heuristics have been implemented as rather problem-dependent methodologies. Hyper-heuristics furnish problem-independent management opportunities differently from such search and optimisation algorithms. The present dissertation focuses on the generality of hyper-heuristics. It thereby aims at designing intelligent hyper-heuristics so that generality is facilitated. While most works on hyper-heuristics make use of the term generality in describing the potential for solving various problems, the performance changes across different domains have only rarely been reported. Additionally, there are other generality related elements such as the performance variations over distinct heuristic sets, that are usually ignored. This means that there is no study fully discussing generality questions while providing a hyper-heuristic design capable of addressing them.To this end, the factors affecting the hyper-heuristics' generality are determined and several novel hyper-heuristic components are developed based on these factors. Then, the hyper-heuristics using the new components are tested across various problem domains on different heuristic sets, while also varying the experimental limits. First, each developed hyper-heuristic is applied to only one problem domain. The performance of these hyper-heuristics is compared with other algorithms encountered in the literature. The information gathered during these experiments is used later on to design a highly adaptive, intelligent selection hyper-heuristic.The ultimate result of the present PhD research is called the Generic Intelligent Hyper-heuristic (GIHH). It is equipped with multiple online adaptive hyper-heuristic procedures and decision mechanisms for simultaneously coordinating them. GIHH is expected to evolve for different search environments without human intervention. A simplified version of GIHH is tested via a series of experiments on three problems from practice to measure its generality level. A comprehensive performance analysis is conducted using a group of selection hyper-heuristics only involving heuristic selection and move acceptance mechanisms from the literature. The analysis provides strong conclusions about when a hyper-heuristic with certain characteristics has advantages or disadvantages.Finally, GIHH is tested on other challenging combinatorial optimisation problems under different empirical conditions. The computational results indicate that GIHH is effective in solving the target instances from distinct problem domains. Additionally, GIHH won the first international cross domain heuristic search challenge 2011 against 19 high-level algorithms developed by the other academic competitors. The winning hyper-heuristic was then used to investigate the performance and contribution of low-level heuristics while simultaneously solving three problems with routing and rostering characteristics. This completely new application of a hyper-heuristic offers promising perspectives for supporting dedicated heuristic development.nrpages: 282status: publishe