1
\$\begingroup\$
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 ?

\$\endgroup\$
2
  • \$\begingroup\$ 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?. \$\endgroup\$
    – pacmaninbw
    Sep 22 at 12:54
  • \$\begingroup\$ @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 ? \$\endgroup\$ Sep 23 at 3:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.