Question

Write code on python for Exponential Cooling Schedule Techniques of the SA algorithm to find the shortest tour to visit all the cities according to TSP??

Answer 1

The travelling salesman problem (also called the traveling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

Python code:

1 import random, numpy, math, copy, matplotlib.pyplot as plt

2 cities = [random.sample(range(100), 2) for x in range(15)];

3 tour = random.sample(range(15),15);

4 for temperature in numpy.logspace(0,5,num=100000)[::-1]:

5 [i,j] = sorted(random.sample(range(15),2));

6 newTour = tour[:i] + tour[j:j+1] + tour[i+1:j] + tour[i:i+1] + tour[j+1:];

7 if math.exp( ( sum([ math.sqrt(sum([(cities[tour[(k+1) % 15]][d] - cities[tour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]]) - sum([math.sqrt(sum([(cities[newTour[(k+1) % 15]][d] - cities[newTour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]])) / temperature) > random.random():

8 tour = copy.copy(newTour);

9 plt.plot([cities[tour[i % 15]][0] for i in range(16)], [cities[tour[i % 15]][1] for i in range(16)], 'xb-');

10 plt.show()

A line by line explanation of code:

1 import random, numpy, math, copy, matplotlib.pyplot as plt

This first line is just Python imports to use different commands.

2 cities = [random.sample(range(100), 2) for x in range(15)];

The goal here is to make an list of “cities”, each which are simply a list of two coordinates, chosen as random integers from 0 to 100. I think a better practice usually would to make a constant for the grid size and the number of cities, and use that throughout the script. But with the 10 line requirement, all that will have to be hardcoded.

To explain the command itself, starting from the innermost command, range(100) returns the list [0,1,2,...,100]. Then random.sample( ,2) randomly chooses a set of size 2 from the list. This in fact makes it so that for each city, it’s first and second coordinates will never be the same. Since we just want to come up with some cities for the algorithm to run on, this doesn’t really matter; we could’ve hardcoded a list of cities here instead. This last piece thus repeats the random sampling 15 times and forms a list of these pairs of coordinates, which I called cities.

3 tour = random.sample(range(15),15);

A “tour” will just be a list of 15 numbers indicating an order to visit the cities. We’ll assume you need a closed loop, so the last city will be automatically connected to the first. Here we just choose a random order to start off with. Python also has a random.shuffle() command, but then we would need two lines: one to create a list, and another to shuffle it. By asking for a random sample of 15 numbers from a list of 15 elements, we get a shuffled list created for us in one line.

one line.

4 for temperature in numpy.logspace(0,5,num=100000)[::-1]:

We start off a for-loop.

while (temp > 1):
    ...
    temp *= 1 - coolingRate

The command numpy.logspace(0,5,num=100000) gives a list of 100,000 numbers between 10^0100 and 10^5105 so that the (base 10) logarithm of these numbers is evenly spaced. So choosing numbers in this alone should recover exponentially distributed temperatures. However, they are in lowest-first order. Since we want the temperature to start high, I added [::-1] which reverses the list.

5 [i,j] = sorted(random.sample(range(15),2));
6 newTour =  tour[:i] + tour[j:j+1] +  tour[i+1:j] + tour[i:i+1] + tour[j+1:];

I’ll group these two lines because together they do a single task which I had hoped to do in one line. The objective here is to make a new tour by randomly swapping two cities in tour. I do this by choosing two numbers i,j from the 15 possible cities via random.sample( ,2) as before (now glad that the two numbers will be distinct), and then order them via sorted( ). Then I piece together the new tour manually, by copying the old tour until (but not including) index i, concatenating the jth city from the old tour, continuing copying the old tour until index j where we swap in the ith city, and finish with the rest of the old tour. These two lines bugged me alot, because it seemed like an inelegant way swap two elements of the list, and because it needed two lines. Looking back now though, I don’t really mind it. Seems like the simple way to go.

7 if math.exp( ( sum([ math.sqrt(sum([(cities[tour[(k+1) % 15]][d] - cities[tour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]]) - sum([ math.sqrt(sum([(cities[newTour[(k+1) % 15]][d] - cities[newTour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]])) / temperature) > random.random():
8   tour = copy.copy(newTour);

This one is terribly long, but only because I skipped using variables to save a few lines. If we define

oldDistances =  sum([ math.sqrt(sum([(cities[tour[(k+1) % 15]][d] - cities[tour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]]
newDistances =  sum([ math.sqrt(sum([(cities[newTour[(k+1) % 15]][d] - cities[newTour[k % 15]][d])**2 for d in [0,1] ])) for k in [j,j-1,i,i-1]]))

then the code becomes a lot cleaner:

7 if math.exp( ( oldDistances - newDistances) / temperature) > random.random():
8   tour = copy.copy(newTour);

which is a little easier to understand. First, if we accept the condition on the if statement, we will update our old tour to this new tour.

Actually finish the algorithm here. We choose to update our tour or not as described above, lower the temperature, randomly swap two cities, and try again until we run out of temperatures (here, I put 100,000 of them). At the end, whatever is in the variable tour is our best guess as to the optimal route. I have no idea how to figure out analytically any type of convergence result or confidence in this output. This is partly why we have the next two lines.

next two lines.

9  plt.plot([cities[tour[i % 15]][0] for i in range(16)], [cities[tour[i % 15]][1] for i in range(16)], 'xb-');
10 plt.show()

In these two lines, the Python module matplotlib plots the cities and connects them according to our best guess tour. I’m pretty impressed that it’s a two line problem! The pictures are nice, and for a small number of cities, fairly convincing to the eye that it’s at least a pretty good route. That is, the algorithm did something! Considering that we used 10^5105 loop iterations and a brute force solution of searching over all possible 15! \sim 10^{12}15!∼1012 tours would take much longer (though would be guaranteed to be optimal), I’m happy with the result. As for the code itself, we just have to get everything in order. First, the list comprehension

[cities[tour[i % 15]] for i in range(16) ]

writes out the cities in order according to the tour, and includes the first one again at the end (using that % in Python is modulo). Then we select for the first or second coordinate by adding a [0] or [1] index:

[cities[tour[i % 15]][0] for i in range(16) ]

The string 'xb-' tells matplotpy to draw x’s on the points, and connect them with blue lines. Lastly, the command plt.plot( ) generates this plot, and plt.show() displays it.

A few sample outputs:

​​​