SIMULATED ANNEALING FOR TRAVELING SALESMAN
PROBLEM
ARAVIND SESHADRI
1. Traveling Salesman Problem
Traveling Salesman Problem (TSP) has been an interes ting problem for a long
time in classical optimization techniques which are based on linea r and no nlinear
programming. TSP can be described as follows: Given a number of cities to visit
and their distances from all other cities know, an optimal travel route has to be
found so that each city is visited one and only once with the least possible distance
traveled. This is a simple problem with handful of cities but be c omes c omplicated
as the number increases.
2. Simulated Annealing
There are several well know classical methods for finding a near optimal solution
using linear and nonlinear programming for TSP’s. Simulated Annealing is not
based on any of the classical optimization techniques but is based on heuristics
from annealing process. Based on the motivation from how crystalline structures are
formed from annealing proc e ss, a heuristic method called simulated annealing was
developed and had a lot of interesting results. I have not put the effort to explain
everything in detail about simulated annea ling but a quick google on simulated
annealing would ge t you started.
To make the long story short, simulated annealing is similar to hill climbing or
gradient search with a few modifications. In gradient based search the search direc-
tion is dependent on gradient and hence the function to be optimized should be a
continuous function without dis c ontinuities. Simulated Annealing does not r e quire
the function to be smooth and co ntinuous since it is not based on gradient of the
function. Consider a minimization problem with a lot of local optima. During
the initial search phase (when temperature is high) loca l search
1
is carried out and
routes which minimize the total distance are always acc epted. To escape the prob-
lem of getting stuck in a local minima occa sionally routes with distance more than
the curr ent route is also accepted but with a proba bility similar to the probability
in the dynamics of the annealing process. As the temperature decr e ases, this prob-
ability of accepting a bad solution is decreas e d and in the final stages it becomes
similar to gradient based search. This idea is blend between a co mpletely random
search and a gradient based search with some heuristics based on the annealing
process.
1
Search meaning random routes are made and their corresponding distances calculated.
1
评论0