Simulated Annealing in MATLAB

Simulated Annealing (SA) is a metaheuristic inspired by the annealing process (opens in a new tab). It starts with an initial solution at a high temperature, where changes are accepted with high probability. This gives the algorithm strong exploration ability, so it can search the space widely.

As the algorithm runs, the temperature decreases gradually, like in annealing, and the probability of accepting unsuccessful moves decreases with it. Simulated Annealing was proposed by Kirkpatrick, Gelatt and Vecchi in 1983 (paper (opens in a new tab)). For more information, see the Wikipedia article on Simulated Annealing (opens in a new tab).

How Simulated Annealing works

SA keeps one current solution $x$ with cost $f(x)$. In each step it creates a neighbor $x'$ by a small random change and compares the two costs:

• If the neighbor is not worse, $f(x') \le f(x)$, it always becomes the current solution.
• If the neighbor is worse, it is still accepted with a probability that depends on how much worse it is and on the temperature $T$.

This acceptance rule comes from the Metropolis algorithm (Metropolis and coauthors, 1953):

At a high temperature, even large increases in cost are often accepted, so the search can leave a local minimum. At a low temperature, only small increases have a real chance, and the search behaves almost like a local descent. The best solution found so far is stored separately, so accepting a worse move never loses it.

The temperature follows a cooling schedule. A common choice, used in this code, is geometric cooling:

At each temperature, the algorithm tries several neighbors before it cools down again. In the code, these are the sub-iterations.

What this post shares

This post shares an open-source MATLAB implementation of Simulated Annealing that solves the Traveling Salesman Problem (TSP). The download package also includes a Population-based Simulated Annealing, in addition to the standard version.

The algorithms are implemented in a structured way. If you know MATLAB programming, the code is easy to use in your research projects.

The problem

In the TSP, a salesman must visit $n$ cities once each and return to the start. A solution is a permutation of the cities, and the cost is the length of the closed tour. The sample model in CreateModel.m has 18 cities with fixed coordinates.

The two versions

• 01 TSP using SA (Standard). One current solution. In every sub-iteration, one neighbor is created and accepted or rejected with the rule above.
• 02 TSP using SA (Population-Based). A population of nPop solutions. Each one creates nMove neighbors. All the neighbors are sorted by cost, and the $i$th best neighbor is compared with the $i$th member of the population using the same acceptance rule.

In both versions, CreateNeighbor.m changes a tour with one of three moves, chosen at random: swap two cities (probability 0.2), reverse a part of the tour (0.5), or move one city to another position (0.3). The code measures the cost increase relative to the current cost, $\Delta = (f(x') - f(x))/f(x)$, which is why the initial temperature is small.

How to run it

Open one of the two folders in MATLAB and run main.m, which calls sa.m. The program prints the best tour length in every iteration, draws the best tour as it improves, and plots the best cost against the iteration at the end. To solve your own TSP, change the city coordinates in CreateModel.m.

Parameters in the code

The parameters are set at the top of sa.m:

Check the result

Recompute the closed-tour length from the returned city order and check that each city appears once. Compare repeated runs using the same city coordinates and evaluation budget. This implementation divides the cost difference by the current tour cost, which is positive for the supplied nondegenerate model. A new objective that can be zero or negative needs a reviewed acceptance rule rather than an unchanged copy of that calculation.

Applications

SA needs only a cost function and a way to create neighbors, so it is easy to apply to many combinatorial problems, such as routing, scheduling, assignment and circuit layout. It is also used for problems with continuous variables. Yarpiz has several posts that use SA:

• Real-Coded Simulated Annealing, for real-valued variables.
• Parallel Machine Scheduling using Simulated Annealing.
• Capacitated Vehicle Routing Problem using Simulated Annealing.
• Tabu Search in MATLAB, another local search method that also solves the TSP.

Mostapha Kalami Heris, Simulated Annealing in MATLAB (YPEA105), Yarpiz, 2015. https://yarpiz.com/simulated-annealing-ypea105

@misc{yarpiz-ypea105,
  author = {{Mostapha Kalami Heris}},
  title = {{Simulated Annealing in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA105},
  url = {https://yarpiz.com/simulated-annealing-ypea105}
}