Methodology for Comparing Evolutionary Algorithms for Optimization of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 140, Issue 1
Abstract
In recent years, a number of evolutionary algorithms have been proposed for optimizing the design and operation of water distribution systems (WDSs). These evolutionary algorithms include genetic algorithms, ant colony optimization, particle swarm optimization, the shuffled leaping frog algorithm, and differential evolution. Although there have been some comparisons made of the performance of the various algorithms, very few of these comparisons have been carried out in a completely rigorous manner. The main aim of this paper is to introduce a methodology for the rigorous comparison of various algorithms for the optimum design of water distribution systems. The methodology involves comparing the various algorithms in terms of (1) the best solution obtained; (2) the speed of convergence; and (3) the spread and consistency of the solutions obtained over a number of random starting seeds and numbers of evaluations. As a demonstration of the methodology, the techniques of genetic algorithms (GA), particle swarm optimization (PSO), and differential evolution (DE) are applied to two frequently used WDS case studies, namely the New York Tunnels and Hanoi water networks. In addition, the techniques are applied to a real-size water distribution system consisting of 476 pipes. The results obtained show that the algorithm performances depend on the specific problem and the number of function evaluations allowed. Moreover, it is shown that correct calibration is an essential phase for a fair comparison of evolutionary algorithms. In fact, the best parameters are a function of the problem characteristics, of the objective function and of the variants in the algorithm operators. Therefore the adoption of configurations tested on slightly different versions of the algorithms can lead to quite different results.
Get full access to this article
View all available purchase options and get full access to this article.
References
Bolognesi, A., Bragalli, C., Marchi, A., and Artina, S. (2010). “Genetic heritage evolution by stochastic transmission in the optimal design of water distribution networks.” Adv. Eng. Softw., 41(5), 792–801.
Coello, C. A. C. (2002). “Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art.” Comput. Methods Appl. Mech. Eng., 191(11–12), 1245–1287.
Dandy, G., Simpson, A., and Murphy, L. (1996). “An improved genetic algorithm for pipe network optimisation.” Water Resour. Res., 32(2), 449–458.
Dandy, G., Wilkins, A., and Rohrlach, H. (2011). “A methodology for comparing evolutionary algorithms for optimizing water distribution systems.” Proc., Water Distribution System Analysis 2010, ASCE, Reston, VA.
Deb, K. (2000). “An efficient constraint handling method for genetic algorithms.” Comput. Meth. Appl. Mech. Eng., 186(2–4), 311–338.
Espinoza, F. P., Minsker, B. S., and Goldberg, D. E. (2005). “Adaptive hybrid genetic algorithm fro groundwater remediation design.” J. Water Resour. Plann. Manage., 14–24.
Eusuff, M. M., and Lansey, K. E. (2003). “Optimization of water distribution network design using the shuffled frog leaping algorithm.” J. Water Resour. Plann. Manage., 210–225.
Fujiwara, O., and Khang, D. B. (1990). “A two phase decomposition method for optimal design of looped water distribution networks.” Water Resour. Res., 26(4), 539–549.
Geem, Z. W. (2006). “Optimal cost design of water distribution networks using harmony searc.” Eng. Optim., 38(3), 259–277.
Geem, Z. W., Tseng, C. L., and Williams, J. C. (2009). “Harmony search algorithms for water and environmental systems.” Stud. Comput. Intell., 191, 113–127.
Gessler, J. (1985). “Pipe network optimization by enumeration.” Proc., Computer Applications for Water Resources, ASCE, Reston, VA, 572–587.
Gibbs, M. S., Dandy, G. C., and Maier, H. R. (2008). “A genetic algorithm calibration method based on convergence due to genetic drift.” Inf. Sci., 178(14), 2857–2869.
Gibbs, M. S., Maier, H. R., and Dandy, G. C. (2010). “Comparison of genetic algorithm parameter setting methods for chlorine injection optimization.” J. Water Resour. Plann. Manage., 288–291.
Gibbs, M. S., Maier, H. R., and Dandy, G. C. (2011). “Relationship between problem characteristics and the optimal number of genetic algorithm generations.” Eng. Optim., 43(4), 349–376.
Izquierdo, J., Montalvo, I., Pérez, R., and Tavera, M. (2008) “Optimization in water systems: A PSO approach.” Proc., Business and Industry Symp., BIS, Ottawa, Canada.
Izquierdo, J., Montalvo, I., Pérez-García, R., and Herrera, M. (2009) “Robust design of water supply systems through evolutionary optimization.” Positive Systems, LNCIS, Springer, Berlin, 321–330.
Keedwell, E., and Khu, S. (2005). “A hybrid genetic algorithm for the design of water distribution networks.” Eng. Appl. Artif. Intell., 18(4), 461–472.
Kennedy, J., and Eberhart, R. (1995). “Particle swarm optimisation.” Proc., IEEE Intl. Conf. on Neural Networks, IEEE Service Center, Piscataway, NJ, 1942–1948.
Maier, H., et al. (2003). “Ant colony optimization for design of water distribution systems.” J. Water Resour. Plann. Manage., 200–209.
Montalvo, I., Izquierdo, J., Perez, R., and Tung, M. M. (2008a). “Particle swarm optimization applied to the design of water supply systems.” Comput. Math. Appl., 56(3), 769–776.
Montalvo, I., Izquierdo, J., Pérez, R., and Iglesias, P. L. (2008b). “A diversity-enriched variant of discrete PSO applied to the design of water distribution networks.” Eng. Optim., 40(7), 655–668.
Nicklow, J., et al. (2010). “State of the art for genetic algorithms and beyond in wáter resources planning and management.” J. Water Resour. Plann. Manage., 136(4), 412–432.
Reca, J., Martinez, C., Gil, C., and Banos, R. (2008). “Application of several meta-heuristic techniques to the optimization of real looped water distribution networks.” Water Resour. Manage., 22(10), 1367–1379.
Reca, J., and Martínez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(5), W05416.
Rossman, L. A. (2000). “EPANET 2.”, Water Supply and Water Resources Division, National Risk Management Research Laboratory, Office of Research and Development, U.S. EPA, Cincinnati, OH.
Savic, D., and Walters, G. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plann. Manage., 67–77.
Schaake, J., and Lai, D. (1969). “Linear programming and dynamic programming applications to water distribution network design.”, Dept. of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MA.
Silver, E. A. (2004). “An overview of heuristic solution methods.” J. Oper. Res. Soc., 55(9), 936–956.
Simpson, A., Dandy, G., and Murphy, L. (1994). “Genetic algorithms compared to other techniques for pipe optimisation.” J. Water Resour. Plann. Manage., 423–443.
Storn, R. S., and Price, K. (1997). “Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces.” J. Global Optim., 11(4), 341–359.
Suribabu, C. R. (2010). “Differential evolution algorithm for optimal design of water distribution networks.” J. Hydroinf., 12(1), 66–82.
Suribabu, C. R., and Neelakantan, T. R. (2006). “Design of water distribution networks using particle swarm optimization.” Urban Water J., 3(2), 111–120.
Tolson, B. A., Asadzadeh, M., Maier, H. R., and Zecchin, A. (2009). “Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization.” Water Resour. Res., 45(12), W12416.
Vasan, A., and Simonovic, S. P. (2010). “Optimization of water distribution network design using differential evolution.” J. Water Resour. Plann. Manage., 279–287.
Wolpert, D. H., and Macready, W. G. (1997). “No free lunch theorems for optimization.” IEEE Trans. Evol. Comput., 1(1), 67–82.
Yates, D. F., Templeman, A. B., and Boffey, T. B. (1984). “The computational complexity of the problem of determining least capital cost designs for water supply networks.” Eng. Optim., 7(2), 143–155.
Zecchin, A. C., Simpson, A. R., Maier, H. R., and Nixon, J. B. (2005). “Parametric study for an ant algorithm applied to water distribution system optimization.” IEEE Trans. Evol. Comput., 9(2), 175–191.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011a). “Performance study of differential evolution with various mutation strategies applied to water distribution system optimization.” Proc., World Environmental and Water Resources Congress 2011: Bearing knowledge for sustainability, ASCE, Reston, VA.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011b). “A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.” Water Resour. Res., 47(8), W08531.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 140 • Issue 1 • January 2014
Pages: 22 - 31
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Nov 17, 2011
Accepted: Oct 5, 2012
Published online: Oct 6, 2012
Discussion open until: Mar 6, 2013
Published in print: Jan 1, 2014
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.