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

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