Automated construction of evolutionary algorithm operators for the bi-objective water distribution network design problem using a genetic programming based hyper-heuristic approach

Abstract

The water distribution network (WDN) design problem is primarily concerned with finding the optimal pipe sizes that provide the best service for minimal cost; a problem of continuing importance both in the UK and internationally. Consequently, many methods for solving this problem have been proposed in the literature, often using tailored, hand-crafted approaches to more effectively optimise this difficult problem. In this paper we investigate a novel hyper-heuristic approach that uses genetic programming (GP) to evolve mutation operators for evolutionary algorithms (EAs) which are specialised for a bi-objective formulation of the WDN design problem (minimising WDN cost and head deficit). Once generated, the evolved operators can then be used ad infinitum in any EA on any WDN to improve performance. A novel multi-objective method is demonstrated that evolves a set of mutation operators for one training WDN. The best operators are evaluated in detail by applying them to three test networks of varying complexity. An experiment is conducted in which 83 operators are evolved. The best 10 are examined in detail. One operator, GP1, is shown to be especially effective and incorporates interesting domain-specific learning (pipe smoothing) while GP5 demonstrates the ability of the method to find known, well-used operators like a Gaussian. © IWA Publishing 2014J.