Basin Hopping Algorithm
Basin-hopping is a stochastic algorithm which attempts to find the global minimum of a smooth scalar function of one or more variables [R110][R111] [R112] [R113]. The algorithm in its current form was described by David Wales and Jonathan Doye [R111] http://www-wales.ch.cam.ac.uk/.
The algorithm is iterative with each cycle composed of the following features
- random perturbation of the coordinates
- local minimization
- accept or reject the new coordinates based on the minimized function value
The acceptance test used here is the Metropolis criterion of standard Monte Carlo algorithms, although there are many other possibilities [R112].
This global minimization method has been shown to be extremely efficient for a wide variety of problems in physics and chemistry. It is particularly useful when the function has many minima separated by large barriers. See the Cambridge Cluster Database http://www-wales.ch.cam.ac.uk/CCD.html for databases of molecular systems that have been optimized primarily using basin-hopping. This database includes minimization problems exceeding 300 degrees of freedom.
See the free software program GMIN (http://www-wales.ch.cam.ac.uk/GMIN) for a Fortran implementation of basin-hopping. This implementation has many different variations of the procedure described above, including more advanced step taking algorithms and alternate acceptance criterion.
For stochastic global optimization there is no way to determine if the true global minimum has actually been found. Instead, as a consistency check, the algorithm can be run from a number of different random starting points to ensure the lowest minimum found in each example has converged to the global minimum. For this reason basinhopping will by default simply run for the number of iterations niter and return the lowest minimum found. It is left to the user to ensure that this is in fact the global minimum.
Choosing stepsize: This is a crucial parameter in basinhopping and depends on the problem being solved. Ideally it should be comparable to the typical separation between local minima of the function being optimized. basinhopping will, by default, adjust stepsize to find an optimal value, but this may take many iterations. You will get quicker results if you set a sensible value for stepsize.
Choosing T: The parameter T is the temperature used in the metropolis criterion. Basinhopping steps are accepted with probability 1 if func(xnew) < func(xold), or otherwise with probability:
exp( -(func(xnew) - func(xold)) / T )
So, for best results, T should to be comparable to the typical difference in function values between local minima.
Basin Hopping Algorithm[edit]
This article "Basin Hopping Algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Basin Hopping Algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
