Navigating Phase Transitions with Path-Finding Algorithms: A Strategic Approach to Replica Exchange Monte Carlo

Akie Kowaguchi, Katsuhiro Endo, Kentaro Nomura, Shuichi Kurabayashi, Paul E. Brumby, Kenji Yasuoka · 2025

Read Navigating Phase Transitions with Path-Finding Algorithms: A Strategic Approach to Replica Exchange Monte Carlo by Akie Kowaguchi, Katsuhiro Endo, Kentaro Nomura, Shuichi Kurabayashi, Paul E. Brumby, Kenji Yasuoka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02549.txt.

Introduction

Akie Kowaguchi and five co-authors bring a path-finding trick from computer games into a well-known way of running models of matter. Their paper is from two thousand twenty-five.

The model method runs many copies of a system at once and swaps them, to beat slow settling. Its yield rests on how many copies are used and how apt swaps are. The team treats copies and swap odds as a graph, and uses a famed shortest-path rule to pick the best swap path. The path keeps change in a key term low. Tests on a change between solid and liquid show faster sampling. The plan gives a clear way to tune such runs.

Catalog record

CREATORAkie Kowaguchi, Katsuhiro Endo, Kentaro Nomura, Shuichi Kurabayashi, Paul E. Brumby, Kenji Yasuoka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-02549

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Navigating Phase Transitions with Path-Finding Algorithms: A Strategic Approach to Replica Exchange Monte Carlo Akie Kowaguchi, Katsuhiro Endo, Kentaro Nomura, Shuichi Kurabayashi, Paul E. Brumby, Kenji Yasuoka Abstract The replica exchange method is a powerful tool for overcoming slow relaxation in molecular simulations, but its efficiency depends strongly on the choice of the number and interval of replicas and their exchange probabilities. Here, we propose a new optimization scheme based on the Dijkstra algorithm that constructs an optimal exchange path by representing replicas and their exchange probabilities as a graph. Inspired by path-finding techniques widely used in computer science, including applications in game algorithms, our approach ensures that transitions follow a minimum entropy gradient path and effectively speeds up sampling even in systems exhibiting slow relaxation near critical points or phase transition regions. The method provides a systematic way to improve replica exchange efficiency and offers new insights into the control of relaxation dynamics, as demonstrated through applications to the solid-liquid phase transition of the Lennard-Jones bulk system. I Introduction In complex systems with high energy barriers, achieving the right balance between accurately capturing the true phase equilibrium states - critical transition states - and computational efficiency is necessary. Molecular dynamics (MD) simulations allow detailed tracking of the motion of atoms and molecules, but their application is restricted to short timescales. In contrast, Monte Carlo (MC) simulations enable the search for global energy minima using statistical random sampling while disregarding time-dependent dynamics. While MC simulations are a powerful tool for solving multidimensional problems, they face challenges in systems exhibiting phase transitions due to the long computational time required for the system to reach equilibrium. Therefore, to efficiently transition between these states of interest, a Replica Exchange Monte Carlo (REMC) method (Parallel Tempering, Metropolis-coupled Markov Chain Monte Carlo) hukushima1996exchange , one of a number of extended ensemble methods berg1991multicanonical ; berg1992multicanonical ; lyubartsev1992new ; marinari1992simulated ; wang2001determining ; mitsutake2010multi (for reviews see, e.g., Refs. henin2022enhanced ; earl2005parallel ), is employed due to its intuitive and straightforward approach. The method uses a Markov Chain Monte Carlo (MCMC) method to sample simultaneous probability distributions, which are a composite of multiple distributions with different parameter values. This study aims to efficiently find the optimal transition pathways between any two states by selecting the appropriate replica parameters in the replica exchange method. It is also interesting to overcome the difficulty of replica exchange near phase transitions and to improve the technique’s reproducibility and overall computational efficiency. A specific example of its use is in predicting the first-order solid-liquid phase transition of the 12-6 Lennard–Jones system. The Lennard–Jones fluid is widely used as a fundamental force field in molecular simulation and is used as the basis of a large number of atomic pair-potentials. Still, studies on its phase diagram have been carried out even in recent years (for reviews see, e.g., Ref. schwerdtfeger2024100 ), as it can reproduce universal solid-liquid behavior, despite its simple mathematical formulae. The use of the replica exchange method is challenging near phase transitions where the specific heat diverges, as the exchange probability is determined by the distance between, and the width of, the two replica’s probability distributions and their degree of overlap. If the parameters are not selected appropriately, localized areas with frequent exchanges and areas with little or no exchanges may occur, making it hard to draw out the benefits of this method. How to set the parameters used in the replica exchange method is still an area of active debate, with various considerations being made in terms of the frequency of exchanges, parameter intervals, and the number of replicas kofke2002acceptance ; kofke2004comment ; kofke2004erratum ; rathore2005optimal ; kone2005selection ; schug2004all ; katzgraber2006feedback ; yan2000hyperparallel ; sugita2000multidimensional ; ogita2025atomistic . Equispaced replica arrangements were found to be inappropriate when applied to the strongly first-order nematic-solid phase transition region of some liquid crystal systems, which exhibit strongly first-order phase transitions in which the specific heat diverges in the \beta=1/k_{B}T axis kowaguchi2021phase . To address this issue, we developed a method that incorporates an evolutionary strategy for a fixed number of replicas and a parameter range such that the exchange probabilities all maintain a preset minimum value for any range kowaguchi2022optimal . As a result, by applying an evolution strategy rechenberg1965cybernetic ; schwefel1965kybernetische to the Hamiltonian replica exchange method sugita1999replica , exchange attempts with divergent specific heats in the \beta axis could be avoided by tuning the replica spacing in the anisotropic term direction. Thus, the hysteresis phenomenon of the coarse-grained Hess-Su liquid crystal model hess1999pressure ; steuer2003pressure ; steuer2004phase was eliminated, and accurate phase transition points were obtained, irrespective of the initial conditions used kowaguchi2024hysteresis . In this study, we extend this method, by removing the constraint that the number of replicas is predetermined and develop a process to find the number of replicas between which all exchanges can occur with a particular exchange probability or higher for an arbitrary parameter range. Traditionally, replica exchange in two dimensions is generally performed on a square grid, but there are alternative approaches to improve the exchange efficiency through distortion of the square grid near phase transitions, as in the work of Kimura et al. kimura2016extension . Here, however, we implement the so-called king’s grid, wherein the diagonal direction is added and we explore the question of whether a square grid is the more favorable exchange geometry for the replica exchange method. Next, after examining the impact of the grid configuration on the replica’s random walk, the aim is to find the path on a graph where the replicas are treated as nodes and the exchange probability is considered as the distance (i.e., the weight of the edges), such that the number of edges is minimized. In addition to the motivation of finding the optimal spacing for the exchange axis in two dimensions, our goal is to identify a path that connects both the solid and liquid phases of the Lennard–Jones potential with high exchange probabilities, thereby enabling exploration between different phases with relatively fast relaxation times. Somewhat surprisingly, there is great potential to apply methods and techniques from graph theory and computer science, which have been extensively used for solving path-finding problems in computer games, to find optimal routes across free energy landscapes in molecular simulations. There has been extensive research on search algorithms for game development in computer science. The simplest examples are the depth-first tarjan1972depth and the breadth-first search methods bundy1984breadth , which perform the entire search from the starting node to the goal. However, neither of these considers edge weights, which are useful when applied to maze problems. Thus, the Dijkstra method dijkstra2022note was developed, which is more appropriate for the shortest path problem in weighted graphs. The aim is to find the path with the minimum total edge weight in a graph with fixed starting and ending points. By considering replicas as nodes and exchange probabilities as distances, i.e., weights of edges, replica selection becomes intuitive and paths can be mathematically determined in a rigorous manner. In a further development, the A* algorithm hart1968formal introduces a heuristic function to preferentially search for the route closest to the goal while predicting possible routes. However, this latter method will not be

Read the complete text