Nondominated Sorting Differential Evolution Algorithms for Multiobjective Optimization of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 143, Issue 4
Abstract
Optimal design of reliable looped water distribution systems (WDSs) is challenging because these problems comprise nonlinear relationships between discharge and energy in the pipes and junctions, and nonconvex objective functions that relate cost and reliability to discrete choices of pipe diameters. Efficient algorithms for identifying optimal WDS designs also must be practical for realistic systems. Differential evolution (DE) algorithms, which harness the mutation operator to identify populations containing very different alternatives, have been shown to be more efficient than other heuristics for solving single objective versions of these problems, e.g., minimizing the cost of WDSs. By examining the entire population and evaluating those members that dominate in terms of two or more objectives, nondominated sorting algorithms efficiently identify the Pareto optimal front in multiobjective problems, and one such algorithm, the improved nondominated sorting genetic algorithm (NSGA-II), has been applied successfully to evaluate the cost-reliability tradeoff for WDSs. The nondominated sorting differential evolution (NSDE) algorithm, which takes advantage of the mutation operations in DE and nondominated sorting, and its variation NSDE with ranking-based mutation (NSDE-RMO), have been demonstrated as efficient for solving multiobjective problems. In this paper, NSDE and NSDE-RMO were applied to discrete WDS optimization for the first time, and their high performance was demonstrated compared with NSGA-II and the multialgorithm, genetically adaptive multiobjective (AMALGAM) method, a widely applied hybrid metaheuristic multiobjective algorithm. For three benchmark networks, NSDE and its variation performed similarly to or better than NSGA-II and AMALGAM except at high cost levels. For hypothetical randomly generated networks ranging from 100 to 400 nodes, and 100 to 800 pipes, the Pareto optimal front of the NSDE algorithms dominated all other algorithms, exhibiting more, and more varied, Pareto optimal solutions, and they converged sooner.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research was funded by the Natural Sciences and Engineering Research Council of Canada through a Discovery Grant to the second author.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Angira, R., and Babu, B. V. (2005). “Non-dominated sorting differential evolution (NSDE): An extension of differential evolution for multi-objective optimization.” Proc., 2nd Indian Int. Conf. on Artificial Intelligence (IICAI-05), Pune, India, 1428–1443.
Chen, X., Wenli, D., and Feng Qian, F. (2014). “Multi-objective differential evolution with ranking-based mutation operator and its application in chemical process optimization.” Chem. Intell. Lab. Syst., 136(15), 85–96.
Dandy, G. C., Simpson, A. R., and Murphy, L. J. (1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res., 32(2), 449–458.
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.
Dong, X., Liu, S., Tao, T., Li, S., and Xin, K. (2012). “A comparative study of differential evolution and genetic algorithms for optimizing the design of water distribution systems.” J. Zhejiang Univ. Sci. A, 13(9), 674–686.
Eusuff, M. M., and Lansey, K. E. (2003). “Optimisation of water distribution network design using shuffled frog leaping algorithm.” J. Water Resour. Plann. Manage., 210–225.
Farmani, R., Savic, D. A., and Walters, G. A. (2005a). “Evolutionary multi-objective optimization in water distribution network design.” Eng. Optim., 37(2), 167–183.
Farmani, R., Walters, G., and Savic, D. (2006). “Evolutionary multiobjective optimization of the design and operation of water distribution network: total cost vs. reliability vs. water quality.” J. Hydroinf., 8(3), 165–179.
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.
Fonseca, C. M., and Fleming, P. J. (1993). “Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization.” Proc., 5th Int. Conf. on Genetic Algorithms, Univ. of Illinois, Urbana-Champaign, IL, 416–423.
Geem, Z. W. (2006). “Optimal cost design of water distribution networks using harmony search.” Eng. Optim., 38(3), 259–277.
Iorio, A. W., and Li, X. (2004). “Solving rotated multi-objective optimization problems using differential evolution.” Proc., AI 2004: Advances in Artificial Intelligence, Vol. 3339, Springer, New York, 861–872.
Maier, H. R., et al. (2003). “Ant colony optimization for the 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. Software, 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.
MATLAB [Computer software]. MathWorks, Natick, MA.
Mohan, S., and Babu, K. S. (2010). “Optimal water distribution network design with honey-bee mating optimization.” J. Comput. Civ. Eng., 117–126.
Moosavian, N., and Jaefarzadeh, R. (2014). “Hydraulic analysis of water supply networks using a Modified Hardy Cross method.” Int. J. Eng., 27(9), 1331–1338.
Moosavian, N., and Roodsari, B. K. (2014). “Soccer league competition algorithm: A novel meta-heuristic algorithm for optimal design of water distribution networks.” Swarm Evol. Comput., 17, 14–24.
Peng, C., Sun, H., Guo, J., and Li, H. (2009). “A new algorithm based on non-dominated sorting differential evolution for multi-objective optimal load dispatch.” 2nd IEEE Int. Conf. on Computer Science and Information Technology, ICCSIT, Beijing, 565–569.
Prasad, T., and Park, N. (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.” Proc., Water Distribution Systems Analysis 2008, J. E. Van Zyl, A. A. Ilemobade, and H. E. Jacobs, eds., ASCE, Reston, VA, 450–461.
Raad, D., Sinske, A., and Van Vuuren, J. (2009). “Robust multi-objective optimization for water distribution system design using a metaheuristic.” Int. Trans. Oper. Res., 16(5), 595–626.
Raad, D. N. (2011). “Multi-objective optimization of water distribution systems design using metaheuristics.” Univ. of Stellenbosch, Stellenbosch, South Africa.
Rozenberg, G., Bäck, T., and Eiben, A. E. (2005). Differential evolution: A practical approach to global optimization, Springer, Berlin.
Savic, D. A., and Walters, G. A. (1997). “Genetic algorithms for least cost design of water distribution networks.” J. Water Resour. Plan. Manage., 67–77.
Srinivas, N., and Deb, K. (1994). “Multiobjective optimization using nondominated sorting in genetic algorithms.” Evol. Comput., 2(3), 221–248.
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.
Suribabu, C. R. (2010). “Differential evolution algorithm for optimal design of water distribution networks.” J. Hydroinf., 12(1), 66–82.
Suribabu, C. R., and Neelakantan, T. R. (2006). “Design of water distribution networks using particle swarm optimization.” Urban Water J., 3(2), 111–120.
Todini, E. (2000). “Looped water distribution networks design using a resilience index based heuristic approach.” Urban Water J., 2(2), 115–122.
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), .
Vrugt, J. A. (2015). “Multi-criteria optimization using the AMALGAM software package: Theory, concepts, and MATLAB implementation.” Manual, Version 1.0, 1–53.
Vrugt, J. A., and Robinson, B. A. (2007). “Improved evolutionary optimization from genetically adaptive multimethod search.” Proc., National 1212 Academy of Sciences of the United States of America, 104, 708–711.
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., .
Williams, G. S., and Hazen, A. (1914). Hydraulic tables, 2nd Ed., Wiley, New York.
Zecchin, A., Thum, P., Simpson, A., and Tischendorf, C. (2012). “Steady-state behavior of large water distribution systems: Algebraic multigrid method for the fast solution of the linear step.” J. Water Resour. Plann. Manage., 639–650.
Zheng, F., Zecchin, A. C., and Simpson, A. R. (2013). “Self-adaptive differential evolution algorithm applied to water distribution system optimization.” J. Comput. Civ. Eng., 148–158.
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.
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 Trans. Evol. Comput., 7(2), 117–132.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 143 • Issue 4 • April 2017
Copyright
©2016 American Society of Civil Engineers.
History
Received: Feb 11, 2016
Accepted: Sep 20, 2016
Published online: Nov 17, 2016
Published in print: Apr 1, 2017
Discussion open until: Apr 17, 2017
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.