## A variation on the classic Simulated Annealing optimisation algorithm and its application to the Travelling Salesman Problem

In my previous article we discussed how to solve the ** Travelling Salesman Problem (TSP)** using the

**optimisation algorithm of**

*meta-heuristic***. You can check out that article here:**

*Simulated Annealing*The TSP is a famous ** combinatorial optimisation** and

**problem. Its objective is to find the shortest distance a salesman can travel through**

*operations research***cities by visiting each city once and ending in the original/starting city.**

*n*The problem sounds simple, however as we add more cities the number of possible routes is subject to a ** combinatorial explosion**. For example, with

**cities the number of possible routes is**

*4***,**

*3***cities it is**

*6***, however for**

*60***cities its a gigantic**

*20***In fact for**

*60,822,550,200,000,000!***cities it would take on the order of**

*20***years to try every route by**

*~2000***!**

*brute-force*The numberof possible solutions to the TSP scales as

(n-1)!/2wherenis the number of cities.

This is where ** heuristic** and meta-heuristic methods, like Simulated Annealing, come in to provide good-enough solutions in a reasonable amount of computation time.

In this article, we will review the process of Simulated Annealing and explain a slight variation to its original algorithm which can lead to an improvement in perforamance. We will then implement this variation to solve the TSP in Python.

## Overview

Simulated Annealing is a stochastic (random) ** global search** optimisation algorithm. It derives its name from the

**process in**

*Annealing***which alters the physical properties of a metal through the use of temperature.**

*Metallurgy*Simulated Annealing uses this idea of temperature to help it compute the probability of transitioning to a less optimal solution to greater ** explore** the state space to have a higher chance of reaching the

**. This is to avoid getting trapped in**

*global optimum***that**

*local optimums***algorithms such as**

*greedy***often do.**

*Nearest Neighbour*## Theory

The general mathematical framework for Simulated Annealing is:

Where:

This transition probability is derived from the

Boltzmann distributionfromthermodynamics.

Here ** x** is the current solution,

**is the new solution,**

*x’***is the difference in performance of the two solutions,**

*Δy***is the probability of transitioning to the new solution and**

*P(x → x’)***is the temperature of the process at that point in time.**

*T*If the new solution is better than the current solution, then we always transition to this new solution as the probability from the above formula is ** 1**. Furthermore, when the new solution is worse but the temperature is very high, we are very likely to transition to the new solution despite its worse performance. However, as the temperature decreases, we are less likely to transition to a worse new solution. Therefore, the process starts to converge and is

**the search space.**

*exploiting*The temperature is often cooled geometrically:

Where ** γ **is the calling factor with a range

**and**

*0 ≤ γ ≤ 1***is the iteration number.**

*t*Another frequent question is how to calculate the initial temperature? This is sophisticated subject and and a good research ** here** helps answer this question. In general, this mainly a trial and error process.

## Variation

Inspired from the authors of this research paper, we can slightly modify this original implementation to help explore the search space more widely. This is done by **resetting the temperature to the initial temperature every time we find a new best solution**. A process which can be described as ** restart. **This is essentially us carrying out several Simulated Annealing processes and choosing the best found solution.

## Modified Algorithm For TSP

Steps to implement the modified Simulated Annealing algorithm for the TSP:

- Get an initial solution, this is any valid route.
- Randomly select two cities and swap them to generate a new route.
- Use Simulated Annealing to compute the probability of whether we accept this new solution.
- Continue this process for a set number of iterations and cool the temperature on every iteration.
- If the new solution is the best solution we have seen so far, then reset the temperature to the initial temperature.
- Always log the best overall solution.

We will now implement this new modified version of Simulated Annealing to solve the TSP. Lets begin by generating some cities and plotting an initial solution:

Now lets build a Python class for the modified Simulated Annealing algorithm for the TSP:

I am not the best coder, so the following snippet of code is not the most optimal or best practice implementation!

Running the algorithm and logging the outputs:

From the above plots we see the temperature restarting frequently at the beginning of the process, but tailing off as the iterations increase. The best found route seems reasonable, however there is still some paths crossing over which may mean we have not found the global optimum. But thats the point of a meta-heuristic algorithm, the solution is meant to be *good-enough*!

In this article we have explained the modified version of the Simulated Annealing algorithm. In this version, we reset the temperature to the initial temperature every time we find a new best solution, a process named *restart*. This approach provided a good solution our simulated Travelling Salesman problem that we implemented in Python.

Full code used in this article is available at my GitHub here:

(All emojis designed byOpenMoji— the open-source emoji and icon project. License:CC BY-SA 4.0)