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 algorithm¹ 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.²

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.¹ The transformed energy is given by:

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

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 LJ₃₈,¹ 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 Morse² and Sutton-Chen families of potentials³ have been found. More recently, the global potential energy minima for (NaCl)_nCl^- have been identified using this global minimization approach.⁴

A recent analysis⁵ 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.

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).