Real-Coded Simulated Annealing (SA) in MATLAB

This package is an implementation of Real-Coded Simulated Annealing (SA) in MATLAB. It searches for the minimum of a cost function with real-valued decision variables.

Simulated Annealing was proposed by Kirkpatrick, Gelatt and Vecchi in 1983. The Simulated Annealing post explains the method and applies it to the Traveling Salesman Problem. This package uses the same idea for continuous problems: the neighbors are created by small random changes of the real-valued variables.

The acceptance rule

A neighbor that is not worse than the current solution is always accepted. A worse neighbor is accepted with the probability

where $f$ is the cost function, $x$ is the current solution, $x'$ is the neighbor and $T$ is the temperature. The code measures $\Delta$ relative to the current cost. A high temperature lets the search accept worse solutions and leave local minima. As $T$ falls, the search accepts fewer worse moves and settles near a good solution. The best solution found so far is always kept.

After each iteration, the temperature is reduced with $T \leftarrow \alpha T$, and the mutation step size is reduced with $\sigma \leftarrow 0.98\,\sigma$.

What is in the download

• sa.m: the algorithm. It keeps a population of solutions and creates several neighbors for each one. A worse neighbor is accepted with a probability that depends on the current temperature. The temperature and the mutation step size are reduced at every iteration.
• Mutate.m: creates a neighbor by adding Gaussian noise to some of the variables, then clips the result to the variable bounds.
• Sphere.m: the example cost function.
• main.m: runs sa.m. The script shows the best cost at each iteration and plots the best cost curve at the end.

The main parameters (MaxIt, MaxSubIt, T0, alpha, nPop, nMove, mu and sigma) are set at the top of sa.m.

Parameters in the code

In every sub-iteration, all the neighbors of the population are sorted by cost, and the $i$th best neighbor is compared with the $i$th member of the population.

To run the code, open the folder in MATLAB and run main.m. The best cost curve is plotted on a logarithmic scale. To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar, VarMin and VarMax at the top of sa.m. The script creates the first population with unifrnd, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Check the result

For the Sphere example, inspect the distance to the origin, the cost, and the variable bounds together. The relative acceptance calculation divides by the current cost, so an exact zero cost needs explicit handling before adapting this code. Objectives that can be negative also need a reviewed acceptance rule. Repeat runs when comparing temperatures or mutation settings, and compare function evaluations as well as iterations.

Mostapha Kalami Heris, Real-Coded Simulated Annealing (SA) in MATLAB (YPEA106), Yarpiz, 2015. https://yarpiz.com/real-coded-simulated-annealing-ypea106

@misc{yarpiz-ypea106,
  author = {{Mostapha Kalami Heris}},
  title = {{Real-Coded Simulated Annealing (SA) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA106},
  url = {https://yarpiz.com/real-coded-simulated-annealing-ypea106}
}