Efficient multi-objective optimal design of water distribution networks on a budget of simulations using hybrid algorithms

https://doi.org/10.1016/j.envsoft.2008.06.008Get rights and content

Abstract

The design of water distribution networks is a large-scale combinatorial, non-linear optimisation problem, involving many complex implicit constraint sets, such as nodal mass balance and energy conservation, which are commonly satisfied through the use of hydraulic network solvers. These problem properties have motivated several prior studies to use stochastic search optimisation, because these derivative-free global search algorithms have been shown to obtain higher quality solutions for large network design problems. Global stochastic search methods, however, require many iterations to be performed in order to achieve a satisfactory solution, and each iteration may involve running computationally expensive simulations. Recently, this problem has been compounded by the evident need to embrace more than a single measure of performance into the design process, since by nature multi-objective optimisation methods require even more iterations. The use of metamodels as surrogates for the expensive simulation functions has been investigated as a possible remedy to this problem. However, the identification of reliable surrogates is not always a viable alternative. Under these circumstances, methods that are capable of achieving a satisfactory level of performance with a limited number of function evaluations represent a valuable alternative. This paper represents a first step towards filling this gap. Two recently introduced multi-objective, hybrid algorithms, ParEGO and LEMMO, are tested on the design problem of a real medium-size network in Southern Italy, and a real large-size network in the UK under a scenario of a severely restricted number of function evaluations. The results obtained suggest that the use of both algorithms, in particular LEMMO, could be successfully extended to the efficient design of large-scale water distribution networks.

Introduction

Present day water distribution networks are complex systems that require a high level of investment for their construction and maintenance. For example, the current rates of activity on water infrastructure renewal in the UK imply that that the average sewer has to last around 700 years. Similar investment costs apply to water distribution systems too. Motivated by the compelling need to improve the efficiency and reduce the associated costs of construction and maintenance of these systems, practitioners have progressively moved away from manual design based on experience in favour of automatic or semi-automatic optimal procedures.

Water distribution system design is one of the most researched areas where optimisation techniques are heavily applied (Sacks et al., 1989). Hundreds of papers and reports on approaches have been developed over the past few decades and several reviews of the state-of-the-art in water distribution optimisation are also available (Lansey, 2000, Walski, 1985). In spite of considerable development in this field, optimisation techniques have not been accepted in practice and Walski (2001) recently highlighted several practical reasons for that. The main ones being that (i) it is difficult for practitioners to define objective functions and constraints; (ii) there is not a single design flow for which the system should be designed, (iii) optimisation fails to account for the fact that a total distribution system is not built all at once, and (iv) optimisation tends to reduce costs by reducing the diameter of or completely eliminating pipes thus leaving the system with insufficient capacity to respond to pipe breaks or demands that exceed design values without failing to achieve required performance levels.

The design of water distribution networks is often viewed as a single-objective, least-cost optimisation problem with pipe diameters acting as the primary decision variables. The optimisation problem of least-cost pipe sizing is a non-linear, discrete combinatorial optimisation problem. It is non-linear because the head-loss relationship and discrete because pipe diameters are produced in distinct diameters only. Optimal design problems of realistic size become intractable for enumeration techniques. This is because of the exponential growth of the problem size with the increase in number of discrete decisions. The problem is compounded if several design criteria have to be considered at the same time, such as robustness, reliability and performance.

In attempting to address the issues raised by Walski (2001) and those of several decision variables, multi-objective optimisation approaches seem to be most promising. However, multi-objective optimisation techniques suffer from the lost of efficiency when compared to its single-objective counterpart. Typically, they required tens, if not hundred of thousand of total number of simulation runs. Hence, it is not practical to apply conventional multi-objective approaches to real world water distribution networks running under “extend period simulation” mode even if each network simulation takes only several seconds.

On these premises, we test the performance of two recently introduced multi-objective, hybrid algorithms, ParEGO (Knowles, 2006) and LEMMO (Jourdan et al., 2006), on the design problem of a real medium-size network in Southern Italy, and a real large-size network in UK under a scenario of a severely restricted number of function evaluations. ParEGO builds an approximation of the response surface of the problem using a surrogate model. This is iteratively exploited to search for the most promising solution, which is subsequently evaluated using the true simulation function, and used to update it. LEMMO integrates a symbolic learning component within a Multi-objective Evolutionary Algorithm (MOEA). As the search progresses, the solutions previously found by the MOEA are used to derive induction rules, which are applied to the new solutions generated to improve them.

The results are then compared to the best solutions known to this problem, which were obtained using PESA-II (Corne et al., 2001), a well-known MOEA. Prior to this study, ParEGO was only shown to perform very well on a suite of analytical functions, but it was never applied to the class of problems addressed herein. On the contrary, recent results on one small and one medium-size network (Jourdan et al., 2006) showed that LEMMO is a promising way to improve and accelerate the search process.

The paper is organized as follows: first we present the problem of the multi-objective optimal design of water distribution network addressed herein. An outline of the methodological framework is given next, with a detailed explanation of the hybrid algorithms tested. Then, the description of the case studies is provided, followed by the experimental setup. Finally, the results are presented and analyzed with some concluding discussion.

Section snippets

Optimisation of water distribution systems

Over the last three decades, a significant number of optimisation methods have been applied to water distribution system design and maintenance planning, including dynamic programming or enumeration techniques (Alperovits and Shamir, 1977, Duan et al., 1990, Fujiwara et al., 1987, Fujiwara and Khang, 1990, Gessler and Walski, 1985, Goulter and Morgan, 1985, Quindry et al., 1981). The majority of these, however, are local search methods requiring derivative information and complex simulation

Problem statement

Herein, the water distribution network design is formulated, for a gravitational one-loading system, as a bi-objective optimisation problem with a selection of pipe sizes as the decision variables. The pipe layout and its connectivity, nodal demand, and minimum head requirements are assumed known. In general terms, this problem can be stated as finding the pipe sizes that minimise the total cost and head deficit while satisfying the following conditions.

  • Conservation of mass: inflows and

Methodological framework

A multi-objective problem (MOP) can be generally described by the following equation:minxΩf(x)=(f1(x),f2(x),,fk(x))T

The vector function f maps the decision space Ω into the objective spacef(Ω)Rk, where k is the number of objectives to be simultaneously optimized for. If the objectives are conflicting, the solution of the MOP is the set of non-dominated solutions called the Pareto Set, referred to as P, and its image FP=f(P) is called the Pareto Front. The notion of dominance is concisely

ParEGO

Various algorithms have been proposed so far that make use of surrogate models to approximate the computationally expensive simulation functions. Among these, EGO (Jones et al., 1998), a global optimisation algorithm that resorts to a version of the design and analysis of computer experiments (DACE) (Sacks et al., 1989) model based on Gaussian processes (Kriging). This algorithm was shown to perform well when approximating functions with local smoothness and low dimension under a scenario of

LEMMO

Another methodology designed to limit the number of expensive function evaluations is based on the hybridisation of the evolutionary search with machine learning techniques. The Learnable Evolution Model (LEM) (Michalski, 2000) integrates a symbolic learning component within the evolutionary framework. As the search progresses, the symbolic learning component exploits all the solutions previously found, or a selection of them, to build a decision tree (classifier); some of these solutions are

Case studies

The performance of the two hybrid algorithms were assessed and compared to those generated using PESA-II (our baseline MOEA) on two network design problems, involving the steady-state hydraulic performance of a medium-size network and the extended period simulation of a larger one. The details are given below.

Experimental setup

Each of the algorithms considered in this study involve some randomness, usually in the form of probability of occurrence of the genetic operators and in the sampling procedure of the initialisation stage. In order to filter the impact of this randomness on the results, 10 optimisation runs were performed with each algorithm. All of them were implemented using binary coding.

The application of genetic operators to feasible solutions may generate infeasible ones. Infeasible solutions may also be

Results and discussion

As previously stated, the results obtained with PESA-II are considered as the best approximation known to the true Pareto Front of the problem, and therefore they represent the baseline for comparing the remaining algorithms.

Conclusions

The aim of this work was to test the performance of two recently presented multi-objective hybrid algorithms, LEMMO and ParEGO, on the design problem of a medium and a large-size network proposed in the case studies, under a scenario of the constrained budget of expensive hydraulic simulations. In order to assess the quality of the solutions generated, they were compared to the best known solutions to this problem, which were obtained using PESA-II, a well-known MOEA, run on a full-length

Acknowledgments

The authors thank Prof. Giustolisi from the Technical University of Bari for providing the hydraulic solver, the network model and the data used for the first case study of this work.

References (58)

  • E. Todini

    Looped water distribution networks design using a resilience index based heuristic approach

    Urban Water

    (2000)
  • E. Alperovits et al.

    Design of optimal water distribution systems

    Water Resources Research

    (1977)
  • D.R. Broad et al.

    A metamodeling approach to water distribution system optimization

  • D.W. Corne et al.

    PESA-II: region-based selection in multiobjective optimization

  • M. da Conceição Cunha et al.

    Water distribution network design optimization: simulated annealing approach

    Journal of Water Resources Planning and Management

    (1999)
  • G.C. Dandy et al.

    An improved genetic algorithm for pipe network optimisation

    Water Resources Research

    (1996)
  • K.A. De Jong

    Evolutionary Computation

    (2002)
  • K. Deb et al.

    A fast and elitist multiobjective genetic algorithm: NSGA-II

    IEEE Transactions on Evolutionary Computation

    (2002)
  • Deb, K., Goel, T., 2000. Controlled Elitist Non-dominated Sorting Genetic Algorithms for Better Convergence. Technical...
  • M. Dorigo et al.

    Ant algorithms for discrete optimization

    Artificial Life

    (1999)
  • N. Duan et al.

    Optimal reliability-based design of pumping and distribution systems

    Journal of Hydraulic Engineering

    (1990)
  • Eberhart, R.C., Kennedy, J., 1995. A new optimizer using particle swarm theory. In: Proceedings of the Sixth...
  • M.M. Eusuff et al.

    Optimization of water distribution network design using the shuffled frog leaping algorithm

    Journal of Water Resources Planning and Management

    (2003)
  • R. Farmani et al.

    The simultaneous multi-objective optimization of Anytown pipe rehabilitation, tank sizing, tank siting and pump operation schedules

  • O. Fujiwara et al.

    A modified linear programming gradient method for optimal design of looped water distribution networks

    Water Resources Research

    (1987)
  • O. Fujiwara et al.

    A two-phase decomposition method for optimal design of looped water distribution networks

    Water Resources Research

    (1990)
  • Z.W. Geem et al.

    Harmony search optimization: application to pipe network design

    International Journal of Modelling and Simulation

    (2002)
  • Z.W. Geem et al.

    A new heuristic optimization algorithm: harmony search

    Simulation

    (2001)
  • J. Gessler et al.

    Water Distribution System Optimization

    (1985)
  • Giustolisi, O., Berardi, L., Doglioni, A., Laucelli, D., 2005. Automatic robust design of water distribution systems in...
  • Giustolisi, O., Doglioni, A., 2005. A water distribution failure analysis. In: Proceedings of the eighth International...
  • F. Glover

    Tabu search – part I

    ORSA Journal on Computing

    (1989)
  • Goldberg, D.E., Deb, K., Kargupta, H., Harik, G.R., 1993. Rapid Accurate Optimization of Difficult Problems Using Fast...
  • D.E. Goldberg et al.

    Messy genetic algorithms: motivation, analysis and first results

    Complex System

    (1989)
  • D.E. Goldberg et al.

    Genetic algorithms in pipeline optimization

    Journal of Computing in Civil Engineering

    (1987)
  • I. Goulter et al.

    Reliability-constrained pipe network model

    Journal of Hydraulic Engineering, ASCE

    (1990)
  • I.C. Goulter et al.

    An integrated approach to the layout and design of water distribution networks

    Civil Engineering Systems

    (1985)
  • R. Gupta et al.

    Reliability analysis of water distribution systems

    Journal of Environmental Engineering, ASCE

    (1994)
  • Cited by (90)

    • Improved MOSADE algorithm incorporating Sobol sequences for multi-objective design of Water Distribution Networks

      2022, Applied Soft Computing
      Citation Excerpt :

      The WDN costs consist of the cost of components such as pipes, valves, etc., pumping cost, and cost of repair and maintenance; while reliability is a measure of the system performance considering the demand fulfillment by consideration of working and failure conditions. The WDN design problem can be formulated either as single-objective optimization problem considering minimization of cost and keeping reliability as a constraint [1–5] or multi-objective optimization problem considering simultaneous minimization of cost and maximization of reliability [6–11]. However, few past studies also recommended that WDNs should be designed using a multi-objective framework since it leads to a set of non-dominated solutions providing the least costs of WDNs for various reliability levels, which could be useful to the administrators to opt for the most appropriate solution as per the requirements.

    View all citing articles on Scopus
    View full text