Improving the optimal solution of GoYang network – using genetic algorithm and differential evolution

A water distribution network (WDN) is an essential infrastructure whose design is considered as a nondeterministic polynomial-time hard problem (Yates et al. 1984). Although researchers have developed numerous models from heuristic, analytical approaches to deterministic, stochastic optimization techniques, a model that designs WDN with its full complexity is yet to emerge (Walski 2001). In general practice, the developed models are validated using benchmark-problems. In the present study, most of the well-established ones are classified considering various parameters as shown in Figure 1. This information on classification may help researchers to select the appropriate network for their developed model objective.

In the first instance, benchmark-problems from the literature can be categorized into new WDN (NWDN) and rehabilitation of existing WDN (RWDN). In the first case, networks are newly designed and in the latter, existing networks are strengthened. Further, based on the pipe count they are classified into small, medium, intermediate and large networks as shown in Figure 1. Under NWDNs, the two-loop network (TLN) (Alperovits & Shamir 1977), serial liquid pipe (Goldberg & Kuo 1987), one-loop 14-pipe, four-loop 17-pipe network (Su et al. 1987), and Ostfeld and Tubaltzev network-1 (Ostfeld & Tubaltzev 2008) are small-sized. The Hanoi network (HN) (Fujiwara & Khang 1990), GoYang network (GYN) (Kim et al. 1994), Ostfeld and Tubaltzev network-2 (Ostfeld & Tubaltzev 2008), and Kadu two-reservoir network (Kadu et al. 2008) come under medium-sized. The real-world network (RN) (Zheng et al. 2014) and ZJ case studies (Zheng et al. 2011) are intermediate and large-sized networks.

Under RWDNs, small-sized networks include the two-reservoir network (Simpson et al. 1994) and Halhal seven-loop network (Halhal et al. 1997). The New York tunnel network (Schaake & Lai 1969), Anytown WDN (Walski et al. 1987), federally owned water main system (Ormsbee & Kessler 1990), Blacksburg (Sherali et al. 2001), and doubled New York city network (Zheng et al. 2014) are medium-sized. The BakRyan network (BRN) (Lee & Lee 2001), and Pescara and Fossolo network (Bragalli et al. 2008) are intermediate and the Moroccan (Halhal et al. 1997), Exeter network (EXNET) (Farmani et al. 2005), Balerma irrigation system (Reca & Martínez 2006), and Modena (Bragalli et al. 2008) are large-sized networks.

In addition, depending on the layout, these networks could be classified into branched, looped or both. The serial liquid pipe and RN case study are serial networks. The TLN, Anytown WDN, Halhal seven-loop, and Kadu two-reservoir network are looped and the remaining are a combination of both. Depending on whether the flow is gravity-fed or aided by pumps, these networks could be further categorized into gravity-fed and pumped networks. Except for one-loop 14-pipe, four-loop 17-pipe, Anytown, GYN, and Ostfeld and Tubaltzev network-1 and -2, the remaining networks are gravity-fed.

In the field of WDN optimal design, a multi-directional search algorithm with better computational efficiency and robustness is futuristic. In this context, bio-inspired evolutionary algorithms (EAs) stand at the forefront. Although EAs are good at convergence to the best solutions there is no direct proof for such a solution to be the global optimum. For small networks like TLN, it is easy to cross-check by enumeration or any other analytical methods. However, the same becomes practically impossible with the increase in decision variables. Therefore, there is still scope for improving solutions of benchmark-problems by applying various techniques such that they can emerge as standard networks for future studies. With this as a motive, in the present study, an approach is made to use different versions of genetic algorithm (GA) and differential evolution (DE) in the search for the best solutions for HN, BRN, and GYN.

The methodology adopted in the present study is not new to the research community. But the way it is attempted is different in terms of conducting sensitivity-analysis for fixing the EA parameters (like population size (N_pop), number of generations (N_gen), crossover probability (P_c), mutation probability (P_m), penalty multiplier), and the usage of an elitism operator (to preserve the best chromosomes at every generation) whose benefits can be reaped as an improvement in the algorithm's convergence capability. In spite of meticulous pre-analysis in fixing EA parameters, convergence to the optimal solution in every trial remains unpredictable as EAs follow random steps in line with their parameters. Therefore, an attempt is made to evaluate EA robustness in terms of success rate (SR), defined as the percentage of the attempts out of the 50 trials that converge to the determined optimum. Here, consideration of 50 trials is purely arbitrary.

For known details of commercially available diameter set, layout, pipeline characteristics (length, material), demand and minimum head requirement at the demand nodes, the main task in WDN design is to choose the set of diameters balancing the network hydraulically, and satisfying the minimum head constraint at the demand nodes besides catering to the economic aspect of the design i.e., the cost of the chosen diameter set sums up to the minimum possible design cost.

Bio-inspired GA that mimics nature's principle of survival of the fittest, and DE, a consistent and robust functional optimizer developed by Storn & Price (1997), are the most widely used EAs in diverse engineering fields. In the present study, seven different models are developed: GA with truncation (GA1), tournament (GA2), roulette-wheel (GA3) and an elitist GA with truncation (EGA1), tournament (EGA2), and roulette-wheel method of selection (EGA3), and a simple DE model.

For all the GA models, single-point crossover and a uniform mutation operator, and for elitist-models, 2% elitism are considered. While performing a sensitivity-analysis, GA parameters are fixed following the guidelines of Simpson et al. (1994) and the same is followed for DE except for the mutation-factor, whose magnitude governs its exploration capability and is varied from 0.5 to 1.0. The static penalty function, a robust approach for penalizing the constraint violation (Michalewicz & Schoenauer 1996), is adopted. To determine the penalty multiplier, network cost with all the pipes set to the largest available diameter is considered at first and then varied until the best value that fits the benchmark-problem is obtained. The termination criterion for the optimization is the predefined N_gen. All these EA parameters are problem-specific and govern the evolutionary process.

The parameters ascertained through sensitive analysis are N_pop 50 for GYN and 100 for the remaining networks. N_gen is 400, 1,500, 1,000, and 500 for TLN, HN, BRN, and GYN respectively. And for these four networks, P_c for all the GA variants is in the range of 0.8–0.9 and 0.6–0.95 for DE. P_m for the GA models is in the range of 0.02–0.035 and 0.5–0.8 for DE. For all the GA variants, the penalty multiplier is 7.5*10⁴ for TLN, 10⁷ for HN, 3.5*10⁵ for BRN and 3*10⁷ for GYN. For the DE model, except for TLN, the penalty multiplier is different: 1.097*10⁷ for HN, 1,388,800 for BRN, and 3.25*10⁸ for GYN.

With these best possible parameters, GA variants and DE models are combined with the EPANET software using the MATLAB toolkit. EPANET evaluates the nodal head values for every alternative set of diameters proposed by the optimization technique. Violation of any head constraint is penalized using the static penalty function.

TLN is a small-sized gravity-fed network first studied by Alperovits & Shamir (1977), where all its details are available. HN is a medium-sized gravity-fed network with three loops. Complete details of HN are available in Fujiwara & Khang (1990). BRN is a medium-sized gravity-fed RWDN studied by Lee & Lee (2001) where all its details are available. Its aim is to resize pipes 1–3 and provide parallel pipes for pipes 4–9 (Geem 2006). GYN is a medium-sized pumped network with nine loops. Complete information on GYN is taken from Kim et al. (1994).

Initially, our implementation of the optimization algorithms is validated using TLN, whose optimal design cost is well-known ($419,000). In the present study, the same is obtained as detailed in Table 1 along with the results from the literature. Although the optimal costs marked by ‘a’ in Table 1 are less than $419,000, they violate the head constraint and are infeasible. Pressure head variation of TLN among various studies for the nodes whose pressure is near to the threshold value of 30 m is shown in Figure 2(a). These nodes, 6 and 7, can be considered as critical in the sense that under any abnormal conditions like the failure of the network (mechanical or hydraulic), these nodes have a greater likelihood to fall below the minimum pressure, making the network much more sensitive to the failure conditions and decreasing its reliability.

Computational results of TLN are tabulated in section A of Table 2. For a fixed population-size, EGA3 is best in converging to the global optimum with a lower number of function evaluations (FEs) (3,600) followed by GA1, GA2, EGA2, GA3, DE, and EGA1. Although EGA1 needs more FEs (7,700), its SR is high (22%) as compared with EGA3 (4%). The effect of elitism is observed only in improving the SR but not in decreasing the computational effort. In terms of SR, DE is efficient over the GA models with 100% SR. Hence, for TLN, all the developed models work well with DE standing out from the GA variants in terms of SR.

After successful validation of the developed models, they are applied to HN, whose optimal cost obtained in the present and previous studies is tabulated in Table 1. In spite of intense search by all the developed models, only the DE model yielded an optimal solution of $6,081,118. Next to DE is GA1 and EGA3, which achieved near-global cost, followed by GA2, EGA2, EGA1, and GA3. The optimal costs marked by ‘a’ in Table 1 for HN are infeasible in regard to head constraint violation. For the DE model in the present study, nodes 13, 27, 29, 30 and 31 have pressure heads just above 30 m (minimum pressure) but below 31 m (these nodes have a greater likelihood of falling below the minimum pressure under failure conditions) as shown in Figure 2(b) and can be considered as the critical nodes of HN. The computational results for HN are listed in section A of Table 2. DE remarkably proves its robustness with 92% SR over GA. Hence, unlike TLN, for HN, DE is more efficient than the GA models both in convergence to the optimal solution and with a high SR.

Besides NWDNs, the present study also aims to apply the developed models to RWDNs. In this regard, BRN is considered. The optimal cost of BRN obtained in the present study and literature is detailed in Table 1. Except for the original network, all the remaining models including the present study yielded the same optimal cost ($903,620). The optimal diameter set corresponding to this cost along with the original network is available in Geem (2006). The change in the design cost from the original network is due to the change in the diameter of pipes 6–9 and these can be stated as the pipes that make the design cost of BRN most vulnerable.

Figure 2(c) depicts the pressure head variation amongst various studies for the nodes 4 and 19 whose pressure head is just above the minimum head constraint (15 m), and these nodes are considered to be the critical nodes of BRN. Computational results of BRN are listed in section A of Table 2. It is found that DE and EGA3 converged to an optimal solution with a lower number of FEs (2,600) followed by GA1, EGA2, GA2, EGA1, and GA3. The number of times the optimal solution is obtained by EGA2, EGA3 is more than by GA2, GA3, showing their efficacy in improving the SR. The GA variants are able to achieve the global optimal solution in a few trials out of 50 attempts while the DE model excels in achieving it in all the trials. This shows the robustness of the DE model in attaining an optimal solution for both the medium-sized and intermediate-sized networks. Hence, for BRN also, DE outperforms the GA variants in terms of robustness.

On successful application of the developed models to the gravity-fed NWDNs and RWDN, it is applied to the pumped NWDN and GYN. The optimal cost of 177,009,557 won, which is the lowest feasible cost over the ones reported in the literature, is obtained by all the models developed in the study as detailed in Table 1. Thus, for EA this reflects its efficacy in convergence to a better optimal solution.

The optimal diameter set of GYN obtained in the present study is compiled in section B of Table 2, and for the previous studies is available in Geem (2006). The variation in design cost obtained in the present study in comparison with Geem (2006) is due to the variation in diameter of pipes 4, 6, 8, 23 and 27, indicating that the design cost is more sensitive to the variation in these pipes' diameters. Nodal pressure head variation amongst various studies for nodes 1, 10, 11, 14, 15 and 22, whose pressure is just above the minimum threshold (15 m), is shown in Figure 2(d), and these nodes are considered to be critical for GYN. As node 1 is in direct contact with the reservoir, under insufficient pressure, the entire system would suffer from deficient supply. Hence, for GYN, node 1 is the most critical node followed by 10, 11, 14, 15 and 22, and the diameter of pipes connected to these nodes plays a vital role in improving their pressure.

The computational results for GYN are detailed in section A of Table 2. Although all the models yielded the same optimal design cost, there is much variation amongst them in terms of FEs and SR. For GA1 and GA2, the number of FEs required to reach the optimal solution is the minimum and maximum respectively with equal SR. As encountered with other networks, for GYN also the effect of elitism is found in improving the SR. The DE model achieved global optimum 37 times with 74% SR. Hence, for GYN both the GA and DE models performed well in converging to an improved optimal cost. However, in terms of robustness, DE outweighs the GA variants.

Unlike the conventional methods for optimization, EAs start the search in multi-directions by generating an initial random population. The evolution of this population over generations depends on its operators. In GA, through the selection mechanism, better chromosomes are selected and processed through crossover and mutation operators to arrive at the best solutions. This may often lead to premature convergence while dealing with the large search domains, which is clearly evident in the present study with HN. In addition, in GA, the chance of randomly chosen chromosomes undergoing crossover or mutation depends upon a check, ‘if the random number generated is less than P_c or P_m’. Thus, GA involves more random walks that keep the chance of attaining the best optimal solution at every trial uncertain, which is also evident from the present study in terms of the low SR for every benchmark-problem considered. For elitist-models, the improved SR over normal ones is due to the feeding of the best solutions to the next generations without change.

On the other hand, in DE, at first, the randomly generated initial population undergoes mutation operation, which improves the diversification of the search, followed by the crossover and selection operators. Because of the much-diversified search, irrespective of the size of the search domain, DE often converges to the best optimal solutions. Further, in DE, the chance of randomly chosen chromosomes undergoing an operation is checked only for a single operator, i.e., crossover. Hence, a balanced search along with the lower usage of the random phenomenon in DE in comparison with GA improves its SR and thus the robustness of the algorithm, which is also evident from the present study.

Hence, from the small to intermediate-sized networks considered in the present study, DE outperforms GA not only in terms of convergence to an optimal solution but also with a high SR, depicting vividly its robustness.

In the present study, seven EA models are developed and are found to be efficient in convergence to an optimal solution for TLN; the best solution in correspondence with the literature for HN and BRN; and an improved solution for GYN. As EA operators are problem-specific and work on random chances there is still scope for improving their robustness and convergence capability. The major conclusions drawn from the present study are as follows:

• 1.

  The available benchmark-problems from the possible water distribution studies are classified and reported based on their age, pipe-number, layout, and network hydraulics.

• 2.

  Nodes with pressure head just above the minimum required pressure are classified as critical nodes. This information is more useful while conducting performance analysis under uncertainties.

• 3.

  The introduction of an elitism operator in GA increased the chance of obtaining the optimal solution and thus the SR.

• 4.

  For every benchmark-problem considered in the present study, DE excelled in convergence to the optimal solution with a high SR proving its robustness.

• 5.

  For GYN, the developed GA and DE models yielded an improved feasible optimal cost of 177,009,557 won.