Fittest Individual Referenced Differential Evolution Algorithms for Optimization of Water Distribution Networks

摘要

Design of water distribution networks (WDNs) is classified as a large combinatorial discrete nonlinear nondeterministic polynomial-hard (NP-hard) optimization problem. The main concerns associated with the optimization of WDNs are related to the nonlinearity of the discharge-head loss relationships for pipes and the discrete nature of pipe sizes. This paper proposes a new evolutionary algorithm, called fittest individual referenced differential evolution (FDE), which is significantly more efficient and reliable than other algorithms for optimization of WDN designs. The fundamental structure of FDE is similar to conventional differential evolution (DE), although the functions of the mutation and crossover operators are to exploit good solutions, and explore very different solutions, respectively, and counting and restarting mechanisms are introduced to identify and avoid local optima. These features are beneficial in WDN design because such problems may have an array of local optima that are far from one another, making finding the global optima difficult. The mutation and crossover operators are developed to accelerate convergence and, although the optimal mutation and crossover parameters may vary among networks, the efficiency of the algorithm reduces the need for adaptive parameters or population size. A sensitivity analysis is conducted for algorithm parameters, as well as counting and restarting limits, based on eight evolutionary algorithm (EA) benchmark test problems, and the efficiency of the FDE for solving 2- and 10-dimensional versions of these problems is demonstrated using the most effective values of the parameters and limits. FDE-based optimal designs of four benchmark networks-the Two-loop, Hanoi, and New York WDNs and the Balerma Irrigation Network-show that on average, a minimal number of function evaluations (or hydraulic simulations) is required to reach the best known optimum, which is less than or equal to 600 in all cases for the first three networks. Furthermore, a detailed application of FDE to a large-sized network, that for the City of Farhadgerd, Iran, shows that FDE is significantly more effective than other EAs in terms of its speed of convergence and reliability.