Chia-Ming Wang, Jeffrey D. Hyman, Allon G. Percus et al. · International Journal of Modern Physics C · 2009
We explore the potential of parallel tempering as a combinatorial optimization method, applying it to the traveling salesman problem. We compare simulation results of parallel tempering with a benchmark implementation of simulated annealing, and study how different choices of parameters affect the relative performance of the two methods. We find that a straightforward implementation of parallel tempering can outperform simulated annealing in several crucial respects. When parameters are chosen appropriately, both methods yield close approximation to the actual minimum distance for an instance with 200 nodes. However, parallel tempering yields more consistently accurate results when a series of independent simulations are performed. Our results suggest that parallel tempering might offer a simple but powerful alternative to simulated annealing for combinatorial optimization problems.
Cited by 18
Grigorios Mingas, Christos-Savvas Bouganis · Lecture notes in computer science · 2012
Cited by 16
Angelini, Maria Chiara · arXiv (Cornell University) · 2018
The theoretical information threshold for the planted clique problem is $2\log_2(N)$, however no polynomial algorithm is known to recover a planted clique of size $O(N^{1/2-ε})$, $ε>0$. In this paper we will apply a standard method for the analysis of disordered models, the Parallel-Tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the Sparse Planted Independent Set problem. In this situation thresholds should be sharper and finite size corrections should be less important. Also in this case PT shows a polynomial scaling in the hard region for the recovery.
Cited by 0Open access
Alex Bunker, Burkhard Dünweg · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2000
We have developed a technique to accelerate the acquisition of effectively uncorrelated configurations for off-lattice models of dense polymer melts that makes use of both parallel tempering and large-scale Monte Carlo moves. The method is based upon simulating a set of systems in parallel, each of which has a slightly different repulsive core potential, such that a thermodynamic path from full excluded volume to an ideal gas of random walks is generated. While each system is run with standard stochastic dynamics, resulting in an NVT ensemble, we implement the parallel tempering through stochastic swaps between the configurations of adjacent potentials, and the large-scale Monte Carlo moves through attempted pivot and translation moves that reach a realistic acceptance probability as the limit of the ideal gas of random walks is approached. Compared to pure stochastic dynamics, this results in an increased efficiency even for a system of chains as short as N=60 monomers, however at this chain length the large-scale Monte Carlo moves were ineffective. For even longer chains, the speedup becomes substantial, as observed from preliminary data for N=200. We also compare our scheme to the end bridging algorithm of Theodorou et al. For N=60, end bridging must allow a polydispersity of more than 10% in order to relax the end-to-end vector more quickly than our method. The comparison is, however, hampered by the fact that the end-to-end vector becomes a somewhat artificial quantity when one implements end bridging, and is perhaps no longer the slowest dynamic variable.
Cited by 91Open access
Nicholas G. Tawn · Warwick Research Archive Portal (University of Warwick) · 2017
Markov Chain Monte Carlo (MCMC) techniques for sampling from complex probability distributions have become mainstream. Big data and high model complexity demand more scalable and robust algorithms. A famous problem with MCMC is making it robust to situations when the target distribution is multi-modal. In such cases the algorithm can become trapped in a subset of the state space and fail to escape during the entirety of the run of the algorithm. This non-exploration of the state space results in highly biased sample output. Simulated (ST) and Parallel (PT) Tempering algorithms are typically used to address multi-modality problems. These methods flatten out the target distribution using a temperature schedule. This allows the Markov chain to move freely around the state space and explore all regions of significant mass. This thesis explores two new ideas to improve the scalability of the PT algorithm. These are implemented in prototype algorithms, QuanTA and HAT, which are accompanied by supportive theoretical optimal scaling results. QuanTA focuses on improving transfer speed of the hot state mixing information to the target cold state. The associated scaling result for QuanTA shows that under mild conditions the QuanTA approach admits a higher order temperature spacing than the PT algorithm. HAT focuses on preserving modal weight through the temperature schedule. This is an issue that can lead to critically poor performance of the PT approach. The associated optimal scaling result is useful from a practical perspective. The result also challenges the notion that without modal weight preservation tempering schedules can be selected based on swap acceptance rates; an idea repeatedly used in the current literature. The new algorithms are prototype designs and have clear limitations. However, the impressive empirical performance of these new algorithms, together with supportive theory, illustrate their substantial improvement over existing methodology.
Cited by 9Open access
Walter Kob, Claudio Brangian, Torsten Stühn et al. · 2001
We discuss the efficiency of the so-called parallel tempering method to equilibrate glassy systems also at low temperatures. The main focus is on two structural glass models, SiO2 and a Lennard-Jones system, but we also investigate a fully connected 10 state Potts-glass. By calculating the mean squared displacement of a tagged particle and the spin-autocorrelation function, we find that for these three glass-formers the parallel tempering method is indeed able to generate, at low temperatures, new independent configurations at a rate which is O(100) times faster than more traditional algorithms, such as molecular dynamics and single spin flip Monte Carlo dynamics. In addition we find that this speedup increases with decreasing temperature. The reliability of the results is checked by calculating the distribution of the energy at various temperatures and by showing that these can be mapped onto each other by the reweighting technique. 1
Cited by 0
Aminata Kone, David A. Kofke · The Journal of Chemical Physics · 2005
A heuristic is developed specifying that temperatures in replica-exchange simulations should be spaced such that about 20% of the phase-swap attempts are accepted. The result is found to be independent of the heat capacity, suggesting that it may be applied generally despite being based on an assumption of (piecewise-) constant heat capacity.
Cited by 232
Masafumi Fukuma, Naoya Umeda · Progress of Theoretical and Experimental Physics · 2017
The algorithm based on integration over Lefschetz thimbles is a promising method to resolve the sign problem for complex actions. However, this algorithm often meets a difficulty in actual Monte Carlo calculations because the configuration space is not easily explored due to the infinitely high potential barriers between different thimbles. In this paper, we propose to use the flow time of the antiholomorphic gradient flow as an auxiliary variable for the highly multimodal distribution. To illustrate this, we implement the parallel tempering method by taking the flow time as a tempering parameter. In this algorithm, we can take the maximum flow time to be sufficiently large such that the sign problem disappears there, and two separate modes are connected through configurations at small flow times. To exemplify that this algorithm does work, we investigate the (0+1)-dimensional massive Thirring model at finite density and show that our algorithm correctly reproduces the analytic results for large flow times such as T=2.
Cited by 69Open access
Wei Deng · TIB Data Manager · 2024
Cited by 0Open access
Magiera, M., Neuhaus, T., Hansmann, U. H. E. · JuSER (Forschungszentrum Jülich) · 2007
Cited by 0
Y. Saito, Shun Kimura, Koujin Takeda · ArXiv.org · 2025
Bayesian inference is useful to obtain a predictive distribution with a small generalization error. However, since posterior distributions are rarely evaluated analytically, we employ the variational Bayesian inference or sampling method to approximate posterior distributions. When we obtain samples from a posterior distribution, Hamiltonian Monte Carlo (HMC) has been widely used for the continuous variable part and Markov chain Monte Carlo (MCMC) for the discrete variable part. Another sampling method, the bouncy particle sampler (BPS), has been proposed, which combines uniform linear motion and stochastic reflection to perform sampling. BPS was reported to have the advantage of being easier to set simulation parameters than HMC. To accelerate the convergence to a posterior distribution, we introduced parallel tempering (PT) to BPS, and then proposed an algorithm when the inverse temperature exchange rate is set to infinity. We performed numerical simulations and demonstrated its effectiveness for multimodal distribution.
Cited by 0Open access
Suzanne Denise Gardner · D-Scholarship@Pitt (University of Pittsburgh) · 2006
We present a new model for characterizing the interactions of excess electrons with (H2O)n- clusters. This model combines a modified Thole-type water model with distributed point polarizable, denoted DPP, with quantum Drude oscillators for treating polarization and dispersion interactions between the excess electron and the water molecules. It is demonstrated by examining several small water clusters that this model closely reproduces the relative energies of different isomers of the anions as well as the electron binding energies from ab initio MP2 calculations. The Drude/DPP model is used to carry out parallel tempering Monte Carlo simulations of (H2O)6-.
Cited by 0Open access
Wei Deng, Qian Zhang, Feng Qi et al. · arXiv (Cornell University) · 2022
Parallel tempering (PT), also known as replica exchange, is the go-to workhorse for simulations of multi-modal distributions. The key to the success of PT is to adopt efficient swap schemes. The popular deterministic even-odd (DEO) scheme exploits the non-reversibility property and has successfully reduced the communication cost from $O(P^2)$ to $O(P)$ given sufficiently many $P$ chains. However, such an innovation largely disappears in big data due to the limited chains and few bias-corrected swaps. To handle this issue, we generalize the DEO scheme to promote non-reversibility and propose a few solutions to tackle the underlying bias caused by the geometric stopping time. Notably, in big data scenarios, we obtain an appealing communication cost $O(P\log P)$ based on the optimal window size. In addition, we also adopt stochastic gradient descent (SGD) with large and constant learning rates as exploration kernels. Such a user-friendly nature enables us to conduct approximation tasks for complex posteriors without much tuning costs.
Cited by 0Open access
Pleydell, David · Zenodo (CERN European Organization for Nuclear Research) · 2020
Adaptive parallel tempering algorithm for sampling nimble models with multi-modal posterior distributions .
Cited by 0Open access
Paul Dupuis, Yufei Liu, Nuria Plattner et al. · Multiscale Modeling and Simulation · 2012
Parallel tempering, also known as replica exchange sampling, is an important method for simulating complex systems. In this algorithm simulations are conducted in parallel at a series of temperatures, and the key feature of the algorithm is a swap mechanism that exchanges configurations between the parallel simulations at a given rate. The mechanism is designed to allow the low temperature system of interest to escape from deep local energy minima where it might otherwise be trapped via those swaps with the higher temperature components. In this paper we introduce a performance criterion for such schemes based on large deviation theory and argue that the rate of convergence is a monotone increasing function of the swap rate. This motivates the study of the limit process as the swap rate goes to infinity. We construct a scheme which is equivalent to this limit in a distributional sense but which involves no swapping at all. Instead, the effect of the swapping is captured by a collection of weights that influence both the dynamics and the empirical measure. While theoretically optimal, this limit is not computationally feasible when the number of temperatures is large, and so variations that are easy to implement and nearly optimal are also developed.
Cited by 58
Garibay Alonso, Raul, Mixteco Sanchez, Juan Carlos, Alonso Herrera, Christian Amadeo · Figshare · 2024
The thermal conductivity of wurtzite ZnO is determined by using molecular dynamics simulation and the auto-correlation measurements Green-Kubo theory. The simulation dynamics are carried out by using the parallel tempering thermostating methodology which avoids or reduce potential ergodicity problems.
Cited by 0Open access
Lei Liang, Yuhang Jia, Feng Zhou · ArXiv.org · 2025
While gradient-based discrete samplers are effective in sampling from complex distributions, they are susceptible to getting trapped in local minima, particularly in high-dimensional, multimodal discrete distributions, owing to the discontinuities inherent in these landscapes. To circumvent this issue, we combine parallel tempering, also known as replica exchange, with the discrete Langevin proposal and develop the Parallel Tempering enhanced Discrete Langevin Proposal (PTDLP), which are simulated at a series of temperatures. Significant energy differences prompt sample swaps, which are governed by a Metropolis criterion specifically designed for discrete sampling to ensure detailed balance is maintained. Additionally, we introduce an automatic scheme to determine the optimal temperature schedule and the number of chains, ensuring adaptability across diverse tasks with minimal tuning. Theoretically, we establish that our algorithm converges non-asymptotically to the target energy and exhibits faster mixing compared to a single chain. Empirical results further emphasize the superiority of our method in sampling from complex, multimodal discrete distributions, including synthetic problems, restricted Boltzmann machines, and deep energy-based models.
Cited by 0Open access
Dspace Repository (Marmara Üniversitesi) · 2022
This paper deals with a parameter estimation problem within a Bayesian framework. Performing Bayesian inference about the parameters is a challenging computational problem and requires an evaluation of complicated high-dimensional integrals. In this context, we make an attempt to improve an efficient stochastic procedure, proposed by Gregory, which is based on a parallel tempering Markov Chain Monte Carlo method (MCMC). We code its algorithm in Mathematica and then test it for estimating parameters of sinusoids corrupted by a random noise. Computer simulations support its effectiveness.
Cited by 0
Pleydell, David R.J. · Zenodo (CERN European Organization for Nuclear Research) · 2017
Library Contents Adaptive parallel tempering algorithm Depends on nimble 0.6-6, 0.6-5 or 0.6-4.
Cited by 0Open access
E.-M. Ilgenfritz, Werner Kerler, M. Müller–Preussker et al. · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · 2002
We study the performance of QCD simulations with dynamical Wilson fermions by combining the hybrid Monte Carlo algorithm with parallel tempering on ${10}^{4}$ and ${12}^{4}$ lattices. In order to compare tempered with standard simulations, covariance matrices between subensembles have to be formulated and evaluated using the general properties of autocorrelations of the parallel tempering algorithm. We find that rendering the hopping parameter $\ensuremath{\kappa}$ dynamical does not lead to an essential improvement. We point out possible reasons for this observation and discuss more suitable ways of applying parallel tempering to QCD.
Cited by 13Open access