Algorithm Guide

SPOTPY comes along with some very powerful techniques for parameter optimization. The conducted algorithms can be very efficient, but also inefficient, depending on your specific parameter search problem. This is why we have developed a decision tree to help you choosing the right algorithm:

Algorithm Guide

Figure 8: Decision-tree as a guidance for the choice of an algorithm in SPOTPY for a specific optimization problem.

Algorithm Overview

To understand, what the algorithms are doing, we can provide a short overview.


Monte Carlo

This algorithm is probably the simplest one. It relays on repeated random parameter samplings which are tested in the simulation function. The algorithm does not learn or adopt its method during the sampling, which makes it easy to parallelize. In principle, this algorithm can solve any parameter search problem, but with an increasing number of parameters, the number of needed iterations is rising exponential. This can be optimized by selecting an appropriate distribution for the parameters.

These steps are performed during the sampling:

Because of its simplicity and easy integration the Monte Carlo sampling is widely used.


Latin Hypercube Sampling

The Latin Hypercube sampling combines the dimensions of the parameter function with the number of iterations into one matrix. This matrix assures that every parameter combination is scanned. The needed number of iterations (N_{max}) can be calculated with the following formula:

$$N_{max} = (k!)^{p-1}$$

with k as divisions per parameter and p as number of parameters.

These steps are performed during the sampling:

For further detailed information check out McKay et al. (1979).


Markov Chain Monte Carlo

The famous Metropolis MCMC is one of the most used parameter optimization method. It can learn during the sampling and can deal with non-monotonically response functions. The sampling method can reject regions of the parameter search space and tries to find the global optimum. The more often a region of the parameter search space was sampled, the more likely it is to be the global optimum.

These steps are performed during the sampling:

The MCMC algorithm can find a (quasi-) global optimum, but with a still remaining risk to stuck in local minima, depending on the chosen step-size in the parameter function. Is the step-size to large, the sampler jumps too often away from the optimum. Is the step size to low, it can get stuck in local minima.

For further detailed information check out Metropolis et al. (1953).


Maximum Likelihood Estimation

If one is just interested in a fast calibration of a simple model (with nearly monotonically response function or a compact parameter search space), the MLE is an efficient choice. To test whether the MLE algorithm is applicable for calibrating the desired model, it is recommend to test the model with MC first. MLE maximizes the likelihood during the sampling, by adapting the parameter only in directions with an increasing likelihood.

These steps are performed during the sampling:

Adopted in the right way, the MLE can be a very efficient algorithm. But the risk to stuck in local optima is high.


Simulated Annealing

Simulated Annealing can be a robust algorithm, but needs to be adopted to every new parameter search problem. The algorithm starts with a high chance to jump to a new point (high temperature), which is getting more and more unlikely with increasing repetitions (cooling down). If everything works, the algorithm freezes at the global optimal parameter-set.

For further detailed information check out Kirkpatrick et al. (1985).


RObust Parameter Estimation

Another non-Bayesian approach is the ROPE algorithm. It determines parameter uncertainty with the concept of data depth. This has the benefit, that the resulting parameter sets have proven to be more likely giving good results when space or time period of the model changes, e.g. for validation.

For further detailed information check out Bardossy et al. (2008).


Shuffled Complex Evolution - University of Arizona

SCE-UA is designed to overcome the risk of MCMC to stuck in local optima. The risk was reduced by starting several chains/complexes that evolve individually in the parameter space. The population is periodically shuffled and new complexes are created with information from the previous complex. SCE-UA has found to be very robust in finding the global optimum of hydrological models and is one the most widely used algorithm in hydrological applications today.

For further detailed information check out Duan et al. (1994).


Differential Evolution Markov Chain

One of the most recent algorithms we present here is the DE MCz. It requires a minimal number of three chains that learn from each other during the sampling. It has the same Metropolis decision as the MCMC algorithm and has found to be quite efficient compared with other MCMC techniques. Like SCE-UA and SA, DE-MCz does not require any prior distribution information, which reduces the uncertainty due to subjective assumptions during the analysis.

For further detailed information check out terBraak et al. (2008).