Auto-enhanced population diversity and ranking selection-based differential evolutionary algorithm applied to the optimal design of water distribution system

Water distribution systems (WDSs) require a significant amount of capital for their construction, making them one of the most expensive types of urban infrastructure to build (Al-Khomairi et al. 2020; Albarakati et al. 2021; Liu & Kang 2022; Xiong & Wang 2022). Therefore, researchers have conducted extensive studies on optimizing WDS design to minimize construction costs (Bi et al. 2015). This optimization process involves finding the combination of pipe diameters that results in the lowest network cost while meeting pressure and demand requirements (Yin et al. 2021; Wang et al. 2022; Yilmaz et al. 2022). However, this task is challenging due to the vast search space encountered in practical engineering and the highly nonlinear constraints that need to be evaluated (Maier et al. 2014; Wang et al. 2020; Zhang et al. 2022).

Traditional optimization methods, including linear and nonlinear programming (NLP), have been employed for WDS optimization (Alperovits & Shamir 1977; Lansey & Mays 1989; Mala-Jetmarova et al. 2018). However, the high-dimensional and discrete nature of WDS optimization problems can cause these methods to become trapped in local minima (Tolson et al. 2009). As a result, population-based evolutionary algorithms (EAs) have become increasingly popular for WDS optimization due to their ability to explore the solution space more broadly and handle discrete pipe diameters with ease, which traditional methods struggle to do. Some representative EAs include the genetic algorithm (GA) (Simpson et al. 1994; Dandy et al. 1996; Savic & Walters 1997), particle swarm optimization (Suribabu & Neelakantan 2006), ant colony optimization (Ursem 2002; Maier et al. 2003), and differential evolution (DE) algorithm (Suribabu 2010). Comparative analysis has demonstrated that the DE algorithm is superior to other EAs in finding optimal solutions for various WDSs (Marchi et al. 2014; Zheng et al. 2015; Moosavian & Lence 2019). Nevertheless, when applying DE to large-scale WDS optimizations, the issue of premature convergence persists and can lead to DE's inability to explore global optimal solutions (Qin et al. 2009; Zhang & Sanderson 2009).

Consider the optimal design of the Balerma irrigation network (BIN) as an example. The DE algorithm yielded the best solution of €1.983 million (Zheng et al. 2011), which was notably inferior compared to the solutions obtained using the HDP-GA (€1.941 million) (Liu et al. 2020), NLP-DE (€1.923 million) (Zheng et al. 2011), and TS-NSGA (€1.9214 million) (Cisty et al. 2016) algorithms. However, although these hybrid algorithms have shown great performance, it is worth noting that they require additional expertise or mathematical skills to narrow down the solution space or generate an initial solution to guide the EA's search. As a result, these could be challenging for practitioners to use in engineering practice. For instance, the HDP-GA algorithm involves identifying a solution based on the least head loss for each pipe in the supply path, followed by refining the solution using the GA. Practitioners need to develop a specific program to iteratively adjust pipe diameters when implementing the HDP method. Similarly, the NLP-DE approach utilizes graph theory and NLP algorithms to generate an initial solution and identify the approximate region of the optimal solution, necessitating graph theory and NLP expertise. Additionally, the TS-NSGA method involves a two-stage optimization process, where sub-optimal solutions are obtained in the first stage to narrow down the search space in the second stage. This method requires implementing NSGA-II twice with varying parameters and expertise in narrowing down the search space.

This paper presents a novel optimization algorithm called the auto-enhanced population diversity and ranking selection-based differential evolutionary (AEPD-RSDE) algorithm for the optimal design of WDSs. Unlike the above hybrid algorithms, AEPD-RSDE overcomes the issue of premature convergence and improves the exploration of global optimal solutions without requiring additional expertise or mathematical skills, making it more practical for real-world applications. The algorithm's core idea is to automatically enhance population diversity when convergence and stagnation are detected at the dimensional level. In addition, to accelerate convergence and reduce computational overhead, the algorithm includes a ranking selection strategy that replaces the tournament selection operator. This strategy is designed to select the most superior individuals in the trial and target vectors for the next generation, rather than using pair-wise comparison as in the tournament selection operator.

The design concept of the proposed AEPD-RSDE algorithm is to incorporate a greedy selection strategy to facilitate rapid convergence and utilize the AEPD strategy to enhance the exploration of the solution space. This concept is derived from the latest developments in the field of DE research. Specifically, in DE research, common approaches to enhance convergence speed involve modifying mutation, crossover, and selection strategies. For example, Das et al. (2009) introduced two topological neighborhood models into the DE mutation operator. Mallipeddi & Suganthan (2010) presented EPSDE, a DE variant that utilizes an ensemble of mutation and crossover strategies with control parameters. Dorronsoro & Bouvry (2011) developed HdDE, a heterogeneous distributed algorithm with two islands employing DE/rand/1/bin and GPBX-α mutation strategies. Tian et al. (2017) proposed a novel DE algorithm that combines a diversity-based selection strategy with a combined mutation strategy to improve search efficiency. In the AEPD-RSDE algorithm, the DE/current-to-pbest/1 mutation operator proposed by Zhang & Sanderson (2009), and the ranking selection operators proposed by Du et al. (2022) are adopted to enable fast convergence.

Another crucial aspect of DE research focuses on preserving population diversity, which is essential for preventing premature convergence and facilitating effective exploration of the solution space. This direction can be categorized into three approaches. The first approach involves adjusting the values of parameters F and Cr to increase the variance of the trial vector population, thereby promoting population diversity. Adaptive DE algorithms such as SaDE (Qin & Suganthan 2005), jDE (Brest et al. 2006), and JADE (Zhang & Sanderson 2009) fall into this category. The second approach addresses population diversity by perturbing population elements through the re-initialization of specific individuals (Mendes & Mohais 2005), specifically designed for dynamic optimization problems. Another strategy is selective destruction (Maresky et al. 1995), where a certain proportion of genes that have converged are retained for the next convergence phase, while the remaining genes are reinitialized. The third approach involves structured populations and controlled migration to preserve population diversity. For example, Blackwell & Branke (2004) proposed the DynDE algorithm, which utilizes an exclusion strategy to ensure that each population remains on different peaks. In the proposed algorithm, the AEPD strategy, initially proposed by Yang et al. (2015), is introduced and modified to restart the research when convergence or stagnation is detected.

This study makes two significant contributions to the optimal design of WDS. Firstly, it introduces the novel application of AEPD to DE-based optimal design of WDSs, which is validated for the first time using three well-known benchmark networks. Secondly, the study compares different mutation and selection strategies, not only focusing on ultimate performance but also on algorithm search behavior. This provides valuable insights into the impact of varied mutation and selection strategies on algorithm search behavior, guiding the development of more advanced EAs in the future.

The remaining sections of this paper are structured as follows. Firstly, the optimal design formulation for WDS is presented, followed by a description of the proposed AEPD-RSDE algorithm. Then, a brief overview of three WDS case studies is presented. The results and conclusions are presented in the following section, which includes a comparison of the algorithm's performance with that of other EAs, an illustration of the effectiveness of the AEPD strategy, and a comparison of the searching behavior between different mutation and selection strategies. Finally, the paper concludes with a summary and conclusions.

The proposed AEPD-RSDE algorithm has a similar evolutionary scheme to the traditional DE algorithm, which includes mutation, crossover, and selection. However, the proposed algorithm has three main improvements over the traditional DE algorithm: (1) it uses the DE/current-to-pbest/1 mutation with an archive operator instead of the DE/rand/1 mutation; (2) it uses a ranking selection strategy instead of a tournament selection; and (3) it introduces and modifies the AEPD strategy to accommodate the WDS optimization problem. These three improvements are elaborated as follows.

Selection is a crucial operator that enables population evolution by selecting better individuals after applying mutation and crossover operators. DE and most DE variants employ the tournament selection operator, which compares the trial vector and the target vector pair-wise. Therefore, this strategy is beneficial in maintaining population diversity as it extends the life span of inferior individuals (Noman & Iba 2008; Islam et al. 2012). However, this strategy might also slow down the convergence and significantly increase the computation cost, especially for problems with long simulation times, such as large-scale WDS optimization. In fact, Bi et al. (2016) showed that a searching mechanism that reduces population diversity quickly and favors exploitative searching is better for large-scale WDS optimization.

To this end, the ranking selection operator is designed to allow as many superior individuals as possible in the trial vector and the target vector to survive to the next generation instead of pair-wise comparison. The proposed ranking selection strategy is intuitively straightforward and consists of three steps. First, we classify the individuals in the trial and target vectors as either feasible or infeasible solutions. Second, we sort the feasible solutions in ascending order of their objective function values, and the infeasible solutions in ascending order of their constraint violations. Third, we select the individuals by giving preference to the feasible solutions with the lowest objective function values, and then to the infeasible solutions with the lowest constraint violations, until we reach the desired population size. The pseudo code shows how to sort a population with both feasible and infeasible solutions.

Pseudo code for sorting population with both feasible and infeasible solutions

The AEPD strategy is a mechanism that automatically diversifies a population at the dimensional level when it converges or stagnates, based on the population distribution measurement. Yang et al. (2015) first proposed the AEPD strategy for continuous variable optimization problems, which requires some modifications to adapt to WDS optimization that deals with real number variables. The modified AEPD strategy is applied after the selection operator, as described below.

Step 1: Identification of Population Convergence or Stagnation

Yang et al. (2015) proposed that UN, an integer value, could be equivalent to the total population size. If λ_j,G ≥ UN, the value of is set to 1, indicating that the population reaches stagnation in the jth dimension as its distribution remains unchanged for several consecutive generations.

Step 2: Enhancement of Population Diversity

The AEPD-RSDE algorithm proposed in this study was evaluated using three case studies, which are listed in Table 1. The necessary information about the networks, including the available diameters and the corresponding unit pipe costs, can be found on the Centre for Water Systems website at the University of Exeter (Wang et al. 2015). These three cases have been most widely utilized in the previous research to assess the effectiveness of different EAs. Thus, using these cases facilitates comparisons between the proposed AEPD-RSDE algorithm and other EAs.

Table 2 provides a summary of the results obtained from applying the proposed AEPD-RSDE algorithm and other EAs to three different case studies. The table allows for a comparison of the performance of different EAs on networks of varying sizes. The results in Table 2 are ranked based on the percentage of trials that resulted in the best solution found (fifth column). Note that in the case of the NYT and HAN networks, it appears that different algorithms achieved the same average cost solutions. This can be attributed to the rounding-up of calculations when the solutions are very close. In such situations, the ranking of algorithms is determined based on the percentage of the best solution found.

Besides, for the AEPD-RSDE algorithm, the following tuned-parameter settings were used: NP = 100, F = 0.9, and Cr = 0.6 for the NYT case; NP = 300, F = 0.7, and Cr = 0.7 for the HAN case study; and NP = 500, F = 0.6, and Cr = 0.2 for the BIN case, where NP represents the number of population size. For parameter settings in different WDS optimization problems, it is advisable to select F values ranging from 0.5 to 0.7 and Cr values ranging from 0.1 to 0.3 for large-size networks. For small-size networks, it is recommended to choose F values ranging from 0.7 to 0.9 and Cr values ranging from 0.5 to 0.7.

Based on the results shown in Table 2, it can be observed that the proposed AEPD-RSDE algorithm performs better than other EAs in terms of exploring the global optimum for the three case studies. This is evidenced by the fact that the proposed algorithm achieved a 100% success rate in finding the current best solution for the NTY and HAN cases, which is higher than other EAs. Moreover, the proposed AEPD-RSDE algorithm obtained the current best solution of €1.9205 million, which is better than the solutions of €1.9214 and €1.923 million reported by Cisty et al. (2016) and Zheng et al. (2011) using the TS-NSGA and NLP-DE algorithms, respectively. Additionally, the proposed AEPD-RSDE algorithm outperformed the SA-SSDE (Du et al. 2022) in terms of the average cost solution, with €1.921 million being smaller than €1.924 million. These results highlight the merit of the proposed AEPD-RSDE algorithm in exploring the global optimal solution for larger-size WDSs, which are representative of those encountered when solving practical engineering problems. This superior performance can be attributed to the adoption of the AEPD strategy, which will be illustrated in the next section.

In terms of computational efficiency, comparisons across the three case studies demonstrate the advantage of the proposed AEPD-RSDE algorithm in solving large-size networks. For instance, in the BIN case with 454 variables, the proposed AEPD-RSDE algorithm identified the optimal solution using only 2,073,600 average evaluations, which is significantly less than the 10,640,000 evaluations required by TS-NSGA and the 9,210,143 evaluations for traditional DE^f. Although NLP-DE takes fewer evaluations to find the optimal solution, it involves the use of graph theory and NLP algorithms to identify a good initial solution to guide DE's search. Additionally, while SADE requires only 1,200,000 evaluations to identify the optimal solution, the identified solution with a cost of €1.983 million is considerably worse than the solution of €1.9205 million found by the proposed AEPD-RSDE algorithm. The great computational benefit of the SA-SSDE algorithm can be attributed to its use of the parameter self-adaptation strategy, while the proposed algorithm uses a fixed parameter setting in addition to the AEPD strategy.

Despite the computational efficiency of the BIN case, the proposed AEPD-RSDE algorithm requires more evaluations for the NYT cases than most other EAs. Specifically, the proposed AEPD-RSDE algorithm found the final optimal solution for the NYT case using 17,864 evaluations, which is significantly greater than the 5,492 and 6,598 evaluations taken by traditional DE and traditional SADE, respectively. This can be explained by the fact that the NYT case has a small and smooth solution space, whose optimal solution can be easily identified without needing the proposed AEPD strategy. Nevertheless, it is important to note that the solving time for small-size networks is typically quite small, and the increased evaluations associated with optimization will not result in a heavy computational burden, thus not impeding the practical application of the proposed algorithm.

The term 2/N(N − 1) represents the total number of pairs of candidate solutions. The D_mean metric provides a quantitative measure of solution dispersion across the search domain, where larger and lower values correspond to periods of high exploration (widespread search within the decision space) and exploitation (focused search within the decision space), respectively. The variation of mean search distance with each generation indicates the convergence behavior. A D_mean value of 0 signifies that all individuals converge to the same solution, leading to a loss of ability to explore better solutions.

As shown in the left panel of Figure 1, the overall value of D_mean decreases as the number of generation increases, suggesting a convergence of individuals through the process of evolution. Furthermore, the red dots indicate that the proposed AEPD strategy automatically enhances population diversity when the D_mean value reaches zero. This feature allows the evolutionary search to restart and explore better solutions. Specifically, for the NYT case, one auto-diversify action was performed, resulting in an improvement from $38.81 million to $38.64 million (see Figure 1(b)). For the HAN and BIN cases, two and three auto-diversity actions were observed, respectively, to achieve the final optimal solution (see Figure 1(c)–1(f)). Additionally, as shown by the blue dot in Figure 1(e), an auto-diversify action is seen prior to full convergence for the BIN case. This random action aids in restarting the search, avoids the local optimum, and is especially beneficial while exploring the global optimum of large-size WDS with high problem dimensions.

The above illustration is based on just one trial, and to provide a better understanding of the proposed algorithm, Table 3 summarizes the auto-diversity activities across all trials. The results show that for the NYT and HAN cases, the vast majority (88 out of 100 and 85 out of 100 trials, respectively) did not require any auto-diversity actions to achieve the current best solution. However, for the BIN case, 6 out of 10 trials required more than 5 times of auto-diversity actions to identify the final optimal solution. This is expected as the BIN case has a substantially larger solution space compared to the NYT and HAN cases, and hence more auto-diversity actions are required. The results indicate that the proposed AEPD approach, when sufficient computational resources are available, can consistently diversify the population and explore enhanced solutions, particularly for large-scale WDS optimization problems. This explains the excellent performance of the proposed algorithm in exploring the global optimal solution.

An interesting observation from the BIN case is that fewer generations are required to achieve convergence after auto-diversity action. Figure 1(e) shows that the search required around 2,000 generations to achieve the first convergence, but after the first auto-diversity action, it only took less than 1,000 generations to converge again. This phenomenon can be attributed to the fact that the search after auto-diversity is guided by the optimal solution previously identified, which leads to faster convergence and, subsequently, fewer evolutions required. This partly explains why the proposed AEPD-RSDE algorithm efficiently explores the global optimum.

In Figure 2, the black, blue, red, and purple lines represent the results of using the DE/rand/1 mutation with tournament selection (traditional DE), the DE/current-to-pbest/1 mutation with tournament selection operators, the DE/rand/1 mutation with ranking selection operators, and the DE/current-to-pbest/1 mutation with ranking selection (proposed algorithm), respectively. All results in Figure 2 are based on the same parameter setting with a population size of 500, F = 0.6, and Cr = 0.2. We did not consider the AEPD strategy to focus on the performance difference across different combinations of mutation and selection operators.

Figure 2(a) illustrates that the proposed algorithm has the most rapid decrease speed in D_mean values (purple line), while the traditional DE exhibits the slowest decrease (black line). This finding explains why the proposed AEPD-RSDE algorithm can converge faster than the traditional DE, resulting in computational efficiency. Moreover, the DE/current-to-pbest/1 mutation operator (blue line) shows a relatively faster decline than the DE/rand/1 mutation operator (black line). This outcome is not surprising as the DE/current-to-pbest/1 mutation operator is a greedy operator that favors the quicker reduction of population, leading to a faster decrease of D_mean. However, the ranking selection strategy proves to be more effective in reducing D_mean than the DE/current-to-pbest/1 mutation operator, as the red line declines faster than the blue line in Figure 2(a). This observation suggests that the proposed ranking selection strategy, rather than the DE/current-to-pbest/1 mutation operator, is the primary driver that enables the rapid decrease of D_mean, making the proposed AEPD-RSDE algorithm a faster-convergent one.

Analysis of both Figure 2(a) and 2(b) indicates that the algorithm's ability to explore better optimal solutions is positively correlated with its convergence speed. Specifically, the more rapid the increase in D_mean value, the better the algorithm is at finding optimal solutions. This finding aligns with Bi et al.’s (2016) discovery that a searching mechanism favoring exploitation (i.e., a rapid reduction in population diversity) enables the identification of near-optimal solutions more quickly. For instance, as seen in Figure 2(b), the proposed algorithm identified the solution of €1.923 million and achieved convergence in approximately 2,000 generations, whereas the traditional DE failed to converge even after 5,000 generations, and its identified solution of €2.997 million is significantly worse than €1.923 million.

It is important to note that the performance of the algorithm is highly dependent on the parameter settings (i.e., the values of F and Cr), and the values of F = 0.6 and Cr = 0.2 used in the above tests may not be the best parameter settings for the traditional DE. Zheng et al. (2011, 2013) found that the traditional DE with F = 0.3 and Cr = 0.8 achieved the best performance, identifying the solution of €1.982 million using approximately 18,420 generations. However, this performance is still significantly worse than that of the proposed algorithm, which identified the solution of €1.923 million in only 2,000 generations. Therefore, it can be concluded that combining the DE/current-to-pbest/1 mutation operator with the proposed ranking selection strategy can be a better alternative to the traditional DE for optimal design of large-size networks. This finding is valuable as it provides new insights into designing advanced EAs by modifying the selection operator.

The previous studies have reported that DE is a powerful algorithm for optimizing WDSs, but it can encounter problems with premature convergence, particularly for large networks. To address this issue, this paper proposes the AEPD-RSDE algorithm, which incorporates an AEPD strategy to restart the search when population convergence is detected. Additionally, a ranking selection strategy is developed to facilitate faster convergence, leading to improved computational efficiency. The proposed algorithm is evaluated on three well-known networks, and the results indicate that:

• (1)

  The proposed AEPD-RSDE algorithm outperforms other EAs in exploring the global optimum, thanks to its AEPD strategy that consistently diversifies the population for improved solutions, especially for large WDS optimization problems. Its reliability in locating high-quality solutions is evident in achieving a 100% success rate in finding the best solution for the NYT and HAN cases. In addition, for the BIN case, the AEPD-RSDE algorithm obtained an average cost solution with a cost of €1.921 million, surpassing the €1.924 million solution reported by Du et al. (2022) using SA-SSDE.

• (2)

  Comparing mutation and selection strategies, the proposed ranking selection strategy drives the rapid convergence of the AEPD-RSDE algorithm, making it more computationally efficient than traditional DE. The DE/current-to-pbest/1 mutation operator with the ranking selection strategy could be better suited for large network optimization than DE/rand/1 mutation with tournament selection, as evidenced by the former finding the €1.923 million solution in 2,000 generations, compared to the latter's 18,420 generations to find the €1.982 million solution. These findings inform the development of advanced EAs by providing a better understanding of operator influences.

Although the AEPD-RSDE method has demonstrated remarkable performance in solving large-scale WDS optimization problems using the BIN network, further investigations are necessary to fully assess its effectiveness in optimizing real-life WDSs with thousands of nodes and pipes. Additionally, in order to provide a more comprehensive demonstration of the advantages of the proposed algorithm, it is crucial to conduct further comparisons with other metaheuristic methods and explore the potential benefits of combining the proposed strategies with other existing metaheuristic approaches.

This work was funded by the National Natural Science Foundation of China (52260011) and the Yunnan Key Research and Development Program (202203AC100004).

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

The authors declare there is no conflict.