# Implementing Simulated Annealing to the Travelling Salesman Problem ; plotting a graph of temperature(x axis) and cost on y axis ; animating using cv2

import numpy as np
import cv2
import matplotlib.pyplot as plt

class animated_simulated_tsp :
"""
Implements Simulated Annealing to solve
the Travelling Salesman Problem \n
Animates the tour as the algorithm progress
"""
def __init__( self, height = 800 , width = 800 , num_cities = 20 , alpha = 0.99 , tmax = 8000 , tmin = 1 , iters = 1000 , cooling = 'geometric') :
self.height = height
self.width = width
self.num = num_cities
self.alpha = alpha
self.iters = iters
self.cooling = cooling
self.tmax = tmax
self.tmin = tmin
self.__cities = [(np.random.randint(150,self.width-50),np.random.randint(150,self.height-50)) for _ in range(self.num)]
self.__dist_mat = np.asarray([ [(lambda a,b :( (a[0]-b[0])**2 + (a[1]-b[1])**2 )**0.5)(i,j) for j in self.__cities] for i in self.__cities])

def __generate_initial_tour(self):
"""
Generate an initial tour
"""
p = [i for i in range(1,self.num)]
np.random.shuffle(p)
return [0]+p+[0]

def __accept(self,delta,t):
"""
Decide whether to accept or reject a solution
"""
if delta < 0 : return True
else : return np.exp(-delta/t) > np.random.rand()

def __neighbor(self,tour):
"""
Generate a random neighbour of
a tour
"""
r = np.random.rand()
copy = tour.copy()
rs = np.random.randint(1, len(copy) - 1, 3)
rs.sort()
if r < 1/4:
r1, r2 = rs[0], rs[1]
copy[r1], copy[r2] = copy[r2], copy[r1]
return copy
elif r < 2/4:
r1, r2 = rs[0], rs[1]
modify = copy[r1:r2]
np.random.shuffle(modify)
copy = np.concatenate([copy[:r1], modify, copy[r2:]])
return copy
elif r < 3/4:
r1, r2 = rs[0], rs[1]
r1, r2 = int(r1), int(r2)  # Ensure integer indices
return np.concatenate([copy[:r1], copy[r1:r2][::-1], copy[r2:]])
else :
r1, r2, r3 = rs[0], rs[1], rs[2]
r1, r2, r3 = int(r1), int(r2), int(r3)  # Ensure integer indices
return np.concatenate([copy[:r1], copy[r2+1:r3+1], copy[r1:r2+1], copy[r3+1:]])

def __draw(self,solution,infos):
"""
Drawing the tour
"""
cities = self.__cities
height,width = self.height,self.width
frame = np.zeros((width,height,4))
for i in range(len(solution)-1):
point0 = cities[int(solution[int(i)])]
point1 = cities[int(solution[int(i)+1])]
cv2.line(frame,point0,point1,(0,255,67),3)
cv2.circle(frame,cities[0],8,(56,0,254),-1)
for city in cities[1:] :
cv2.circle(frame,city,8,(0,0,255),-1)
cv2.putText(frame,"TEMPERATURE : {}".format(round(infos[0],3)),(25,50),cv2.FONT_HERSHEY_DUPLEX,0.7,(255,255,255))
cv2.putText(frame,"BEST : {}".format(round(infos[1],4)),(25,75),cv2.FONT_HERSHEY_DUPLEX,0.7,(255,255,255))
cv2.putText(frame,"CURRENT : {}".format(round(infos[2],4)),(25,100),cv2.FONT_HERSHEY_DUPLEX,0.7,(255,255,255))
cv2.imshow("Simulated Annealing TSP - {} cities ".format(len(cities)),frame)
cv2.waitKey(1)

def __cost(self,tour):
"""
Returns cost of the tour , including the last edge
"""
c = 0
for i in range(len(tour)-1):
c += self.__dist_mat[int(tour[int(i)]),int(tour[int(i+1)])]
return c

def main(self) :
"""
Implements simulated annealing
and draws current tour on each temperature
level
"""
t = self.tmax
current = self.__generate_initial_tour()
current_cost = self.__cost(current)
best = current
best_cost = self.__cost(best)
iter = 0
tour_vals = []
fits = []
temps = []
while t > self.tmin :
temps.append(t)
fits.append(current_cost)
for _ in range(self.iters) :

new = self.__neighbor(current)
new_cost = self.__cost(new)
delta = new_cost - current_cost
if self.__accept(delta,t) :
current = new
current_cost = new_cost
if self.__cost(new) < best_cost :
best = new
best_cost = new_cost
tour_vals.append(current_cost)

if len(tour_vals)>30:
if np.std(tour_vals[::-1][:30])<0.0005 : break

iter += 1
infos = ( t , best_cost , current_cost )
match self.cooling :
case 'geometric' : t *= self.alpha
case 'exponential' : t = self.tmax*self.alpha**iter
self.__draw(current , infos)
plt.plot(temps,fits)
plt.show()
while True:
key = cv2.waitKey(20)
if key == ord('q') : break

animated_simulated_tsp(num_cities=10,cooling='exponential',tmax=1000,tmin=1e-5,alpha=0.99).main()


My plot for 10 cities [1]: https://i.stack.imgur.com/NVLll.png

As seen in the plot , as the temperature decreases , so does the cost . But I'm unable to understand the reason for the cost , although reducing overall , to vary so drastically . Is there scope for improvement in my neighbor generating strategies ? Or are my parameters not tuned enough ?

• Is the code working as intended? We can only review code is working as intended. We can't explain what the code is doing, you are supposed to know that because you write the code. Please read How do I ask a good question?. Sep 22 at 12:54
• @pacmaninbw it is working as intended - the cost is converging as the temperature decreases , which is what i meant to do . my only question is why are there so many spikes in my plot. Maybe i shouldve asked this in a CS forum ? Sep 23 at 3:11