Improving the efficiency of multi-objective evolutionary algorithms through decomposition: An application to water distribution network design

Highlights

• The graph decomposition dramatically improves the optimization efficiency.

• The propagation method effectively evolves sub-network fronts to the full network front.

• The optimization strategy is demonstrated using real-world WDNs with high complexities.

• Provide an efficient decision-making tool for the water network optimization.

Abstract

Evolutionary algorithms (EAs) have been widely used in handling various water resource optimization problems in recent years. However, it is still challenging for EAs to identify near-optimal solutions for realistic problems within the available computational budgets. This paper introduces a novel multi-objective optimization method to improve the efficiency of a typically difficult water resource problem: water distribution network (WDN) design. In the proposed approach, a WDN is decomposed into different sub-networks using decomposition techniques. EAs optimize these sub-networks individually, generating Pareto fronts for each sub-network with great efficiency. A propagation method is proposed to evolve Pareto fronts of the sub-networks towards the Pareto front for the full network while eliminating the need to hydraulically simulate the intact network itself. Results from two complex realistic WDNs show that the proposed approach is able to find better fronts than conventional full-search algorithms (optimize the entire network without decomposition) with dramatically improved efficiency.

Introduction

Evolutionary algorithms (EAs) have been extensively used in dealing with a broad range of water resource problems over the past few decades (Nicklow et al., 2010, Maier et al., 2014). One issue exists in the use of EAs to solve large and complex optimization problems in water resources is that they are typically computationally very demanding, mainly caused by the high number of function calls to computationally expensive system simulation models and the extremely large search spaces defined by the problems. This results in difficulties for EAs to find near-optimal solutions for realistic problems using a time-feasible framework, particularly when many-objective evolutionary optimization is considered for managing complex environmental systems (Kasprzyk et al., 2012, Kasprzyk et al., 2013). The computational inefficiency has become a significant barrier for the wider uptake of EAs in water resource fields (Nicklow et al., 2010). This motivates an urgent need to increase EA's efficiency for solving various large, real-world optimization problems (Maier et al., 2014). This paper aims to address the inefficiency issue of EAs applied to one typical type of the difficult water resource problem: the design of water distribution networks (WDNs).

Multi-objective optimization for WDN design has been the subject of extensive investigation over the past ten years. The main focus has been on the development or application of various multi-objective evolutionary algorithms (MOEAs), such as the NSGA-II (Prasad and Park, 2004), the SPEA (Farmani et al., 2005), and the MOCE method (Perelman and Ostfeld, 2008). The majority of existing MOEAs face significant challenges in finding near-optimal fronts for large, real-world WDN design problems using computational budgets typically available in practice (di Pierro et al., 2009, Ostfeld, 2012). The need of hydraulic simulation for large WDNs and the high dimensionality of the search space impose considerable computational expenditure during the MOEA optimization process (Fu et al., 2012).

Attempts have previously been made to improve the efficiency of multi-objective optimization for WDNs, generally by solving the problems with one of two approaches, either: (i) the reduction of the computational overhead of the hydraulic simulation model or (ii) the development of advanced optimization algorithms to explore the complex search space more efficiently. In terms of reducing the computational overhead of the simulation model, a common approach has been the use of the metamodelling techniques (Bi and Dandy, 2014), in which Artificial Neural Networks (ANNs) are used to replace the full hydraulic simulation model. Difficulties with the utilization of the metamodelling approach, however, include the poor approximation accuracy for large WDNs and misleading system representations for complex response surfaces inherent in WDN optimization problems (Razavi et al., 2012). In parallel with the developments of metamodelling approaches, studies have also been conducted to manage the simulation of large size real WDNs such as the forest-core partitioning algorithm (Simpson et al., 2014) and the linearization method (Alvisi and Franchini, 2014).

Efforts to develop advanced optimization algorithms for efficiently exploring complex search spaces have resulted in several interesting investigations. di Pierro et al. (2009), for example, developed two hybrid algorithms, PArEGO and LEMMO, for handling WDN multi-objective design. The authors reported, however, that while the efficiency of the two hybrid optimization methods was improved relative to standard MOEAs, this was at the expense of the quality of the optimal fronts. Fu et al. (2012) later proposed a preconditioning method to allow an MOEA to exclusively focus on promising regions determined by global sensitivity analysis. The efficiency and effectiveness of the sensitivity analysis based method were demonstrated using two small networks with 21 and 35 decision variables. Performance on large networks (of say WDNs with more than 100 decision variables), however, remains unclear.

This current study proposes a new multi-objective optimization method for tackling WDN design problems, attempting specifically to efficiently provide good quality near-optimal Pareto fronts and effectively handle large WDNs. This is achieved by the incorporation of graph decomposition techniques in the optimization of WDNs.

In practice, it is very common for a WDN to have multiple trees, blocks and bridges according to its connectivity properties (Deuerlein, 2008). Tree networks are normally scattered at the ends of a large WDN, while blocks are looped portions of the networks that typically represent different supply zones or regions, which are connected by the bridges (pipes). Motivated by such a common property of water networks, a combined graph decomposition and MOEA method is conceived that could be used for finding optimal fronts for large WDN design problems in a computationally efficient manner.

In recent years, the multi-objective differential evolution (MODE) algorithm has been demonstrated to outperform other existing MOEAs such as NSGA-II in terms of searching ability. However, such conclusions were often made based on problems with continuous search spaces, such as reservoir operation (Reddy and Kumar 2007) and hydrological model calibration problems (Guo et al., 2014). There is still a lack of empirical knowledge on the performance of the MODE algorithm applied to the WDN design problems, whose search spaces are significantly higher nonlinearity, dimensionality, and complexity than the continuous search problems. Therefore, we have developed a MODE algorithm and compared its performance with one of the most widely used MOEAs-NSGA-II (Deb et al., 2002) in terms of efficiently offering Pareto fronts for the WDN design problems.

The main innovations within the proposed optimization method include (i) the partitioning of the original large-scale multi-objective optimization problem into a series of smaller computationally manageable sub-problems (sub-networks) using graph decomposition techniques; (ii) instead of optimizing the full network as a whole, sub-networks are separately optimized and a propagation method is proposed to evolve the Pareto fronts of the sub-networks towards the Pareto front for the original full network without the need to hydraulically simulate the intact network itself; and (iii) the development of MODE algorithm as well as the comparison between the MODE and NSGA-II in terms of optimizing WDNs. Item (ii) is the most novel aspect of the proposed optimization approach as presented in this paper.

The remainder of this paper is organized as follows. Section 2 presents the multi-objective optimization model for the WDN design problems. Section 3 describes the details of the proposed method, followed by the results of the proposed method, the MODE and the NSGA-II applied to three WDN case studies in Section 4. Finally, Section 5 presents the conclusion and the future work of the proposed method.