Simulated Annealing
Annealing
It is a heat treatment process.
It changes materials' physical and chemical properties.
It makes materials more workable by reducing the hardness, increasing the ductability of various steels, cast irons and alloys.
It involves:
-
Heating a material above re-crystallization temperature to attain a high energy state
-
Holding it there for a set amount of time
-
Cooling it steadily to attain a minimal energy final state.
The process of energy reduction is called valley descending, in which the objective function provides the energy level.
Physical substances usually move from high energy configuration to lower ones so valley descending occurs naturally.
@TODO: Insert valley descending diagram
Procedure
If \(\Delta E\) is less than zero (that is, the move is downhill), it is accepted and \(s_\text{current}\) is set to \(s_\text{new}\). Otherwise, the state is accepted based on some probability.
The probability that a transition to a higher energy state occurs (that is, probability of an uphill move):
where:
-
\(T \rightarrow \) temperature
-
\(k \rightarrow \) Boltzmann constant
@TODO: add diagram showing s_current and possible s_new's
The probability of a large uphill move is lower than the probability of a small one.
The probability than an uphill move will be made decreases as the temperature decreases.
The rate at which the system is cooled is called annealing schedule.
Algorithm
Steps
-
\(s_\text{current} = s_0\) [arbitrarily chosen initial solution]
-
best_solution\(= s_\text{current}\) -
while stopping criterion not reached {
-
while required number of states not generated {
-
Generate a neighbouring solution \(s_\text{new}\) from \(s_\text{current}\)
-
\(\Delta E = E(s_\text{new}) - E(s_\text{current}) \)
-
if \(\Delta E \geq 0\) { \(s_\text{current} = s_\text{new}\) }
-
else {
-
Generate a uniform random number \( R \in [0, 1] \)
-
\( P = e^{-\frac{\Delta E}{T}} \) [probability of accepting]
-
if \( R < P \) { \( s_\text{current} = s_\text{new} \) }
-
}
-
if \( E(s_\text{current}) \lt E(\)
best_solution\()\) {best_solution\(=\) \(s_\text{current}\) } -
}
-
Update \( T \)
-
}
-
stop
Parameters
The set of parameters for simulated annealing is: \(\{T_0, \alpha, T_\text{final}, n(T)\}\)
where:
-
\(T_0 \rightarrow\) initial temperature
-
\(\alpha \) temperature reduction factor
-
\(T_\text{final} \rightarrow\) final temperature
-
\(n(T) \rightarrow\) no. of solutions generated per temperature
\(T_0\) is often taken to be:
-
a value such that for an average \(\Delta E\), \(p\) is 0.5
-
\(\Delta E_\text{max}\)
The temperature \(T\) is updated as: \(T = \alpha \cdot T\), where \(0 \lt \alpha \lt 1\)
Termination Conditions
Simulated annealing is often used to solve problems in which the number of neighbouring solutions from the current one is very large such as the number of permutations that can be made to a proposed TSP route.
For such problems, it may not make sense to try all possible neighbouring solutions.
@TODO: add diagram of neighbouring solutions
Instead, it may be useful to exploit some criterion involving the number of neighbouring solutions that have been tried since an improvement was found.
-
while \( T > T_\text{min} \) {
-
for \(i\) in \(0..n(T)\) {
-
…steps for SA…
-
}
-
}
Several SA algorithms terminate once the temperature reaches 0.
-
while \( T > T_\text{min} \) & \( E > E_\text{threshold} \) {
-
…steps for SA…
-
}
-
while count for same best solution \( < 1500 \) & count for same energy difference \( < 1500000 \) {
-
…steps for SA…
-
}