Incorporating Domain Expertise into Evolutionary Algorithm Optimisation of Water Distribution Systems
Johns, Matthew Barrie
Thesis or dissertation
University of Exeter
Evolutionary Algorithms (EAs) have been widely used for the optimisation of both theoretical and real-world non-linear problems, although such optimisation methods have found reasonably limited utilisation in fields outside of the academic domain. While the causality of this limited uptake in non-academic fields falls outside the scope of this thesis, the core focus of this research remains strongly influenced by the notions of solution feasibility and making optimisation methods more accessible for engineers, both factors attributed to low EA adoption rates in the commercial space. This thesis focuses on the application of bespoke heuristic methods to the field of water distribution system optimisation. Water distribution systems are complex entities that are difficult to model and optimise as they consist of many interacting components each with a set of considerations to address, hence it is important for the engineer to understand and assess the behaviour of the system to enable its effective design and optimisation. The primary goal of this research is to assess the impact that incorporating water systems knowledge into an evolution algorithm has on algorithm performance when applied to water distribution network optimisation problems. This thesis describes the development of two heuristics influenced by the practices of water systems engineers when designing water distribution networks with the view to increasing an algorithm’s performance and resultant solution feasibility. By utilising heuristics based on engineering design principles and integrating them into existing EAs, it is found that both engineering feasibility and general algorithmic performance can be notably improved. Firstly the heuristics are applied to a standard single-objective EA and then to a multi-objective genetic algorithm. The algorithms are assessed on a number of water distribution network benchmarks from the literature including real-world based, large scale systems and compared to the standard variants of the algorithms. Following this, a set of extensive experiments are conducted to explore how the inclusion of water systems knowledge impacts the sensitivity of an evolutionary algorithm to parameter variance. It was found that the performance of both engineering inspired algorithms were less sensitive to parameter change than the standard genetic algorithm variant meaning that non-experts in the field of meta-heuristics will potentially be able to get much better performance out of the engineering heuristic based algorithms without the need for specialist evolutionary algorithm knowledge. In addition this research explores the notion that visualisation techniques can provide water system engineers with a greater insight into the operation and behaviour of an evolutionary algorithm. The final section of this thesis presents a novel three-dimensional representation of pipe based water systems and demonstrates a range of innovative methods to convey information to the user. The interactive visualisation system presented not only allows the engineer to visualise the various parameters of a network but also allows the user to observe the behaviour and progress of an iterative optimisation method. Examples of the combination of the interactive visualisation system and the EAs developed in this work are shown to enable the user to track and visualise the actions of the algorithm. The visualisation aggregates changes to the network over an EA run and grants significant insight into the operations of an EA as it is optimising a network. The research presented in this thesis demonstrates the effectiveness of integrating water system engineering expertise into evolutionary based optimisation methods. Not only is solution quality improved over standard methods utilising these new heuristic techniques, but the potential for greater interaction between engineer, problem and optimiser has been established.
Johns M, Keedwell EC, Savic D. (2012) Adaptive Locally Constrained Genetic Algorithm for Least-Cost Water Distribution Network Design, 10th International Conference on Hydroinformatics, Hamburg, Germany, 14th - 18th Jul 2012.
Johns M, Keedwell EC, Savic D. (2013) Pipe Smoothing Genetic Algorithm for Least Cost Water Distribution Network Design, Genetic and Evolutionary Computation Conference, Amsterdam, 5th - 10th Jul 2013.
Johns M, Keedwell EC, Savic D. (2014) Adaptive Locally Constrained Genetic Algorithm For Least-Cost Water Distribution Network Design, Journal of Hydroinformatics, volume 16, no. 2, pages 288-301, DOI:10.2166/hydro.2013.218.
Johns M, Keedwell EC, Savic D. (2014) Interactive 3D Visualisation of Optimisation for Water Distribution Systems,11th International Conference on Hydroinformatics, New York, 17th - 21st Aug 2014.
Johns M, Keedwell EC, Savic D. (2014) Multi-objective Pipe Smoothing Genetic Algorithm for Water Distribution Network Design, 11th International Conference on Hydroinformatics, New York, 17th - 21st Aug 2014.
Keedwell EC, Johns M, Savic D. (2015) Spatial and Temporal Visualisation of Evolutionary Algorithm Decisions in Water Distribution Network Optimisation, VizGEC Workshop, Genetic and Evolutionary Computation Conference, 2015, Madrid, Spain, 10th - 15th Jul 2015.
PhD in Computer Science