Heuristics: Simulated Annealing 2: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(→Problem: Application of the Method) |
(→Problem: Application of the Method) |
||
| Zeile 21: | Zeile 21: | ||
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: | 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: | ||
| + | |||
A temperature function C(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]: | A temperature function C(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]: | ||
| Zeile 29: | Zeile 30: | ||
# 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 <math>p = e^{-\Delta E/T} > r</math>, Sn is the new best solution St+1. Otherwise St stays best solution and is named St+1 | # 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 <math>p = e^{-\Delta E/T} > r</math>, Sn is the new best solution St+1. Otherwise St stays best solution and is named St+1 | ||
# T is reduced as described in the temperature function. A check is performed to determine whether the stopping criterion is reached. | # 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. | 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. | ||
Version vom 27. Juni 2013, 20:24 Uhr
Inhaltsverzeichnis
Theory: Fundamental Principles
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 a 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]:
- A defined state space
- A function which randomly generates various states
- An „energy function“, also known as cost function, which is supposed to be minimized
- A control parameter, e.g. temperature, and a function that describes the change of this parameter over time
- 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:
A temperature function C(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)
- A random neighbour (here: another possible circuit) of St is chosen and named Sn with value E(Sn)
- If Sn has a lower value than St, Sn will be our new best solution St+1.
- 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
- 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. He decides to use simulated annealing to find the best possible solution for his temperature function C(T)=T-25 with a starting temperature TS = 100 and a stopping criterion TE = 0.
T=100
Generate a random initial circuit S0: 998 km
Generate a neighbour circuit Sn: 972 km
New best solution S1 := Sn
C(T) = 100 – 25 = 75 > 0
T=75
Generate a neighbour circuit Sn: 1001 km
r = 0,7241
p = e^-((1001-972)/75) = 0,6793 < r
Keep previous solution S2 := S1
C(T) = 75 – 25 = 50 > 0
T=50
Generate a neighbour circuit Sn: 821 km
New best solution S3 := Sn
C(T) = 50 - 25 = 25 > 0
T=25
Generate a neighbour circuit Sn: 832 km
r = 0,5492
p= e^-((836-821)/25) = 0,5488 > r
New solution S4 := Sn
C(T) = 25 – 25 = 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-Verlag, 2010
