
In applied mathematics and computational chemistry, Basin-hopping is a stochastic global optimization technique that iterates by performing random perturbation of coordinates, performing local optimization, and accepting or rejecting new coordinates based on a minimized function value. The algorithm was described in 1997 by David J. Wales and Jonathan Doye. It is useful algorithm for global optimization in very high-dimensional landscapes, such as finding the minimum energy structure for molecules. The method is inspired from Monte-Carlo Minimization first suggested by Li and Scheraga in 1987 for protein folding. It is used for problems ranging from nanoalloy clusters to protein structure prediction. However, like other stochastic methods, it cannot guarantee that the global minimum is found.
Basin-hopping grew out of a method for protein folding. In 1987 Li and Scheraga introduced Monte Carlo minimization, where Metropolis sampling is used to cross the barriers between local minima. Li and Scheraga used it to find the lowest energy structure for the pentapeptide Met-enkephalin. In 1997 Doye and Wales described the same algorithm and coined the name basin-hopping, after the way the algorithm search jumps between the basins of local minima. Using this, Doye and Wales found the lowest known structures of all Lennard-Jones clusters up to 110 atoms. The following year, Doye and Wales applied the algorithm to landscapes with a multi-funnel structure. Basin-Hopping has been used in chemistry, biology, and materials science since its development. Basin-hopping has implementations available in GMIN in Fortran and SciPy in Python.
Each basin-hopping step has three parts. First, the coordinates of the current minimum are perturbed randomly. Second, a local optimizer takes this trial point to the bottom of its basin. Finally, an acceptance test decides whether to move to the minimum of this new basin or not, which is usually the Metropolis criterion. Downhill movements between basins are always accepted, and uphill moves are accepted with a probability , where is the energy increase and T is a temperature parameter. Because every trial point is minimized, the search often takes the shape of a staircase of flat steps, meaning saddle points between minima are avoided, without changing the global minimum. The step size between basins is often tuned to give an acceptance rate of 0.5, and T should be on the same order of magnitude as the typical energy difference between minima.


Most variants of Basin-hopping change one part of this loop to prevent it from getting stuck.
Basin-hopping is used to predict the most stable structures of atomic and molecular clusters, requiring global optimization on a cluster’s potential energy landscape. Even in simple clusters, the most stable structure changes as size does. It is also applied to nanoalloys, clusters of two or more elements, with energies computed by DFT rather than empirical potential energies. Due to the simplicity of basin-hopping only requiring a function to minimize, the method is also used in packing problems in geometry and protein structure prediction.
Basin-hopping has known weaknesses. It cannot prove that its lowest minimum is the global minimum, so it is recommended to repeat runs from several random starting locations. Landscapes with more than one funnel are difficult. For example, in the 38-atom Lennard-Jones cluster, the algorithm enters a wide funnel that a large barrier separates from the narrow funnel with the global minimum. This double funnel can be seen in a disconnectivity graph which PyConnect can draw. Genetic algorithms are a widely used alternative for clusters, and in a 2026 comparison of search algorithms replica exchange can use the least CPU time.
