Wang and Landau algorithm

The Wang and Landau algorithm, proposed by Fugao Wang and David P. Landau, is a Monte Carlo method designed to estimate the density of states of a system. The method performs a non-Markovian random walk to build the density of states by quickly visiting all the available energy spectrum. The Wang and Landau algorithm is an important method to obtain the density of states required to perform a multicanonical simulation. The Wang–Landau algorithm can be applied to any system which is characterized by a cost (or energy) function. For instance, it has been applied to the solution of numerical integrals and the folding of proteins. The Wang–Landau sampling is related to the metadynamics algorithm.

Overview

The Wang and Landau algorithm is used to obtain an estimate for the density of states of a system characterized by a cost function. It uses a non-Markovian stochastic process which asymptotically converges to a multicanonical ensemble. (I.e. to a Metropolis–Hastings algorithm with sampling distribution inverse to the density of states) The major consequence is that this sampling distribution leads to a simulation where the energy barriers are invisible. This means that the algorithm visits all the accessible states (favorable and less favorable) much faster than a Metropolis algorithm.

Algorithm

Consider a system defined on a phase space [math]\displaystyle{ \Omega }[/math], and a cost function, E, (e.g. the energy), bounded on a spectrum [math]\displaystyle{ E\in\Gamma = [E_\min,E_\max] }[/math], which has an associated density of states [math]\displaystyle{ \rho(E) }[/math], which is to be estimated. The estimator is [math]\displaystyle{ \hat \rho(E) \equiv \exp(S(E)) }[/math]. Because Wang and Landau algorithm works in discrete spectra, the spectrum [math]\displaystyle{ \Gamma }[/math] is divided in N discrete values with a difference between them of [math]\displaystyle{ \Delta }[/math], such that

[math]\displaystyle{ N = \frac{E_\max-E_\min}{\Delta} }[/math].

Given this discrete spectrum, the algorithm is initialized by:

• setting all entries of the microcanonical entropy to zero, [math]\displaystyle{ S(E_i) = 0\ \ i=1,2,...,N }[/math]
• initializing [math]\displaystyle{ f = 1 }[/math] and
• initializing the system randomly, by putting in a random configuration [math]\displaystyle{ \boldsymbol{r}\in\Omega }[/math].

The algorithm then performs a multicanonical ensemble simulation: a Metropolis–Hastings random walk in the phase space of the system with a probability distribution given by [math]\displaystyle{ P(\boldsymbol{r}) = 1/\hat{\rho}(E(\boldsymbol{r})) = \exp (-S(E(\boldsymbol{r}))) }[/math] and a probability of proposing a new state given by a probability distribution [math]\displaystyle{ g(\boldsymbol{r} \rightarrow \boldsymbol{r}') }[/math]. A histogram [math]\displaystyle{ H(E) }[/math] of visited energies is stored. Like in the Metropolis–Hastings algorithm, a proposal-acceptance step is performed, and consists in (see Metropolis–Hastings algorithm overview):

1. proposing a state [math]\displaystyle{ \boldsymbol{r}'\in\Omega }[/math] according to the arbitrary proposal distribution [math]\displaystyle{ g(\boldsymbol{r} \rightarrow \boldsymbol{r}') }[/math]
2. accept/refuse the proposed state according to

[math]\displaystyle{ A(\boldsymbol{r}\rightarrow \boldsymbol{r}') = \min\left(1,e^{S - S'}\frac{g(\boldsymbol{r}'\rightarrow \boldsymbol{r})}{g(\boldsymbol{r}\rightarrow \boldsymbol{r}')}\right) }[/math]

where [math]\displaystyle{ S = S(E(\boldsymbol{r})) }[/math] and [math]\displaystyle{ S' = S(E(\boldsymbol{r}')) }[/math].

After each proposal-acceptance step, the system transits to some value [math]\displaystyle{ E_i }[/math], [math]\displaystyle{ H(E_i) }[/math] is incremented by one and the following update is performed:

[math]\displaystyle{ S(E_i) \leftarrow S(E_i) + f }[/math].

This is the crucial step of the algorithm, and it is what makes the Wang and Landau algorithm non-Markovian: the stochastic process now depends on the history of the process. Hence the next time there is a proposal to a state with that particular energy [math]\displaystyle{ E_i }[/math], that proposal is now more likely refused; in this sense, the algorithm forces the system to visit all of the spectrum equally. The consequence is that the histogram [math]\displaystyle{ H(E) }[/math] is more and more flat. However, this flatness depends on how well-approximated the calculated entropy is to the exact entropy, which naturally depends on the value of f. To better and better approximate the exact entropy (and thus histogram's flatness), f is decreased after M proposal-acceptance steps:

[math]\displaystyle{ f \leftarrow f/2 }[/math].

It was later shown that updating the f by constantly dividing by two can lead to saturation errors. A small modification to the Wang and Landau method to avoid this problem is to use the f factor proportional to [math]\displaystyle{ 1/t }[/math], where [math]\displaystyle{ t }[/math] is proportional to the number of steps of the simulation.

Test system

We want to obtain the DOS for the harmonic oscillator potential.

[math]\displaystyle{ E(x) = x^2, \, }[/math]

The analytical DOS is given by,

[math]\displaystyle{ \rho(E) = \int \delta (E(x)-E) \, dx= \int \delta (x^2-E) \, dx, }[/math]

by performing the last integral we obtain

[math]\displaystyle{ \rho(E) \propto \begin{cases} E^{-1/2}, \text{for } x \in \mathbb{R}^1 \\ \text{const}, \text{for } x \in \mathbb{R}^2 \\ E^{1/2}, \text{for } x \in \mathbb{R}^3 \\ \end{cases} }[/math]

In general, the DOS for a multidimensional harmonic oscillator will be given by some power of E, the exponent will be a function of the dimension of the system.

Hence, we can use a simple harmonic oscillator potential to test the accuracy of Wang–Landau algorithm because we know already the analytic form of the density of states. Therefore, we compare the estimated density of states [math]\displaystyle{ \hat \rho(E) }[/math] obtained by the Wang–Landau algorithm with [math]\displaystyle{ \rho(E) }[/math].

Sample code

The following is a sample code of the Wang–Landau algorithm in Python, where we assume that a symmetric proposal distribution g is used:

[math]\displaystyle{ g(\boldsymbol{x}'\rightarrow \boldsymbol{x})=g(\boldsymbol{x}\rightarrow \boldsymbol{x}') }[/math]

The code considers a "system" which is the underlying system being studied.

currentEnergy = system.randomConfiguration()  # A random initial configuration

while f > epsilon:
    system.proposeConfiguration()  # A proposed configuration is proposed
    proposedEnergy = system.proposedEnergy()  # The energy of the proposed configuration computed

    if random() < exp(entropy[currentEnergy] - entropy[proposedEnergy]):
        # If accepted, update the energy and the system:
        currentEnergy = proposedEnergy
        system.acceptProposedConfiguration()
    else:
        # If rejected
        system.rejectProposedConfiguration()

    H[currentEnergy] += 1
    entropy[currentEnergy] += f

    if isFlat(H):  # isFlat tests whether the histogram is flat (e.g. 95% flatness)
        H[:] = 0
        f *= 0.5  # Refine the f parameter

Wang and Landau molecular dynamics: Statistical Temperature Molecular Dynamics (STMD)

Molecular dynamics (MD) is usually preferable to Monte Carlo (MC), so it is desirable to have a MD algorithm incorporating the basic WL idea for flat energy sampling. That algorithm is Statistical Temperature Molecular Dynamics (STMD), developed by Jaegil Kim et al at Boston University.

An essential first step was made with the Statistical Temperature Monte Carlo (STMC) algorithm. WLMC requires an extensive increase in the number of energy bins with system size, caused by working directly with the density of states. STMC is centered on an intensive quantity, the statistical temperature, [math]\displaystyle{ T(E) = 1/(dS(E)/dE) }[/math], where E is the potential energy. When combined with the relation, [math]\displaystyle{ \Omega(E) = e^{S(E)} }[/math], where we set [math]\displaystyle{ k_B=1 }[/math], the WL rule for updating the density of states gives the rule for updating the discretized statistical temperature,

[math]\displaystyle{ \tilde{T}_{j\pm 1}^\prime= \alpha_{j\pm 1} \tilde{T}_{j\pm 1}, }[/math]

where where [math]\displaystyle{ \alpha_{j\pm 1}=1/(1\mp \delta f \tilde{T}_{j \pm 1}), \delta f = (ln f/2\Delta E), \Delta E }[/math] is the energy bin size, and [math]\displaystyle{ \tilde{T} }[/math] denotes the running estimate. We define f as in, a factor >1 that multiplies the estimate of the DOS for the i'th energy bin when the system visits an energy in that bin.

The details are given in Ref. With an initial guess for [math]\displaystyle{ T(E) }[/math] and the range restricted to lie between [math]\displaystyle{ T_L }[/math] and [math]\displaystyle{ T_U }[/math], the simulation proceeds as in WLMC, with significant numerical differences. An interpolation of [math]\displaystyle{ \tilde{T}(E) }[/math] gives a continuum expression of the estimated [math]\displaystyle{ S(E) }[/math] upon integration of its inverse, allowing the use of larger energy bins than in WL. Different values of [math]\displaystyle{ S(E) }[/math] are available within the same energy bin when evaluating the acceptance probability. When histogram fluctuations are less than 20% of the mean, [math]\displaystyle{ f }[/math] is reduced according to [math]\displaystyle{ f \rightarrow \sqrt{f} }[/math].

STMC was compared with WL for the Ising model and the Lennard-Jones liquid. Upon increasing energy bin size, STMC gets the same results over a considerable range, while the performance of WL deteriorates rapidly. STMD can use smaller initial values of [math]\displaystyle{ f_d=f-1 }[/math] for more rapid convergence. In sum, STMC needs fewer steps to obtain the same quality of results.

Now consider the main result, STMD. It is based on the observation that in a standard MD simulation at temperature [math]\displaystyle{ T_0 }[/math] with forces derived from the potential energy [math]\displaystyle{ E([x]) }[/math], where [math]\displaystyle{ [x] }[/math] denotes all the positions, the sampling weight for a configuration is [math]\displaystyle{ e^{-E([x])/T_0} }[/math]. Furthermore, if the forces are derived from a function [math]\displaystyle{ W(E) }[/math], the sampling weight is [math]\displaystyle{ e^{-W(E([x]))/T_0} }[/math].

For flat energy sampling, let the effective potential be [math]\displaystyle{ T_0 S(E) }[/math] - entropic molecular dynamics. Then the weight is [math]\displaystyle{ e^{-S(E)} }[/math]. Since the density of states is [math]\displaystyle{ e^{+S(E)} }[/math], their product gives flat energy sampling.

The forces are calculated as

[math]\displaystyle{ F = (-d/dx) T_0 S(E) = T_0 (dS/dE) (-d/dx) E([x]) = (T_0/T(E)) F^0 }[/math]

where [math]\displaystyle{ F^0 }[/math] denotes the usual force derived from the potential energy. Scaling the usual forces by the factor [math]\displaystyle{ (T_0/T(E)) }[/math] produces flat energy sampling.

STMD starts with an ordinary MD algorithm at constant [math]\displaystyle{ T_0 }[/math] and V. The forces are scaled as indicated, and the statistical temperature is updated every time step, using the same procedure as in STMC. As the simulation converges to flat energy sampling, the running estimate [math]\displaystyle{ \tilde{T}(E) }[/math] converges to the true [math]\displaystyle{ T(E) }[/math]. Technical details including steps to speed convergence are described in and.

In STMD [math]\displaystyle{ T_0 }[/math] is called the kinetic temperature as it controls the velocities as usual, but does not enter the configurational sampling, which is unusual. Thus STMD can probe low energies with fast particles. Any canonical average can be calculated with reweighting, but the statistical temperature, [math]\displaystyle{ T(E) }[/math], is immediately available with no additional analysis. It is extremely valuable for studying phase transitions. In finite nanosystems [math]\displaystyle{ T(E) }[/math] has a feature corresponding to every “subphase transition”. For a sufficiently strong transition, an equal-area construction on an S-loop in [math]\displaystyle{ 1/T(E) }[/math] gives the transition temperature.

STMD has been refined by the BU group, and applied to several systems by them and others. It was recognized by D. Stelter that despite our emphasis on working with intensive quantities, [math]\displaystyle{ ln(f) }[/math] is extensive. However [math]\displaystyle{ \delta f = (ln(f)/2\Delta E) }[/math] is intensive, and the procedure [math]\displaystyle{ f \rightarrow \sqrt{f} }[/math] based on histogram flatness is replaced by cutting [math]\displaystyle{ \delta f }[/math] in half every fixed number of time steps. This simple change makes STMD entirely intensive and substantially improves performance for large systems. Furthermore, the final value of the intensive [math]\displaystyle{ \delta f }[/math] is a constant that determines the magnitude of error in the converged [math]\displaystyle{ T(E) }[/math], and is independent of system size. STMD is implemented in LAMMPS as fix stmd.

STMD is particularly useful for phase transitions. Equilibrium information is impossible to obtain with a canonical simulation, as supercooling or superheating is necessary to cause the transition. However an STMD run obtains flat energy sampling with a natural progression of heating and cooling, without getting trapped in the low energy or high energy state. Most recently it has been applied to the fluid/gel transition in lipid-wrapped nanoparticles.

Replica exchange STMD has also been presented by the BU group.