Jordan Group Home Page
Ken Jordan (CV)
Research Support
Present and former group members
Group Meetings
Educational Activities
Computational Resources - Center for Simulation and Modeling
News and Other Links
Computational Modeling & Simulation PhD Program

NCSA Nanotechnology Initiative

Details of algorithm

As the number of atoms in a cluster increases, the number of local minima on the potential energy surface (PES) grows rapidly. Successful global optimization techniques must be able to escape from local basins of attraction.

The GMIN algorithm1 falls into the `hypersurface deformation' category of techniques, which usually attempt to increase the rate of transition between minima by reducing the number of local minima on the PES by smoothing the surface, and therefore reducing the search space. In general, these methods rely on the assumption that the global minimum of the deformed PES will lead back to the global minimum of the original surface when the transformation is reversed. However, this is not necessarily the case, as shown by Doye and Wales.2

Wales' and Doye's GMIN algorithm avoids this problem. It transforms the PES into a collection of interpenetrating terraces by associating the energy at any point in configuration space with that of the local minimum found by a geometry optimization started from that point.1 The transformed energy is given by:

Ê(X)=min{E(X)} ,

where X is the vector representing a point in nuclear configuration space and min indicates that an energy minimization, (usually either conjugate gradient or BFGS methods), has been completed starting from X. This transformation does not alter the global minimum nor the number of local minima. It simply removes transition state regions from the problem. Therefore, it is now easier to explore the transformed PES using a Monte Carlo (MC) simulation since areas separated by barriers on the original PES are now only separated by steps between the energy levels of the minima. The system can hop directly between basins of attraction at each MC step (`basin hopping').

This schematic illustrates the way GMIN might change a potential (black) into a modified "terrace" potential (red).

potential energy step function

Previous applications of the GMIN basin-hopping algorithm

The GMIN algorithm has been successfully used to locate the global minima of Lennard-Jones (LJ) clusters with up to 110 atoms, including the face-centered-cubic truncated octahedron for LJ38,1 which has proven particularly difficult to locate using unbiased searches. In addition, the global minima of clusters containing up to 80 atoms modeled by both the Morse2 and Sutton-Chen families of potentials3 have been found. More recently, the global potential energy minima for (NaCl)nCl- have been identified using this global minimization approach.4

A recent analysis5 of why the basin-hopping or MC minimization method is so successful concluded that there were two key features:

  • The transformation applied to the PES removes the transition state barriers without changing the global minimum and this accelerates the dynamics.
  • This transformation also broadens the thermodynamic transitions so that there is a significant probability of finding the global minimum at temperatures where the free energy barriers between funnels of this and other minima may be crossed.
The method is similar to the MC minimization method of Li and Scheraga,7 and to some genetic algorithms. 8,9

  1. a D.J. Wales and J.P.K. Doye, J. Phys. Chem. A 101, 5111 (1997).
    Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 Atoms
    b J.P.K. Doye and D.J. Wales, Phys. Rev. Lett. 80, 1357 (1998).
    Thermodynamics of global optimization
  2. J.P.K. Doye and D.J. Wales, J. Chem. Soc. Faraday Trans. 93, 4233 (1997).
    Structural consequences of the range of the interatomic potential: a menagerie of clusters
  3. J.P.K. Doye and D.J. Wales, New J. Chem. 22, 733 (1998).
    Global minima for transition metal clusters described by Sutton-Chen potentials
  4. J.P.K. Doye and D.J. Wales, Phys. Rev. B 59, 2292 (1999).
    Structural transitions and global minima of Sodium Chloride Clusters
  5. J.P.K. Doye, D.J. Wales and M.A. Miller, J. Chem. Phys. 109, 8143 (1998).
    Thermodynamics and the global optimization of Lennard-Jones clusters
  6. J.P.K. Doye and D.J. Wales, J. Chem. Phys. 105, 8428 (1996).
    On potential energy surfaces and relaxation to the global minimum
  7. Z. Li and H.A. Scheraga, Proc. Natl. Acad. Sci. USA 84, 6611 (1987).
  8. D.M. Deaven, N. Tit, J.R. Morris and K.M. Ho, Chem. Phys. Letts. 256, 195 (1996).
  9. J.A. Niesse and H.R. Mayne, J. Chem. Phys. 105, 4700 (1996).
Kenneth D. Jordan
Dept. of Chemistry, University of Pittsburgh,
219 Parkman Avenue, Pittsburgh, PA 15260
Phone: (412) 624-8690     FAX: (412) 624-8611     email: jordan at
This page last updated: