Interactive companion · Chapter 5 · Simulated annealing

Simulated Annealing Lab

While the search is “hot,” simulated annealing is willing to climb hills to see what lies behind them; as it cools, only downhill steps remain.

f(x) Continuous 9 × 9 Sudoku 3 1 5 2 4 Routing A–F Plant layout M1 M2 Scheduling

Based on Chapter 5, “Simulated annealing,” in Alaa Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning Publications, 2024 (ISBN 978-1633438835).

coldhot

Simulated annealing on a rugged landscape.

Part 1 · Sections 5.1 and 5.2.1

Trajectory-based search and physical annealing

Simulated annealing (SA) sometimes accepts worse moves, less often as it cools, so it can leave a local valley.

Section 5.1 places SA among the metaheuristics (Figure 5.1), and Table 5.1 maps physical annealing onto the algorithm.

Physical annealing: slow cooling vs. quenching

Press Start: the left box cools slowly, the right one at once. Which reaches crystal order (gold) and lower energy?

Figures 5.2 and 5.3 in Section 5.2.1 explain why slow cooling yields a crystal and quenching does not.

Slow cooling vs. fast cooling

64 atoms · Metropolis rule
in perfect crystal order (6 neighbors) defect
Slow cooling (annealing)
Fast cooling (quenching)

Temperature over time. The quench drops to cold almost at once.

Energy per atom over time (lower is more stable).

Press Start to heat both boxes and cool them.

Part 2 · Section 5.2.2

The SA algorithm

Algorithm 5.1: Simulated annealing initialize T = T0, initial guess x0, n = 0 set the final temperature Tf, kmax iterations per temperature, a maximum number of iterations N and a cooling schedule while T > Tf and n < N for k = 1 .. kmax move randomly to a neighbor x′ Δf = f(x′) − f(x) if Δf < 0 then accept x′ else draw r ∈ [0, 1]; accept x′ if e−Δf/T > r update T with the cooling schedule; n = n + 1 return the best solution found

Each iteration tries a random neighbor, always keeps it if it is better, and otherwise keeps it with probability e−Δf/T; then the temperature drops.

Section 5.2.2 explains SA as a Markov chain (Figure 5.4) and surveys its variants, including quantum annealing.

Part 3 · Section 5.2.3

Acceptance probability

A worse move is accepted when

p = e−Δf/T;   accept a worse move if p > r, r uniform in [0, 1]

Move the sliders, then draw random numbers to see which moves pass.

Section 5.2.3 derives this rule from physics and shows cheaper forms (Figure 5.6).

To accept or not to accept?

Minimization

Part 4 · Sections 5.2.4 and 5.2.5

The annealing schedule

The schedule sets the starting temperature, how it decreases, the iterations per temperature and the final temperature.

Figure 5.7 and Section 5.2.4 discuss how to pick each of these four settings.

Initial temperature

T0 ≈ −max(Δf) / ln p0

Set max(Δf) and p0, or run the warm-up on Berlin52.

Equation 5.5 and the text around it explain both ways of choosing T0.

Choosing T₀

Share of worse 2-opt moves accepted at each temperature (log scale on x).

Cooling schedules

Tune T0 and each schedule’s factor to compare how fast they cool.

Cooling schedule explorer

Figure 5.8

Adaptation in SA

SA can adapt its schedule, for example by reheating when it stalls; try it in the Berlin52 lab.

Section 5.2.5 covers reheating, nonmonotonic cooling (equation 5.12) and Figure 5.9.

Part 5 · Section 5.3

Function optimization

Hand iterations: minimize (x − 6)² on [0, 31]

Press Next iteration to follow each candidate, its Δf and the accept or reject decision.

Section 5.3 works these first iterations out by hand, with every random number shown.

Step through SA

T₀ = 5 · α = 0.85 · 2 iterations per T

Function lab

Pick a function, then Run or step one temperature at a time.

Listings 5.1 and 5.2 solve these functions with SciPy, MEALPY and the book’s solver.

Continuous SA lab

Minimize f

Temperature at each level.

Current (faint) and best value.

Run it in Python: Listing 5.1 SciPy and MEALPY Listing 5.2 Function optimization From-scratch code ↓
Part 6 · Section 5.4

Sudoku

A move swaps two cells inside a box; the cost counts digits missing from rows and columns. Pick a puzzle and press Run.

Listing 5.3 solves Sudoku with SA, and Table 5.2 compares it with backtracking and PuLP.

Sudoku with SA

Minimize row and column conflicts

Cost (missing digits in rows and columns) as SA runs.

Bold digits on gray are given. Highlighted cells repeat a digit in their row or column.

Run it in Python: Listing 5.3 Sudoku From-scratch code ↓
Part 7 · Section 5.5

The traveling salesman problem

Five cities (Figures 5.11 to 5.14)

Step through SA with swap moves on a five-city tour and watch which swaps are accepted.

Figures 5.11 to 5.14 work this example through by hand, iteration by iteration.

5-city walkthrough

T₀ = 500 · T = T − 50 · swap moves

Berlin52 lab (Listing 5.5)

Choose a neighborhood and schedule, then run SA on the 52 Berlin locations.

Listing 5.5 gives the book’s Berlin52 settings and compares its result with the optimum.

Berlin52 SA lab

Minimize tour length

Current (faint) and best tour per level; dashed: the optimum and the book’s result.

Run it in Python: Listing 5.4 Simple TSP Listing 5.5 Berlin52 From-scratch code ↓
Part 8 · Facility layout

Plant layout

Place six departments on a 2 × 3 grid to minimize TMHC = Σ flow × distance. A move swaps two departments.

The book works the first swaps of this example by hand.

Plant layout with SA

Minimize TMHC

Part 9 · Scheduling

Scheduling

Minimize weighted tardiness on one machine and the makespan on three; press Next iteration in each.

The book defines the main scheduling objectives and solves both examples by hand.

One machine, weighted tardiness

Three machines, makespan

Six jobs (times 2, 3, 4, 6, 2, 2); each job gets a machine, and every machine at least one job.

Part 10 · Section 5.6 and appendix C

More applications

Section 5.6 solves the delivery routing case on real road data, and appendix C adds the US-cities TSP examples.

Delivery semi-truck routing

Route a truck to 18 Walmart stores in the Greater Toronto Area on real roads.

Listing 5.6

TSP of 20 US cities

The twenty largest US cities with the book’s SA solver.

Listing C.2

TSP with simanneal

The same cities with the simanneal package.

Listing C.3

Part 11 · Code

Python in Google Colab

Open the book’s notebooks in Colab, or the companion notebook with the from-scratch code below.

Notebooks

All examplesSA Lab companion notebookThe from-scratch code below, ready to run Chapter 5Listing 5.1Bohachevsky with SciPy and MEALPY Chapter 5Listing 5.2Function optimization with optalgotools Chapter 5Listing 5.3Sudoku Chapter 5Listing 5.4Five-city TSP Chapter 5Listing 5.5Berlin52 TSP Chapter 5Listing 5.6Delivery semi-truck routing ExtrasCooling schedulesFigure 5.8 ExtrasAcceptance probabilityFigures 5.5 and 5.6 Appendix CListing C.2TSP of 20 US cities Appendix CListing C.3TSP with simanneal

From-scratch implementations

Open all six in Colab
# Acceptance probability, initial temperature and cooling schedules (Chapter 5, Sections 5.2.3 and 5.2.4)
import math
import numpy as np
import matplotlib.pyplot as plt


def accept_probability(delta_f, T):
    """Metropolis criterion: improving moves (delta_f < 0) are always accepted."""
    return 1.0 if delta_f < 0 else math.exp(-delta_f / T)


print("p(9.17, T=5) =", round(accept_probability(23.23 - 14.06, 5), 4))       # 0.1597, the book's hand iteration

# Initial temperature for a target acceptance probability p0 of the largest expected increase (equation 5.5)
max_delta, p0 = 50, 0.8
print("T0 =", round(-max_delta / math.log(p0), 1))


def temperature(i, schedule, T0=100, Tf=0.001, N=100, alpha=0.9, n=1):
    if schedule == "linear":                       # T = T0 - beta i, beta = (T0 - Tf) / N
        return T0 - (T0 - Tf) / N * i
    if schedule == "linear_inverse":              # T = T0 / (1 + alpha i)
        return T0 / (1 + alpha * i)
    if schedule == "geometric":                   # T = T0 alpha^i
        return T0 * alpha ** i
    if schedule == "logarithmic":                 # T = T0 / (1 + alpha ln(1 + i)), alpha > 1
        return T0 / (1 + alpha * math.log(1 + i))
    if schedule == "exponential":                 # T = T0 exp(-alpha i^(1/n)), n = dimension
        return T0 * math.exp(-alpha * i ** (1 / n))
    raise ValueError(schedule)


i = np.arange(101)
for s, a in [("linear", 0), ("geometric", 0.7), ("geometric", 0.9), ("logarithmic", 10), ("exponential", 0.9), ("linear_inverse", 0.9)]:
    plt.plot(i, [temperature(k, s, alpha=a) for k in i], label=f"{s}" + (f", alpha = {a}" if a else ""))
plt.xlabel("iteration"); plt.ylabel("temperature"); plt.legend(); plt.title("SA cooling schedules (Figure 5.8)"); plt.show()

# Acceptance probability against the objective change for several temperatures (Figure 5.5)
d = np.linspace(0, 10, 200)
for T in [0.5, 1, 2, 5, 10]:
    plt.plot(d, np.exp(-d / T), label=f"T = {T}")
plt.xlabel("objective change Δf"); plt.ylabel("acceptance probability"); plt.legend(); plt.show()

To run: open the companion notebook in Colab and press Shift+Enter in each cell, or paste a tab’s code into any notebook.

Part 12 · Summary

What to remember

Trajectory-based

One agent always takes better moves and sometimes worse ones.

Temperature

p = e−Δf/T: hot explores, cold exploits.

Schedule

Temperatures, cooling and iterations per level shape the result.

Derivative-free

SA needs only objective values but guarantees no optimum.

References: N. Metropolis et al., “Equation of state calculations by fast computing machines,” 1953. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by simulated annealing,” Science, 1983. L. Ingber, “Adaptive simulated annealing (ASA): Lessons learned,” 1996. X. Geng et al., “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” 2011. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 5.

Part 13 · Quiz

Check your understanding

Two quick questions on Chapter 5. Pick an answer to check it.

Q1. In simulated annealing, a worse move with objective change Δf > 0 is accepted with probability e−Δf/T. What happens as the temperature T approaches 0?

Q2. In the slow cooling vs. quenching experiment, why does slow cooling reach a lower-energy state?

For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms. The coding solutions are also on GitHub (Chapter 5).