Comment on “Dynamically dimensioned search algorithm for computationally efficient watershed model calibration” by Bryan A. Tolson and Christine A. Shoemaker

Abstract

[1] Tolson and Shoemaker [2007] recently introduced an optimization algorithm, entitled dynamically dimensioned search (DDS), for automatic calibration of watershed models. The DDS method is a simple stochastic neighborhood search algorithm that has been developed with the purpose of finding preferred parameter combinations fast within the user specified maximum number of function evaluations (as opposed to globally optimal solutions). The definition of “good” solution appears somewhat subjective, and has not formally been defined by Tolson and Shoemaker [2007], but refers to the best attainable parameter combination (the lowest value of objective function) for a given number of function evaluations. To benchmark the effectiveness and robustness of DDS, Tolson and Shoemaker [2007] provide a comparison analysis against the shuffled complex evolution (SCE-UA) algorithm previously developed by Duan et al. [1992] for four different optimization problems with increasing complexity. On the basis of this comparison analysis, Tolson and Shoemaker [2007, paragraph 65] conclude that “the DDS algorithm is a more computationally efficient and robust optimization algorithm than SCE-UA in the context of distributed watershed model automatic calibration.” We would like to congratulate Tolson and Shoemaker on their paper, which we believe makes a valuable contribution to the field of optimization theory and hydrologic model calibration. However, we wish to communicate some concerns regarding the evaluation methods used in comparison of the SCE-UA and the DDS algorithm. [2] The development of SCE-UA was motivated by the concerns at the time that the commonly available optimization methods (both gradient and nongradient search techniques) were not adequate to address the highly nonlinear, nonconvex, and noncontinuous D-dimensional parameter spaces of typical lumped parameter conceptual watershed models during their calibration phase. This development was warranted and needed, to reduce ambiguity about the optimized parameter estimates (facilitating sound inferences about the system under study), and to obtain a better understanding of the limits of predictive capability of watershed models. Indeed, many contributions to the hydrologic literature and beyond (appropriately acknowledged by Tolson and Shoemaker [2007]), have demonstrated the power and efficiency of the SCE-UA method for finding globally optimal solutions in models with simulation times often on the order of a few seconds or less. The DDS algorithm of Tolson and Shoemaker [2007], however has been developed in the context of finding preferred parameter solutions in computationally demanding models. This context is different than what inspired the original development of the SCE-UA algorithm. Therefore, we believe that any comparison between these methods require careful interpretation and need to be framed within the context of the original goals of the developed algorithms. [3] The difference between the DDS and SCE-UA methods is best highlighted and illustrated in Figure 2 of Tolson and Shoemaker [2007]. For a small budget of function evaluations, it is obvious that the DDS algorithm finds better solutions than the SCE-UA algorithm. However, for larger number of function evaluations, the SCE-UA method generally outperforms the DDS algorithm, locating better overall solutions in the parameter space. One must therefore consider the intended goal, which in the case of DDS is a maximum decline in objective function within a limited but fixed number of function (model) evaluations. For this purpose, we initiated a study related to the efficiency and convergence issues of the SCE-UA algorithm. [4] If the goal is to find preferred solutions fast within a limited budget of model evaluations, the algorithmic parameters of the SCE-UA method might need to be modified in such a way that the method emphasizes less on exhaustive exploration of the global parameter domain, and focuses more on local exploitation of existing solutions. Running SCE-UA with default values of the algorithmic parameters as recommended by Duan et al. [1994], and developed within the context of precisely locating the global optimum, might therefore not be optimal. To improve the initial efficiency of the SCE-UA method, we experimented with the selection of the values of the algorithmic parameters in the Simplex evolution steps. First, and as done by Tolson and Shoemaker [2007], we recommend using only a small number of complexes (i.e., p = 2) to avoid unnecessary overhead of evaluating a large population of individuals without any information exchange. Second, our initial studies on a number of test functions to date, have demonstrated that a much faster initial decay of the objective function can be achieved when the reflection and contraction step lengths in the Simplex method [Nelder and Mead, 1965] are changed from their default values of 1.0 and 0.5 as recommended in the literature and used in the classical SCE-UA method, to 0.8 and 0.45 respectively. [5] Figure 1 shows the evolution of the average best function value for the DDS and modified SCE-UA method as function of the number of function evaluations for the Griewank (Figure 1a), Rastrigin (Figure 1b), and Ackley (Figure 1c) functions. These classical benchmark functions were considered by Tolson and Shoemaker [2007], and used here within the same parameter bounds as mentioned in their paper, to compare both methods in terms of efficiency and robustness. The presented lines in Figure 1 denote averages over 25 different optimization trials. This averaging was done to minimize statistical variability and the influence of the selection of the initial population. The minima are 0, −30 and −22.718 for the 10-D Griewank, 30-D Rastrigin and Ackley functions, respectively. [6] With the modified values for the algorithmic parameters, it is apparent that SCE-UA exhibits a much better performance, with an initial decline of the objective function that is very similar, if not better than the DDS algorithm. Moreover, this rapid convergence of SCE-UA does not prohibit its ability to approximate the global optimum, at least not for the test functions considered here (although about 1,000 more function evaluations are needed for the Griewank function). The improvements of SCE-UA are most pronounced for the Rastrigin function, depicted in Figure 1b, and less significant for the Griewank, and Ackley function (Figures 1b and 1c). However, if we compare the results more closely for the Ackley function, it is observed that (1) The “DDS 1000” terminates with a final objective function value of about −22.1, which is slightly removed from the global minimum; (2) “DDS 2500” reaches approximately −22.5 after 2500 function evaluations, while SCE-UA reaches the same function value in about 2,100 function evaluations; and (3) even after 10,000 function evaluations, DDS is not capable of exactly locating the global minimum (also applies to function 1), while SCE-UA consistently finds the minimum of −22.718 in about 4,000 function evaluations. It is also important to note that the DDS performance as shown in the above examples is highly dependent on the total number of function evaluations. If the purpose of using DDS is to find the global optimum, the user is required to try different number of function evaluations or simply consider a very large value of m, to ensure proper algorithm convergence. [7] The results presented here inspire confidence that the SCE-UA method is a robust search method, and question whether the DDS algorithm is indeed as efficient. We have tried various additional modifications to SCE-UA to further speed up its convergence for the test functions considered herein. Our analysis has shown that replacement of the original mutation step in SCE-UA with an explicit reflection boundary handling approach (as used in DDS) further improves algorithm efficiency. It also seems reasonable to assume that further initial efficiency improvements of SCE-UA can be achieved, if the algorithmic parameters and mathematical definition of the reflection and contraction steps in the Simplex method are tuned in a more systematic and comprehensive manner. [8] Finally, those engaged in research, testing and applications in the field of optimization know well that judgment on the performance of a given algorithm is not a trivial matter and requires comprehensive study and no concrete conclusions can be drawn from tests performed on a limited number of examples. In fact Wolpert and Macready [1997] theoretically demonstrate that it is impossible to develop a single optimization algorithm that is always most efficient for a large range of different problem features. What this practically means is that one can always find a set of optimization problems (test functions) for which a particular algorithm works best. [9] In their reply, Tolson and Shoemaker [2007] also argue that one of the main advantages of DDS is that it scales well with the number of dimensions and model evaluations used to search the parameter space, and does not require tuning of the algorithmic parameter r. The same can be said for other optimization algorithms in the literature, including the original and the modified SCE-UA algorithm considered herein. It is common practice, to either base the values of the algorithmic parameters in optimization algorithms on some theoretical analysis, or to tune them in such a way that the best performance is obtained for a range of different problem features with varying degrees of dimensionality. After this, the values of the parameters are simply hard wired in the code and used in applications. [10] The first, second and last authors are supported by NASA NEWS (grant NNX06AF934), NOAA CPPA (grant NA060AR4310062) and NSF STC for Sustainability of Semi-Arid Hydrology and Riparian Areas (SAHRA) (grant EAR-9876800) programs. The third author is supported by a J. Robert Oppenheimer Fellowship from the LANL Postdoctoral Program. The work of the fourth author was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52–07NA27344. We gratefully acknowledge the help of Kuo-lin Hsu and the comments of the editor, Tom Torgersen; associate editor, Alberto Montanari; and two anonymous reviewers that have improved our manuscript.