PADDS Algorithm Assessment for Biobjective Water Distribution System Benchmark Design Problems
Publication: Journal of Water Resources Planning and Management
Volume 144, Issue 3
Abstract
Two implementations of the Pareto archived dynamically dimensioned search (PADDS) algorithm using different selection metrics are applied to 12 water distribution network (WDN) design benchmark problems from the literature. Convex hull contribution (CHC) and hypervolume contribution (HVC) are used as selection metrics for PADDS making this study the first to assess their relative performance on WDN design problems. Past research applied five state-of-the-art multiobjective evolutionary algorithms (MOEAs) to these 12 benchmark problems to generate the best-known Pareto fronts (PFs). The PADDS-CHC and PADDS-HVC both find all solutions on the known true PFs of the first three problems. Together, both PADDS results augment the previously best-known PFs in the nine other benchmark problems with new PF solutions, some of which dominate previous best-known PF solutions, to define updated best-known PFs. Comparative results against five state-of-the-art MOEAs show PADDS derived best-known PFs are equal or better than all other algorithms in 11 of 12 WDN design problems. A comprehensive comparison between PADDS-CHC and PADDS-HVC performance on the largely convex benchmark problem Pareto fronts reveals the different responses of PADDS algorithm to increment of computational budget. An innovative measure called effective archive size (EAS) is introduced to quantify the portion of PADDS archived solutions that play the dominant role in directing PADDS toward the final PF. Tracking the EAS value throughout the search revealed that compared with PADDS-HVC, the EAS of PADDS-CHC is typically close to an order of magnitude smaller. In fact, the PADDS-CHC algorithm generates candidate solutions from a surprisingly small effective archive size that ranges from only 16 to 73 solutions across the 12 benchmark WDN problems while being only 24 for the largest problem.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors would like to thank Mr. Qi Wang (Centre for Water Systems, College of Engineering, Mathematics and Physical Sciences, University of Exeter, Exeter, U.K.) for kindly providing their detailed results. This work was made possible by the facilities of the Shared Hierarchical Academic Research Computing Network (SHARCNET: www.sharcnet.ca) and Compute/Calcul Canada. This work was financially supported by the Natural Sciences and Engineering Council of Canada (NSERC) Strategic Projects Grant Program.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Asadzadeh, M., and Tolson, B. (2012). “Hybrid Pareto archived dynamically dimensioned search for multi-objective combinatorial optimization: Application to water distribution network design.” J. Hydroinf., 14(1), 192–205.
Asadzadeh, M., and Tolson, B. (2013). “Pareto archived dynamically dimensioned search with hypervolume-based selection for multi-objective optimization.” Eng. Optim., 45(12), 1489–1509.
Asadzadeh, M., and Tolson, B. A. (2009). “A new multi-objective algorithm, Pareto archived DDS.” Proc., 11th Annual Conf. Companion on Genetic and Evolutionary Computation Conf.: Late Breaking Papers, ACM, Montreal, Canada, 1963–1966.
Asadzadeh, M., Tolson, B. A., and Burn, D. H. (2014). “A new selection metric for multiobjective hydrologic model calibration.” Water Resour. Res., 50(9), 7082–7099.
Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. (1996). “The quickhull algorithm for convex hulls.” ACM Trans. Math. Software, 22(4), 469–483.
Bi, W., Dandy, G., and Maier, H. (2016). “Use of domain knowledge to increase the convergence rate of evolutionary algorithms for optimizing the cost and resilience of water distribution systems.” J. Water Resour. Plann. Manage., 04016027.
Bragalli, C., D’Ambrosio, C., Lee, J., Lodi, A., and Toth, P. (2008). “Water network design by MINLP.”, IBM Research, Yorktown Heights, New York.
Choi, Y. H., Lee, H. M., Yoo, D. G., and Kim, J. H. (2017). “Self-adaptive multi-objective harmony search for optimal design of water distribution networks.” Eng. Optim., 49(11), 1957–1977.
Das, I. (1999). “On characterizing the ‘knee’ of the Pareto curve based on normal-boundary intersection.” Struct. Opt., 18(2–3), 107–115.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms, Wiley, New York.
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.” Evol. 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 Trans. Evol. Comput., 6(2), 182–197.
EPANET [Computer software]. U.S. Environmental Protection Agency, Washington, DC .
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, International Federation of Automatic Control’s Workshop on Modelling and Control for Participatory Planning and Managing Water Systems, Venice, Italy.
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.
Gessler, J. (1985). “Pipe network optimization by enumeration.” Proc., Computer Applications for Water Resources, ASCE, New York, 572–581.
Hadka, D., and Reed, P. (2013). “Borg: An auto-adaptive many-objective evolutionary computing framework.” Evol. Comput., 21(2), 231–259.
Hanne, T. (1999). “On the convergence of multiobjective evolutionary algorithms.” Eur. J. Oper. Res., 117(3), 553–564.
Khedr, A., Tolson, B., and Ziemann, S. (2015). “Water distribution system calibration: Manual versus optimization-based approach.” Procedia Eng., 119(1), 725–733.
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.
Knowles, J. D., and Corne, D. W. (2000). “Approximating the nondominated front using the Pareto archived evolution strategy.” Evol. Comput., 8(2), 149–172.
Knowles, J. D., Corne, D. W., and Fleischer, M. (2003). “Bounded archiving using the Lebesgue measure.” Proc., Congress on Evolutionary Computation (CEC), IEEE, New York, 2490–2497.
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.
Lee, S., and Lee, S. (2001). “Genetic algorithms for optimal augmentation of water distribution networks.” J. Korea Water Resour. Assoc., 34(5), 567–575.
Marchi, A., et al. (2014). “Battle of the water networks II.” J. Water Resour. Plann. Manage., 04014009.
Marques, G., Lund, J., and Howitt, R. (2010). “Modeling conjunctive use operations and farm decisions with two-stage stochastic quadratic programming.” J. Water Resour. Plann. Manage., 386–394.
Moosavian, N., and Lence, B. (2016). “Nondominated sorting differential evolution algorithms for multiobjective optimization of water distribution systems.” J. Water Resour. Plann. Manage., 04016082.
Prasad, T., and Park, N. (2004). “Multiobjective genetic algorithms for design of water distribution networks.” J. Water Resour. Plann. Manage., 73–82.
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 users manual, National Risk Management Research Laboratory, U.S. Environmental Protection Agency, Cincinnati, 45268.
Schaake, J. C., and Lai, F. H. (1969). Linear programming and dynamic programming application to water distribution network design, MIT Hydrodynamics Laboratory, Cambridge, MA.
Sherali, H. D., Subramanian, S., and Loganathan, G. (2001). “Effective relaxations and partitioning schemes for solving water distribution network design problems to global optimality.” J. Global Optim., 19(1), 1–26.
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., Khedr, A., and Asadzadeh, M. (2012). “The battle of the water networks (BWN-II): PADDS based solution approach.” Proc., 14th Water Distribution Systems Analysis Symp., Engineers Australia, Adelaide, Australia.
Tolson, B. A., and Shoemaker, C. A. (2007). “Dynamically dimensioned search algorithm for computationally efficient watershed model calibration.” Water Resour. Res., 43(1), W01413.
Vrugt, J. A., and Robinson, B. A. (2007). “Improved evolutionary optimization from genetically adaptive multimethod search.” Proc. Natl. Acad. Sci., 104(3), 708–711.
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.
Wang, Q., Savić, D. A., and Kapelan, Z. (2017). “GALAXY: A new hybrid MOEA for the optimal design of water distribution systems.” Water Resour. Manage., 53(3), 1997–2015.
Yazdi, J. (2016). “Decomposition based multi objective evolutionary algorithms for design of large-scale water distribution networks.” Water Resour. Manage., 30(8), 2749–2766.
Zheng, F., Qi, Z., Bi, W., Zhang, T., Yu, T., and Shao, Y. (2017). “Improved understanding on the searching behavior of NSGA-II operators using run-time measure metrics with application to water distribution system design problems.” Water Resour. Manage., 31(4), 1121–1138.
Zheng, F., Zecchin, A., Maier, H., and Simpson, A. (2016). “Comparison of the searching behavior of NSGA-II, SAMODE, and Borg MOEAs applied to water distribution system design problems.” J. Water Resour. Plann. Manage., 04016017.
Zheng, F., Zecchin, A., Newman, J., Maier, H., and Dandy, G. (2017). “An adaptive convergence-trajectory controlled ant colony optimization algorithm with application to water distribution system design problems.” IEEE Trans. Evol. Comput., 21(5), 773–791.
Zitzler, E., Knowles, J., and Thiele, L. (2008). “Quality assessment of Pareto set approximations.” Multiobjective optimization, Springer, Berlin, 373–404.
Zitzler, E., Laumanns, M., and Thiele, L. (2001). “SPEA2: Improving the strength Pareto evolutionary algorithm.” Eurogen, 103, 95–100.
Zitzler, E., and Thiele, L. (1998). “Multiobjective optimization using evolutionary algorithms—A comparative case study.” Proc., Int. Conf. on Parallel Problem Solving from Nature, Springer, Berlin, 292–301.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 144 • Issue 3 • March 2018
Copyright
©2017 American Society of Civil Engineers.
History
Received: Dec 16, 2016
Accepted: Jul 25, 2017
Published online: Dec 28, 2017
Published in print: Mar 1, 2018
Discussion open until: May 28, 2018
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.