Heuristics2:
Simulated Annealing
Simulated Annealing is a probabilistic algorithm used to find an approximate solution to a global optimization problem. It is inspired by the controlled cooling of metals to reduce defects, known as annealing. Simulated annealing starts with a random initial solution and a very high initial "temperature" parameter. Each iteration generates a random neighbouring solution. If this solution is better it replaces the current solution. If it is worse then it may replace the current solution with a probability that depends on the temperature parameter; higher temperatures give a higher probability. As the algorithm progresses, the temperature parameter decreases, giving worse solutions a smaller chance of replacing the current solution. Allowing worse solutions at the beginning avoids converging to a local minimum rather than the global minimum. The algorithm explores the solution space widely at the beginning, but gradually homes in on a local solution as the temperature decreases.
We will use simulated annealing to solve a fully connected travelling salesman problem The table below displays the distances between each city that the salesman must visit. The salesman must visit each city only once and return to the starting city (this is called a tour). A tour is represented by an ordering of the cities. The goal is to find the shortest possible tour. A neighbouring solution is generated by randomly swapping the position of two cities in the tour.
The parameters that control the algorithm are:
the initial temperature,
the rate at which the temperature decreases (r),
the stopping condition of the algorithm (final temperature).
You can adjust these parameters to see how the algorithm responds. Enter the desired values of the control parameters and press the Start button. The resulting solution trajectory is graphed. The blue curve plots the length of the current tour at every 200th iteration of the algorithm. The green curve plots the length of the shortest tour found to that point. To return to this page, press the back button on the browser. To re-run the algorithm with the same parameters, refresh the page.
The best possible solution for this problem is a tour length of 17.