4.3 Simulated Annealing and Related Stochastic Walker-Based Algorithms 75
ionization states of the atoms, i.e., both the charge that enters the Coulomb term
and the corresponding ionic radius in the dispersion and repulsion terms of the
potential are varied during the run. Here, one adds the ionization energy or electron
affinity for cations or anions, respectively, to the total energy [7, 18].
In general, one can perform simulated annealing both via discrete-step walkers
and via, e.g., constant temperature molecular dynamics simulations. In the latter
case, one reduces the temperature of the system, i.e., the average kinetic energy
of the particles, during the simulation.
6)
Quite generally, a great advantage of the
discrete steps in Monte Carlo simulations for global optimization purposes is the
large freedom in choosing a moveclass most appropriate to the type of exploration
being performed. In contrast to, e.g., molecular-dynamics-based algorithms, one
can replace the physically realistic moveclass of moving one or a few atoms by
a small amount by a more optimization effective moveclass that allows larger
changes in the atom configuration during each move, in order to explore a larger
part of the landscape during, e.g., a global optimization run. In this case, it is
sometimes efficient, to combine such large moves every time with a quench and/or
a gradient-based minimization. Then one applies the acceptance criterion to the
minimum configurations; this scheme is often called basin hopping [65, 66] (for
more details, cf. e.g., the chapters by Goedecker and Wales).
However, one should also recall that one can, in principle (although in practice
often only a posteriori), remove any local minimum except the global one by
designing a special moveclass such that the walkers ‘‘tunnel’’ from the bottom of
a minimum basin into a deeper basin. As long as the goal is only to find the global
minimum this does not constitute a problem and would even be helpful. But in the
case of structure prediction, we are usually interested in all locally ergodic regions
of the landscape, corresponding to kinetically stable modifications. Thus one needs
to be careful about the choice of moveclass, in order not to eliminate important min-
ima.
7)
As a consequence, in spite of its disadvantages as a global search mechanism,
the ‘‘natural’’ moveclass implied in the Newtonian dynamics can in some situations
appear to be the more appropriate one to use during the global search.
Another question is how one can deal with systems that contain not only
continuous but also discrete degrees of freedom, such as spin structures, that
might noticeably contribute to the overall energy via some semiempirical interaction
potential (unless they are incorporated directly in an ab initio calculation and thus
are integrated out during the energy evaluation). Since the spins take on discrete
values, they are more easily dealt with within the framework of discrete random
6) When studying problems derived from
physics and chemistry, one often encoun-
ters a certain prejudice in favor of the molec-
ular dynamics instead of Monte Carlo-based
methods, since the former appear to be
more ‘‘realistic’’ than the random walker
algorithms. However, once the simulation
times are longer than the typical vibra-
tional time scales, and one employs a move-
class consisting of local atom displacement
moves, the expectation values of thermo-
dynamic quantities are approximately the
sameforbothdynamics[64].Thisispartic-
ularly relevant if one wants to derive local
densities of states from the trajectories of
the walkers.
7) Note that this caveat does not only apply to
random walker algorithms but also to, e.g.,
genetic algorithms.