Solve the Traveling Salesman Problem (TSP) by Simulated Annealing (SA)

1.     Objective

The objective of this work is developing a generic simulated annealing (SA) algorithm to solve the traveling salesman problem (TSP), which is find the shortest route through N given cities such that every city is visited exactly once.

2.     Concepts and Programming

Simulated annealing algorithm, first described by Scott Kirkpatric [2], has its name and inspiration come from annealing in metallurgy, a technique involving heating and slowly cooling of a material to increase physical strength and/or reduce defects. When the temperature is hot, the atoms of the material piece gain high energy and wander randomly. The slow cooling gives them more chances of finding configurations with lower internal energy than the initial one [3]. In term of an optimization algorithm, each step of the SA algorithm replaces the current solution by a random "neighbor" solution, chosen with a probability that depends both on the difference between the corresponding function values (energy) and also on a global parameter T (called the temperature). The temperature is gradually decreased during the process. At the beginning,  T is large, the "upnhill" moves (go to higher energy states) are more likely accepted than when T is go to zero at the end of the process. This allows the SA algorithm move out of the local minimum at the early states.

Table 1: Pseudo code of SA algorithm [2]

s ← s0;                       // Initial state, energy. e ← E(s)                 sbest ← s;        // "best" solution ebest ← e  k ← 0 while k < kmax and e > emax          // Trail move to ‘ neighbor’           snew ← neighbor(s)             enew ← E(snew)      // Accept uphill move if ‘feel lucky’       if P(e, enew, temp(k/kmax)) > random() then             s ← snew;           e ← enew;      end      // Tracking the best-ever          if enew < ebest then                     sbest ← snew;            ebest ← enew                   end      k ← k + 1                                     return sbest

There are different schemes to accept the “uphill” move as well as to reduce the temperature, such as Fast Cauchy, Geometric, or Boltzmann’s methods as given in [1]- lecture 3, page 5.The pseudo code for generic SA algorithm is given in [2] as Table 1.

Actually, the "pure" SA algorithm as described in [1] does not keep track of the best solution found so far: it does not use the variables sbest and ebest, it lacks the second if inside the loop, and, at the end, it returns the current state s instead of sbest. While remembering the best state is a standard technique in optimization that can be used in any meta-heuristic, it does not have an analogy with physical annealing — since a physical system can "store" a single state only.

In TSP problem:

- Each state “s” is represented by a combinatory of N cities’ indexes.

- The energy E(s) is a function to compute the total travel distance of visiting N cities following the route or the state s.

- The initial sate or route s is selected randomly.

- The “neighbor” of s is implemented by swapping 2 random cities of the route s. There are 2 ways to swap: swap the two vertices or swap the two edges as described in [1]-lecture 3, page 17, and are both implemented in my code (See Code listing section)

- The probability to accept a move is P = exp(- DE/kT) = exp(-(enew-e)/kT)

- Update temperature T = αT, where 0<α<1

3.     Some Results

SA process

The convergence of SA

GUI (Graphic User Interface) written in Matlab

Aravind Seshadri already posted his code for solving TSP by SA in Mathworks website

http://www.mathworks.com/matlabcentral/fileexchange/9612-traveling-salesman-problem-tsp-using-simulated-annealing . So what the difference?

Main thing is the speed. I am inspired by his work, but after downloaded, I found that his program could take "forever" for 101 cities. Could not sit and wait, (not a patient person) so I wrote this program. Most of the time, it just needs less than 10 seconds for 101 cities (including time for plot). For 500 cities, it may take 1 minutes. 

Next time, I will upload the code and talk about using SA for solving N-Queens problem.    

References

1.      Gary Yen. ECEN 5773 Intelligent Systems- Fall 2011 lecture notes. Oklahoma State University, 2011

2.      Kirkpatrick, S., C. D. Gelatt Jr., M. P. Vecchi, "Optimization by Simulated Annealing",Science, 220, 4598, 671-680, 1983. 

3.      http://en.wikipedia.org/wiki/Simulated_annealing

4.      http://en.wikipedia.org/wiki/Traveling_salesman_problem

5.      TSP Database http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

6. TSP formation and database http://www.tsp.gatech.edu/