Coursify

Simulated Annealing (SA): Working Mechanism and Worked Example

Simulated Annealing (SA): Working Mechanism and Worked Example

Verified Sources
Nov 1, 2026

Simulated Annealing Simulated annealing (SA) is a stochastic optimization method inspired by annealing in metallurgy. In each iteration, SA perturbs the current candidate solution to generate a neighboring state; if the new state is better (lower “energy” / objective value), it is accepted. If it is worse, SA may still accept it with probability that depends on the current temperature TT and the objective increase ΔE\Delta E. This allows SA to escape local minima early, while later it becomes greedier as TT decreases according to a cooling schedule. The method is built around the Metropolis-style acceptance rule and a temperature update rule Tk+1=αTkT_{k+1}=\alpha T_k with 0<α<10<\alpha<1.2

Key concepts (used throughout):

  • Temperature parameter TT
  • Neighboring solution generation
  • [Cooling schedule]{def="Rule that decreases temperature over time (e.g., geometric)}}
  • Metropolis criterion

Footnotes

  1. Simulated annealing - Cornell University Computational Optimization Open Textbook - Provides SA pseudocode, ΔE\Delta E, and acceptance probability plus geometric cooling discussion. ↩

  2. Chapter 2 - Temperature and Cooling Schedules | Algorithm Afternoon - Explains Metropolis acceptance probability e−DeltaE/Te^{-\\Delta E/T} and temperature effect with numeric example. ↩

Simulated Annealing Explained (Metropolis criterion & cooling)

Core working loop of simulated annealing

A standard SA loop can be described as:

  1. Initialize: pick an initial solution s0s_0 and a high initial temperature T0T_0.
  2. Neighbor generation: from the current solution ss, generate a neighbor snews_{\text{new}} (a small random modification).
  3. Evaluate objective/energy: compute ΔE=f(snew)−f(s).\Delta E = f(s_{\text{new}})-f(s).
  4. Accept/reject:
    • If ΔE<0\Delta E<0, accept (the neighbor improves the objective).
    • If ΔE>0\Delta E>0, accept with probability P(accept)=exp⁡(−ΔET).P(\text{accept})=\exp\left(-\frac{\Delta E}{T}\right).
  5. Cool down: reduce temperature, commonly using geometric cooling Tk+1=αTk,0<α<1.T_{k+1}=\alpha T_k,\quad 0<\alpha<1.
  6. Stop: when temperature is low enough (T≤Tmin⁡T\le T_{\min}) or after a max number of iterations.

This matches commonly cited pseudocode and temperature/acceptance rules.3

Footnotes

  1. Simulated annealing - Cornell University Computational Optimization Open Textbook - Provides SA pseudocode, ΔE\Delta E, and acceptance probability plus geometric cooling discussion. ↩

  2. Chapter 2 - Temperature and Cooling Schedules | Algorithm Afternoon - Explains Metropolis acceptance probability e−DeltaE/Te^{-\\Delta E/T} and temperature effect with numeric example. ↩

  3. LAB 8 – SIMULATED ANNEALING (Tufts University PDF) - Describes geometric vs linear cooling and guidance on initial temperature and cooling rate. ↩

Simulated Annealing: step-by-step procedure

  1. 1
    Step 1

    Define f(s)f(s) to minimize. Specify how a solution ss is represented (e.g., a permutation for TSP) and how neighbors are generated.

  2. 2
    Step 2

    Set initial solution s0s_0 and initial temperature T0T_0 (high enough to allow frequent acceptance of worse moves early).

  3. 3
    Step 3

    Sample a neighbor snews_{new} using a small perturbation of the current solution.

  4. 4
    Step 4

    Compute 0˘394E=f(snew)−f(s)\u0394E=f(s_{new})-f(s). If 0˘394E<0\u0394E<0, the move improves the objective.

  5. 5
    Step 5

    If 0˘394E<0\u0394E<0, accept. Otherwise accept with probability P=0˘3c3−0˘394E/TP=\u03c3^{-\u0394E/T}, i.e., P=2˘009exp⁡(−0˘394E/T)P=\u2009\exp(-\u0394E/T); accept if a uniform random draw is below PP.

  6. 6
    Step 6

    Update temperature using a cooling schedule such as geometric cooling T2˘009←2˘009αTT\u2009\leftarrow\u2009\alpha T with 0<α<10<\alpha<1.

  7. 7
    Step 7

    Optionally store the best solution encountered. Stop when T≤TminT\le T_{min} or after a maximum iteration budget.

Why the acceptance probability depends on TT

At high temperature, the factor exp⁡(−ΔE/T)\exp(-\Delta E/T) becomes closer to 1, so SA is more likely to accept worse moves—behaving more like a random walk that can cross barriers between basins of attraction.2 As TT decreases, the probability of accepting worse moves drops, so SA transitions from exploration to exploitation (local refinement).

Interpretation by cases (for ΔE>0\Delta E>0):

  • If ΔE\Delta E is small, exp⁡(−ΔE/T)\exp(-\Delta E/T) is relatively large, so slight worsenings are tolerated.
  • If ΔE\Delta E is large, the probability becomes tiny.
  • If TT is high, worsenings are frequently accepted early.
  • If TT is low, worsenings are rarely accepted, making the algorithm increasingly greedy.2

Footnotes

  1. Chapter 2 - Temperature and Cooling Schedules | Algorithm Afternoon - Explains Metropolis acceptance probability e−DeltaE/Te^{-\\Delta E/T} and temperature effect with numeric example. ↩ ↩2

  2. LAB 8 – SIMULATED ANNEALING (Tufts University PDF) - Describes geometric vs linear cooling and guidance on initial temperature and cooling rate. ↩

  3. Simulated Annealing: How the Algorithm Works (beon.tech) - Highlights exploration vs exploitation via temperature and the role of P=exp(−DeltaE/T)P=\\exp(-\\Delta E/T). ↩

  4. Simulated Annealing - GeeksforGeeks - Summarizes acceptance of worse solutions using P=e−Delta/TP=e^{-\\Delta/T}. ↩

Cooling schedules and practical tuning

A geometric cooling schedule is frequently described as: Tk=T0⋅αk,0<α<1,T_k = T_0 \cdot \alpha^k,\quad 0<\alpha<1, or equivalently Tk+1=αTkT_{k+1}=\alpha T_k.2 Lab/teaching references often recommend:

  • start with a temperature high enough to “melt” the system (high probability of accepting bad moves),
  • reduce temperature gradually, especially near the “freezing point,”
  • recognize that finding a good schedule may require experimentation.

Common alternatives (mentioned in educational references) include linear and logarithmic schedules, each affecting exploration/exploitation balance differently.2

Footnotes

  1. LAB 8 – SIMULATED ANNEALING (Tufts University PDF) - Describes geometric vs linear cooling and guidance on initial temperature and cooling rate. ↩ ↩2 ↩3

  2. Rafael E. Banchs - Simulated Annealing (PDF) - Presents common cooling schedule forms including logarithmic and geometric and discusses typical 0˘3b1\u03b1 behavior. ↩

  3. ENAC - HAL (Simulated annealing: From basics to applications) - Discusses schedule choices and stopping conditions in SA applications. ↩

Worked example: Simulated annealing for the Traveling Salesman Problem (TSP)

We will use the SA mechanism on a small TSP instance to show the working decisions.

Setup

Let the objective be the total tour length (distance traveled). In TSP, a state is a permutation of cities. A typical neighbor move is swap two cities in the tour.

This is consistent with descriptions of SA applied to TSP:

  • start with an initial route,
  • propose a neighbor by swapping two cities,
  • accept improvements and probabilistically accept worsenings based on temperature,
  • gradually decrease temperature and track the best tour seen so far.

Mini numerical walk-through

Assume at some iteration:

  • Current tour length: f(s)=100f(s)=100
  • Proposed neighbor length: f(snew)=120f(s_{new})=120
  • So ΔE=120−100=20\Delta E=120-100=20 (worse move)
  • Acceptance probability: P=exp⁡(−ΔE/T)=exp⁡(−20/T).P=\exp(-\Delta E/T)=\exp(-20/T).

Case 1: High temperature T=1000T=1000
P=exp⁡(−20/1000)=exp⁡(−0.02)≈0.98.P=\exp(-20/1000)=\exp(-0.02)\approx 0.98.
So SA is very likely to accept this worse route early, supporting exploration.

Case 2: Lower temperature T=10T=10
P=exp⁡(−20/10)=exp⁡(−2)≈0.135.P=\exp(-20/10)=\exp(-2)\approx 0.135. So the same worse move is much less likely to be accepted late in the run, supporting convergence.

Full iteration view (conceptual)

At each SA step for TSP:

  1. pick a neighbor by swapping two cities in the current permutation,
  2. compute the new tour length,
  3. if it’s shorter, accept; if longer, accept with probability exp⁡(−ΔE/T)\exp(-\Delta E/T),
  4. cool T←αTT\leftarrow \alpha T.

In a TSP-specific explanation, SA’s neighbor generation via swapping and the probabilistic acceptance rule (Metropolis criterion) are explicitly described.2

Footnotes

  1. Simulated annealing - Wikipedia - Describes SA as a random walk over states and TSP neighbor generation via swapping cities. ↩ ↩2

  2. Simulated Annealing : Methods and Real-World Applications – OMSCS 7641 (Georgia Tech) - Explains SA applied to TSP: initial route, swapping two cities, probabilistic acceptance, and tracking best solution. ↩ ↩2

  3. Chapter 2 - Temperature and Cooling Schedules | Algorithm Afternoon - Explains Metropolis acceptance probability e−DeltaE/Te^{-\\Delta E/T} and temperature effect with numeric example. ↩ ↩2

Acceptance probability for a worse move (0˘394E=20\u0394E=20) at different temperatures

Illustrates how decreasing T reduces acceptance of worsening neighbors: P=exp⁡(−0˘394E/T)P=\exp(-\u0394E/T).

Pro Tip

When implementing SA, always track the best solution found so far. Even if later iterations accept worse moves, you still retain the best objective value seen during the run (common in SA descriptions and implementations).2

Footnotes

  1. Simulated annealing - Cornell University Computational Optimization Open Textbook - Provides SA pseudocode, ΔE\Delta E, and acceptance probability plus geometric cooling discussion. ↩

  2. Simulated Annealing : Methods and Real-World Applications – OMSCS 7641 (Georgia Tech) - Explains SA applied to TSP: initial route, swapping two cities, probabilistic acceptance, and tracking best solution. ↩

Warning: Cooling schedule choice affects results

SA’s performance is sensitive to how fast temperature decreases. If you cool too quickly (small 0˘3b1\u03b1 / aggressive schedule), SA can “freeze” before it escapes local minima; if you cool too slowly, it may take too long to converge. Educational sources explicitly describe this trade-off and tuning necessity.2

Footnotes

  1. LAB 8 – SIMULATED ANNEALING (Tufts University PDF) - Describes geometric vs linear cooling and guidance on initial temperature and cooling rate. ↩

  2. Rafael E. Banchs - Simulated Annealing (PDF) - Presents common cooling schedule forms including logarithmic and geometric and discusses typical 0˘3b1\u03b1 behavior. ↩

Common edge questions about SA

Simulated Annealing: key terms

1 / 5
Question · Term

[Simulated annealing]{def="A metaheuristic that minimizes an objective by probabilistically accepting worse moves while cooling temperature decreases"}

Click to reveal
Answer · Definition

Stochastic optimization using neighbor proposals + Metropolis acceptance + cooling schedule.2

Footnotes

  1. Simulated annealing - Cornell University Computational Optimization Open Textbook - Provides SA pseudocode, ΔE\Delta E, and acceptance probability plus geometric cooling discussion. ↩

  2. Chapter 2 - Temperature and Cooling Schedules | Algorithm Afternoon - Explains Metropolis acceptance probability e−DeltaE/Te^{-\\Delta E/T} and temperature effect with numeric example. ↩

Knowledge Check

Question 1 of 4
Q1Single choice

In simulated annealing, a worse move with objective increase ΔE>0\Delta E>0 is accepted with probability:

Explore Related Topics

1

CASE (Computer-Aided Software Engineering): Full Form, CASE Diagram, and Components

2

Why Electrical Analogies Are Used in Control Systems

3

Two-Phase Locking (2PL): Protocol, Phases, and a Worked Example

Browse all research articles