Multi-Objective Hyper-heuristics and their Application to Water Distribution Network Design
Thesis or dissertation
University of Exeter
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.
A thesis on the topic of multi-objective hyper-heuristics (selective and generative) applied to problems from hydro-informatics.
Kent McClymont, Ed Keedwell, Dragan Savić and Mark Randall-Smith (2012): A General Multi-objective Hyper-Heuristic for Water Distribution Network Design with Discolouration Risk, Journal of Hydroinformatics, doi:10.2166/hydro.2012.022
K. McClymont and E. C. Keedwell (2011): Deductive Sort and Climbing Sort: New Methods for Non-Dominated Sorting, Evolutionary Computation. Spring 2012, Vol. 20, No. 1, Pages 1-26.
K. McClymont, E. C. Keedwell and D. Savić (2012): Automated Construction of Fast Heuristics for the Water Distribution Network Design Problem, Proceedings of the 10th International Conference on Hydroinformatics (HIC 2012), July 14-18, Hamburg, Germany.
K. McClymont and E. C. Keedwell (2011): Markov chain Hyper-heuristic (MCHH): an Online Selective Hyper-heuristic for Multi-objective Continuous Problems, Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO 2011), Pages 2003-2010, Dublin, Ireland, ACM: New York, USA.
K. McClymont and E. C. Keedwell (2011): Benchmark Multi-objective Optimisation Test Problems with Mixed Encodings, IEEE Congress on Evolutionary Computation (CEC 2011), Pages 2131-2138, 5-8 June, USA.
K. McClymont, E. C. Keedwell, D. Savić and M. Randall-Smith (2011): A Hyper-heuristic Approach to Water Distribution Network Design, Urban Water Management: Challenges and Oppurtunities - Computing and Control for the Water Industry (CCWI 2011), 5-7 September, Exeter, UK.
K. McClymont, D. Walker, E. C. Keedwell, R. Everson, J. Fieldsend, D. Savić and M. Randall-Smith (2011): Novel Methods for Ranking District Metered Areas for Water Distribution Network Maintenance Scheduling, Urban Water Management: Challenges and Oppurtunities - Computing and Control for the Water Industry (CCWI 2011), 5-7 September, Exeter, UK.
M. Randall-Smith, J. Collingbourne, J. Harvey and K. McClymont (2011): Targeting Water Distribution Network Interventions for the Cost-Effective Mitigation of Discolouration Risk: a Case Study, Urban Water Management: Challenges and Oppurtunities - Computing and Control for the Water Industry (CCWI 2011), 5-7 September, Exeter, UK.
K. McClymont, E. C. Keedwell, D. Savić and M. Randall-Smith (2010): Mitigating Discolouration Risk with Optimised Network Design, The 9th International Conference on Hydroinformatics (HIC 2010), Tianjin, China.
K. McClymont and E. C. Keedwell (2010): Optimising Multi-Modal Polynomial Mutation Operators for Multi-Objective Problem Classes, IEEE Congress on Evolutionary Computation (CEC 2010), 18-23 July, Barcelona.
K. McClymont and Z. Wood (2011): A Classification of Heuristics, The Postgraduate Conference for Computing: Applications and Theory (PCCAT), Exeter.
PhD in Computer Science