Two-Objective Design of Benchmark Problems of a Water Distribution System via MOEAs: Towards the Best-Known Approximation of the True Pareto Front
Publication: Journal of Water Resources Planning and Management
Volume 141, Issue 3
Abstract
Various multiobjective evolutionary algorithms (MOEAs) have been applied to solve the optimal design problems of a water distribution system (WDS). Such methods are able to find the near-optimal trade-off between cost and performance benefit in a single run. Previously published work used a number of small benchmark networks and/or a few large, real-world networks to test MOEAs on design problems of WDS. A few studies also focused on the comparison of different MOEAs given a limited computational budget. However, no consistent attempt has been made before to investigate and report the best-known approximation of the true Pareto front (PF) for a set of benchmark problems, and thus there is not a single point of reference. This paper applied 5 state-of-the-art MOEAs, with minimum time invested in parameterization (i.e., using the recommended settings), to 12 design problems collected from the literature. Three different population sizes were implemented for each MOEA with respect to the scale of each problem. The true PFs for small problems and the best-known PFs for the other problems were obtained. Five MOEAs were complementary to each other on various problems, which implies that no one method was completely superior to the others. The nondominated sorting genetic algorithm-II (NSGA-II), with minimum parameters tuning, remains a good choice as it showed generally the best achievements across all the problems. In addition, a small population size can be used for small and medium problems (in terms of the number of decision variables). However, for intermediate and large problems, different sizes and random seeds are recommended to ensure a wider PF. The publicly available best-known PFs obtained from this work are a good starting point for researchers to test new algorithms and methodologies for WDS analysis.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors thank Jasper Vrugt (University of California, Irvine, California) and David Hadka (from the Hydroinformatics Research Group led by Prof. Patrick Reed) for kindly providing the source code of AMALGAM, -NSGA-II, and Borg for testing in this paper. Also, we would like to thank Mr. Xiaolei Dong and Mrs. Alix Slater for providing some benchmark networks and the proofreading, respectively. The insightful comments and suggestions given by four anonymous reviewers substantially improved the quality of this paper, which are gratefully acknowledged.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Basupi, I., Kapelan, Z., and Butler, D. (2013). “Reducing life-cycle carbon footprint in the redesign of water distribution systems.” J. Water Clim. Change., 4(3), 176–192.
Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., Toth, P. (2008). “Water network design by MINLP.”, IBM Research, Yorktown Heights, NY.
Cheung, P. B., Reis, L. F. R., Formiga, K. T. M., Chaudhry, F. H., and Ticona, W. G. C. (2003). “Multiobjective evolutionary algorithms applied to the rehabilitation of a water distribution system: A comparative study.” Proc., 2nd Int. Conf. on Evolutionary Multi-Criterion Optimization, Springer, Faro, Portugal.
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.
Creaco, E., and Franchini, M. (2014). “Low level hybrid procedure for the multi-objective design of water distribution networks.” Procedia Eng., 70, 369–378.
Deb, K., and Agrawal, R. B. (1995). “Simulated binary crossover for continuous search space.” Complex Syst., 9(2), 115–148.
Deb, K., Mohan, M., and Mishra, S. (2005). “Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions.” Evolut. Comput., 13(4), 501–525.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE T.” Evolut. Comput., 6(2), 182–197.
Deb, K., Thiele, L., Laumanns, M., and Zitzler, E. (2005). “Scalable test problems for evolutionary multiobjective optimization.” Evolutionary multiobjective optimization, A. Abraham, L. Jain, and R. Goldberg, eds., Springer, London, 105–145.
di Pierro, F., Khu, S.-T., Savic, D., and Berardi, L. (2009). “Efficient multi-objective optimal design of water distribution networks on a budget of simulations using hybrid algorithms.” Environ. Modell. Softw., 24(2), 202–213.
Engelhardt, M. O., Skipworth, P. J., Savic, D. A., Saul, A. J., and Walters, G. A. (2000). “Rehabilitation strategies for water distribution networks: A literature review with a UK perspective.” Urban Water, 2(2), 153–170.
Farmani, R., Savic, D., and Walters, G. A. (2006). “A hybrid technique for optimisation of branched urban water systems.” Proc., 7th Int. Conf. on Hydroinformatics, Research, San Jose, CA, Nice, France.
Farmani, R., Savic, D. A., and Walters, G. A. (2003). “Multi-objective optimization of water system: A comparative study.” Pumps, electromechanical devices and systems applied to urban water management, E. Cabrera and E. Cabrera, Jr., eds., Swets & Zeitlinger, Lisse, The Netherlands, 247–256.
Farmani, R., Savic, D. A., and Walters, G. A. (2004). ““EXNET” benchmark problem for multi-objective optimization of large water systems.” Modelling and Control for Participatory Planning and Managing Water Systems, IFAC Workshop, Venice, Italy.
Farmani, R., Savic, D. A., and Walters, G. A. (2005a). “Evolutionary multi-objective optimization in water distribution network design.” Eng. Optimiz., 37(2), 167–183.
Farmani, R., Walters, G. A., and Savic, D. A. (2005b). “Trade-off between total cost and reliability for Anytown water distribution network.” J. Water Resour. Plann. Manage., 161–171.
Fu, G., Kapelan, Z., Kasprzyk, J., and Reed, P. (2012a). “Optimal design of water distribution systems using many-objective visual analytics.” J. Water Resour. Plann. Manage., 624–633.
Fu, G., Kapelan, Z., and Reed, P. M. (2012b). “Reducing the complexity of multi-objective water distribution system optimization through global sensitivity analysis.” J. Water Resour. Plann. Manage., 196–207.
Fujiwara, O., and Khang, D. (1990). “A two-phase decomposition method for optimal design of looped water distribution networks.” Water Resour. Res., 26(4), 539–549.
Gelman, A., Carlin, J. B., Stern, H. S., and Rubin, D. B. (2003). Bayesian data analysis, CRC Press, Boca Raton, FL.
Gessler, J. (1985). “Pipe network optimization by enumeration.” Proc., Computer Applications for Water Resources, ASCE, New York, 572–581.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Longman Publishing, Boston.
Guidolin, M., Fu, G., and Reed, P. (2012). “Parallel evolutionary multiobjective optimization of water distribution system design.” Water Distribution Systems Analysis 2012, Adelaide, Australia.
Haario, H., Saksman, E., and Tamminen, J. (2001). “An adaptive metropolis algorithm.” Bernoulli, 7(2), 223–242.
Hadka, D., and Reed, P. (2013). “Borg: An auto-adaptive many-objective evolutionary computing framework.” Evolut. Comput., 21(2), 231–259.
Halhal, D., Walters, G., Ouazar, D., and Savic, D. (1997). “Water network rehabilitation with structured messy genetic algorithm.” J. Water Resour. Plann. Manage., 137–146.
Hu, X., Eberhart, R. C., and Shi, Y. (2003). “Swarm intelligence for permutation optimization: A case study of n-queens problem.” Proc., 2003 Swarm Intelligence Symp., IEEE, Washington, DC, 243–246.
Iorio, A. W., and Li, X. (2005). “Solving rotated multi-objective optimization problems using differential evolution.” AI 2004: Advances in artificial intelligence, Springer, Berlin, 861–872.
Keedwell, E. C., and Khu, S. T. (2003). “More choices in water system design through hybrid optimization.” Computing and Control for the Water Industry 2003, C. Maksimovic, D. Butler and F. A. Memon, eds., Taylor and Francis, London, 257–264.
Kennedy, J., and Eberhart, R. C. (2001). Swarm intelligence, Morgan Kaufmann Publishers, San Francisco, CA.
Kim, J. H., Kim, T. G., Kim, J. H., and Yoon, Y. N. (1994). “A study on the pipe network system design using non-linear programming.” J. Korean Water Resour. Assoc., 27(4), 59–67.
Knowles, J., and Corne, D. (2002). “On metrics for comparing nondominated sets.” Proc., 2002 Congress on Evolutionary Computation, IEEE, Washington, DC, 711–716.
Kollat, J. B., and Reed, P. (2007). “A framework for visually interactive decision-making and design using evolutionary multi-objective optimization (VIDEO).” Environ. Modell. Softw., 22(12), 1691–1704.
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.
Laumanns, M., Thiele, L., Deb, K., and Zitzler, E. (2002). “Combining convergence and diversity in evolutionary multiobjective optimization.” Evolut. Comput., 10(3), 263–282.
Lee, S. C., and Lee, S. I. (2001). “Genetic algorithms for optimal augmentation of water distribution networks.” J. Korean Water Resour. Assoc., 34(5), 567–575.
Marchi, A., et al. (2013). “The battle of the water networks II (BWN-II).” J. Water Resour. Plann. Manage., 04014009.
Montalvoa, I., Izquierdo, J., Schwarzeb, S., and Pérez-García, R. (2010). “Multi-objective particle swarm optimization applied to water distribution systems design: An approach with human interaction.” Math. Comput. Model., 52(7–8), 1219–1227.
Papadimitriou, C. H., and Steiglitz, K. (1998). Combinatorial optimization: Algorithms and complexity, Dover Publications, New York.
Parsopoulos, K. E., and Vrahatis, M. N. (2002). “Particle swarm optimization method in multiobjective problems.” Proc., 2002 ACM Symp. on Applied computing, ACM, Madrid, Spain.
Perelman, L., Ostfeld, A., and Salomons, E. (2008). “Cross entropy multiobjective optimization for water distribution systems design.” Water Resour. Res., 44(9), W09413.
Prasad, T. D., and Park, N.-S. (2004). “Multiobjective genetic algorithms for design of water distribution networks.” J. Water Resour. Plann. Manage., 73–82.
Prasad, T. D., and Tanyimboh, T. T. (2008). “Entropy based design of “Anytown” water distribution network.” Water Distribution Systems Analysis 2008, J. E. Van Zyl, A. A. Ilemobade and H. E. Jacobs, eds., ASCE, Kruger National Park, South Africa, 450–461.
Purshouse, R. C., and Fleming, P. J. (2007). “On the evolutionary optimization of many conflicting objectives.” IEEE T. Evolut. Comput., 11(6), 770–784.
Raad, D., Sinske, A., and van Vuuren, J. (2009). “Robust multi-objective optimization for water distribution system design using a meta-metaheuristic.” Int. Trans. Oper. Res., 16(5), 595–626.
Raad, D. N., Sinske, A., and van Vuuren, J. H. (2011). “Water distribution systems design optimisation using metaheuristics and hyperheuristics.” ORiON, 27(1), 17–44.
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), W05524.
Reca, J., and Martínez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(5), W05416.
Reed, P. M., Hadka, D., Herman, J. D., Kasprzyk, J. R., and Kollat, J. B. (2013). “Evolutionary multiobjective optimization in water resources: The past, present, and future.” Adv. Water Resour., 51(0), 438–456.
Rossman, L. A. (2000). EPANET 2 users manual, U.S. Environment Protection Agency, Cincinnati, OH.
Schaake, J., and Lai, D. (1969). “Linear programming and dynamic programming application to water distribution network design.” Dept. of Civil Engineering, Massachusetts Institute of Technology, Cambridge, MA.
Sherali, H., Subramanian, S., and Loganathan, G. V. (2001). “Effective relaxations and partitioning schemes for solving water distribution network design problems to global optimality.” J. Global Optim., 19(1), 1–26.
Srivastava, R. P. (2002). “Time continuation in genetic algorithms.” M.S. thesis, Univ. of Illinois at Urbana-Champaign, Urbana, IL.
Storn, R., and Price, K. (1997). “Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces.” J. Global Optim., 11(4), 341–359.
Talbi, E. G. (2002). “A taxonomy of hybrid metaheuristics.” J. Heuristics, 8(5), 541–564.
Tang, Y., Reed, P., and Wagener, T. (2006). “How effective and efficient are multiobjective evolutionary algorithms at hydrologic model calibration?” Hydrol. Earth Syst. Sci., 10(2), 289–307.
Todini, E. (2000). “Looped water distribution networks design using a resilience index based heuristic approach.” Urban Water, 2(2), 115–122.
Vrugt, J. A., and Robinson, B. A. (2007). “Improved evolutionary optimization from genetically adaptive multimethod search.” Proc. Natl. Acad. Sci. U.S.A., 104(3), 708–711.
Walski, T. M., et al. (1987). “Battle of the network models: Epilogue.” J. Water Resour. Plann. Manage., 191–203.
Walski, T. M. (2001). “The wrong paradigm, why water distribution optimization doesn’t work.” J. Water Resour. Plann. Manage., 203–205.
Wang, Q., Liu, S., Wang, H., and Savić, D. (2012). “Multi-objective cuckoo search for the optimal design of water distribution systems.” Civil engineering and urban planning 2012, ASCE, Reston, VA, 402–405.
Wang, Q., Savić, D. A., and Kapelan, Z. (2014). “Hybrid metaheuristics for multi-objective design of water distribution systems.” J. Hydroinform., 16(1), 165–177.
Wolpert, D. H., and Macready, W. G. (1997). “No free lunch theorems for optimization.” IEEE T. Evolut. Comput., 1(1), 67–82.
Zitzler, E., Laumanns, M., and Thiele, L. (2002). “SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization.” Evolutionary Methods for Design, Optimisation and Control, K. Giannakoglou, et al. eds., International Center for Numerical Methods in Engineering (CIMNE), Barcelona, Spain, 95–100.
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., and da Fonseca, V. G. (2003). “Performance assessment of multiobjective optimizers: An analysis and review.” IEEE T. Evolut. Comput., 7(2), 117–132.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 141 • Issue 3 • March 2015
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Dec 24, 2013
Accepted: Apr 22, 2014
Published online: Jul 16, 2014
Discussion open until: Dec 16, 2014
Published in print: Mar 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.