
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^{1}
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).
Previous applications of the GMIN basinhopping algorithm
The GMIN algorithm has been successfully used to locate the global minima of LennardJones (LJ)
clusters with up to 110 atoms,
including the facecenteredcubic truncated octahedron for
LJ_{38},^{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
Morse^{2} and SuttonChen families of
potentials^{3} have been found. More recently,
the global potential energy minima for (NaCl)_{n}Cl^{} have been
identified using this global minimization approach.^{4}
A recent analysis^{5} of why the basinhopping
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}

^{a} D.J. Wales and J.P.K. Doye, J. Phys. Chem. A 101, 5111 (1997).
Global optimization by basinhopping and the lowest energy structures of LennardJones
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
 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
 J.P.K. Doye and D.J. Wales, New J. Chem. 22, 733 (1998).
Global minima for transition metal clusters described by SuttonChen potentials
 J.P.K. Doye and D.J. Wales, Phys. Rev. B 59, 2292 (1999).
Structural transitions and global minima of Sodium Chloride Clusters
 J.P.K. Doye, D.J. Wales and M.A. Miller, J. Chem. Phys. 109, 8143 (1998).
Thermodynamics and the global optimization of LennardJones clusters
 J.P.K. Doye and D.J. Wales, J. Chem. Phys. 105, 8428 (1996).
On potential energy surfaces and relaxation to the global minimum
 Z. Li and H.A. Scheraga, Proc. Natl. Acad. Sci. USA 84, 6611 (1987).
 D.M. Deaven, N. Tit, J.R. Morris and K.M. Ho, Chem. Phys. Letts. 256, 195 (1996).
 J.A. Niesse and H.R. Mayne, J. Chem. Phys. 105, 4700 (1996).
