Comparison of the Searching Behavior of NSGA-II, SAMODE, and Borg MOEAs Applied to Water Distribution System Design Problems
Publication: Journal of Water Resources Planning and Management
Volume 142, Issue 7
Abstract
A number of multiobjective evolutionary algorithms (MOEAs) have been developed and applied to water resource optimization problems over the past decade. The comparative performance of these MOEAs has been investigated often according to their overall end-of-run results (quality of optimal fronts) within prespecified computational budgets. Despite the importance of such comparative analyses, these studies have provided little knowledge of how different MOEAs navigate through the decision space toward the Pareto front. To address this issue, this paper uses a range of metrics to quantitively characterize MOEAs’ run-time searching behavior, with a focus on the statistics of search quality and convergence progress. The metrics are applied to three state-of-the-art MOEAs, including the nondominated sorting genetic algorithm-II (NSGA-II), self-adaptive multiobjective differential evolution (SAMODE), and Borg, for six water distribution system (WDS) design problems with the objectives of minimizing network cost and maximizing network resilience. Moreover, the relationship between algorithm operators and behavioral properties is discussed. The run-time behavioral results successfully capture the underlying search characteristics associated with each MOEA, thereby offering a significantly improved understanding of how different operators affect the MOEA’s searching behavior. This insight not only offers guidance for practitioners to select appropriate MOEAs (and operators) for given optimization problems, but also builds fundamental understanding of MOEA operators, which can be used to develop further advanced optimization algorithms.
Get full access to this article
View all available purchase options and get full access to this article.
References
Baeck, T., Fogel, D. B., and Michalewicz, Z. (2000). Evolutionary computation 1: Basic algorithms and operators, CRC Press, Boca Raton, FL.
Bi, W., Dandy, G. C., and Maier, H. R. (2015). “Improved genetic algorithm optimization of water distribution system design by incorporating domain knowledge.” Environ. Model. Software, 69, 370–381.
Coello Coello, C. A., Lamont, G. B., and Van Veldhuizen, D. A. (2007). Evolutionary algorithms for solving multi-objective problems, Springer, New York.
Corcoran, L., McNabola, A., and Coughlan, P. (2015). “Optimization of water distribution networks for combined hydropower energy recovery and leakage reduction.” J. Water Resour. Plann. Manage., 04015045.
Das, S., and Suganthan, P. N. (2011). “Differential evolution: A survey of the state-of-the-art.” IEEE Trans. Evol. Comput., 15(1), 4–31.
Deb, K., and Agrawal, R. B. (1994). “Simualted binary crossover for continuous search space.”, Indian Institute of Technology, Kanpur, India.
Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T. (2000). “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II.” Parallel problem solving from nature PPSN VI, M. Schoenauer, et al., eds., Springer, Berlin, 849–858.
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 any town water distribution network.” J. Water Resour. Plann. Manage., 161–171.
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.
Khedr, A., and Tolson, B. (2015). “Comparing optimization techniques with an engineering judgment approach to WDN design.” J. Water Resour. Plann. Manage., C4015014.
Knowles, J., and Corne, D. (2002). “On metrics for comparing nondominated sets.” Proc., 2002 Congress on Evolutionary Computation, 2002. CEC’02, IEEE Service Center, New York, 711–716.
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., and Reed, P. M. (2007). “A computational scaling analysis of multiobjective evolutionary algorithms in long-term groundwater monitoring applications.” Adv. Water Resour., 30(3), 408–419.
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.
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.
Prasad, T. D., and Park, N.-S. (2004). “Multiobjective genetic algorithms for design of water distribution networks.” J. Water Resour. Plann. Manage., 73–82.
R Core Team. (2013). “R: A language and environment for statistical computing.” R Foundation for Statistical Computing, Vienna, Austria.
Reed, P., Kollat, J. B., and Devireddy, V. K. (2007). “Using interactive archives in evolutionary multiobjective optimization: A case study for long-term groundwater monitoring design.” Environ. Modell. Software, 22(5), 683–692.
Reed, P. M., and Hadka, D. (2014). “Evolving many-objective water management to exploit exascale computing.” Water Resour. Res., 50(10), 8367–8373.
Smith, R., Kasprzyk, J., and Zagona, E. (2015). “Many-objective analysis to optimize pumping and releases in multireservoir water supply network.” J. Water Resour. Plann. Manage., 04015049.
Stokes, C., Maier, H. R, and Simpson, A. R. (2015). “Water distribution system pumping operational greenhouse gas emissions minimization by considering time-dependent emissions factors.” J. Water Resour. Plann. Manage., 04014088.
Tang, Y., Reed, P. M., and Kollat, J. B. (2007). “Parallelization strategies for rapid and robust evolutionary multiobjective optimization in water resources applications.” Adv. Water Resour., 30(3), 335–353.
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.
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.
Zaharie, D. (2002). “Critical values for control parameters of differential evolution.” Proc., 8th Int. Mendel Conf. on Soft Computation, Humusoft, Czech Republic, 62–67.
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. (2014). “An efficient hybrid approach for multiobjective optimization of water distribution systems.” Water Resour. Res., 50(5), 3650–3671.
Zheng, F., Zecchin, A. C., and Simpson, A. R. (2015). “Investigating the run-time searching behavior of the differential evolution algorithm applied to water distribution system optimization.” Environ. Modell. Software, 69, 292–307.
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 7 • July 2016
Copyright
© 2016 American Society of Civil Engineers.
History
Received: Jul 28, 2015
Accepted: Dec 17, 2015
Published online: Mar 22, 2016
Published in print: Jul 1, 2016
Discussion open until: Aug 22, 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.