Synopsis
Monte Carlo optimization method
Description
The Sherpa Monte Carlo optimization method, an implementation of the differential evolution algorithm.
The "forward-fitting" algorithm employed by the Sherpa software package is a standard technique used to model X-ray data. A statistic, usually an assumed weighted chi2 or Poisson likelihood (e.g. Cash), is minimized in the fitting process to obtain a set of the best model parameters. Astronomical models often have complex forms with many parameters that can be correlated (e.g. an absorbed power-law); minimization is not trivial in such a setting, as the statistical parameter space becomes multimodal, and finding the global minimum is difficult. Therefore several optimization algorithms have been developed for Sherpa which target a wide range of minimization problems. One of these is a global search Monte-Carlo method, which has been implemented following a differential evolution algorithm presented by Storn and Price (1997).
Differential Evolution
When using the Sherpa 'moncar' method, a population of fixed size - which contains n-dimensional vectors, where n is the number of free parameters - is randomly initialized. At each iteration, a new n-dimensional vector is generated by combining vectors from the pool of population, the resulting trial vector is selected if it lowers the objective function. For more details see:
Storn, R. and Price, K. "Differential Evolution: A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces." J. Global Optimization 11, 341-359, 1997.
or http://www.icsi.berkeley.edu/~storn/code.html
Method Options
- ftol - the function tolerance to terminate the search for the minimum; default is sqrt( DBL_EPSILON ) ~ 1.19209289551e-07, where DBL_EPSILON is the smallest number x such that 1.0 != 1.0 + x.
- maxfev - the maximum number of function evaluations; default is 8192 * n (number of free parameters).
- verbose - the amount of information to print about the fit progress. Default is 0 (no output).
- seed - the seed for the random number generator; default value is 2357.
- population_size - the population of potential solutions is allowed to evolve to search for the minimum of the fit statistics. The trial solution is randomly chosen from a combination from the current population, and it is only accepted if it lowers the statistics. The default value for the population size is 16 times the number of free parameters.
- xprob - the crossover probability should be within the range [0.5,1.0]; default value is 0.9. A high value for the crossover probability should result in a faster convergence rate; conversely, a lower value should make the differential evolution method more robust.
- weighting_factor - the weighting factor should be within the range [0.5, 1.0]; default is 0.8. Differential evolution is more sensitive to the weighting_factor then the xprob parameter. A lower value for the weighting_factor, coupled with an increase in the population_size, gives a more robust search at the cost of efficiency.
Example
sherpa> set_method("moncar") sherpa> get_method_name() 'moncar'
Set the optimization method and then confirm the new value.
Bugs
See the bugs pages on the Sherpa website for an up-to-date listing of known bugs.
See Also
- methods
- gridsearch, levmar, list_iter_methods, list_methods, neldermead, set_method, set_method_opt
- statistics
- set_sampler_opt