Multi-Objective Hyper-heuristics and their Application to Water Distribution Network Design
Date: 1 October 2012
Thesis or dissertation
University of Exeter
PhD in Computer Science
Hyper-heuristics is a new field of optimisation which has recently emerged and is receiving growing exposure in the research community and literature. Hyper-heuristics are optimisation methods which are designed with a high level of abstraction from any one specific problem or class of problems and therefore are more generally applicable ...
Hyper-heuristics is a new field of optimisation which has recently emerged and is receiving growing exposure in the research community and literature. Hyper-heuristics are optimisation methods which are designed with a high level of abstraction from any one specific problem or class of problems and therefore are more generally applicable than specialised meta-heuristic and heuristic methods. Instead of being designed to solve a specific real-world problem, hyper-heuristics are designed to solve the problem of heuristic generation and selection. As such, hyper-heuristics can be thought of as methods for optimising the operations of an optimisation process which finds good solutions to a problem as a by-product. This approach has been shown to be very effective and in some cases provides improvement in search performance as well as reducing the burden associated with tailoring meta-heuristics which is often required when solving new problems. In this thesis, the hypothesis that hyper-heuristics can be competitively applied to real-world multi-objective optimisation problems such as the water distribution design problem is tested. Although many single-objective hyper-heuristics have been proposed in the literature, only a few multi-objective methods have been proposed. This thesis explores two different novel multi-objective hyper-heuristics: one designed for generating new specialised heuristics; and one designed for solving the online selection of heuristics. Firstly, the behaviour of a set of heuristics is explored to create a base understanding of different heuristic behavioural traits in order to better understand the hyper-heuristic behaviours and dynamics later in the study. Both approaches are tested on a range of benchmark optimisation problems and finally applied to real-world instances of the water distribution network design problem where the selective hyper-heuristics is demonstrated as being very effective at solving this difficult problem. Furthermore, the thesis demonstrates how heuristic selection can be improved by incorporating a greater level of information about heuristic performance, namely the historical joint performance of different heuristics, and shows that exploiting this sequencing information in heuristic selection can produce highly competitive results.
Item views 0
Full item downloads 0