A new multi-objective evolutionary algorithm for the optimization of water distribution networks

Previous research on the optimization of the water distribution network (WDN) focuses only on reducing the network cost, i.e. single-objective optimization. This optimization leaves us with a least-cost solution that saves a lot of capital when compared with other options. However, the least-cost solution may not be reliable during failure, which may lead to a sudden increase in the pressure in the distribution network, due to the choice of diameters that are selected just to satisfy the minimum pressure requirement. Also, WDN is not only an expensive but complex engineering problem due to the involvement of non-linear relations between discharge and head, its discrete nature, and various constraints of the problem. Thus, redesign is not possible as well as not feasible at any stage of the design. This is where the need for multi-objective optimization of WDN is felt, i.e. designing the network with various objectives such that the design is not only cheap but also reliable. Such networks can function under different failure scenarios. The failure in WDN occurs either due to hydraulic or mechanical reasons. Hydraulic failure refers to the deficiency in the pressure head due to the uncertainty or sudden increase in the nodal demand or pipe roughness. Mechanical failure occurs due to the failure of WDN components such as pipe, valves, etc. To record the response of the network toward these failures, reliability is determined. However, there is not a universally accepted definition for the reliability of WDN. Broadly, it is defined as the ability of the network to meet demand under different failure scenarios. Many authors have defined and determined the reliability of WDN, both hydraulic and mechanical, by determining the ratio of available flow to the flow required, taking into consideration the probability of failure in each scenario (Creaco et al. 2016). The minimum cut-set method was used by Su et al. (1987) which was later used by other authors (Sirsant & Reddy 2017) to determine the mechanical reliability. Bhave & Gupta (2004) incorporated the fuzziness in demand for determining the hydraulic reliability of WDN. Monte Carlo simulation is also used for generating the various random samples that are later used for determining the hydraulic reliability (Sirsant & Janga Reddy 2018) of the WDN. However, such techniques are not only complex but require a large number of hydraulic computations when implemented. This adds to the computational efforts required by the optimization technique. To ease the process of determining the reliability of WDN various surrogate measures are proposed and have been used extensively over the last decade. Todini (2000) was given the credit for proposing the first-ever reliability surrogate measure (RSM) called resilience index (RI). Thereafter many indices such as the network resilience index (NRI) (Prasad & Park 2004), modified resilience index (MRI) (Jayaram & Srinivasan 2008), minimum surplus head index, and flow uniformity index (Moosavian & Lence 2020) have been proposed and implemented to different problems. Many studies compared the different reliability indices under various failure scenarios. Raad et al. (2010) compared four reliability indices namely RI, NRI, flow entropy, and mixed reliability index for three WDN using the AMALGAM optimization algorithm. They compared the solutions obtained by different reliability indices for demand satisfaction and found RI to be a better performer. Baños et al. (2011) incorporated the Strength Pareto Evolutionary Algorithm 2 (SPEA2) for the multi-objective design of Two Loop and Hanoi networks using RI, NRI, and MRI. Various over-demand scenarios are used for comparison of the indices and concluded RI to be a better performer for Two Loop network and NRI for Hanoi network. Greco et al. (2012) found that, unlike entropy, the robustness of any network is better represented by its resilience. Anytown benchmark network was optimized by Atkinson et al. (2014) for both hydraulic and mechanical reliability. According to them the solutions with high entropy are found to be better performers under mechanical failures. Liu et al. (2017) developed two new reliability surrogate measures, Pipe Hydraulic Resilience Index (PHRI) and Available Power Index (API), and compared them with four available reliability indices. Demand uncertainty is simulated using stochastic sampling that is distributed normally. PHRI and API outperform RI, MRI, NRI, and diameter-sensitive flow uniformity. Most recently a detailed comparative analysis was carried out by Jeong & Kang (2020). The authors addressed the most complicated issue faced by water engineers, i.e., which reliability index should be selected for the different hydraulic scenarios. They developed various correlations between hydraulic measures and reliability index so that the correct reliability index is chosen for the different hydraulic measures, for example, PHRI index performed better for the single pipe failure scenario, for fire flow scenarios RI, MRI and API performs better, and so on. Thus researchers can select the hydraulic scenarios and choose the relevant reliability index accordingly. This may prove very efficient for hydraulic engineers.

Multi-objective (MO) optimization leads to the generation of various non-dominated solutions, which when spread across the objectives, and is termed as Pareto Front (PF), unlike in single-objective optimization the result of which for the design of WDN is a single solution with minimum cost. The designer can choose any solution from the non-dominated set based on the requirements, as all the solutions present in the Pareto front are feasible and satisfy all the constraints of the problem. Various multi-objective evolutionary algorithms (MOEA) have been applied to the design of WDN. Farmani et al. (2005) applied Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and SPEA2 to Newyork Tunnel and Hanoi network. Minimum cost and maximum head deficiency were two objectives that were considered. The authors found SPEA2 slightly better than NSGA-II. Ostfeld et al. (2014) applied MOGA to three WDNs and reconfirms that the reliability of network increases with its cost. RI and network costs were optimized using MOGA. A memetic algorithm (MA) for two objectives for reducing cost and pressure deficit was applied by Barlow & Tanyimboh (2014). The algorithm outperformed NSGA-II when tested on two benchmark problems. Wang et al. (2015) developed the best-known Pareto Fronts (BKPF) using cost and NRI for different water supply networks using five MOEAs. Monsef et al. (2019) tested three MOEAs, namely NSGA-II, Multi-objective Differential Evolution (MODE), and Multi-objective Particle Swarm Optimization (MOPSO), on four WDNs. Minimum cost and maximum NRI were considered as two objectives of the problem. All three algorithms were able to produce the PF, however, the PF obtained by MODE was found to be more accurate. Fuso et al. (2020) incorporated the GALAXY algorithm for generating the PF. The author also developed various performance indices (PI) to access the network performance under different failure scenarios. Moghaddam et al. (2021) used the GANetXL (an excel tool for optimization using a Genetic Algorithm) for optimizing the network and used statistics to determine the critical pipes and analyze the failure of these pipes for three networks. The author finds the NRI to be a poor performer when compared with other indices. All the above-mentioned MOEA are sensitive to the parameters and required extensive fine-tuning of the parameters for their proper convergence which further enhances the complexity of the MO design. Fine-tuning is a rigorous exercise that needs to be done ‘n’ times for ‘n’ different problems since the algorithm once tuned cannot be directly used for another problem. Jaya optimization algorithm has been used widely in different fields. Therefore it will be interesting and novel to test this parameter-less algorithm for a non-linear polynomial hard discrete multi-objective design problem. Hence the main objective of the present work is to introduce the MO-JAYANET, a completely parameter-less multi-objective optimization model for the design of WDN. The algorithm does not require any algorithm-specific parameters as required by other meta-heuristic techniques, in addition to this, it is also free from penalty parameters. Only common parameters like population size and iteration numbers are required that need to be tuned. These parameters are required for any of the evolutionary algorithms in addition to its algorithm-specific parameters. The MO-JAYANET algorithm is developed and tested on two benchmark networks using three reliability indices. PFs are plotted and the maximum reliability solution of the three indices is checked for various failure scenarios.

Equation (3) defines the continuity at any node, where Q_I, Q_O, q_k are the inflow, outflow, and demand at any node k, nn are total nodes in the network. The constraint of energy conservation in any loop is defined by Equation (4), where nl are total loops in the network, hfi is frictional head loss. For any design in the distribution network, the pressure available at any node must be greater than the prescribed minimum pressure head and this constraint is defined by Equation (5) where h_avl and h_min are available and minimum pressure head required. The diameters for the design of WDN must be selected from the set of commercially available diameters, i.e. {D}, as defined in Equation (6).

The second objective of the optimization model is to maximize the reliability of the network, which is achieved by maximizing the RSM. The present work uses the following reliability surrogate measures as the second objective.

The optimization technique Jaya was introduced by Rao (2016). Like any other meta-heuristic technique, Jaya begins its implementation by generating a random initial population. The main advantage behind choosing the Jaya technique for the development of a multi-objective optimization model for WDN is its simple structure along with the parameterless nature of the Jaya. Being parameterless, Jaya skips all the computational efforts that are otherwise required to fine-tune any Evolutionary Algorithm (EA). The formulation of the MO-JAYANET model is explained below.

• 1.
  The random initial population is generated within the lower and upper bound of the decision variable:

  

  (11)

  where the random value of the decision variable is represented by x_ij, rand_ij is any random number generated between 0 and 1 that is distributed uniformly. are the lower and upper limits, respectively of the decision variable.
• 2.
  Since the generated initial population is continuous, thus it is converted to the discrete initial population by applying the average discrete constraint rule as given in Equation (12):

  

  (12)

  where x_i is commercially available pipe diameters. The available pipe diameters are arranged in increasing order of magnitude and the nearby diameters between which the value of x_ij lies are selected. is the diameter smaller than x_ij and is the diameter larger than x_ij. Thus, if the value of x_ij is less than the average of the selected diameters (smaller and larger), x_ij becomes else If the value of x_ij is smaller than the least value among the commercially available diameters then it is replaced by the least commercially available diameter. Similarly, if the value of x_ij is greater than the largest value among the commercially available diameter, it is replaced by the largest commercially available diameter. The discretization of the continuous diameter is explained with the help of an example. Consider the Hanoi network, its commercially available diameters are given in Table 1.

• • i.

    Arrange the commercially available diameters in increasing order i.e., 304.8, 406.4, 508, 609.6, 762, 1016.

  • ii.

    Suppose the continuously generated diameter is 931.81.

  • iii.

    When compared with the available diameters we can say that 931.81 lie in between 762 and 1,016.

  • iv.

    Calculate an average of 762 and 1016 which is 889.

  • v.

    931.81 (continuously generated diameter) is greater than the average value of 889, thus 931. 81 is replaced by 1016. If the continuously generated value is less than the average of two commercially available diameters then it will be replaced by the smaller of the two chosen commercially available diameters.

  • vi.

    If the continuously generated diameter is 300, then this value is less than the least available commercial diameter, hence it is replaced by 304.8. The same applies to the value generated greater than 1016, it will be replaced by 1016.

• 3.

  After the discretization of the initial population, these discrete diameters are passed to the simulation software, EPANET 2.0 (Rossman 2000), and discharge, head, and pressure values at all demand nodes are determined and noted. Once these parameters are known, the reliability of the network can be calculated using the reliability indices described in Equations (7), (9) and (10) (applying one at a time). The total cost of the network is also determined using Equation (1). However, no penalty is imposed on infeasible solutions in this methodology, thus fitness value includes only the cost of the network.

• 4.
  The next step is to calculate the constraint violation (CV) for each solution in the population using Equation (13):

  

  (13)

  where nc is the number of nodes for which and nn is the number of demand nodes. For example, if there are 10 nodes at which pressure is less than the minimum pressure requirement, then CV is the summation of all the 10 nodes pressure differences from the minimum pressure requirement. A CV tells about the total violation a solution has in terms of pressure. It is obvious to state that the solution with less CV value is superior to the solution with more CV value.
• 5.
  The constraint violation ratio (CVR) is next determined for every solution in the population using Equation (14):

  

  (14)

  where CV_i is the constraint violation of solution i, is the maximum constraint violation among the population N. In the initial stage of the algorithm almost all the solutions may violate the minimum pressure requirement constraint. However, as the algorithm advances the count of such solutions decreases, and the algorithm may reach a point with zero constraint violation solutions. In such a case is taken as 1, as it is in the denominator and cannot take zero as a value.
• 6.

  The solutions are then sorted and ranked based on their respective CVR values. This ratio is chosen to sort the solutions because the solution with higher CV values will require larger diameters to satisfy the pressure. Hence such solutions will be costly, and thus will be less probable to be picked up for the next iteration for a minimization cost problem.

Thus the chance of a solution performing better than others depends on its CV value and hence solutions are sorted based on the CVR. The solution with minimum and maximum CVR is ranked 1 and N (N is the population size) respectively. However, different solutions may have the same CVR since for some solutions the CV_max comes out to be very large as compared to individual CV values. Hence when divided, the CVR values come out to be nearly the same.

So we can say that the solutions are divided into different fronts based on their CVR and the solution with the same CVR lies on the same front.

• 7.

  After getting sorted into different fronts, solutions in the same front are sorted based on the concept of dominance and non-dominance. One solution is said to dominate other solutions if it is better in at least one objective. However, if no solution is found to dominate a solution then the latter is categorized as a non-dominant solution. This creates two distinct sets, one of non-dominated and the other of dominated solutions within a front. Similar front non-dominated and dominated solutions are again sorted based on the crowding distance (CD) (Deb et al. 2002).

• 8.

  After sorting the solutions, the first front non-dominated solution with maximum CD is selected as the best solution (Deb et al. 2002) and the last front last solution is selected as the worst.

• 9.
  Once the best and worst solutions are identified, the population is updated using Equation (15). Steps 2, 3 and 4 are repeated for the newly generated population. At this stage the initial population is combined with the new population, making the population size twice the initial population, i.e. 2N. Steps 5–8 are repeated for 2N population { is determined from the entire 2N population for step 5}:

  

  (15)

r₁ and r₂ are the random numbers generated between 0 and 1. The best and worst solution is represented by index b and index w respectively. i,j,k are the indices of iteration, variable, and candidate solution respectively. denotes the new value of the variable j, which is determined by using the old value of variable j, the best and the worst values from the population represented by respectively.

• 10.

  Top N solutions are selected from 2N solutions and become the initial population for the next iteration. The process is continued till the termination criteria are met.

Including the constraint violation domination in the above methodology eliminates the use of penalty function for penalizing the non-feasible solutions, making the MO-JAYANET a completely parameter-less optimization technique. The code for MO-JAYANET is written in Python by linking it with EPANET 2.0 (Rossman 2000) for performing all the hydraulic simulations.

Figure 2(b) shows the second benchmark network which is a 3-looped real network of Hanoi city taken from Fujiwara & Khang (1990). The network consists of 34 pipes with a Hazen-William coefficient of 130, connecting 31 demand nodes and a reservoir kept at an elevation of 100 m. The diameter for 34 pipes can be chosen from six commercially available diameters given in Table 1 which leads to a total search space of 2.85×10⁻²⁶. A minimum of 30 m pressure head is required at all the nodes of the network. All the hydraulic data for the Hanoi network is given in Fujiwara & Khang (1990). The optimal network cost reported in the literature is 6.081 M$ (Siew & Tanyimboh 2012) when only minimizing the cost is considered and the corresponding optimal diameters are given in Table 3. Multi-objective optimization using MO-JAYANET for the Hanoi network is carried out using RI, NRI and MRI as the second objective. To obtain the PF shown in Figure 3(d)–3(f) for RI, NRI and MRI respectively, 10 trial runs are performed with a population size of 150 and 1000 iterations as the termination criteria. The PF for Hanoi network ranges from 6,403,449.4 $ to 9,590,894 $ and 0.2186 to 0.3502 for RI, 6,186,046 $ to 9,390,643.8 $ and 0.1985 to 0.3339 for NRI & 6,714,648 $ to 84,66,717 $ and 0.4833 to 0.7902 for MRI. The PF of three reliability indices RI, NRI and MRI reports a total of 180, 163 & 124 feasible and distinct solutions respectively. Among the three indices, solutions with NRI as the second objective report proximity to the optimal solution by obtaining a solution from 163 with a cost of 6.18 M$. PF obtained by MO-JAYANET for NRI is overlapped with the BKPF for the Hanoi network as shown in Figure 3(e) indicating the feasibility of the solutions. The shape of the PF for RI and MRI obtained by MO-JAYANET also matches the PF obtained by Moghaddam et al. (2021).

For the three indices, the summation of the SPH at all nodes for the three DM and failure of pipes 2, 3 and 5 for the Two Loop and DM = 1 and failure of pipes 4, 5, 6 and 20 for the Hanoi network is determined. SPH tells about the extra pressure head that is available at any node after the minimum pressure head is satisfied. Hence, the higher the value of SPH, the higher is the power available within the network which can be dissipated during any failure (Todini 2000). All the RSM discussed in the present work are based on the surplus power available within the network. Thus, the index having the maximum SPH indirectly tells about the reliability of the network. However, much research is needed to comment on the best-performing index but based on the value of SPH, Todini's RI can be seen as a better performer when compared with NRI and MRI. From Table 5 it is clear that for both the networks, Todini's RI has the highest SPH value of 1216 m for Two Loop and 2223.69 m for the Hanoi network).

Single objective optimization for WDN searches for a solution with minimum cost only. However least-cost solutions are less reliable and thus cannot sustain failures. The above problem can be solved by multi-objective optimization with reliability being one of the objectives. However, multi-objective optimization is a complex process and the complexity of it increases more when solved using evolutionary algorithms due to the involvement of various parameters in the algorithm. Optimal parameters must be found which is a tedious task.

The above mentioned problem is solved in the present work with the introduction of a new multi-objective evolutionary technique, MO-JAYANET, for the optimal design of water distribution networks. MO-JAYANET is found to be free from any algorithm-specific parameters and penalty parameters, thus skipping all the efforts that are otherwise required to tune the algorithm. MO-JAYANET is developed and tested on two well-known benchmark networks from the literature using three different extensively used RSMs as the second objective. PF for the three indices RI, NRI and MRI are developed and the PF of NRI is also overlapped with the BKPF from the literature for both the networks and found to cover the maximum curve area with single population size and fewer iterations. Thus the major achievement on application of Jaya algorithm for optimal design of WDN are:

• (i)

  No algorithm parameters are involved and thus no need of their synchronization for optimal solution.

• (ii)

  It is more efficient as the optimal solution is obtained in less function evaluations.

Efforts are made to test the maximum reliability solution obtained by MO-JAYANET under different hydraulic and mechanical failures. SPH graph for the maximum reliability solution is plotted and the index with maximum summation of SPH is selected as a better performing index. Based on the results obtained from the SPH analysis for both the hydraulic and mechanical failures it is concluded that Todini's RI performs slightly better for both the distribution networks under 11 different failure scenarios for the Two Loop network and 14 different failure scenarios for the Hanoi network. When compared between NRI and MRI, NRI is found to be a better performer for the Two Loop network and for the Hanoi network MRI performs better. These results are based on the SPH value, however extensive research is needed to comment on the best-performing index.

All relevant data are included in the paper or its Supplementary Information.

The authors declare there is no conflict.