Reducing the Complexity of Multiobjective Water Distribution System Optimization through Global Sensitivity Analysis
Publication: Journal of Water Resources Planning and Management
Volume 138, Issue 3
Abstract
This study investigates the use of global sensitivity analysis as a screening tool to reduce the computational demands associated with multiobjective design and rehabilitation of water distribution systems (WDS). Sobol’s method is used to screen insensitive decision variables and guide the formulation of reduced complexity WDS optimization problems (i.e., fewer decision variables). This sensitivity-informed problem decomposition dramatically reduces the computational demands associated with attaining high-quality approximations for optimal WDS trade-offs. This study demonstrates that the results for the reduced-complexity WDS problems can then be used to precondition and significantly enhance full search of the original WDS problem. Two case studies of increasing complexity—the New York Tunnels network and the Anytown network—are used to demonstrate the proposed methodology. In both cases, sensitivity analysis results reveal that WDS performance is strongly controlled by a small proportion of decision variables, which should be the focus of preconditioning problem formulations. Sensitivity-informed problem decomposition and preconditioning are evaluated rigorously for their ability to improve the efficiency, reliability, and effectiveness of multiobjective evolutionary optimization. Overall, this study reveals for the first time that the use of global sensitivity analysis is computationally efficient and potentially critical when solving the complex multiobjective WDS problems.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This study was supported by U.K. Engineering and Physical Sciences Research Council Grant No. EP/G001405/1, which is gratefully acknowledged. The third author was partially supported by the U.S. National Science Foundation (NSF) under CAREER Grant No. CBET-0640443. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not reflect the views of NSF.
References
Babayan, A.V., Kapelan, Z, Savic, D. A., and Walters, G.A. (2005). “Least cost design of water distribution networks under demand uncertainty.” J. Water Resour. Plann. Manage., 131(5), 375–382.JWRMD5
Dandy, G. C., Simpson, A. R., and Murphy, L. J. (1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res.WRERAQ, 32(2), 449–458.
Deb, K., and Jain, S. (2002). “Running performance metrics for evolutionary multi-objective optimisation.” 4th Asia-Pacific Conf. on Simulated Evolution and Learning (SEAL’02), Nanyang Technical. Univ., Singapore.
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.
Farmani, R., Walters, G. A, and Savic, D. A. (2005). “Trade-off between total cost and reliability for Anytown water distribution network.” J. Water Resour. Plann. Manage.JWRMD5, 131(3), 161–171.
Ferringer, M., Spencer, D., and Reed, P. (2009). “Many-objective reconfiguration of operational satellite constellations with the large-cluster epsilon non-dominated sorting genetic algorithm-II.” IEEE Congress on Evolutionary Computation (CEC ’09), IEEE, Trondheim, Norway.
Fu, G., and Kapelan, Z. (2010). “Embedding neural networks in multiobjective genetic algorithms for water distribution system design.” Proc., 12th Annual Water Distribution Systems Analysis Conf. (WDSA 2010), ASCE, Reston, VA.
Fu, G., and Kapelan, Z. (2011). “Fuzzy probabilistic design of water distribution networks.” Water Resour. Res.WRERAQ, 47, W05538.
Goldberg, D. E. (2002). The design of innovation: Lessons from and for Competent genetic algorithms, Kluwer Academic, Norwell, MA.
Hall, J. W., Boyce, S. A., Wang, Y., Dawson, R. J., Tarantola, S., and Saltelli, A. (2009). “Sensitivity analysis for hydraulic models.” J. Hydraul. Eng.JHEND8, 135(11), 959–969.
Izquierdo, J., Montalvo, I., Pérez, R., and Herrera, M. (2008). “Sensitivity analysis to assess the relative importance of pipes in water distribution networks.” Math. Comput. Model.MCMOEG, 48(1-2), 268–278.
Jayaram, N., and Srinivasan, K. (2008). “Performance-based optimal design and rehabilitation of water distribution networks using life cycle costing.” Water Resour. Res.WRERAQ, 44, W01417.
Kadu, M. S., Gupta, R., and Bhave, P. R. (2008). “Optimal design of water networks using a modified genetic algorithm with reduction in search space.” J. Water Resour. Plann. Manage.JWRMD5, 134(2), 147–160.
Kapelan, Z. S., Savic, D. A., and Walters, G. A. (2005). “Multiobjective design of water distribution systems under uncertainty.” Water Resour. Res.WRERAQ, 41, W11407.
Kapelan, Z., Savic, D., Walters, G. A., and Babayan, A. (2006). “Risk and robustness based solutions to a multiobjective water distribution system rehabilitation problem under uncertainty.” Water Sci. Technol., 53(1), 61–75.
Kasprzyk, J. R, Reed, P. M., Kirsch, B., and Characklis, G. (2009). “Managing population and drought risks using many-objective water portfolio planning under uncertainty.” Water Resour. Res.WRERAQ, 45, W12401.
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.AWREDI, 29(6), 792–807.
Kollat, J. B., and Reed, P. M. (2007). “A computational scaling analysis of multiobjective evolutionary algorithms in long-term groundwater monitoring applications.” Adv. Water Resour.AWREDI, 30(3), 408–419.
McKay, M. D., Conover, W. J., and Beckman, R. J. (1979). “A comparison of three methods for selecting values of input variables in the analysis of output from a computer code.” TechnometricsTCMTA2, 21(2), 239–245.
Murphy, L. J., Dandy, G. C., and Simpson, A. R. (1994). “Optimum design and operation of pumped water distribution systems.” Proc., Conf. on Hydraulics in Civil Engineering, Institution of Engineers, Brisbane, Australia, 149–155.
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.JWRMD5, 136(4), 412–432.
Olsson, R. J, Kapelan, Z., and Savic, D. (2009). “Probabilistic building block identification for the design and rehabilitation of water distribution systems.” J. Hydroinf., 11(2), 89–105.
Perelman, L., Ostfeld, A., and Salomons, E. (2008). “Cross entropy multiobjective optimization for water distribution systems design.” Water Resour. Res.WRERAQ, 44, W09413.
Reed, P., Ferringer, M., Thompson, T., and Kollat, J. B. (2008). “Parallel evolutionary multi-objective optimization on large, heterogeneous clusters: an applications perspective.” J. Aerosp. Comput. Inform. Commun., 5(11), 460–478.
Rossman, L. A. (2000). “EPANET 2 users manual.” Rep. EPA/600/R-00/057, U.S. EPA, Cincinnati, OH.
Saltelli, A. (2002). “Making best use of model evaluations to compute sensitivity indices.” Comput. Phys. Commun.CPHCBZ, 145(2), 280–297.
Saltelli, A., and Annoni, P. (2010). “How to avoid a perfunctory sensitivity analysis.” Environ. Modell. SoftwareEMSOFT, 25(12), 1508–1517.
Saltelli, A., Tarantola, S.,Campolongo, F., and Ratto, M. (2004). Sensitivity analysis in practice: A guide to assessing scientific models, Wiley, New York.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plann. Manage.JWRMD5, 123(2), 67–77.
Schaake, J, and Lai, D. (1969). “Linear programming and dynamic programming applications to water distribution network design.” Rep. 116, Dept. of Civil Engineering, Massachusetts Institute of Technology, Cambridge. MA.
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.JWRMD5, 120(4), 423–443,
Sobol’, I. M. (2001). “Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates.” Math. Comput. Simul.MCSIDR, 55(1-3), 271– 280.
Tang, Y., Reed, P., and Kollat, J. B. (2007a). “Parallelization strategies for rapid and robust evolutionary multiobjective optimization in water resources applications.” Adv. Water Resour.AWREDI, 30(3), 335–353.
Tang, Y., Reed, P. M., van Werkhoven, K., and Wagener, T. (2007b). “Advancing the identification and evaluation of distributed rainfall-runoff models using global sensitivity analysis.” Water Resour. Res., 43, W06415.
Tang, Y., Reed, P. M., and Wagener, T. (2006).“How effective and efficient are multiobjective evolutionary algorithms at hydrologic model calibration?.” Hydrol. Earth Syst. Sci.HESSCF, 10(2), 289–307.
Tang, Y., Reed, P. M., Wagener, T., and van Werkhoven, K. (2007c). “Comparing sensitivity analysis methods to advance lumped watershed model identification and evaluation.” Hydrol. Earth Syst. Sci.HESSCF, 11(2), 793–817.
Todini, E. (2000). “Looped water distribution networks design using a resilience index based heuristic approach.” Urban WaterURWAFE, 2(2), 115–122.
Tolson, B. A., Asadzadeh, M., Maier, H. R., and Zecchin, (2009). “Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization.” Water Resour. Res.WRERAQ, 45, W12416.
Vairavamoorthy, K., and Ali, M. (2005) “Pipe index vector: A method to improve genetic-algorithm-based pipe optimization.” J. Hydraul. Eng.JHEND8, 131(12), 1117–1125.
Van WerkhovenK., Wagener, T, Reed, P. M., and Tang, Y. (2009). “Sensitivity-guided reduction of parametric dimensionality for multi-objective calibration of watershed models.” Adv. Water Resour.AWREDI, 32(8), 1154–1169.
Walski, T., et al. (1987). “Battle of the network models: epilogue.” J. Water Resour. Plann. Manage.JWRMD5, 113(2), 191–203.
Walters, G. A., Halhal, D., Savic, D., and Ouazar, D. (1999). “Improved design of anytown distribution network using structured messy genetic algorithms.” Urban WaterURWAFE, 1(1), 23–38.
While, L., Hingston, P, Barone, L., and Huband, S. (2006). “A faster algorithm for calculating hypervolume.”Trans. Evol. Comput., 10(1), 29–38.
Xu, C., and Goulter, I. C. (1999). “Reliability-based optimal design of water distribution networks.” J. Water Resour. Plann. Manage.JWRMD5, 125(6), 352–362.
Yan, S., and Minsker, B. (2006). “Optimal groundwater remediation design using an adaptive neural network genetic algorithm.” Water Resour. Res.WRERAQ, 42, W05407.
Zitzler, E., and Thiele, L. (1998). “Multiobjective optimization using evolutionary algorithms—a comparative case study.” Lecture notes in computer science 1498: Parallel problem solving from nature—PPSN V, Eiben, A. E., Bäck, T., Schoenauer, M., and Schwefel, H.-P, eds., Springer-Verlag, Berlin/Amsterdam, 292–301.
Zitzler, E., Thiele, L, Laumanns, M, Fonseca, C. M., and Fonseca, V. G. (2003). “Performance assessment of multiobjective optimizers: An analysis and review.” IEEE Trans. Evol. Comput., 7(2), 117–132.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 138 • Issue 3 • May 2012
Pages: 196 - 207
Copyright
© 2012. American Society of Civil Engineers.
History
Received: Nov 2, 2010
Accepted: Jun 2, 2011
Published online: Jun 4, 2011
Published in print: May 1, 2012
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.