Analysis and optimization of population annealing

Population annealing is an easily parallelizable sequential Monte Carlo algorithm that is well suited for simulating the equilibrium properties of systems with rough free-energy landscapes. In this work we seek to understand and improve the performance of population annealing. We derive several useful relations between quantities that describe the performance of population annealing and use these relations to suggest methods to optimize the algorithm. These optimization methods were tested by performing large-scale simulations of the three-dimensional (3D) Edwards-Anderson (Ising) spin glass and measuring several observables. The optimization methods were found to substantially decrease the amount of computational work necessary as compared to previously used, unoptimized versions of population annealing. We also obtain more accurate values of several important observables for the 3D Edwards-Anderson model.

Figure 1

Scatter plot of ${\rho }_t-1-(2\epsilon -2\pi {\epsilon }^2)k$ vs. ${\rho }_f$ at $\beta =5$ ($k=95$) for $L=6$ and $L=8$; each data point corresponds to a single bond configuration. The solid line corresponds to ${\rho }_t-1+(2\pi {\epsilon }^2-2\epsilon )k={\rho }_f$, see Eq. (43).

Figure 2

${\left[{\rho }_f\right]}_{\mathcal{J}}$ and ${\left[{\rho }_t\right]}_{\mathcal{J}}$ of $L=6$ as a function of annealing step $k$, with the nonlinear $\beta$ scale on the upper $x$ axis. Dashed lines correspond to the theoretically predicted MCMC-equilibrated estimates, Eqs. (38) and (42). The solid line corresponds to the difference ${\left[{\rho }_t\right]}_{\mathcal{J}}-1-(2\epsilon -2\pi {\epsilon }^2)k$, see Eq. (43).

Figure 3

The disordered-averaged family size distribution ${\left[P\left(\eta \right)\right]}_{\mathcal{J}}$ as a function of family size $\eta$, at several temperatures all in the high-temperature regime (the $\beta$ of each distribution increases from left to right). The distributions are exponential and have shape parameters that match the predictions of Eq. (40). The value at $\eta =0$ is not shown in this plot.

Figure 4

The distribution of ${log}_{10}{\rho }_t$ for system sizes $L=6$ (left), 8 (middle), and 10 (right). The solid lines are inverse Gaussian fits with the parameters given in Table 2.

Figure 5

Values of ${\rho }_t$ at $\beta =5$ for the optimized and unoptimized annealing schedules. Each point corresponds to one of 300 $L=8$ bond configurations. The horizontal coordinate of each point is the unoptimized value and the vertical coordinate the optimized value of ${\rho }_t$. The central (black) line corresponds to an improvement of the optimized relative to the unoptimized annealing schedule by a factor of 7.6, and the upper and lower (red) lines correspond to factors of $7.6/3$ and $7.6\times 3$, respectively.

Figure 6

${\mathrm{\Delta }}_{\mathrm{KY}}$ as a function of inverse temperature $\beta$ for $L=6$ (a), $L=8$ (b), and $L=10$ (c).