Use of Domain Knowledge to Increase the Convergence Rate of Evolutionary Algorithms for Optimizing the Cost and Resilience of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 142, Issue 9
Abstract
Evolutionary algorithms (EAs) have been used extensively for the optimization of water distribution systems (WDSs) over the last two decades. However, computational efficiency can be a problem, especially when EAs are applied to complex problems that have multiple competing objectives. In order to address this issue, there has been a move toward developing EAs that identify near-optimal solutions within acceptable computational budgets, rather than necessarily identifying globally optimal solutions. This paper contributes to this work by developing and testing a method for identifying high-quality initial populations for multiobjective EAs (MOEAs) for WDS design problems aimed at minimizing cost and maximizing network resilience. This is achieved by considering the relationship between pipe size and distance to the source(s) of water, as well as the relationship between flow velocities and network resilience. The benefit of using the proposed approach compared with randomly generating initial populations in relation to finding near-optimal solutions more efficiently is tested on five WDS optimization case studies of varying complexity with two different MOEAs. The results indicate that there are considerable benefits in using the proposed initialization method in terms of being able to identify near-optimal solutions more quickly. These benefits are independent of MOEA type and are more pronounced for larger problems and smaller computational budgets.
Get full access to this article
View all available purchase options and get full access to this article.
References
Bi, W., Dandy, G. C., and Maier, H. R. (2015). “Improved genetic algorithm optimization of water distribution system design by incorporating domain knowledge.” Environ. Modell. Software, 69, 370–381.
Creaco, E., and Franchini, M. (2012). “Fast network multi-objective design algorithm combined with an a-posteriori procedure for reliability evaluation under various operational scenarios.” Urban Water J., 9(6), 385–399.
Deb, K. (2000). “An efficient constraint handling method for genetic algorithms.” Comput. Meth. Appl. Mech. Eng., 186(2–4), 311–338.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II.” IEEE Trans. Evol. Comput., 6(2), 182–197.
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. (2011). “Relationship between problem characteristics and the optimal number of genetic algorithm generations.” Eng. Optim., 43(4), 349–376.
Gibbs, M. S., Maier, H. R., and Dandy, G. C. (2015). “Using characteristics of the optimisation problem to determine the genetic algorithm population size when the number of evaluations is limited.” Environ. Modell. Software, 69, 226–239.
Hadka, D., and Reed, P. (2012a). “Borg: An auto-adaptive many-objective evolutionary computing framework.” Evol. Comput., 21(2), 231–259.
Hadka, D., and Reed, P. (2012b). “Diagnostic assessment of search controls and failure modes in many-objective evolutionary optimization.” Evol. Comput., 20(3), 423–452.
Hadka, D., and Reed, P. (2015). “Large-scale parallelization of the Borg multiobjective evolutionary algorithm to enhance the management of complex environmental systems.” Environ. Modell. Software, 69, 353–369.
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.
Keedwell, E., and Khu, S.-T. (2006). “A novel evolutionary meta-heuristic for the multi-objective optimization of real-world water distribution networks.” Eng. Optim., 38(3), 319–333.
Khedr, A., and Tolson, B. (2015). “Comparing optimization techniques with an engineering judgment approach to WDN design.” J. Water Resour. Plann. Manage., C4015014.
Kollat, J. B., and Reed, P. M. (2006). “Comparing state-of-the-art evolutionary multi-objective algorithms for long-term groundwater monitoring design.” Adv. Water Resour., 29(6), 792–807.
Kollat, J. B., Reed, P. M., and Kasprzyk, J. R. (2008). “A new epsilon-dominance hierarchical Bayesian optimization algorithm for large multiobjective monitoring network design problems.” Adv. Water Resour., 31(5), 828–845.
Li, X., Wei, J., Fu, X., Li, T., and Wang, G. (2014). “Knowledge-based approach for reservoir system optimization.” J. Water Resour. Plann. Manage., 04014001.
Maier, H. R., et al. (2014). “Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions.” Environ. Modell. Software, 62, 271–299.
Maier, H. R., Kapelan, Z., Kasprzyk, J., and Matott, L. S. (2015). “Thematic issue on evolutionary algorithms in water resources.” Environ. Modell. Software, 69, 222–225.
Marchi, A., et al. (2014). “Battle of the water networks II.” J. Water Resour. Plann. Manage., 04014009.
Marques, J., Cunha, M., and Savić, D. A. (2015). “Multi-objective optimization of water distribution systems based on a real options approach.” Environ. Modell. Software, 63, 1–13.
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.
Ong, Y. S., and Keane, A. J. (2002). “A domain knowledge based search advisor for design problem solving environments.” Eng. Appl. Artif. Intell., 15(1), 105–116.
Prasad, T. D., and Park, N.-S. (2014). “Multiobjective genetic algorithms for design of water distribution networks.” J. Water Resour. Plann. Manage., 73–82.
Prasad, T. D., Sung-Hoon, H., and Namsik, P. (2003). “Reliability based design of water distribution networks using multiobjective genetic algorithms.” KSCE J. Civ. Eng., 7(3), 351–361.
Raad, D. N., Sinske, A. N., and van Vuuren, J. H. (2010). “Comparison of four reliability surrogate measures for water distribution systems design.” Water Resour. Res., 46(5), 186.
Sapuan, S. M. (2001). “A knowledge-based system for materials selection in mechanical engineering design.” Mater. Des., 22(8), 687–695.
Stokes, C. S., Maier, H. R., and Simpson, A. R. (2015a). “Effect of storage tank size on the minimization of water distribution system cost and greenhouse gas emissions while considering time-dependent emissions factors.” J. Water Resour. Plann. Manage., 04015052.
Stokes, C. S., Maier, H. R., and Simpson, A. R. (2015b). “Water distribution system pumping operational greenhouse gas emissions minimization by considering time-dependent emissions factors.” J. Water Resour. Plann. Manage., 04014088.
Stokes, C. S., Simpson, A. R., and Maier, H. R. (2015c). “A computational software tool for the minimization of costs and greenhouse gas emissions associated with water distribution systems.” Environ. Modell. Software, 69, 452–467.
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.
Tolson, B. A., Maier, H. R., Simpson, A. R., and Lence, B. J. (2004). “Genetic algorithms for reliability-based optimization of water distribution systems.” J. Water Resour. Plann. Manage., 63–72.
Tolson, B. A., and Shoemaker, C. A. (2007). “Dynamically dimensioned search algorithm for computationally efficient watershed model calibration.” Water Resour. Res., 43(1), 208–214.
Walski, T. M. (2001). “The wrong paradigm—Why water distribution optimization doesn’t work.” J. Water Resour. Plann. Manage., 203–205.
Wang, Q., Guidolin, M., Savic, D., and Kapelan, Z. (2015). “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, W., Maier, H. R., and Simpson, A. R. (2010). “Single-objective versus multiobjective optimization of water distribution systems accounting for greenhouse gas emissions by carbon pricing.” J. Water Resour. Plann. Manage., 555–565.
Wu, W., Maier, H. R., and Simpson, A. R. (2013). “Multiobjective optimization of water distribution systems accounting for economic cost, hydraulic reliability, and greenhouse gas emissions.” Water Resour. Res., 49(3), 1211–1225.
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.
Zheng, F. (2015). “Comparing the real-time searching behavior of four differential-evolution variants applied to water-distribution-network design optimization.” J. Water Resour. Plann. Manage., 04015016.
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), 2924–2930.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2014). “An efficient hybrid approach for multiobjective optimization of water distribution systems.” Water Resour. Res., 50(5), 3650–3671.
Zitzler, E., and Thiele, L. (1999). “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach.” IEEE Trans. Evol. Comput., 3(4), 257–271.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 142 • Issue 9 • September 2016
Copyright
© 2016 American Society of Civil Engineers.
History
Received: Sep 5, 2015
Accepted: Dec 16, 2015
Published online: Apr 29, 2016
Published in print: Sep 1, 2016
Discussion open until: Sep 29, 2016
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.