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

, which is to be estimated. The estimator. Because Wang and Landau algorithm works in discrete spectra,, such that

1. .

Given this discrete spectrum, the algorithm is initialized by:

• and

• .

The algorithm then performs a multicanonical ensemble simulation: a Metropolis–Hastings random walk in the phase space of the system with a probability distribution 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. accept/refuse the proposed state according to

   1. 1. .

is incremented by one and the following update is performed:

1. .

This is the crucial step of the algorithm, and it is what makes the Wang and Landau algorithm non-Markovian: the stochastic process, that proposal is now more likely refused; in this sense, the algorithm forces the system to visit all of the spectrum equally. 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:

1. .

It was later shown that updating the f by constantly dividing by two can lead to saturation errors. is proportional to the number of steps of the simulation.

Test system

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

The analytical DOS is given by,

by performing the last integral we obtain

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.

.

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:

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

Parallel Implementations

The Wang–Landau algorithm lends itself to parallelisation (utilising multiple CPU and/or GPU cores to improve simulation performance) in three key ways. First is that the energy domain may be divided into several smaller energy sub-domains, with an independent Wang–Landau walker gathering statistics in each sub-domain. (In this case, the global DOS is periodically recovered from the local DOS.) These energy sub-domains may be chosen to be non-uniform in size, to ensure a higher concentration of walkers in regions where the density of states is most challenging to converge. Second is that, in a given energy domain, multiple independent Wang–Landau walkers may gather statistics which are later combined. Third is that, in the case that multiple energy sub-domains are used, an overlap between energy sub-domains facilitates replica exchange, i.e. swapping of walkers from one energy sub-domain to another, which can improve exploration of the configuration space.

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.

, the WL rule for updating the density of states gives the rule for updating the discretized statistical temperature,

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

STMC was compared with WL for the Ising model for more rapid convergence. In sum, STMC needs fewer steps to obtain the same quality of results.

.

For flat energy sampling, let the effective potential, their product gives flat energy sampling.

The forces are calculated as

produces flat energy sampling.

. Technical details including steps to speed convergence are described in and.

gives the transition temperature.

STMD has been refined by the BU group, in half every fixed number of time steps. This simple change makes STMD entirely intensive and substantially improves performance for large systems., 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.

References