Comparison of Stochastic Optimization Algorithms in Hydrological Model Calibration
Publication: Journal of Hydrologic Engineering
Volume 19, Issue 7
Abstract
Ten stochastic optimization methods—adaptive simulated annealing (ASA), covariance matrix adaptation evolution strategy (CMAES), cuckoo search (CS), dynamically dimensioned search (DDS), differential evolution (DE), genetic algorithm (GA), harmony search (HS), pattern search (PS), particle swarm optimization (PSO), and shuffled complex evolution–University of Arizona (SCE–UA)—were used to calibrate parameter sets for three hydrological models on 10 different basins. Optimization algorithm performance was compared for each of the available basin-model combinations. For each model-basin pair, 40 calibrations were run with the 10 algorithms. Results were tested for statistical significance using a multicomparison procedure based on Friedman and Kruskal-Wallis tests. A dispersion metric was used to evaluate the fitness landscape underlying the structure on each test case. The trials revealed that the dimensionality and general fitness landscape characteristics of the model calibration problem are important when considering the use of an automatic optimization method. The ASA, CMAES, and DDS algorithms were either as good as or better than the other methods for finding the lowest minimum, with ASA being consistently among the best. The SCE–UA method performs better when the model complexity is reduced, whereas the opposite is true for DDS. Convergence speed was also studied, and the same three methods (CMAES, DDS, and ASA) were shown to converge faster than the other methods. The SCE–UA method converged nearly as fast as the best methods when the model with the smallest parameter space was used but was not as worthy in the higher-dimension parameter space of the other models. Convergence speed has little impact on algorithm efficiency. The methods offering the worst performance were DE, CS, GA, HS, and PSO, although they did manage to find good local minima in some trials. However, the other available methods generally outperformed these algorithms.
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 L. Ingber and contributors for the ASA source code—available at http://www.ingber.com/#ASA—and S. Sakata for making the MATLAB routines to use ASA public. The codes are available at http://ssakata.sdf.org/software/. The authors would also like to thank B. A. Tolson for supplying the DDS algorithm. Finally, the authors wish to thank the reviewers who contributed to the quality of this paper.
References
Abramson, M. A., Audet, C., and Dennis, J. E., Jr. (2004). “Generalized pattern searches with derivative information.” Math. Program., 100(1), 3–25.
Arsenault, R., Malo, J., Brissette, F., Minville, M., and Leconte, R. (2013). “Structural and non-structural climate change adaptation strategies for the Péribonka water resource system.” Water Resour. Manage., 27(7), 2075–2087.
Audet, C., and Dennis, J. E., Jr. (2006). “Mesh adaptive direct search algorithms for constrained optimization.” SIAM J. Optim., 17(1), 188–217.
Barrette, M., Wong, T., de Kelper, B., and Côté, P. (2008). “Statistical multi-comparison of evolutionary algorithms.” Bioinspired Optimization Methods and Applications, Jozef Stefan Institute Press, Ljubljana, Slovenia, 71–80.
Beven, K. (2001). Rainfall-runoff modelling—The primer, Wiley, Chichester, U.K., 372.
Blasone, R. S., Madsen, H., and Rosbjerg, D. (2007). “Parameter estimation in distributed hydrological modelling: Comparison of global and local optimisation techniques.” Nord. Hydrol., 38(4–5), 451–476.
Charbonneau, R., Fortin, J.-P., and Morin, G. (1977). “Le modèle CEQUEAU: Description et exemples d’utilisation dans le cadre de problèmes reliés à l’aménagement [Description and examples of its use in problems related to water resource management].” Hydrol. Sci. Bull., 22(1), 193–202.
Chen, J., Brissette, F. P., Poulin, A., and Leconte, R. (2011). “Global uncertainty study of the hydrological impacts of climate change for a Canadian watershed.” Water Resour. Res., 47(12), W12509.
Chen, M., and Lu, Q. (2005). “A hybrid model based on genetic algorithm and ant colony algorithm.” J. Inf. Comput. Sci., 2(4), 647–653.
Duan, Q., et al. (2006). “Model parameter estimation experiment (MOPEX): Overview and summary of the second and third workshop results.” J. Hydrol., 320(1–2), 3–17.
Duan, Q., Sorooshian, S., and Gupta, V. K. (1992). “Effective and efficient global optimization for conceptual rainfall runoff models.” Water Resour. Res., 28(4), 1015–1031.
Duan, Q., Sorooshian, S., and Gupta, V. K. (1993). “Shuffled complex evolution approach for effective and efficient global minimization.” J. Optimiz. Theory Appl., 76(3), 501–521.
Duan, Q., Sorooshian, S., and Gupta, V. K. (1994). “Optimal use of the SCE-UA global optimization method for calibrating watershed models.” J. Hydrol., 158(3–4), 265–284.
Fang, L., Chen, P., and Shihua, L. (2007). “Particle swarm optimization with simulated annealing for TSP.” Proc., WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases—Vol. 6. Corfu Island, World Scientific and Engineering Academy and Society (WSEAS), Greece, 206–210.
Fortin, J.-P., Turcotte, R., Massicotte, S., Moussa, R., Fitzback, J., and Villeneuve, J.-P. (2001). “Distributed watershed model compatible with remote sensing and GIS data. 1: Description of the model.” J. Hydraul. Eng., 91–99.
Fortin, V. (2000). “Le modèle météo-apport HSAMI: Historique, théorie et application.” Institut de Recherche d’Hydro-Québec, Varennes, QC, Canada, 1–68.
Fortin, V., and Turcotte, R. (2007). “Le modèle hydrologique MOHYSE (Bases théoriques et manuel de l’usager).”, Département des sciences de la terre et de l’atmosphère, Université du Québec à Montréal, Montréal, 1–17.
Fortnow, L. (2009). “The status of the P versus NP problem.” Commun. ACM, 52(9), 78–86.
Franchini, M., Galeati, G., and Berra, S. (1998). “Global optimization techniques for the calibration of conceptual rainfall-runoff models.” Hydrol. Sci. J., 43(3), 443–458.
Friedman, M. (1937). “The use of ranks to avoid the assumption of normality implicit in the analysis of variance.” J. Am. Stat. Assoc., 32(200), 675–701.
Friedman, M. (1940). “A comparison of alternative tests of significance for the problem of m rankings.” Ann. Math. Stat., 11(1), 86–92.
Geem, Z. W., Kim, J. H., and Loganathan, G. V. (2001). “A new heuristic optimization algorithm: Harmony search.” Simulation, 76(2), 60–68.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Boston, 432.
Hansen, N., and Ostermeier, A. (1996). “Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation.” Proc., 1996 IEEE Int. Conf. on Evolutionary Computation, IEEE Press, NY, 312–317.
Hansen, N., and Ostermeier, A. (2001). “Completely derandomized self-adaptation in evolution strategies.” Evol. Comput., 9(2), 159–195.
Hochberg, Y. (1988). “A sharper Bonferroni procedure for multiple tests of significance.” Biometrika, 75(4), 800–802.
Holland, J. (1975). Adaptation in natural and artificial systems, Univ. of Michigan Press, Oxford, England, 1–183.
Ingber, L. (1989). “Very fast simulated re-annealing.” Math. Comput. Model., 12(8), 967–973.
Ingber, L. (1993). Adaptive simulated annealing (ASA), Lester Ingber Research, McLean, VA.
Ingber, L. (1996). “Adaptive simulated annealing (ASA): Lessons learned.” Control Cybern., 25(1), 33–54.
Kennedy, J., and Eberhart, R. (1995). “Particle swarm optimization.” Proc., IEEE Int. Conf. on Neural Networks, Vol. 4, IEEE Press, Piscataway, NJ, 1942–1948.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). “Optimization by simulated annealing.” Science, 220(4598), 671–680.
Kruskal, W. H., and Wallis, W. A. (1952). “Use of ranks in one-criterion variance analysis.” J. Am. Stat. Assoc., 47(260), 583–621.
Lunacek, M., and Whitley, D. (2006). “The dispersion metric and the CMA evolution strategy.” Proc., 8th Annual Conf. on Genetic and Evolutionary Computation, Association for Computing Machinery, New York.
Mariani, V. C., Luvizotto, L. G. J., Guerra, F. A., and Leandro, D. S. C. (2011). “A hybrid shuffled complex evolution approach based on differential evolution for unconstrained optimization.” Appl. Math. Comput., 217(12), 5822–5829.
MATLAB [Computer software]. MathWorks, Natick, MA.
Minville, M., Brissette, F., Krau, S., and Leconte, R. (2009). “Adaptation to climate change in the management of a Canadian water-resources system.” Water Resour. Manage., 23(14), 2965–2986.
Minville, M., Brissette, F., and Leconte, R. (2008). “Uncertainty of the impact of climate change on the hydrology of a Nordic watershed.” J. Hydrol., 358(1–2), 70–83.
Minville, M., Krau, S., Brissette, F., and Leconte, R. (2010). “Behaviour and performance of a water resource system in Québec (Canada) under adapted operating policies in a climate change context.” Water Resour. Manage., 24(7), 1333–1352.
Moradkhani, H., and Sorooshian, S. (2008). “General review of rainfall-runoff modeling: Model calibration, data assimilation and uncertainty analysis.” Hydrological modelling and the water cycle: Coupling the atmospheric and hydrological models, S. Sorooshian, K.-L. Hsu, E. Coppola, B. Tomassetti, M. Verdecchia, and G. Visconti, eds., Springer, Berlin, Germany, 1–24.
Nash, J. E., and Sutcliffe, J. V. (1970). “River flow forecasting through conceptual models part I—A discussion of principles.” J. Hydrol., 10(3), 282–290.
Neitsch, S. L., Arnold, J. G., Kiniry, J. R., Williams, J. R., and King, K. W. (2002). “Soil water assessment tool theoretical documentation.”, Grassland, Soil and Water Research Laboratory, Temple, TX.
Pedersen, M. E. H. (2010). “Good parameters for differential evolution.”, Hvass Laboratories, Denmark.
Poulin, A., Brissette, F., Leconte, R., Arsenault, R., and Malo, J. S. (2011). “Uncertainty of hydrological modelling in climate change impact studies in a Canadian, snow-dominated river basin.” J. Hydrol., 409(3–4), 626–636.
Ronkkonen, J., Kukkonen, S., and Price, K. V. (2005). “Real-parameter optimization with differential evolution.” Proc., IEEE Congress on Evolutionary Computation, Vol. 1, IEEE Computer Society, Washington, DC, 506–513.
Salomon, R. (1996). “Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions.” BioSystems, 39(3), 263–278.
Schmitt, L. M. (2001). “Theory of genetic algorithms.” Theor. Comput. Sci., 259(1–2), 1–61.
Schulla, J., and Jasper, K. (2000). “Model description WASIM-ETH (Water balance simulation model ETH).” ETH-Zurich, Zurich, Switzerland.
Singh, V. P., and Frevert, D. K. (2001). Mathematical models of large watershed hydrology, Water Resources Publications, Highlands Ranch, CO.
Singh, V. P., and Woolhiser, D. A. (2002). “Mathematical modeling of watershed hydrology.” J. Hydrol. Eng., 270–292.
Spears, W. M., Green, D. T., and Spears, D. F. (2010). “Biases in particle swarm optimization.” Int. J. Swarm Intell. Res., 1(2), 34–57.
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.
Tolson, B. A., and Shoemaker, C. A. (2007). “Dynamically dimensioned search algorithm for computationally efficient watershed model calibration.” Water Resour. Res., 43(1), W01413.
Trelea, I. C. (2003). “The particle swarm optimization algorithm: Convergence analysis and parameter selection.” Inf. Process. Lett., 85(6), 317–325.
Tuba, M., Subotic, M., and Stanarevic, N. (2011). “Modified cuckoo search algorithm for unconstrained optimization problems.” Proc., 5th European Computing Conf. (ECC’11), R. Leandre, M. Demiralp, M. Tuba, L. Vladareanu, and O. Martin, eds., World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, WI, 263–268.
Ülker, E. D., and Haydar, A. (2012). “Comparison of the performances of differential evolution, particle swarm optimization and harmony search algorithms on benchmark functions.” Acad. Res. Int., 3(2), 85–92.
Velazquez, J. A., Anctil, F., and Perrin, C. (2010). “Performance and reliability of multimodel hydrological ensemble simulations based on seventeen lumped models and a thousand catchments.” Hydrol. Earth Syst. Sci., 14(11), 2303–2317.
Vrugt, J. A., and Robinson, B. A. (2007). “Improved evolutionary optimization from genetically adaptive multimethod search.” Proc. Natl. Acad. Sci., 104(3), 708–711.
Whitley, D., Lunacek, M., and Sokolov, A. (2006). “Comparing the niches of CMA-ES, CHC and pattern search using diverse benchmarks.” Parallel problem solving from nature (PPSN IX), Springer, Berlin, Germany, 988–997.
Yang, X.-S., and Deb, S. (2009). “Cuckoo search via Levy flights.” Proc., World Congress on Nature & Biologically Inspired Computing, IEEE Publications, Piscataway, NJ, 210–214.
Yen, J., Liao, J. C., Lee, B., and Randolph, D. (1998). “A hybrid approach to modeling metabolic systems using genetic algorithms and simplex method.” IEEE Trans. Syst. Man Cybern., 28(2), 173–191.
Information & Authors
Information
Published In
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Mar 21, 2013
Accepted: Nov 4, 2013
Published online: Nov 6, 2013
Discussion open until: Apr 6, 2014
Published in print: Jul 1, 2014
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.