Simulated Annealing
Created on: 2024-12-08
Tags: #SimulatedAnnealing
Course: Optimization
Definition
Simulated Annealing is a neighborhood based meta-heuristics technique which is based on the annealing process.
If the heating temperature is sufficiently high to ensure random state and the cooling process is slow enough to ensure thermal equilibrium, then the atoms will place themselves in a pattern that corresponds to the global energy minimum of a perfect crystal.
The random perturbations in the position of the atom decreases with reduction in temperature.
Algorithm
- Select a point $X_{c}$ and find the value of objective function at that point $E(x_{c})$.
- Select an initial temperature T>0
- Set number of iterations at each temperature N.
- Set the cooling rate $\alpha$.
- Set n = 0.
- Generate a new state $x_{new}$ in the neighborhood of $x_{c}$.
- Calculate $\Delta E = E(x_{n}) - E(x_{c})$.
- If $\Delta E <0$, then $x_{c} = x_{n}$
- Else if random (0,1)< $exp \left( -\frac{\Delta E}{BT} \right)$, then $x_{c} = x_{n}$.
- Set n = n+1.
- If $n\neq N$, go to Step 6.
- Set $T = T\times \alpha$
- Go to Step 5, if stopping criteria is not reached.
Algorithm Parameters
- Set initial temperature to be large enough.
- Cooling rate is generally 0.8 to 0.99
- Stopping Criteria
- When the solution isn’t changing for consecutive temperature changes.
- When temperature reaches a specific value.
- Constant B: Should be chosen depending on the value of $\Delta E$ and initial temperature T and the final temperature.
Advantages
- Easy to implement.
- Applicable to wide range of problems.
- High quality solutions.
- Better than greedy algorithms.
Weakness
- Care is needed to devise an appropriate neighborhood structure and cooling schedule.
- Results are not reproducible.
- Can leave an optimal solution and not find it again.
- Good for multimodal functions.
Linked from
- No other published notes link here yet.