Heuristics: Simulated Annealing 2

Theory: Fundamental Principles

An example of an energy function with multiple local minima. It visualizes the principle of simulated annealing. While shallow holes require little energy to overcome, deep ones are likely to hinder the algorithm from proceeding to prevent it from leaving a probably optimal state.

The method of Simulated Annealing is a mathematical optimization model. It is inspired by the metallurgical process of annealing, where atoms that have not yet acquired a globally optimal state of energy are being moved further until they reach said state. While the movement itself actually requires an increase in temperatures, it ultimately leads to a cooldown. [1]

Simulated Annealing formulates an algorithm that simulates this process by systematically searching for the global optimum. The unique feature of this method is its ability to temporarily accept inferior solutions with a certain feasibility to ultimately reach the desired state. This resembles the increase in temperatures in metallurgical annealing. Given an infinitely running simulation the global optimum is always found. In common practice however a stopping criterion is required which might possibly only lead to a local optimum. [1]

The method is developed from the Metropolis algorithm. The following conditions must be fulfilled to apply the algorithm [1]:

1. A defined state space
2. A function which randomly generates various states
3. An „energy function“, also known as cost function, which is supposed to be minimized
4. A control parameter, e.g. temperature, and a function that describes the change of this parameter over time
5. A topological structure of the state space which defines the neighbour states

Example: Travelling Salesman Problem

A travelling salesman needs to travel all twenty cities in his territory to buy and sell his products. Depending on how he plans his roundtrip, the distance will vary greatly. Thus, he thinks about a way to minimize the total distance without leaving out any of the cities. He finally decides to use a heuristic - Simulated Annealing - to find the best possible solution.

Problem: Application of the Method

Imagine a function that possibly possesses various local optima. It will be called "Energy Function". The goal is to find the best solution, i.e. the global minimum for problem at hand. In the following, the necessary steps are presented [1, 2]:

A temperature function X(T) is initialized. The slower this function proceeds, the more iterations will be performed. As long as T has not reached its stopping criterion, the following loop is performed:

1. The current best solution (here: the shortest known path) of our energy function is defined as St with value E(St)
2. A random neighbour (here: another possible circuit) of St is chosen and named Sn with value E(Sn)
3. If Sn has a lower value than St, Sn will be our new best solution St+1.
4. Else a random number r ϵ [0, 1] is generated. ΔE is the difference between Sn and St (here: the difference in length between the two circuits). If Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): p = e^{-\Delta E/T} > r

, Sn is the new best solution St+1. Otherwise St stays best solution and is named St+1

1. T is reduced as described in the temperature function. A check is performed to determine whether the stopping criterion is reached.

The outcome of this method depends on how fast the temperature function is reaching its target temperature, namely the stopping criterion. As stated above, an infinite loop would definitely lead to an optimal solution.

Detailed Solution Process

A travelling salesman must find the shortest circuit to travel all twenty cities in his territory. Fortunately he has a function E(S) at hand that outputs the total length of a trip for a chosen combination S of cities. He decides to use Simulated Annealing to find the best possible solution for the temperature function X(T) = T - 25 with a starting temperature TS = 100 and a stopping criterion TE = 0.

T=100

Generate a random initial circuit S0: E(S0) = 998 km

Generate a neighbour circuit Sn: E(Sn) = 972 km

New best solution S1 := Sn

X(100) = 100 – 25 = 75 > 0

T=75

Continue search with circuit S1: E(S1) = 972 km

Generate a neighbour circuit Sn: E(Sn) = 1001 km

r = 0,7241

p = Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): e^{-((1001-972)/75)}

= 0,6793 < r

Keep previous solution S2 := S1

T := X(75) = 75 – 25 = 50 > 0

T=50

Continue search with circuit S2: E(S2) = 972 km

Generate a neighbour circuit Sn: E(Sn) = 821 km

New best solution S3 := Sn

T := X(50) = 50 - 25 = 25 > 0

T=25

Continue search with circuit S3: E(S3) = 821 km

Generate a neighbour circuit Sn: E(Sn) = 832 km

r = 0,5492

p = Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): e^{-((836-821)/25)}

= 0,5488 > r

New solution S4 := Sn

T := X(25) = 25 – 25 = 0

T=0

The cooldown is complete, meaning that the stopping criterion is reached. The method outputs a solution of 832 km. Looking at step three (821 km), it is obvious that four iterations were not sufficient to reach an optimal solution. So it can be concluded that - depending on the complexity of a problem – an appropriate temperature function must be chosen.

Sources

[1] Schmidt, Jörn et al.: Programmierung naturanaloger Verfahren. Springer, 2010

[2] Eglese, R.W. (1990). "Simulated Annealing: A tool for Operational Research". European Journal of Operational Research 46: 271-281