Efficient multi-objective optimal design of water distribution networks on a budget of simulations using hybrid algorithms
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:
The vector function f maps the decision space Ω into the objective space, 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 , and its image 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)
Looped water distribution networks design using a resilience index based heuristic approach
Urban Water
(2000)- et al.
Design of optimal water distribution systems
Water Resources Research
(1977) - et al.
A metamodeling approach to water distribution system optimization
- et al.
PESA-II: region-based selection in multiobjective optimization
- et al.
Water distribution network design optimization: simulated annealing approach
Journal of Water Resources Planning and Management
(1999) - et al.
An improved genetic algorithm for pipe network optimisation
Water Resources Research
(1996) Evolutionary Computation
(2002)- 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...
Ant algorithms for discrete optimization
Artificial Life
Optimal reliability-based design of pumping and distribution systems
Journal of Hydraulic Engineering
Optimization of water distribution network design using the shuffled frog leaping algorithm
Journal of Water Resources Planning and Management
The simultaneous multi-objective optimization of Anytown pipe rehabilitation, tank sizing, tank siting and pump operation schedules
A modified linear programming gradient method for optimal design of looped water distribution networks
Water Resources Research
A two-phase decomposition method for optimal design of looped water distribution networks
Water Resources Research
Harmony search optimization: application to pipe network design
International Journal of Modelling and Simulation
A new heuristic optimization algorithm: harmony search
Simulation
Water Distribution System Optimization
Tabu search – part I
ORSA Journal on Computing
Messy genetic algorithms: motivation, analysis and first results
Complex System
Genetic algorithms in pipeline optimization
Journal of Computing in Civil Engineering
Reliability-constrained pipe network model
Journal of Hydraulic Engineering, ASCE
An integrated approach to the layout and design of water distribution networks
Civil Engineering Systems
Reliability analysis of water distribution systems
Journal of Environmental Engineering, ASCE
Cited by (90)
Enhanced watershed model evaluation incorporating hydrologic signatures and consistency within efficient surrogate multi-objective optimization
2024, Environmental Modelling and SoftwareA parallel approximate evaluation-based model for multi-objective operation optimization of reservoir group
2023, Swarm and Evolutionary ComputationImproved MOSADE algorithm incorporating Sobol sequences for multi-objective design of Water Distribution Networks
2022, Applied Soft ComputingCitation 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.
A multi-objective adaptive surrogate modelling-based optimization algorithm for constrained hybrid problems
2022, Environmental Modelling and Software