Optimizing the ensemble for equilibration in broad-histogram Monte Carlo simulations

We present an adaptive algorithm which optimizes the statistical-mechanical ensemble in a generalized broad-histogram Monte Carlo simulation to maximize the system’s rate of round trips in total energy. The scaling of the mean round-trip time from the ground state to the maximum entropy state for this local-update method is found to be $O\left({\left[N\ln N\right]}^2\right)$ for both the ferromagnetic and the fully frustrated two-dimensional Ising model with $N$ spins. Our algorithm thereby substantially outperforms flat-histogram methods such as the Wang-Landau algorithm.

Figure 1

Histograms of the optimal ensemble for the 2D fully frustrated Ising model with Metropolis dynamics. For various system sizes and a broad energy range the rescaled data points collapse onto a power-law divergence ${[(E-E_0)∕N\ln N]}^{-1}$ (bold line). The inset shows the diffusivity $D\left(E\right)$ for the same model which is proportional to ${[(E-E_0)∕N]}^2$ (bold line).

Figure 2

Scaling of round-trip times in the energy interval $[-N,0]$ for the flat histogram (open symbols) and optimized ensemble (filled symbols) of the 2D fully frustrated Ising model with Metropolis (circles) and $N$-fold way (squares) dynamics. The solid lines correspond to a logarithmic (power-law) fit for the optimized (flat-histogram) ensemble. The inset illustrates the frustrated couplings of the fully frustrated model.

Figure 3

Histograms for the 2D ferromagnetic Ising model obtained after feedback: for the optimal ensemble a peak evolves around the critical energy in the histograms. The additional peak near the fully polarized ground state found for Metropolis updates (thin line) can be eliminated by changing the dynamics to $N$-fold way updates (bold line). The inset shows the fraction $f\left(E\right)$ of walkers which have most recently visited $E_{+}=0$ for flat-histogram (multicanonical) sampling and the optimal ensembles for Metropolis and $N$-fold way dynamics.

Figure 4

Scaling of round-trip times in the energy interval $[-2N,0]$ for the flat-histogram ensemble (open symbols) and the optimal ensemble (filled symbols) of the 2D ferromagnetic Ising model with Metropolis (circles) and $N$-fold way dynamics (squares). The solid (dashed) lines correspond to a logarithmic (power-law) fit for the optimized (flat-histogram) ensemble. The inset shows the scaling of histograms for the optimal ensemble for $N$-fold way updates.

Figure 5

Average statistical error ${⟨\Delta \ln g\left(E\right)⟩}_E$ of the computed density of states of the FFI model versus the number of round trips in the energy interval $[-N,0]$. The statistical errors were obtained for 16 independent runs and averaged over all energies for $N=36$ (open symbols). Data points for larger system sizes are superimposed (solid symbols), with the system size increasing from right to left. The statistical error reduces like $1∕{\left(\text{round}\text{trips}\right)}^{1∕2}$ (solid line) for all system sizes. The inset shows the deviation $\delta \left(E\right)=\ln g\left(E\right)-\ln g_{\text{exact}}\left(E\right)$, from the exact result for the $24\times 24$ FMI model obtained for 16 independent runs with $3.2\times {10}^6$ sweeps.