Python Programming for Biology: Bioinformatics and Beyond

Simulated annealing of the travelling salesman

The first simulated annealing example in Python is the same as the travellingSalesman()

described above but with the introduction of the cool variable, which can act as a kind of

temperature.  We  will  use  an  exponential  cooling  decay  based  on  the  proportion  of  the

current  step  through  the  whole  run:  the  current  step  relative  to  the  total  (i/m).  The  only

three  differences  in  the  Python  function  are  the  introduction  of  m,  the  total  number  of

steps as a floating point number; cool,  the  current  effective  temperature  in  the  annealing

schedule; and a different score: this is now divided by cool before the exponent is taken.

The effect of this is that as the search proceeds cool diminishes exponentially from 1.0 to

almost 0.368 (e

−1

), and the difference in distances, as they affect the acceptance criterion,

is magnified. Thus the score will be closer to zero for the same distance difference in later

cycles.  Better  distances  will  still  always  be  accepted  at  any  stage,  but  it  will  be

increasingly  less  likely  for  other  scores  to  be  accepted.  Hence,  the  state  will  tend  not  to

jump out of a good solution towards the end, but initial exploration is unaffected.

def travellingSalesmanSimAnneal(distanceData, cities, numIter=10000):

n = len(cities)

bestRoute = cities[:]

shuffle(bestRoute)

dists = list(distanceData.values())

scale = 0.5 * array(dists).std()

bestDistance = getRouteLength(distanceData, bestRoute)

prevRoute = bestRoute

prevDistance = bestDistance

---

m = float(numIter) # Use to calculate cool

for i in range(numIter): # could use xrange in Python 2

cool = exp(-i/m) # annealing schedule 'temperature'

a = randint(0, n-1)

b = randint(0, n-1)

route = prevRoute[:]

route[a] = prevRoute[b]

route[b] = prevRoute[a]

distance = getRouteLength(distanceData, route)

score = exp( (prevDistance - distance) / (scale*cool) ) # Adjusted

score

if score > uniform():

prevRoute = route

prevDistance = distance

if distance < bestDistance:

bestRoute = route[:]

bestDistance = distance

print('%5d Dist:%.5f Temp:%.5f' % (i, distance, cool))

return bestDistance, bestRoute

The function may be tested in exactly the same manner as the non-annealing version.

distances = calcCityDistances(cityCoords)

cities = list(cityCoords.keys())

dist, route = travellingSalesmanSimAnneal(distances, cities, 1000000)

print('%.3f %s' % (dist, '-'.join(route)))

With the appropriate number of search steps this will generally give the same result as

the  previous  function  travellingSalesman(),  although  the  last  tested  route  will  usually  be

much closer to the best route than for the non-annealing version. Testing different numbers

of cycles will show that if the number of search steps is too small the annealing will ‘cool’

before a reasonable number of states have been sampled and the final result will not be the

best. Accordingly, it is critical to give the algorithm enough steps if the absolute optimum

is required. However, an advantage of simulated annealing compared to plain Monte Carlo

is  its  speed,  so  if  all  you  want  is  a  reasonably  good  solution  in  a  reasonable  time  extra

steps may not be needed.