Redefining the application of an evolutionary algorithm for the optimal pipe sizing problem

Water supply systems are one of the most important infrastructures for mankind as they supply water from the treatment plants to the consumers. These systems fall under the category of non-deterministic polynomial hard problems (NP-hard) (Babu & Vijayalakshmi 2012) due to the non-linear relation between the pressure and discharge in a pipe. In addition to this, the decision variables for the optimization of water distribution networks (WDNs) are discrete pipe diameters to be chosen from a set of commercially available diameters for the design. The design of these decision variables as continuous and rounding off to the nearest commercially available diameter may not guarantee the true optimality. Above all, the optimal pipe sizing is a constrained optimization problem (minimum pressure requirement at nodes and conservation of energy and mass equation) having outsize search space which makes it impractical to evaluate every possible alternative. Due to the various challenges mentioned above, the design of any WDN is difficult to solve and requires attention. The very first technique that was used for the WDN design is dynamic programming (DP; Schaake & Lai 1969). Thereafter linear programming (LP; Alperovits & Shamir 1977) is used. These techniques give satisfactory results; however, these are based on various assumptions. These techniques require gradient information to locate the solution. Also, the optimal solution obtained by DP and LP may get trapped in local optima and may not be able to locate the global optima. The above drawbacks are overcome with the introduction of evolutionary algorithms (EAs). EA is based on certain metaphors, for example, the well-known genetic algorithm (GA) is based on the evolution of human beings. These techniques are widely used as an optimization technique since they are easy to use and can be used for a large number of problems. EA works by mimicking its metaphor. This mimicking becomes possible due to the involvement of various constants that are associated with the algorithm. The main flaw of using EA as an optimization technique is that the constants of the algorithm are to be fine-tuned for every optimization problem which involves huge computational efforts and is a tedious task. Thus, the main motivation to carry out the present study is to introduce a technique that eliminates the tedious task of tuning the parameters of the algorithm. Considering this, the authors of the present work introduce the Rao algorithms for the optimal pipe sizing for the very first time. Rao (2020) developed the Rao algorithms, namely Rao-I, Rao-II, and Rao-III. These algorithms do not need tuning of any algorithm-specific parameters and require only common parameters such as population size and number of iterations for searching the optimal point, and thus, the sensitivity analysis is eliminated. Such techniques not only reduce the computational time but also reduce extra efforts in tuning the parameters. The only difference between Rao-II and Rao-III is the position of modulus in the evolution process of the algorithm and their working principle is similar, and hence has not been incorporated in the present work. The computer program has been developed for Rao optimization algorithms (Rao-I and Rao-II) in a Python environment and is linked to a well-known hydraulic network solver EPANET 2.0 (Rossman 2000) for the pressure-driven analysis to obtain flows and pressure head in the network.

From the past two decades, EAs, as the optimization techniques to solve a complex problem of WDN design, have increased drastically. Many EAs such as GA (Savic & Walters 1997), simulated annealing (SA; Cunha & Sousa 1999), shuffled frog leaping algorithm (SFLA; Eusuff & Lansey 2003), shuffled complex evolution (SCE; Liong & Atiquzzaman 2004), harmony search (HS; Geem 2006), differential evolution (DE; Suribabu 2010), particle swarm optimization (PSO; Aghdam et al. 2014), self-adaptive differential evolution (SADE; Sirisant & Janga Reddy 2018), and cuckoo search (CS; Naidu et al. 2020) have been applied for the optimal pipe sizing problem. These algorithms have proved their efficiency in the past by performing very well in finding the optimal solution from small to large networks. However, the reliability and robustness of these techniques are found to be largely dependent on various algorithm-specific parameters and need extensive effort for tuning the parameters. In addition to this, the parameters once tuned cannot be used for other problems, as with the change in the problem, the value of these parameters also changes. Regressive sensitivity analysis is to be carried out for each network to find the appropriate parameters, thus it makes these algorithms computationally very expensive and time-consuming. The pool of such metaheuristic techniques, based on certain metaphors and thus involving various algorithm-specific constants, is emerging every day. Such metaphor-based EAs are complex to understand and are thus ending soon as there is no taker (Rao 2020).

To overcome the above-mentioned drawback, the research has been focused on developing techniques that eliminate pre-specifying the algorithm-specific parameters. Such techniques are either called the self-adaptive parameter technique (Geem & Cho 2011; Babu & Vijayalakshmi 2012; Zheng et al. 2012) or parameterless techniques (Rao et al. 2011; Rao 2016, 2020). Self-adaptive techniques do not require parameters to specify at the start of the technique and will adapt and change parameters as the algorithm advances based on the number of iterations or objective function value. Geem & Cho (2011) developed a parameter setting free harmony search, PSF-HS, which dynamically adjusts two parameters of the algorithm, namely harmony memory considering rate (HMCR) and pitch adjusting rate (PAR), which otherwise is a very tedious task to tune. These parameters are initially given a central value (e.g., HMCR = 0.5 and PAR = 0.5) and are dynamically adjusted as new population vectors are generated. Zheng et al. (2012) identified that the convergence of DE is highly sensitive to the parameters, namely mutation weighing factor (F) and crossover rate (CR). The authors then developed a SADE that assigns the random values of F and CR to each individual and the individual that performs better, its F and CR are directly passed to the next generation. However, in some cases, if the F and CR are not able to generate better offsprings, these are again generated randomly. On the other hand, some techniques do not involve any parameters specific to the technique. Rao et al. (2011) developed a teaching learning based optimization (TLBO) technique that mimics the learning behavior of the students. Students are allowed to learn from the teacher as well as from the interaction among the class. TLBO does not need any parameter values specific to the technique. This requires only common parameters such as population size, number of iterations, and in some cases penalty parameter to convert the constrained problem to unconstrained. This is to highlight that these parameters are required for almost all EAs on top of algorithm-specific parameters. The research is focused on developing less complicated optimization techniques, involving no or least interaction of algorithm-specific parameters with the ability to solve such non-deterministic polynomial hard problems that are otherwise difficult to solve using conventional optimization techniques.

• i.

  Continuity at nodes:

However, for the pipes in series connecting two fixed head reservoirs, the head loss is equal to the numerical difference of head between the two reservoirs.

• iii.Minimum pressure at nodes:

ω in Equation (6) is the unit conversion factor whose value depends on the units chosen, and α and β are the coefficients having the values of 1.85 and 4.87, respectively. Thus, the headloss calculated from Equation (6) largely depends on the value of ω chosen. The higher value of which increases the headloss in the pipe and hence demands greater pipe diameter which in turn increases the cost of the network, and vice versa. Thus, directly comparing the cost of the network obtained by different studies is not justified since many researchers have used different values of ω, for example, Savic & Walters (1997) used 10.5088 and 10.9031 as ω values, Cunha & Sousa (1999) used ω value as 10.5088, hence the comparison can be done based on the number of function evaluations (NFEs) required to reach the previously reported optimal network cost with the reported value of ω. EPANET 2.0 uses the Hazen–William equation with ω = 10.667, and hence, the same is adopted in the present optimization model of Rao algorithms.

Rao (2020) developed the three metaphor-less metaheuristic techniques, Rao-I, Rao-II, and Rao-III. Since these techniques are metaphor-less, no parameters are required to mimic the behavior of the algorithms. Hence, these techniques are free from any algorithm-specific parameters which eliminate the process of synchronization of the parameters, known as sensitivity analysis; this, in turn, reduces computational efforts and time. Only common algorithm parameters like population size and termination criteria are required by these techniques.

The main objective for the optimal sizing of a pipe network problem is to reduce the network cost, thus it is a minimization problem. Rao-I, Rao-II, and Rao-III are based on selecting the best and worst solutions from a set of populations. Hence, the solutions with the maximum and minimum objective function values are referred to as the worst and the best solution, respectively. The algorithms begin with random interaction among the solutions like any other metaheuristic technique and use the best and worst solutions to update the population set.

The effectiveness of the Rao evolutionary techniques for the optimization of WDN is demonstrated by applying it to five different size benchmark networks. The networks considered are the two-loop network (Alperovits & Shamir 1977), Hanoi network (Fujiwara & Khang 1990), Go-Yang network (Kim et al. 1994), Kadu network (Kadu et al. 2008), and the Farhadgerd network of Iran (Moosavian & Lence 2018). The above-stated benchmark networks differ in their physical characteristics so that the algorithm is tested for different scenarios. The two-loop network considered in the present work is a hypothetical network, while Hanoi and other networks belong to the category of real networks. The Go-Yang benchmark network has a pump of 4.52 kW capacity, and the Kadu network is a two-reservoir problem, for which the minimum head requirement at each node is different. The Farhadgerd network consists of 68 pipes and belongs to the category of large networks. Thus, the search space for these networks is very large and extends from 1.48E+09 to 7.74E+68 and is difficult to solve using conventional optimization techniques (Babu & Vijayalakshmi 2012). A detailed description of each network such as the number of pipes and nodes, previously reported optimal cost of the network, and the minimum pressure head requirement is given in Table 1. The hydraulic data of all the networks are given in the supplementary material. This includes pipe lengths, nodal demand, and elevation. Commercially available pipe diameters and the corresponding unit cost for each network are mentioned in Table 2. Thirty trial runs are performed for each Rao-I and Rao-II for all the networks considered. The different optimization techniques are run at different machine configurations, and thus, comparing these techniques based on simulation run time is not justified (Jabbary et al. 2016). Thus, the evolutionary techniques are more commonly compared based on the computational efforts, that is, how many evaluations of the objective function, that is, NFEs, are taken by any technique. Minimum function evaluations (MFEs) show the least number of evaluations taken by any evolutionary technique. Maximum allowable function evaluations (MAFEs) are adopted as the termination criteria, that is, how many maximum evaluations are given to any EA (Sirisant & Janga Reddy 2018). In the present work, all EAs are compared based on MFE.

This network was proposed by Alperovits & Shamir (1977). All pipes of the network are 1,000 m long with the Hazen–William coefficient of 130. The network was studied by various researchers, Savic & Walters (1997), Eusuff & Lansey (2003), Sirisant & Janga Reddy (2018), etc., and obtained the optimal cost of the network as 419,000 units. The schematic sketch of the network along with hydraulic data of the network like demands at nodes and nodal pressure is shown in Figure 2(a). There are 13 commercially available pipe diameters which lead to a search space of 1.48E+09. In Table 3, a comparison of the optimal diameters obtained and computational efforts taken by various other techniques for the optimization of this network is given. From Table 3, it is observed that all the optimization techniques obtain the same optimal diameters and hence the same cost of the network, that is, 419,000 units. However, the Rao algorithms are found to be computationally very cheap as compared with other techniques. Rao-I took 370 MFEs to reach the optimal cost of 419,000 units for a MAFE of 5,000 when compared with MFEs of 25,000 (Cunha & Sousa 1999), 9,500 (Sirisant & Janga Reddy 2018), 15,300 (Naidu et al. 2020), etc. Under similar conditions, Rao-II obtained the same optimal cost in 1,410 MFE. Thus, Rao-I outperforms Rao-II for the two-loop network, but the performance of Rao-II is better when compared with other techniques as seen from Table 3 in terms of MFE. It is evident from the convergence curves for Rao-I and Rao-II in Figure 3(a) that Rao-I converges faster than Rao-II.

The second benchmark network considered for the study is the Hanoi network (Figure 2(b)). All the hydraulic data for the Hanoi network can be obtained from Fujiwara & Khang (1990) and are also given in the supplementary material. Due to the large search space, the network has been tested by various researchers (Savic & Walters 1997; Kadu et al. 2008; Zheng et al. 2012, Naidu et al. 2020). The optimal cost of the Hanoi network is different with different ω values. It is $6.056 million for ω = 10.5088 (Cunha & Sousa 1999), $6.183 million for ω = 10.9031 (Kadu et al. 2008; Siew & Tanyimboh 2012), and $6.081 for ω = 10.667 (Suribabu 2010). The optimal diameters obtained by Rao-I and Rao-II along with the MFE required to reach the optimal cost are given in Table 4. As it is observed from Table 4, the diameters of the network obtained by various other techniques are very similar to those obtained by Rao algorithms except for SCE by Liong & Atiquzzaman (2004) and CS by Naidu et al. (2020). In addition to this, the diameter of pipe 18 (bold values in Table 4) obtained by Rao algorithms is different from that obtained by Cunha & Sousa (1999) and this is responsible for a lesser cost than Rao algorithms. This is because of the adoption of a lower ω value (ω = 10.508) than the present optimization model (ω = 10.667). Kadu et al. (2008) obtained a higher cost due to ω = 10.903. However, the computational efforts required to reach the optimal solution presented in Table 4 vary to a large extent. The MFE required by Rao-II is lower, that is, 6,350 as compared with SA (53,000), SCE (25,402), GA (18,000), and Rao-I (11,400) to reach the optimal solution. DE outperforms all the techniques and gives the optimal solution in just 3,540 MFE. However, as many as 300 trial runs are performed due to variation in crossover and weighing factor to reach at the trial with 3,540 MFE. The convergence curves for Rao-I and Rao-II shown in Figure 3(b) depict that Rao-II has a better convergence rate than Rao-I for the Hanoi network.

The Go-Yang network shown in Figure 2(c) was first introduced by Kim et al. (1994) and differs from other networks due to the provision of a pump of 4.52 kW instead of an elevated reservoir. The comparison of optimal diameters along with the MFE required to reach the optimal solution is given in Table 5. The original design of the network is shown in column 2 of Table 5 along with the total network cost of $179,428.6. The network was first optimized by Kim et al. (1994) using the Lagrangian method (non-linear programming (NLP)) and obtained the continuous diameters, which were further rounded off to the available discrete diameters. The cost of the network was obtained as $179,142.7, which is slightly less than the original network cost. Geem (2006) solved the network using HS and obtained a $177,135.8 network cost which is about 1.2% cheaper than the original network cost taking almost 10,000 MFE. Rao-I and Rao-II obtained the minimum network cost of $177,010 with just 1,120 and 800 MFE, respectively, which are very few when compared with Geem (2006). Dong et al. (2012) applied the DE for the optimal design of the Go-Yang network and obtained the network cost as $177,010 with 8,750 AFEs (average function evaluations) in comparison to 1,957 and 980 AFE taken by Rao-I and Rao-II, respectively. The convergence curve for Rao-I and Rao-II for this network is shown in Figure 3(c). It is seen that Rao-II converges fast.

The Kadu network (Figure 2(d)) was first proposed and optimized by Kadu et al. (2008) using GA. This is a two-reservoir problem with different minimum pressure head requirements at different nodes. Node number 3–6, 9–12, 15, 18 requires minimum pressure head of 85 m, while 6, 8, 13, 14, 16, 17, 19–21, 23 require a minimum pressure head of 82 m. The requirement of the minimum pressure head at the remaining nodes is 80 m. Kadu et al. (2008) obtained the network cost of Rs. 131.678 MRs with the diameter configurations given in Table 6. After this, the network has been optimized by many researchers using various computational techniques, some of which are listed in Table 6. Haghighi et al. (2011) combined the GA with integer linear programming (ILP) and took just 3.66% of function evaluations (FEs) as required by Kadu et al. (2008) to obtain the solution that is also slightly better than it. However, the obtained solution is expensive when compared with other techniques such as PSO, central force optimization (CFOnet), and Rao algorithms. The Rao-II algorithm obtained the minimum cost of the network as Rs. 125.434 MRs in just 19,700 MFE and compared it with other algorithms in Table 6. The network cost obtained by CFOnet applied by Jabbary et al. (2016) is slightly less than that obtained by Rao-I, but the computational efforts taken by it are almost 10 times more than Rao-I. Thus, when comparing Rao-I and Rao-II, Rao-II performs better in searching for the least costly solution with lower computational effort. Diameters obtained from Rao-I and Rao-II are found to satisfy the minimum pressure head requirement when checked in EPANET 2.0. From the results reported in Table 6, it is worth stating that the MFE required to reach the optimal cost by Rao algorithms are free from any sensitivity analysis and thus no efforts are invested in tuning the parameters as required by GA, PSO, etc. Thus, MFE reported by these techniques is post sensitivity analysis and thus does not include those in the results presented in Table 6. The convergence curves for Rao-I and Rao-II are shown in Figure 3(d). From the curves, it is clear that Rao-II obtains the lower cost in fewer iterations as compared with Rao-I.

The Farhadgerd network (Figure 2(e)) was introduced and optimized by Moosavian & Lence (2018) using various optimization techniques They reported that the optimal cost of the Farhadgerd ranges from $17.80 million to $28.00 million. Since the network is newly developed, it has not been used by many researchers, and hence comparing the diameters obtained by Rao-I and Rao-II with other techniques is not possible. The diameters obtained by Rao-I and Rao-II for the Farhadgerd network along with the computational efforts required to reach the reported optimal cost are given in Table 7. Moosavian & Lence (2018) compared 10 EAs for the optimal design of the Farhadgerd network with an MAFE of 40,000; however, none of the EA reported the optimal cost as less than or equal to that obtained by Rao-II for an MAFE of 40,000. Rao-II obtained the network cost as $17.498 million in just 23,760 MFE, while the network cost obtained by Rao-I is $17.633 million in 47,400 MFE. The above values highlight that the Rao algorithms can search the optimal solution with less MFE. It is also evident that the performance of Rao-II is better than Rao-I for the Farhadgerd network as seen from the convergence curves for Rao-I and Rao-II shown in Figure 3(e).

The optimal diameters obtained for all the benchmark networks using Rao-I and Rao-II are simulated in EPANET 2.0 and pressure values at every node for each network are obtained. The minimum and maximum pressure head obtained by Rao-I and Rao-II for the two-loop, Hanoi, Go-Yang, Kadu, and Farhadgerd network is shown in Table 8. It is evident from Table 8 that for each network, the obtained minimum pressure head is greater than the prescribed minimum pressure head which indicates that solutions obtained by Rao-I and Rao-II are feasible.

In the present work, two different evolutionary optimization algorithms developed by Rao (2020) have been used for the optimal design of the pipe networks. Both the algorithms are tested on five different benchmark problems from the literature, and their performance comparison is made with various evolutionary techniques applied previously. The major conclusion drawn from the present work is that Rao algorithms perform better when compared with other techniques in terms of MFE for the two-loop, Hanoi, and Go-Yang network. However, for the Kadu network and Farhadgerd network of Iran, the Rao algorithms also obtain a better solution with lower MFE. For the Kadu network, the optimal costs obtained by the Rao-I and Rao-II algorithms are not only 3.68 and 4.74% cheaper, but took just 20.80 and 16.41% of computational efforts as taken by GA. For the Farhadgerd network of Iran, the optimal solutions obtained by Rao-I and Rao-II are 0.17M$ and 0.3M$ cheaper when compared with the minimum optimal solution reported as well as 2.37M$ and 2.5M$ cheaper when compared with the maximum optimal solution reported so far in the literature. In addition to this, when the performance of Rao-I is compared with Rao-II, the latter converges much faster and obtained a similar cost to that of Rao-I or even better, especially for large networks. This is due to the larger involvement of the randomness in the Rao-II algorithm.

Since the Rao algorithms are metaphor-less and parameterless techniques, they are very simple in application and also free from the tuning of the parameters. The algorithms are capable of locating historically reported solutions with much better convergence. The present work highlights that Rao algorithms are the more efficient and reliable option for the optimization of WDN. This work may bring motivation to the researchers for developing new computational techniques that are preferably parameterless, such that they are not only simpler in construction but also as efficient as Rao techniques.

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