This Python program solves the traveling salesman problem using simulated annealing with the Metropolis Monte Carlo algorithm. The problem has many local minima, so to make sure we find a global minimum, we want so sample the space widely while staying within reasonable computational time. The concept of a ``temperature'' is useful, since it allows us to control the probability of a transition is between minima. The simulated annealing is done by controlling the temperature profile. We want to go from a high temperature to a low temperature to first do rough sampling for the global minimum and then narrow down to a single point. When temperature is high, the MMC algorithm accepts states almost randomly. When temperature is low, the MMC algorithm only accepts states below the current one.
Paths of the salesman are states of the system, and the the length of the path is equivalent to energy of the system. The ``energy minimum'' of the system is the shortest path. Since we have an ergodic system, we can start from a random path. We can reach a path from any other path by swapping two path elements. We can represent the path between points (e.g. in a 2D plane) using their indices
We accept the trial state
The program takes a file containing the
The simulated annealing starts from a temperature
All simulations can be run using:
./run.sh
Usage:
./annealed_salesman.py [input.dat] [T0] [nsteps] [show]
input.dat
= input file of location coordinates with names
T0
= starting temperature for simulated annealing
nsteps
= number of MC steps
show
= if 0, don't show plots
The awk script random.sh
can be used to generate randomized