What is the Travelling Salesman Problem?
The
travelling salesman problem states that: Given $n$ cities, what is the shortest path that visits each city exactly once and returns to the origin city? The TSP is one of the
NP-hard problems. No polynomial time algorithms exist to solve this problem. The direct solution will be to try all possible permutations aka the brute force search and return the least costly path. There are $n!$ permutations for a n-city problem which means the running time is of the order of $O(n!)$. To solve a simple 20 city problem you'll have to check $2432902008176640000$ possible routes in worst case scenario.
Why is it important
The TSP has applications in areas such as planning, logistics and manufacture of microchips. For example, if a robotic hand has to solder n connections, what is the best route it should follow such that it minimizes time and energy consumed. It also appears as a sub-problem in DNA sequencing.
What is Simulated Annealing
We don't always require the best solution for this problem. To solve the TSP we use what are called heuristics which give us a "good enough" which may or may not be the optimal solution. Some of these heuristics are genetic algorithms, hill climbing, ant colony optimization etc. Simulated Annealing is one such heuristic. Annealing is the process of heating metals above their recrystallization temperature and then cooling them. The molten metals cool down slowly and crystallize in a low energy state.
Hill Climbing vs. Simulated Annealing
A hill climbing heuristic begins which a random route and slightly mutates it to get a neighbor solution. If the neighbor solution is better than the current solution, the neighbor solution becomes the current solution and the process proceeds as such. There's however a problem with the hill climbing approach that it easily gets stuck in a local optimum and misses the global best.
Simulated Annealing solves this problem by sometimes choosing a bad neighbor to jump all over the search space. This gives it a better chance to find the global maximum and prevents it from getting stuck in a locally best solution.
The steps of simulated annealing are as follows:
- Generate a random solution.
- Calculate the cost of this solution i.e. the length of the route in case of TSP.
- Mutate this solution to generate a neighboring solution i.e. a solution which differs slightly from the current solution.
- Calculate the cost of neighboring solution.
- Compare the two costs.
- if costnew < costold: move to the new solution
- if costnew > costold: maybe move to the new solution
The last step is the most important which prevents the solution from getting stuck in a local optimum. Simulated annealing uses something called "temperature" to simulate the temperature as in case of metals. When the cost
new > cost
old we move to the new solution which a certain acceptance probability which is given by:
$$probability = e^{\frac{cost_{old} - cost_{new}}{T}}$$
where $T$ is the temperature.
Initially, when the temperature is high the bad neighbor is chosen with a greater probability which decreases as the temperature cools down. The rate at which the temperature cools down is $\alpha$ which ranges between $0.8$ to $1.0$ (exclusive).
2-opt algorithm
Even after using simulated annealing the search gets stuck with routes which cross over themselves. To solve this problem the
2-opt local search algorithm is used which reorders a route such that it does not over cross itself. The 2-opt swap reverses the order of cities between $i$ and $j$ (chosen randomly) so that the number of crosses can be reduced.
Source Code
The javascript source code is released under MIT License and is available on
GitHub. Feel free to fork the repository and submit a pull request.
Demo
A basic javascript demo of the above mentioned method can be found
here.
Credits & Further Reading