Comparing the Real-Time Searching Behavior of Four Differential-Evolution Variants Applied to Water-Distribution-Network Design Optimization
Publication: Journal of Water Resources Planning and Management
Volume 141, Issue 10
Abstract
Differential evolution (DE) algorithms have been successfully used to handle a wide range of water resource optimization problems in recent years. The relative performance of various DE variants has been typically assessed based on the quality of the final solutions for the selected problems within the given computational budget. Such a comparative analysis, however, provides limited understanding on how various operational mechanisms alter the DE algorithms’ searching behavior and what searching properties lead to improved performance. To improve research in this area, this study aims to characterize and compare the searching behavior of four DE variants using a range of measure metrics, mainly focusing on real-time statistics of the algorithm’s search quality, search progress, and convergence manner. The utility of the metrics is demonstrated using the four DE variants (SDE, dDE, MdDE, and SADE) applied to three water distribution network (WDN) design problems with significantly increased complexity (scales). The behavioral results offer an appreciably improved understanding of the searching characteristics associated with each DE variant, thereby providing guidance for choosing the most suitable DE algorithm to solve a particular WDN optimization problem as well as offering knowledge to develop new advanced algorithms. For real-world problems, the SDE algorithm is more suitable if a limited computational budget is allowed, whereas the SADE and MdDE variants are respectively more appealing when moderate and large computational budgets are available. A new solution with a cost of $12.62 million for the large-scale problem (1,278 decision variables) is presented.
Get full access to this article
View all available purchase options and get full access to this article.
References
Afshar, A., Zahraei, A., and Marino, M. A. (2010). “Large-scale nonlinear conjunctive use optimization problem: Decomposition algorithm.” J. Water Resour. Plann. Manage., 59–71.
Bayer, P., de Paly, M., and Bürger, C. M. (2010). “Optimization of high-reliability-based hydrological design problems by robust automatic sampling of critical model realizations.” Water Resour. Res., 46(5), W05504.
Bi, W., and Dandy, G. (2014). “Optimization of water distribution systems using online retrained metamodels.” J. Water Resour. Plann. Manage., 04014032.
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.
Bolognesi, A., Bragalli, C., Marchi, A., and Artina, S. (2014). “Multiobjective design of water distribution networks through the generation of pseudofronts in the hydraulically feasible region.” J. Comput. Civ. Eng., 06014004.
Das, S., Konar, K., and Chakraborty, U. K. (2005). “Two improved differential evolution schemes for faster global search.” Proc., Conf. Genetic and Evolutionary Computation (GECCO 2005), Association for Computing Machinery, New York, 991–998.
Das, S., and Suganthan, P. N. (2011). “Differential evolution: A survey of the state-of-the-art.” IEEE Trans. Evol. Comput., 15(1), 4–31.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II.” IEEE Trans. Evolut. Comput., 6(2), 182–197.
Elçi, A., and Ayvaz, M. T. (2014). “Differential-evolution algorithm based optimization for the site selection of groundwater production wells with the consideration of the vulnerability concept.” J. Hydrol., 511, 736–749.
Guo, J., Zhou, J., Lu, J., Zou, Q., Zhang, H., and Bi, S. (2014). “Multi-objective optimization of empirical hydrological model for streamflow prediction.” J. Hydrol., 511, 242–253.
Ji, C., Jiang, Z., Sun, P., Zhang, Y., and Wang, L. (2014). “Research and application of multidimensional dynamic programming in cascade reservoirs based on multilayer nested structure.” J. Water Resour. Plann. Manage., 04014090.
Kang, D., and Lansey, K. (2012). “Revisiting optimal water-distribution system design: Issues and a heuristic hierarchical approach.” J. Water Resour. Plann. Manage., 208–217.
Maier, H. R., et al. (2003). “Ant colony optimization for design of water distribution systems.” J. Water Resour. Plann. Manage., 200–209.
Maier, H. R., et al. (2014). “Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions.” Environ. Model. Softw., 62, 271–299.
Marchi, A., Dandy, G., Wilkins, A., and Rohrlach, H. (2014). “Methodology for comparing evolutionary algorithms for optimization of water distribution systems.” J. Water Resour. Plann. Manage., 22–31.
Nicklow, J., et al. (2010). “State of the art for genetic algorithms and beyond in water resources planning and management.” J. Water Resour. Plann. Manage., 412–432.
Ostfeld, A. (2012). “Optimal reliable design and operation of water distribution systems through decomposition.” Water Resour. Res., 48(10), W10521.
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. (2001). EPANET 2-User manual, National Risk Management Research Laboratory, Office of Research and Development, US Environmental Protection Agency, Cincinnati.
Schardong, A., Simonovic, S., and Vasan, A. (2013). “Multiobjective evolutionary approach to optimal reservoir operation.” J. Comput. Civ. Eng., 139–147.
Simpson, A. R., Dandy, G. C., and Murphy, L. J. (1994). “Genetic algorithms compared to other techniques for pipe optimization.” J. Water Resour. Plann. Manage., 423–443.
Storn, R., and Price, K. (1995). “Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous space.”, International Computer Science Institute, Berkeley, CA.
Suribabu, C. R. (2010). “Differential evolution algorithm for optimal design of water distribution networks.” J. Hydroinform., 12(1), 66–82.
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.
Vesterstrom, J., and Thomsen, R. (2004). “A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems.” Congress on Evolutionary Computation, 2004, CEC2004, Vol. 2, IEEE, New York.
Wang, Q., Guidolin, M., Savic, D., and Kapelan, Z. (2014). “Two-objective design of benchmark problems of a water distribution system via MOEAs: Towards the best-known approximation of the true Pareto front.” J. Water Resour. Plann. Manage., 04014060.
Wu, Z. Y., and Walski, T. (2005). “Self-adaptive penalty approach compared with other constraint-handling techniques for pipeline optimization.” J. Water Resour. Plann. Manage., 181–192.
Xie, X., Nachabe, M., and Zeng, B. (2014). “Optimal scheduling of automatic flushing devices in water distribution system.” J. Water Resour. Plann. Manage., 04014081.
Zaharie, D. (2002). “Critical values for control parameters of differential evolution.” Proc., 8th Int. Mendel Conf. on Soft Computation, Brno Univ. of Technology, Brno, Czech Republic, 62–67.
Zecchin, A. C., Maier, H. R., Simpson, A. R., Leonard, M., and Nixon, J. B. (2007). “Ant colony optimization applied to water distribution system design: Comparative study of five algorithms.” J. Water Resour. Plann. Manage., 87–92.
Zecchin, A. C., Simpson, A. R., Maier, H. R., Marchi, A., and Nixon, J. B. (2012). “Improved understanding of the searching behavior of ant colony optimization algorithms applied to the water distribution design problem.” Water Resour. Res., 48(9), W09505.
Zhang, X., Srinivasan, R., Zhao, K., and Van Liew, M. (2009). “Evaluation of global optimization algorithms for parameter calibration of a computationally intensive hydrologic model.” Hydrol. Processes, 23(3), 430–441.
Zheng, F., Simpson, A., and Zecchin, A. (2014). “Coupled binary linear programming–differential evolution algorithm approach for water distribution system optimization.” J. Water Resour. Plann. Manage., 585–597.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2010). “A method of assessing the performance of genetic algorithm optimization water distribution design.” Proc., 12th Water Distribution System Analysis Symp., ASCE, New York.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011). “A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.” Water Resour. Res., 47(8), W08531.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2013a). “A decomposition and multistage optimization approach applied to the optimization of water distribution systems with multiple supply sources.” Water Resour. Res., 49(1), 380–399.
Zheng, F., and Zecchin, A. (2014). “An efficient decomposition and dual-stage multi-objective optimization method for water distribution systems with multiple supply sources.” Environ. Model. Softw., 55, 143–155.
Zheng, F., Zecchin, A., and Simpson, A. (2013b). “Self-adaptive differential evolution algorithm applied to water distribution system optimization.” J. Comput. Civ. Eng., 148–158.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 141 • Issue 10 • October 2015
Copyright
© 2015 American Society of Civil Engineers.
History
Received: Jun 19, 2014
Accepted: Feb 4, 2015
Published online: Mar 18, 2015
Discussion open until: Aug 18, 2015
Published in print: Oct 1, 2015
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.