Towards a unified method to synthesising scenarios and solvers in combinatorial optimisation via graph-based approaches

Stone, Christopher Luciano

Abstract

Hyper-heuristics is a collection of search methods for selecting, combining and generating heuristics used to solve combinatorial optimisation problems. The primary objective of hyper-heuristics research is to develop more generally applicable search procedures that can be easily applied to a wide variety of problems. However, current hyper-heuristic architectures assume the existence of a domain barrier that does not allow low-level heuristics or operators to be applied outside their designed problem domain. Additionally the representation used to encode solvers differs from the one used to encode solutions. This means that hyper-heuristic internal components can not be optimised by the system itself. In this thesis we address these issues by using graph reformulations of selected problems and search in the space of operators by using Grammatical Evolution techniques to evolve new perturbative and constructive heuristics. The low-level heuristics (representing graph transformations) are evolved using a single grammar which is capable of adapting to multiple domains. We test our generators of heuristics on instances of the Travelling Salesman Problem, Knapsack Problem and Load Balancing Problem and show that the best evolved heuristics can compete with human written heuristics and representations designed for each problem domain. Further we propose a conceptual framework for the production and combination of graph structures. We show how these concepts can be used to describe and provide a representation for problems in combinatorics and the inner mechanics of hyper-heuristic systems. The final contribution is a new benchmark that can generate problem instances for multiple problem domains that can be used for the assessment of multi-domain problem solvers.

Citation

Stone, C. L. Towards a unified method to synthesising scenarios and solvers in combinatorial optimisation via graph-based approaches. (Thesis). Edinburgh Napier University. http://researchrepository.napier.ac.uk/Output/2707229

• Thesis Type: Thesis
• Deposit Date: Dec 1, 2020
• Publicly Available Date: Dec 1, 2020
• DOI: https://doi.org/10.17869/enu.2020.2707229
• Keywords: hyper-heuristic; search procedures; domain barrier
• Public URL: http://researchrepository.napier.ac.uk/Output/2707229
• Award Date: Jul 1, 2020