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 meta-heuristic optimisation algorithm of Simulated Annealing. You can check out that article here:
The TSP is a famous combinatorial optimisation and operations research problem. Its objective is to find the shortest distance a salesman can travel through n cities by visiting each city once and ending in the original/starting city.
The problem sounds simple, however as we add more cities the number of possible routes is subject to a combinatorial explosion. For example, with 4 cities the number of possible routes is 3, 6 cities it is 60, however for 20 cities its a gigantic 60,822,550,200,000,000! In fact for 20 cities it would take on the order of ~2000 years to try every route by brute-force!
The numberof possible solutions to the TSP scales as (n-1)!/2 where n is 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 Annealing process in Metallurgy which alters the physical properties of a metal through the use of temperature.
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 global optimum. This is to avoid getting trapped in local optimums that greedy algorithms such as Nearest Neighbour often do.
Theory
The general mathematical framework for Simulated Annealing is:
Where:
This transition probability is derived from the Boltzmann distribution from thermodynamics.
Here x is the current solution, x’ is the new solution, Δy is the difference in performance of the two solutions, P(x → x’) is the probability of transitioning to the new solution and T is the temperature of the process at that point in time.
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 exploiting the search space.
The temperature is often cooled geometrically:
Where γ is the calling factor with a range 0 ≤ γ ≤ 1 and t is the iteration number.
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 by OpenMoji — the open-source emoji and icon project. License: CC BY-SA 4.0)
