Review: Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms¶
Citation
- Wales, D. J. & Doye, J. P. K. (1997). Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. The Journal of Physical Chemistry A, 101(28), 5111–5116.
- DOI
Abstract¶
A global optimization technique is described in which the potential energy surface is transformed into a collection of interpenetrating staircases by associating every point in configuration space with the local minimum reached from it by geometry optimization. The transformation removes transition-state barriers without changing the global minimum. Applied to Lennard-Jones clusters of up to 110 atoms, the method locates all known lowest-energy structures, including several never previously found by unbiased searches.
Finding the lowest-energy configuration of an atomic cluster is a hard global optimization problem: the potential energy surface (PES) has enormous numbers of local minima separated by barriers, and a local search started at an arbitrary point relaxes into the nearest minimum and stops.
Basin-hopping attacks this by transforming the surface rather than the search. Each point \( \mathbf{X} \) is assigned the energy of the local minimum reached from it by geometry optimization,
which maps the rugged PES onto a set of flat plateaus, one per basin of attraction. Barriers between basins vanish under this transformation, but the global minimum is unchanged. The transformed surface \( \tilde{E} \) is then explored by canonical Monte Carlo at a constant temperature: each step displaces the coordinates at random, relaxes to the local minimum, and accepts or rejects by the Metropolis criterion. The scheme is equivalent to the "Monte Carlo minimization" of Li and Scheraga. On Lennard-Jones clusters it found every known global minimum up to 110 atoms and three previously unknown ones.
Relevance to Hifuku¶
The likelihood landscape over tree space is rugged in the same way as a molecular PES: several high-likelihood topologies act as basins, separated by regions of lower likelihood that a purely local tree search struggles to cross. Basin- hopping is a classic strategy for landscapes of this shape, and it names the family of methods, alongside Lévy-flight relocation and iterated local search, that motivate goal-directed exploration over a single hill climb.
Hifuku shares the propose-then-keep-the-improvement pattern in a limited form: the archive survey varies an elite and keeps the offspring when it improves its niche, so each niche undergoes a local hill climb. The differences are the point. Hifuku is a survey, not a global optimizer: it keeps the best tree in every niche and maps the whole landscape rather than driving toward one global minimum, and it neither transforms the likelihood surface nor runs a Metropolis acceptance step (placement is a plain keep-if-better rule). Basin-hopping is therefore context for the exploration stance, not a component of the current engine.