Impact of Starting Position and Searching Mechanism on the Evolutionary Algorithm Convergence Rate
Publication: Journal of Water Resources Planning and Management
Volume 142, Issue 9
Abstract
Evolutionary algorithms (EAs) have been used extensively to find globally optimal solutions for water distribution system (WDS) optimization problems. However, as these algorithms are being applied to increasingly complex systems, computational efficiency is becoming an issue, and hence approaches that enable near-optimal solutions to be identified within reasonable computational budgets have received increasing attention. One of these approaches is the initialization of EAs in a manner that accounts for domain knowledge of WDS design problems. Although the effectiveness of these initialization approaches has been studied previously, the impact of algorithm searching behavior on the speed with which near-optimal solutions can be found has not yet been examined. To this end, this study aims to investigate the relative impact of different algorithm initialization methods and searching mechanisms on the speed with which near-optimal solutions can be identified for large WDS optimization problems. Fitness function and run-time behavioral statistics are used for this purpose. The results show that both the starting population and algorithm searching mechanism have an impact on the speed with which near-optimal solutions are identified. The fitness function and run-time behavioral statistics indicate that EA parameterizations that favor exploitation over exploration enable near-optimal solutions to be identified earlier in the search, which is due to the “big bowl” shape of the fitness function for all of the WDS problems considered. Using initial populations that are informed by domain knowledge further increases the speed with which near-optimal solutions can be identified.
Get full access to this article
View all available purchase options and get full access to this article.
References
Arsenault, R., Poulin, A., Côté, P., and Brissette, F. (2014). “Comparison of stochastic optimization algorithms in hydrological model calibration.” J. Hydrol. Eng., 1374–1384.
Beh, E. H. Y., Maier, H. R., and Dandy, G. C. (2015). “Adaptive, multiobjective optimal sequencing approach for urban water supply augmentation under deep uncertainty.” Water Resour. Res., 51(3), 1529–1551.
Bi, W., Dandy, G. C., and Maier, H. R. (2015). “Improved genetic algorithm optimization of water distribution system design by incorporating domain knowledge.” Environ. Modell. Software, 69(0), 370–381.
Bi, W., Dandy, G. C., and Maier, H. R. (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., in press.
Deb, K. (2000). “An efficient constraint handling method for genetic algorithms.” Comput. Methods Appl. Mech. Eng., 186(2–4), 311–338.
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. Software, 24(2), 202–213.
Gibbs, M. S., Maier, H. R., and Dandy, G. C. (2010). “Comparison of genetic algorithm parameter setting methods for chlorine injection optimization.” J. Water Resour. Plann. Manage., 288–291.
Gibbs, M. S., Maier, H. R., and Dandy, G. C. (2011). “Relationship between problem characteristics and the optimal number of genetic algorithm generations.” Eng. Optim., 43(4), 349–376.
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(0), 226–239.
Kang, D., and Lansey, K. (2012). “Revisiting optimal water-distribution system design: Issues and a heuristic hierarchical approach.” J. Water Resour. Plann. Manage., 208–217.
Kapelan, Z. S., Savic, D. A., and Walters, G. A. (2005). “Multiobjective design of water distribution systems under uncertainty.” Water Resour. Res., 41(11), W11407.
Keedwell, E., and Khu, S.-T. (2006). “A novel evolutionary meta-heuristic for the multi-objective optimization of real-world water distribution networks.” Eng. Optim., 38(3), 319–333.
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(0), 271–299.
Maier, H. R., Kapelan, Z., Kasprzyk, J., and Matott, L. S. (2015). “Thematic issue on evolutionary algorithms in water resources.” Environ. Modell. Software, 69, 222–225.
Marchi, A., et al. (2014). “Battle of the water networks II.” J. Water Resour. Plann. Manage., 04014009.
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.
Ostfeld, A., Oliker, N., and Salomons, E. (2014). “Multiobjective optimization for least cost design and resiliency of water distribution systems.” J. Water Resour. Plann. Manage., 04014037.
Reca, J., and Martínez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(5), W05416.
Vasan, A., and Simonovic, S. P. (2010). “Optimization of water distribution network design using differential evolution.” J. Water Resour. Plann. Manage., 279–287.
Walski, T. M. (2001). “The wrong paradigm—Why water distribution optimization doesn’t work.” J. Water Resour. Plann. Manage., 203–205.
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.
Weinberger, E. (1990). “Correlated and uncorrelated fitness landscapes and how to tell the difference.” Biol. Cybern., 63(5), 325–336.
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., Simpson, A., and Zecchin, A. (2015a). “Improving the efficiency of multi-objective evolutionary algorithms through decomposition: An application to water distribution network design.” Environ. Modell. Software, 69(0), 240–252.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2011). “A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.” Water Resour. Res., 47(8), W08531.
Zheng, F., Simpson, A. R., and Zecchin, A. C. (2013a). “A decomposition and multistage optimization approach applied to the optimization of water distribution systems with multiple supply sources.” Water Resour. Res., 49(1), 380–399.
Zheng, F., Simpson, A. R., Zecchin, A. C., and Deuerlein, J. W. (2013b). “A graph decomposition-based approach for water distribution network optimization.” Water Resour. Res., 49(4), 2093–2109.
Zheng, F., Zecchin, A., Maier, H. R., and Simpson, A. R. (2015c). “Comparison of the searching behavior of NSGA-II, SAMOE, and Borg MOEAs applied to water distribution system design problems.” J. Water Resour. Plann. Manage., 04016017.
Zheng, F., Zecchin, A., and Simpson, A. (2013d). “Self-adaptive differential evolution algorithm applied to water distribution system optimization.” J. Comput. Civ. Eng., 148–158.
Zheng, F., Zecchin, A. C., and Simpson, A. R. (2015e). “Investigating the run-time searching behavior of the differential evolution algorithm applied to water distribution system optimization.” Environ. Modell. Software, 69(0), 292–307.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 142 • Issue 9 • September 2016
Copyright
© 2016 American Society of Civil Engineers.
History
Received: Jul 25, 2015
Accepted: Jan 7, 2016
Published online: Apr 28, 2016
Published in print: Sep 1, 2016
Discussion open until: Sep 28, 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.