A novel self-adaptation and sorting selection-based differential evolutionary algorithm applied to water distribution system optimization

Water distribution systems (WDSs) are among the most expensive urban infrastructures owing to the large capital expenditure required for system construction (Al-Khomairi et al. 2020; Albarakati et al. 2021; Diao 2021; Lyu et al. 2021; Liu & Kang 2022). This inspires intensive studies into the optimal design of WDSs in order to minimize construction costs (Olsson 2020). The optimal design of WDS (WDS optimization) can be considered as a process that seeks a pipe diameter combination with the lowest network cost while meeting demand and pressure requirements (Yin et al. 2021). This process, however, is challenged by: (i) the huge search space encountered typically in practical engineering and (ii) the highly nonlinear constraints to be assessed, which necessitate the solution of a computationally expensive network simulation model (Wang et al. 2020; Zhang et al. 2022).

Many traditional optimization approaches have been developed for WDS optimization, such as linear and nonlinear programming (Alperovits & Shamir 1977; Lansey & Mays 1989). However, they are prone to being trapped by local minima due to the high-dimensional and discrete solution space of WDS optimization problems. As a consequence, population-based evolutionary algorithms (EAs) have gained popularity for WDS optimization. This is owing to their greater ability to explore broadly the entire solution space and the ease with which they can handle discrete pipe diameters, which traditional methods find difficult to handle. The GA (Simpson et al. 1994; Dandy et al. 1996; Savic & Walters 1997), particle swarm optimization (Suribabu & Neelakantan 2006), ant cony optimization (Maier et al. 2003), and the differential evolution (DE) algorithm (Suribabu 2010) are examples of representative EAs. According to comparison tests (Marchi et al. 2014), the DE algorithm outperforms other EAs in terms of finding optimal solutions for a wide variety of WDSs. However, the substantial computational burden due to slow convergence remains an issue when using DE for large-scale WDS optimizations, as well as other EAs (Maier et al. 2014; Mala-Jetmarova et al. 2018).

Certain preconditioning or heuristic approaches (Zheng et al. 2011; Kang & Lansey 2012; Bi et al. 2015; Liu et al. 2020) have been developed to obtain good initial solutions to improve the convergence speed of EAs. However, the approach proposed by Zheng et al. (2011) involves an extension of the Dijkstra graph algorithm to identify the shortest-distance tree of looped WDSs with multisource, which can be challenging to implement for practitioners with little expertise. In the studies of Kang & Lansey (2012), Bi et al. (2015), and Liu et al. (2020), specific programs must be designed to incorporate domain knowledge in order to find good initial solutions, making practitioners reluctant to employ these methods in their design work. Therefore, it would be more sensible to develop a computationally efficient and user-friendly EA for WDS optimization, given that the working principle of EA is theoretically much simpler and more likely to become a full-automatic optimization tool.

Besides, regarding the computational efficiency of EAs, Bi et al. (2016) have proved that while good starting solutions produced via preconditioning approaches enable more rapid identification of near-optimal solutions, the searching mechanism dominates the algorithm performance. More specifically, the searching mechanism that encourages exploitative search and allows for the rapid reduction of population diversity is the key to effectively identifying optimal solutions for large-scale WDS optimization problems. Therefore, modifying EAs' searching mechanism to improve the exploitative searching ability appears to be the soundest strategy to boost the computational efficiency of EAs in large-scale WDS optimization.

In addition to the low optimization efficiency, another issue that exists in EA applications is parameter adjustment, which is problem-dependent and has a significant impact on the algorithm performance. Taking DE-based WDS optimization as an example, while various studies have been undertaken and attempted to give general guidelines for selecting the control parameters F (the differential weight adopted in the mutation operator) and CR (the crossover probability adopted in the crossover operator), no agreement has been reached. Specifically, Zheng et al. (2015) suggested that a small F combined with a moderate CR within [0.3, 0.6] is preferred for efficiently solving large-scale WDSs, whereas Marchi et al. (2014) suggested that F = 0.3 with CR = 0.1 are the best parameter configuration for a real-size network (Rural with 476 pipes). Furthermore, Zheng et al. (2011) used F = 0.3 and CR = 0.8 to optimally design the Balerma network (BN) with 454 pipes and the ZJ network with 164 pipes. Although the aforementioned studies have made significant contributions to appropriately selecting F and CR values for WDS optimization, their inconsistent options on F and CR values highlight the fact that selecting appropriate F and CR values can be difficult for even seasoned experts, let alone practitioners with little related experience.

To address the parameter adjustment issue, Zheng et al. (2013) proposed a self-adaptive DE (SADE) algorithm that eliminates the need to manually adjust the F and CR values. Moreover, based on the fact that individuals in DE will eventually converge to an identical one, Zheng et al. (2013) proposed a convergence criterion to automatically terminate algorithm proceeds, which further increases the utility of SADE in practice. For large-scale WDS optimization, however, it appears that the SADE algorithm proposed by Zheng et al. (2013) does not perform as well as other EAs or even the classic DE. Specifically, SADE's best solution for the BN₄₅₄ case is €1.983 million, which is worse than the €1.923 million found by NLP-DE (Zheng et al. 2011), the €1.940 million found by HD-DDS (Tolson et al. 2009), the €1.9460 million found by FDE (Moosavian & Lence 2019), and the €1.982 million found by the classic DE (Zheng et al. 2011). Thus, further research is warranted to develop a more powerful self- adaptation DE for large-scale WDS optimization.

The goal of this paper is to propose a novel self-adaptation and sorting selection operator-based differential evolutionary (SA-SSDE) algorithm that can solve large-scale WDSs more efficiently, while also having a greater ability to explore global optimal solutions. This is achieved by introducing greedier mutation and selection operators that favor exploitation and a novel parameter adaptive strategy that can enhance exploration. The ability of an EA to broadly explore the whole search space is referred to as exploration, while the ability to intensively exploit the promising regions within the search process is referred to as exploitation (Maier et al. 2014). Excessive exploration causes slow convergence, whereas overexploitation induces premature convergence to inferior solutions. Therefore, a good balance between exploration and exploitation is important to ensure robust algorithm performance.

The following are contributions that fill gaps in the current literature and main findings of this study: (1) the DE/current-to-pbest/n mutation and sorting selection operators are proposed for the first time for WDS optimization; (2) the parameter adaptation strategy pioneered by Zhang & Sanderson (2009) in JADE is firstly introduced and modified to cater for WDS optimization; (3) new best solutions with the cost of $7.068, €1.9205, and $30.852 million of three well-known large networks (ZJ₁₆₄, Balerma₄₅₄, and Rural₄₇₆) are found with the proposed SA-SSDE algorithm; and (4) besides comparisons with other EAs on end-of-run performance, the searching behavior and the control parameter evolution (i.e., F and CR) during optimization are explored, which enhance knowledge regarding why one algorithm outperforms another, thereby providing a new perspective for developing more advanced EAs.

The rest of this paper is organized as follows. First, the formulation of the WDS optimization problem is presented, followed by a detailed description of the proposed SA-SSDE algorithm. Then, a brief description of four well-known WDS case studies, namely Hanoi network (HAN), ZJ, BN, and rural network (RN), is presented, which are used to validate the algorithm's efficacy. Following that, the proposed SA-SSDE algorithm is thoroughly investigated in the result and discussion section, including parameter sensitivity analysis, performance comparisons with other EAs, searching behavior comparisons between different mutation and selection operators, and the visualization of control parameter evolution. Finally, a summary and conclusions are drawn.

The evolutionary strategy of the proposed SA-SSDE algorithm is similar to that of the classic DE. Specifically, the algorithm enters a circle of evolutionary operations: mutation, crossover, and selection, following a random creation of the initial population. The proposed SA-SSDE, on the other hand, differs from classic DE in three aspects: (1) the DE/current-to-pbest/1 mutation with the archive is used to replace the DE/rand/1 mutation strategy; (2) the sorting selection operator is developed to replace the tournament selection operators in classic DE; and (3) the parameter adaptation strategy of JADE is introduced and modified to accommodate WDS optimization. The three modifications will be elaborated subsequently, and the convergence criterion provided by Zheng et al. (2013) is used to automatically terminate the algorithm proceeds.

The selection operator determines which of the target vectors or trial vectors survive to the next generation. The tournament selection operator, which performs a pair-wise comparison between the trial vector and the corresponding target vector, has been used in classic DE and nearly all DE variations. Such a pair-wise comparison strategy results in a one-to-one spawning relationship and a longer life span of inferior individuals, which thus benefits the maintenance of population diversity. However, this benefit can sometimes turn into a drawback since it might lead to a significantly higher computational burden due to the resultant longer generations required to achieve convergence (Noman & Iba 2008). This is especially true for problems that require a longer simulation time for objective function evaluation, such as large-scale WDS optimization. In fact, as revealed by Bi et al. (2016), the searching mechanism that allows population diversity to be rapidly reduced (i.e., favors exploitative searching) is better suited for large-scale WDS optimization.

To this end, the sorting selection operator is developed to allow as many fitter trial vectors as possible to survive into the next generation, which therefore encourages the rapid reduction of population diversity. The proposed sorting selection procedure is straightforward and comprises the three phases listed subsequently. First, all individuals in trial and target vectors are classified as feasible or infeasible solutions. Second, individuals in the feasible solution group are sorted in ascending order based on objective function values, whereas individuals in the infeasible solution group are sorted in ascending order based on constraint violations. Third, selection can be accomplished by giving priority to choosing feasible solutions with smaller objective function values, followed by infeasible solutions with smaller constraint violations until the number of selected individuals reaches the pre-specified population size. The following pseudo-code can be used to sort a population with feasible and infeasible solutions.

Pseudo-code for sorting population of feasible and infeasible solutions

The primary idea behind the parameter adaption strategy (PAS) is to record F and CR values that can generate better trial vectors in the current generation and then utilize them to generate new F and CR values in the next generation. The PAS in JADE, pioneered by Zhang & Sanderson (2009), has been demonstrated to work well with the DE/current-to-pbest/1 mutation operator and is adopted in this study, but with the following two modifications to cater for WDS optimization.

Pseudo-code of the proposed SA-SSDE algorithm

As shown in Table 1, four WDS case studies with increased network complexity have been used to test the efficacy of the proposed SA-SSDE algorithm. Detailed information for the HAN and BN, including the commercially available diameters and the corresponding unit pipe costs, is available from the website of the Centre for Water Systems at the University of Exeter (Wang et al. 2015). For details on the ZheJia (ZJ) network and the RN, see Zheng et al. (2011) and Marchi et al. (2014), respectively.

These four WDSs were chosen for the following two reasons. First, they are all from publicly available literature and based on EPANET simulation, and thus their fundamental information is readily available, allowing the exact replication of optimization results as well as a comparison with other EAs. Second, all four WDSs have either a rugged solution space or an unknown global optimum, which are representative of difficult optimization problems faced in real-world situations and hence useful in evaluating the algorithm's global searching ability.

As mentioned previously, six parameters (μ_F, μ_CR, σ_F, σ_CR, p, and c) that affect algorithm performance need to be initialized. Based on the four WDS cases mentioned in the preceding section, parameter sensitivity tests were performed and show that four of them (μ_F, μ_CR, c, and p) have an insignificant impact on algorithm performance, which agrees with the earlier work of Zhang & Sanderson (2009). Surprisingly, it was observed that σ_F = 0.01 and σ_CR = 0.01 are better suited for WDS optimization problems. Table 2 presents the statistical results of the proposed SA-SSDE algorithm with various σ_F and σ_CR values applied to four WDS case studies. Other parameters were set as μ_F and μ_CR = 0.7, c and p = 0.2 based on the recommendation of Zhang & Sanderson (2009). A population size of 300 was used for all case studies, since increasing the population size only slightly improved solution quality while significantly increasing computational costs.

Results in Table 2 reveal an interesting finding, and consistently for four WDS optimizations, the smaller σ_F and σ_CR (e.g., σ_F and σ_CR = 0.01) provide an improved algorithm performance in both solution quality and computational efficiency, particularly for three large-scale WDSs. Specifically, for the BN case, the algorithm with σ_F and σ_CR = 0.01 produced an optimal solution of $1.9205 million, which is better than $1.9224 and $1.9230 million found by σ_F and σ_CR = 0.05 and 0.1. Moreover, σ_F and σ_CR = 0.01 enable faster convergence using only 789,705 evaluations averaged over 10 runs, nearly 30% fewer than the 1,118,025 evaluations required by σ_F and σ_CR = 0.1. Similar observations can be made for the remaining three case studies, demonstrating that σ_F and σ_CR = 0.01 are better suited for WDS optimization. This finding differs from SaDE (Qin et al. 2009), JADE (Zhang & Sanderson 2009), MDE_pBX (Islam et al. 2012), and ADDE (Zhan et al. 2019), in which the σ_F and σ_CR are fixed as 0.1 to solve various numerical benchmarks, thereby providing improved knowledge on developing more powerful PAS to solve real-world engineering problems.

The improved algorithm performance associated with σ_F and σ_CR = 0.01 can be explained by the fact that smaller σ_F and σ_CR enable F and CR to be generated in a narrower but more suitable region than larger σ_F and σ_CR. As a result of generating a greater number of suitable F and CR, a larger number of better trial vectors can be produced, thereby leading to improved algorithm performance. It is worth noting that utilizing too small F and CR values (such as 0.001) can result in F and CR values being generated in an excessively limited range, leading to poor parameter adaptation ability and thereby poor algorithm performance.

Performance comparisons with other EAs are undertaken in this section to verify the efficacy of the proposed SA-SSDE algorithm. Table 3 summarizes the optimization results of the proposed SA-SSDE algorithm and other EAs applied to four WDS case studies, where optimal results are ranked based on the best solution found, with the higher rank indicating more competence in exploring global optimums.

According to the results in Table 3, the proposed SA-SSDE algorithm outperforms other EAs in finding the global optimum for three large-scale WDSs (i.e., ZJ₁₆₄, BN₄₅₄, and RN₄₇₆). Specifically, the proposed SA-SSDE algorithm found new best solutions for ZJ, RN, and BN with costs of $7.068, $30.852, and €1.9205 million, which are better than the current best solution of $7.082, $31.221, and €1.9214 million reported by Zheng et al. (2011), Marchi et al. (2014), and Cisty et al. (2016), respectively. Furthermore, as shown in Table 3, the average solutions obtained by the proposed SA-SSDE method for ZJ₁₆₄, BN₄₅₄, and Rural₄₇₆ cases are also better than those of other EAs, demonstrating the robustness of the proposed SA-SSDE algorithm. For the HAN case, the proposed SA-SSDE performs slightly worse than the NLP-DE. This is due to the HAN case's small solution space, for which the proposed SA-SSDE algorithm achieves convergence in a few generations and the F and CR values have not yet been self-adapted.

In terms of computational efficiency, the proposed SA-SSDE algorithm also performs better than the majority of other EAs for ZJ, RN, and BN cases. For example, for the BN case, the TS-NSGA (Cisty et al. 2016) method used 10,640,000 evaluations to find the current best solution of €1.9214 million, whereas the proposed SA-SSDE algorithm required just 787,365 evaluations to find the new best solution of €1.9205 million. More importantly, in contrast to the pre-specified 20,000,000 evaluations for TS-NSGA to terminate the algorithm proceeds, the proposed SA-SSDA algorithm uses only 819,375 evaluations to do that when convergence criteria are met, implying greater computational efficiency and application convenience.

It is worth noting that the advantage of the proposed SA-SSDE algorithm rises with network size increases, notably in terms of computational efficiency. Specifically, the proposed SA-SSDE algorithm found the optimal solution of $6.081 million for the HAN₃₄ case, with a similar computational overhead to the standard DE, as shown in Table 3. In contrast, the proposed SA-SSDE algorithm found the new best optimal solutions for three larger cases with significantly less computational overhead than classic DE. More specifically, the proposed SA-SSDE algorithm only requires 405,670; 787,365; and 817,380 average evaluations to find the optimal solutions for ZJ, BN, and RN cases, whereas the traditional DE requires 820,657; 2,300,000; and 5,712,809 average evaluations, indicating that the proposed algorithm converges 1.02, 1.92, and 5.99 times faster than the classic DE for three large networks.

To summarize, the previously mentioned comparisons demonstrate the superiority of the proposed algorithm for large-scale WDS optimization. This can be attributed to (1) the adaptation of DE/current-to-pbest/n mutation and the sorting selection operators, which encourages exploitative searching and thus improves optimization efficiency, and (2) the improved parameter self-adaptation strategy, which enables a dynamical balance between exploration and exploitation according to the fitness landscape characteristic of large-scale WDS optimization problems, resulting in enhanced exploring ability. Detailed explanations will be given in the following sections.

This section compares the searching behavior between the traditional and the proposed mutation and selection operators, namely the DE/rand/1 mutation with the tournament selection operators used in classic DE and the DE/current-to-pbest/n mutation with the sorting selection operators used in the proposed SA-SSDE algorithm. Such a comparison aims to gain a deep understanding of how mutation and crossover operators affect the algorithm performance.

By comparing the decrease speed of d_mean(G) presented in the right and left panels in Figure 2, it is clearly seen that the proposed mutation and selection operators result in a notably faster decrease of d_mean(G) than traditional operators, regardless of which pairs of F and CR are used. The rapid decrease of d_mean(G) is most clearly shown in subfigure (b) for CR = 0.1, where the proposed mutation and selection operators require no more than 250 generations to reach convergence, regardless of the F values chosen. The classic DE with CR = 0.1, on the other hand, exhibits an extremely slow convergence speed even with F = 0.1, as seen in subfigure (a) in Figure 1. As a result, it can be concluded that the proposed mutation and selection operators favor exploitative searching as opposed to exploratory searching emphasized by traditional mutation and selection operators in classic DE. This is to be expected because the proposed mutation and selection operators are more greedy in terms of producing and selecting fitter trial vectors, resulting in faster convergence of d_mean(G), and thus exploitative searching behavior.

More importantly, the left panels of Figure 2 show that the classic DE with F ≥ 0.5 cannot reach convergence in 10,000 generations. This suggests that, under an appropriate computational budget, classical DE can only employ a lower value of F (F ≤ 0.3) for large-scale WDS optimization. This phenomenon has also been noted by Zheng et al. (2015) and Bi et al. (2016), resulting in a lack of exploratory ability of the classic DE in exploring global optimums for large WDSs (e.g., ZJ, RN, and BN), as seen from the results in Table 3. In contrast, due to the employment of greedy mutation and selection operators, the proposed SA-SSDE algorithm can converge fast even with extremely high F, as reflected by the subfigures (b), (d), and (f) in Figure 2. This enables the greater ability of the proposed SA-SSDE algorithm to explore global optimums while allowing for faster convergence.

The previous searching behavior comparisons illustrate why the proposed SA-SSDE algorithm outperforms the classic DE in optimization efficiency, guiding the design of more advanced EAs by manipulating its searching behavior with modified mutation and selection operators.

As can be seen from left panels in Figure 3, except for the optimization of HAN, which needs less than 150 generations to attain convergence due to its relatively smaller solution space, three changing phases of μ_F and μ_CR are clearly observed for the optimization of three large networks (i.e., ZJ, BN, and RN). In particular, the value of μ_F declines rapidly in contrast to the rapid rise of the μ_CR during phase I. This was followed by a continual increase in μ_F and a consistent decrease in μ_CR during phase II. Finally, there is a significant increase in μ_CR during phase III, as well as a moderate increase of μ_F.

However, given the rugged solution space at the bottom of the big bowl, exploratory searching associated with increasing μ_F will aid the search to escape from local optimal solutions during phase II. This is illustrated by the slow improvement rate of the best solution found in this phase, as shown in the right panels of Figure 3. In phase III, stronger exploratory searching is necessary to further polish optimal solutions identified in phase II, explaining why μ_F and μ_CR abruptly increased. Based on the previous analysis, it is clear that the proposed PAS is capable of dynamically adapting appropriate μ_F and μ_CR to the fitness landscape characteristics of larger-size WDS optimization problems, resulting in a dynamical balance between exploitation and exploration. This explains why the proposed SA-SSDE algorithm is superior at exploring global optimums while also being more efficient.

This paper presents a novel SA-SSDE algorithm that aims to address issues regarding the slow convergence, reduced exploratory ability, and parameter adjustment encountered with the classic DE for large-scale WDS optimization. The DE/current-to-pbest/n mutation and sorting selection operators, as well as an enhanced parameter adaptation strategy, are employed in the proposed SA-SSDE algorithm to achieve this aim. The efficacy of the proposed SA-SSDE algorithm was validated using four well-known WDSs, including three large well-known networks (ZJ₁₆₄, BN₄₅₄, and RN₄₇₆), with studies into searching behavior and control parameter evolution providing the following conclusions:

• (1)

  The proposed SA-SSDE algorithm outperforms existing EAs in terms of exploring global optimums for large-scale WDS optimization problems, as evidenced by the discovery of new best solutions for ZJ₁₆₄, BN₄₅₄, and RN₄₇₆ with costs of $7.068 million, €1.9205 million, and $30.852 million, respectively. Nevertheless, it should be emphasized that because all EAs are stochastic, the uncertainty in solution quality might be as high as 3%. This uncertainty can be reduced by increasing population size and running the proposed SA-SSDE algorithm with a different initial population.

• (2)

  The proposed SA-SSDE algorithm has a significantly faster convergence speed than the classic DE, and this advantage grows with network size. This is reflected by the fact that the proposed SA-SSDE algorithm found optimal solutions 1.02, 1.92, and 5.99 times faster than the classic DE for ZJ₁₆₄, BN₄₅₄, and RN₅₅₉ cases with increased network size. Note that rather than the DE/current-to-pbest/n mutation operator, the sorting selection operator is the key to speeding up DE's convergence. The DE/current-to-pbest/n mutation operator works better with PAS than the traditional DE/rand/1 mutation operator, which is why this study used it.

• (3)

  The proposed DE/current-to-pbest/n mutation and sorting selection operators allow for rapid reduction of population diversity even with a large F, encouraging exploitative searching. This explains why the proposed SA-SSDE algorithm surpasses the classic DE in terms of computational efficiency, providing the groundwork for developing more efficient EAs by modifying the mutation and tournament selection operators.

• (4)

  The proposed parameter self-adaptation strategy can dynamically adapt appropriate F and larger CR values to the WDS optimization problems with a big-bowl function structure, with small F and larger CR generated early to encourage exploitative searching and large F and small (mediate) CR generated later to support exploration searching. The resultant dynamical balance between exploitation and exploration leads to the superior ability of the proposed SA-SSDE algorithm to explore global optimums. However, because the proposed SA-SSDE algorithm is designed specifically for WDS optimization problems with a large bowl function structure and extremes tightly grouped at the bottom, its performance on other problem types may suffer according to ‘no free lunch theorem’. More case studies are needed to evaluate the proposed algorithm's performance in future work.

• (5)

  The six parameters in PAS were subjected to parameter sensitivity tests, with the findings indicating that σ_F and σ_CR = 0.01 are more suited for WDS optimization. This finding differs from existing studies that use σ_F and σ_CR = 0.1 for various numerical benchmarks, allowing researchers to develop more powerful PAS to solve real-world engineering problems. Besides, when compared to other well-known PASs like those in the jDE (Brest et al. 2006) and the SADE (Zheng et al. 2013), the PAS framework proposed by Zhang & Sanderson (2009) in JADE is more suited for WDS optimization and hence merits greater attention from WDS researchers.

• (6)

  Results in the case study demonstrate the merit of the proposed SA-SSDE algorithm in least-cost single-objective WDS optimization, and future research will extend it to multi-objective WDS optimization problems. In addition, the proposed SA-SSDE algorithm can also be utilized to solve other water resources management problems, such as burst localization (Zhou et al. 2019) and model calibration (Chen et al. 2022).

This work is supported by the Key R&D projects in Yunnan Province (202003AC100001), the Key R&D plan of Yunnan Province (202103AC10017), and the National Natural Science Foundation of China (51608424). The authors thank to Dr Qi Wang for providing the WDS simulation code which greatly facilitates algorithm performance testing. We are also thankful to the reviewers for their constructive suggestions which greatly improved the quality of this paper.

All relevant data are included in the paper or its Supplementary Information. Pipe diameter combinations for the new best solutions of ZJ, RN and BN cases are given in supplementary file, as well as comparison between the optimal results of €1.9205 million and €1.9230 million for BIN case, aiming to help readers better understand the optimal results.

The authors declare there is no conflict.