Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 539-556 |
Number of pages | 18 |
Journal | International Journal of Modern Physics C |
Volume | 20 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2009 |
Keywords
- Combinatorial optimization
- Parallel tempering
- Simulated annealing
- Traveling salesman problem
ASJC Scopus subject areas
- Statistical and Nonlinear Physics
- Mathematical Physics
- General Physics and Astronomy
- Computer Science Applications
- Computational Theory and Mathematics