Local search and simulated annealing: a travelling salesman through the Czech regional capitals

The optimization problem, the travelling salesman problem, hill climbing with the 2-opt neighbourhood, local minima and restarts, simulated annealing, temperature and the cooling schedule — on a route through thirteen regional capitals with a known optimum.

13 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 26 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

A blacksmith who wants a strong blade does not let the red-hot metal cool abruptly — he cools it slowly. That gives the atoms time to settle into a regular arrangement with the lowest energy. If the metal were quenched all at once, the atoms would freeze wherever they happened to be and the blade would be brittle. In 1983 physicists noticed that exactly the same thing troubles algorithms that look for the best solution: if they only ever go “downhill”, they freeze in the first hollow. That is how simulated annealing was born — and with it one of the most useful ideas in optimization.

This part opens the module on algorithms inspired by nature. It follows on from the part State-space search, where hill climbing and annealing first appeared.

1. The optimization problem

Definition — optimization problem and neighbourhood

Let S be a non-empty set whose elements we call feasible solutions, and let f : S → ℝ be a function we call the objective function. The optimization (minimization) problem (S, f) is the problem of finding an element s* ∈ S for which

∀ s ∈ S : f(s*) ≤ f(s),   i.e.   s* ∈ argmin_{s ∈ S} f(s) = {s ∈ S : ∀ s′ ∈ S : f(s) ≤ f(s′)}.

Such an element s* is called a global minimum. If S is finite, a global minimum exists (there may be more than one). For a maximization problem the inequalities are reversed; maximizing f is the same as minimizing −f.

Let 2^S denote the set of all subsets of S. A neighbourhood is a mapping N : S → 2^S that assigns to every solution s ∈ S the set N(s) ⊆ S of its neighbours; in practice these are the solutions obtained from s by one small change of a prescribed type. A solution s ∈ S is a local minimum with respect to the neighbourhood N if and only if

∀ s′ ∈ N(s) : f(s) ≤ f(s′).

A global minimum is thus a solution with no better solution anywhere in S, whereas a local minimum only has no better solution among its neighbours. Every global minimum is also a local one; the converse does not hold.

2. The travelling salesman problem

A travelling salesman has to visit all thirteen regional capitals of Czechia, each exactly once, and return to where he started. Which route is the shortest? We measure distances as the crow flies.

Definition — travelling salesman problem (TSP)

Let n ≥ 3 be the number of cities, numbered 1, …, n, and let d : {1, …, n} × {1, …, n} → ℝ be the distance function, where d(i, j) ≥ 0 is the distance from city i to city j. In this part d is moreover symmetric: d(i, j) = d(j, i) for all i, j.

A feasible solution (a tour) is a permutation π = (π₁, …, π_n) of the set {1, …, n} — the order in which we visit the cities, returning from the last one to the first. The objective function is the length of the tour

f(π) = ∑_k=1ⁿ d(π_k, π_k+1),   where π_n+1 = π₁.

The travelling salesman problem is the optimization problem of finding a permutation π with the smallest length f(π).

Permutations that differ only in the city they start from (by a cyclic shift) or in the direction of travel have the same length and describe the same tour. There are therefore n!/2n = (n − 1)!/2 different tours (breakdown below). The decision version of the problem (“is there a tour of length at most L?”) is NP-complete.

number of tours = n!/n · 2 = (n − 1)!/2

n!

all orders in which n cities can be listed — that is how many permutations there are; but each tour is counted among them several times

n

a tour has no beginning: Praha → Brno → … → Praha is the same route as Brno → … → Praha → Brno. Every tour can start in any of the n cities, hence n times fewer

2

the distance there is the same as back, so a tour driven in reverse is the same route of the same length

Example — the straight-line distance from Praha to Brno

The cities are given by latitude φ and longitude λ in degrees. Within Czechia a flat approximate projection is enough: a degree of latitude is 110.57 km, a degree of longitude 111.32 · cos φ₀ km, where φ₀ = 49.8° is the middle of the country (meridians converge towards the pole). Then

d(i, j) = √(71.85 · Δλ)² + (110.57 · Δφ)².

Praha (50.08° N, 14.42° E), Brno (49.20°, 16.61°)

Δλ = 2.19° → 71.85 · 2.19 = 157.35 km to the east

Δφ = −0.88° → 110.57 · 0.88 = 97.30 km to the south

d = √157.35² + 97.30² = √24,759 + 9,467 = √34,226 ≈ 185.0 km

Compared with an exact calculation on a sphere, the error at such distances is about 1%; for comparing routes it does not matter.

Thirteen cities are still few enough for us to compute the optimum exactly — with Held–Karp dynamic programming over subsets of cities, which takes 2ⁿ · n² steps instead of (n − 1)!. The shortest tour measures 1,060.4 km. Thanks to that, for every further algorithm we will see exactly how close it got to the optimum:

Algorithm — Held–Karp dynamic programming (1962)

Input: the number of cities n ≥ 3, cities numbered 0, …, n − 1, and distances d : {0, …, n − 1}² → ℝ, d ≥ 0. Output: the length of the shortest tour (the travelling salesman problem above); the tour itself is recovered by tracing back at which k the minimum was attained.

A tour has no beginning, so without loss of generality it starts in city 0. For every set of cities M ⊆ {0, …, n − 1} with 0 ∈ M and every city j ∈ M, let D(M, j) be the length of the shortest path that leaves city 0, passes through every city of M exactly once, no other, and ends in j. For M ≠ {0} we put D(M, 0) = ∞ (the path must not return to 0 prematurely).

1. Set D({0}, 0) = 0.
2. For m = 2, …, n in turn: for every M ∋ 0 with |M| = m and every j ∈ M ∖ {0} compute D(M, j) = min_{k ∈ M ∖ {j}} [ D(M ∖ {j}, k) + d(k, j) ]. All values on the right have a set one element smaller, so they have already been computed.
3. After finishing m = n, stop and return min_{j ∈ {1, …, n − 1}} [ D({0, …, n − 1}, j) + d(j, 0) ].

The algorithm thus always terminates after a finite number of steps: there are at most 2ⁿ · n values of D, and each is the minimum of at most n numbers.

n = 13:   2¹³ · 13² = 8,192 · 169 = 1,384,448 steps

going through all orders from a fixed start: 12! = 479,001,600 — about 346 times more

3. Hill climbing and the 2-opt neighbourhood

Definition — the 2-opt move

Let n ≥ 4, let d be the symmetric distance from the definition of TSP and c = (c₀, c₁, …, c_n−1) a tour through n cities (after c_n−1 comes c₀ again). Let i, j be indices, 1 ≤ i < j ≤ n − 1. The 2-opt move (i, j) assigns to the tour c the tour

c′ = (c₀, …, c_i−1, c_j, c_j−1, …, c_i, c_j+1, …, c_n−1),

i.e. it reverses the order of the section c_i, …, c_j. Let a = c_i−1, b = c_i, e = c_j and f = c_{(j+1) mod n} (here f denotes a city, not the objective function). The move removes the edges (a, b) and (e, f) from the tour and adds the edges (a, e) and (b, f); the other edges stay, only the section between b and e is driven in reverse. The length of the tour therefore changes by

Δ = length(c′) − length(c) = d(a, e) + d(b, f) − d(a, b) − d(e, f).

The 2-opt neighbourhood N(c) is the set of all tours obtained from c by one move (i, j); there are (n − 1)(n − 2)/2 pairs (i, j).

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

Δ

how much longer the tour gets; a negative Δ means it gets shorter. Both hill climbing and annealing decide by its sign, which is why we need it cheaply

d(a, e) + d(b, f)

two new edges with which we reconnect the cut ends — they are added because the route gains them

d(a, b) + d(e, f)

the two edges we cut — they are subtracted because they disappear from the route. The section between b and e is merely driven in reverse and distances are symmetric, so its length does not change and it is missing from the formula

Algorithm — hill climbing (steepest descent)

Input: an optimization problem (S, f) with a finite set S, a neighbourhood N : S → 2^S with non-empty sets N(s) and an initial (random) solution s₀ ∈ S. Output: a local minimum s ∈ S with respect to N.

1. Set s ← s₀.
2. Find the best neighbour s′ ∈ argmin_{t ∈ N(s)} f(t) (on a tie, any of them).
3. If f(s′) < f(s), set s ← s′ and continue with step 2.
4. Otherwise (f(s′) ≥ f(s)) stop and return s.

The stopping condition is in step 4: no neighbour is strictly better, so f(s) ≤ f(t) for all t ∈ N(s) and s is a local minimum. Since f(s) strictly decreases with every move, no solution repeats, and on a finite S the algorithm therefore always terminates.

def delta(c, i, j):                    # 2-opt move: reverse c[i..j]
    a, b = c[i - 1], c[i]
    e, f = c[j], c[(j + 1) % len(c)]
    return d(a, e) + d(b, f) - d(a, b) - d(e, f)

def horolezec(c):
    n = len(c)
    while True:
        tahy = [(i, j) for i in range(1, n - 1) for j in range(i + 1, n)]
        i, j = min(tahy, key=lambda t: delta(c, *t))   # steepest descent
        if delta(c, i, j) >= 0:                        # nothing shortens the route
            return c                                    # local minimum
        c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]

We keep the first city in place (i ≥ 1) — a tour has no beginning, so moving it would bring nothing new. For n = 13 the pairs 1 ≤ i < j ≤ 12 give exactly 12 · 11/2 = 66 moves.

From a random tour 2,402 km long, hill climbing reaches 1,065.8 km in 8 steps — and stops there. Only 5 km short of the optimum, yet no single 2-opt move shortens the route any more. Hill climbing is in a local minimum and does not know it:

4. Where hill climbing gets stuck

Out of a hundred random starts, hill climbing ended in the optimum 61 times. In the remaining 39 cases it got stuck elsewhere, at worst at 1,162.6 km — a hundred kilometres off. There are three traps:

• Local minimum — a hollow from which every step leads uphill.
• Plateau — all neighbours are equally good, so hill climbing does not know where to go.
• Ridge — a good direction exists but does not lie along any single move; it can only be reached through worse solutions.

Example — why hill climbing cannot get out of 1,065.8 km

Hill climbing from the first start ended on the tour Zlín → Ostrava → Olomouc → Pardubice → Hradec Králové → Liberec → Ústí nad Labem → Karlovy Vary → Plzeň → Praha → České Budějovice → Jihlava → Brno → Zlín. We compute Δ for all 66 2-opt moves: one of them (reversing everything except the first city) gives the same tour in the opposite direction and Δ = 0, all the others make the route longer. The cheapest of them reverses the pair Pardubice – Hradec Králové:

a = Olomouc, b = Pardubice, e = Hradec Králové, f = Liberec

Δ = d(a, e) + d(b, f) − (d(a, b) + d(e, f))

  = 122.9 + 95.9 − (116.8 + 83.0) = +19.0 km

(Colours as in the breakdown of the 2-opt move above.)

So every single move makes the route at least 19.0 km longer — while the optimum is a mere 5.4 km shorter. The way to it leads through worse tours, and hill climbing never accepts those.

The simplest remedy is random restarts: run hill climbing again from a different place and keep the best result. If one start succeeds with probability 0.61, then out of five starts at least one succeeds with probability P₅ = 1 − 0.39⁵ ≈ 99% (colours as in the formula below). For a small problem that is enough. For a large one there are millions of hollows and far too many restarts would be needed.

P_r = 1 − (1 − p)^r

P_r

the probability that at least one of r starts finds the optimum — we compute it via the complement, because “at least one” comes in many forms, whereas “not a single one” comes in only one

1 − p

the probability that one start fails (0.39 in our hundred attempts)

r

the number of starts in the exponent: the starts are independent (each has a different random seed), so the failure probabilities multiply

5. Simulated annealing

Algorithm — simulated annealing

Input: an optimization problem (S, f), a neighbourhood N : S → 2^S with non-empty finite sets N(s), an initial (random) solution s₀ ∈ S, an initial temperature T₀ > 0, a cooling coefficient α ∈ (0, 1) and a number of iterations K ∈ ℕ. Output: the best solution s_best ∈ S the algorithm visited during the run.

1. Set s ← s₀, s_best ← s₀, T ← T₀.
2. For k = 1, …, K repeat:
   1. pick a neighbour s′ ∈ N(s) at random (uniformly) and compute Δ = f(s′) − f(s);
   2. if Δ ≤ 0, set s ← s′; otherwise draw u uniformly from [0, 1) and if u < exp(−Δ/T), set s ← s′ (the Metropolis criterion: a worse neighbour is accepted with probability exp(−Δ/T));
   3. if f(s) < f(s_best), set s_best ← s;
   4. lower the temperature according to the cooling schedule, here a geometric one: T ← α · T.
3. After K iterations, stop and return s_best.

The algorithm thus always stops after a predetermined number K of iterations; for cooling schedules other than the geometric one, see the section on temperature.

P(accept) = min(1, exp(−Δ/T))

P(accept)

the probability with which we move to the proposed neighbour; in the program we draw u uniformly from [0, 1) and accept the move when u < P

min(1, …)

for an improvement (Δ ≤ 0) the exponential is ≥ 1 and a probability must not exceed 1 — so a better step is always accepted, just as in hill climbing

Δ

how much worse the neighbour is, in km. It sits in the exponent with a minus sign, so every additional kilometre of worsening multiplies the chance by the same number smaller than 1 — large worsenings are exponentially rarer than small ones

T

the temperature, in the same units as Δ (km). It divides Δ and thereby sets the scale: a worsening by T km gets through with probability exp(−1) = 1/e ≈ 0.37 at any temperature. A high T makes large worsenings “small”, T → 0 forbids them all

The rule for accepting a worse step comes from physics: in 1953 Nicholas Metropolis and his colleagues used it to simulate atoms in thermal equilibrium, where the probability of a state with energy E is proportional to exp(−E/kT). For optimization it was adapted independently in 1983 by Kirkpatrick, Gelatt and Vecchi at IBM — and two years later, also independently, by the Slovak physicist Vladimír Černý, on the very travelling salesman problem.

import math, random

def zihani(c, T0=200, Tk=0.5, K=10_000):
    alfa = (Tk / T0) ** (1 / K)          # geometric cooling
    T, delka = T0, delka_okruhu(c)
    nej, nej_delka = c, delka
    for k in range(K):
        i, j = sorted(random.randint(1, len(c) - 1) for _ in range(2))
        if i != j:                          # i = j: no move
            D = delta(c, i, j)
            if D <= 0 or random.random() < math.exp(-D / T):
                c = c[:i] + c[i:j + 1][::-1] + c[j + 1:]
                delka += D
                if delka < nej_delka:
                    nej, nej_delka = c, delka
        T *= alfa
    return nej

What it looks like for real: the first six iterations of our run and six iterations from its middle. p is the acceptance probability min(1, exp(−Δ/T)), u the number drawn; a worsening move gets through when u < p. The columns T, Δ and p have colours as in the formula above.

At the start, at T ≈ 200, even a move that makes the route 146.6 km longer gets through — the chance is 0.48 and the draw was u = 0.14. Halfway through the run T = 10 and the route already lies in the optimum; moves that would lengthen it by 70 kilometres or more have a chance below one in a thousand, and all are rejected. Sometimes both random numbers land on the same place (i = j) and the iteration proposes nothing — over the whole run this happened 824 times.

Theorem — the Boltzmann distribution (modern formulation)

Let S be a finite set of solutions, f : S → ℝ the objective function, N a neighbourhood and T > 0 a fixed temperature. Let neighbours be proposed with probabilities q(s, s′) ≥ 0 (q(s, s′) > 0 only for s′ ∈ N(s), ∑_s′ q(s, s′) = 1) that are symmetric:

∀ s, s′ ∈ S : q(s, s′) = q(s′, s)

(for 2-opt this holds, because we draw every pair (i, j) with the same probability and the same move (i, j) also leads back). A proposed neighbour is accepted with probability min(1, exp(−f(s′) − f(s)/T)). Then this Metropolis process is a Markov chain on S, and the distribution

π_T(s) = exp(−f(s)/T)/Z(T),   Z(T) = ∑_{t ∈ S} exp(−f(t)/T),

π_T(s)

how often, after long wandering at temperature T, we find ourselves in solution s

exp(−f(s)/T)

the weight of a solution: the shorter the route f(s), the larger. It is exactly the weight that the Metropolis criterion balances — the ratio of the weights of two neighbours is exp(−Δ/T)

Z(T)

the sum of the weights over all solutions; we divide by it so that the probabilities add up to 1

is its stationary distribution: when the chain is in the distribution π_T, it stays in it after the next step as well. If, moreover, every solution can be reached from every other through neighbours, the stationary distribution is unique.

Proof (detailed balance condition). Let s ≠ s′ and f(s′) = f(s) + Δ with Δ ≥ 0 (otherwise swap s and s′). The probability flow from s to s′ is π(s) · q(s, s′) · exp(−Δ/T) and the flow back is π(s′) · q(s′, s) · 1. For π = π_T and symmetric q, both expressions equal q(s, s′) · exp(−f(s′)/T)/Z(T). The flows between every pair of solutions balance, so summing over all s we get that the probability of every s′ does not change in a step. ∎

optimum (1,060.4 km) versus the hill-climbing trap (1,065.8 km), ratio of frequencies:

π_T(optimum)/π_T(trap) = exp(5.38/T)

T = 100: 1.06   T = 10: 1.71   T = 1: 217   T = 0.5: 47,089

6. Temperature and the cooling schedule

What chance does a step that makes the route longer by Δ = 20 km have? It depends on the temperature (colours as in the formula for P(accept) in the previous section):

At 200 almost every worsening step gets through, at 0.5 none does — at that point annealing behaves like hill climbing. The cooling schedule decides how long the algorithm “wanders” and how long it “descends”. The cheapest escape from the hill-climbing trap (Δ = +19.0 km, see above) would get through at T = 50 with probability 0.68, at T = 10 with 0.15 and at T = 2 practically never.

T_k = T₀ · α^k,   α = (T_K/T₀)^1/K

T_k

the temperature in the k-th iteration — it determines how large worsenings are still accepted at that moment

T₀

the initial temperature; it is chosen so that most worsenings get through at the start — 200 km here, more than a typical 2-opt move on a random route

α

the cooling coefficient, just below 1; we compute it from the target temperature T_K and the number of iterations K, so that the run ends exactly where we want

k

the iteration number in the exponent: every iteration multiplies the temperature by the same number, so over the same number of iterations the temperature always drops by the same ratio — from 200 to 100 takes as long as from 1 to 0.5

Theorem — convergence of annealing

Let S be a finite set of solutions, f : S → ℝ the objective function and N a neighbourhood that is symmetric (s′ ∈ N(s) ⇔ s ∈ N(s′)) and connected (every solution can be reached from every other through neighbours). Let S* ⊆ S be the set of global minima and s_k the solution of annealing after the k-th iteration. For a local minimum s ∉ S*, define its depth

h(s) = min { max_{l = 0, …, m} f(t_l) − f(s) : t₀ = s, t_l+1 ∈ N(t_l), f(t_m) < f(s) },

i.e. the least amount by which a path through neighbours from s has to climb before it reaches a strictly better solution, and let d* = max h(s) over all local minima s ∉ S* (if there are none, d* = 0). Let the temperature decrease logarithmically:

T_k = c/ln(k + 1),   k = 1, 2, …,   c > 0.

Then P(s_k ∈ S*) → 1 as k → ∞ if and only if c ≥ d* (Hajek, 1988).

In words: if cooling is slow enough, annealing ends in the global minimum with probability close to one, and “slow enough” is determined by the deepest trap the algorithm must be able to climb out of.

if c = 20 km were enough, we would reach temperature 0.5 only at ln(k + 1) = 20/0.5 = 40,

that is after k ≈ e⁴⁰ ≈ 2.4 · 10¹⁷ iterations — roughly a billion times more than all 239,500,800 tours

7. Annealing on the regional capitals

Let us run annealing on the same problem: 10,000 iterations, the temperature dropping geometrically from 200 to 0.5. The map shows what the route looked like at the start and after 1,000, 3,000, 5,000 and 10,000 iterations:

After a thousand iterations the route is still chaotic (1,985 km) — at a high temperature annealing accepts almost everything. After three thousand it already has a shape (1,159 km), and after five thousand it is in the optimum, 1,060.4 km. Of the 1,498 accepted moves, 695 were worsening; hill climbing would not have made a single one of them. The chart shows how the route length jumps up and down until the temperature drops:

The transition from wandering to descending also shows in the number of accepted moves in each thousand iterations: 597, 411, 232, 104, 35, 35, 26, 21, 26, 11. In the first thousand, when T is between 200 and 110, more than half of the proposals are accepted. From the fifth thousand on (T below 20) only dozens; 37 of them were worsening, 26 of those tiny, under 3 km.

And it is not the luck of a single run: out of a hundred runs with different seeds, 98 ended in the optimum and the other two less than 3 km off. Compared with 61% for hill climbing from a single start, that is a big difference.

8. When annealing pays off

To be fair: annealing made 10,000 iterations, hill climbing from one start only about six hundred evaluations. On a small problem, hill climbing with restarts would have done just as well for the same price. The difference shows on a larger problem. Let us take 60 randomly placed cities and give both algorithms the same budget — 200,000 evaluated 2-opt moves:

Hill climbing fit into the budget only twice: with 60 cities the neighbourhood has 1,711 moves and steepest descent examines all of them at every step. Annealing tries one random move at a time and spreads the same budget over exploring the whole landscape. Each of its three runs ended better than hill climbing.

9. Annealing in artificial intelligence and beyond

• Chip design and scheduling. Placing components on a chip was one of the first big applications of annealing in the 1980s; to this day it is used for timetables, vehicle routing or warehouse layout.
• Training neural networks. Stochastic gradient descent computes the gradient from a small batch of data, so every step is a little random — like annealing, it can slip out of a shallow hollow. Learning-rate schedules that gradually lower it are even called cosine annealing.
• The temperature of language models. When a language model chooses the next word, it divides the word scores by a temperature T and turns them with the softmax function into probabilities proportional to exp(z/T) — the same Boltzmann formula. A high temperature means more inventive and riskier text, a low one more cautious and predictable text.
• Quantum annealing. Specialized computers (for example D-Wave) look for the energy minimum physically, using quantum effects. Whether and when they are faster than classical algorithms is still a subject of research.

Example — temperature when choosing the next word

A model gives three candidates for the next word the scores z = (z₁, z₂, z₃) = (2, 1, 0). At temperature T > 0 the probability of the i-th word (i = 1, 2, 3) is

p_i = exp(z_i/T)/∑_j=1³ exp(z_j/T)

p_i

the probability that the model chooses the i-th word

exp(z_i/T)

the weight of the word — the Boltzmann weight from the section on annealing, just with the “energy” −z_i: a higher score, a larger weight

∑_j exp(z_j/T)

the sum of the weights of all candidates; we divide by it so that the probabilities add up to 1

T = 1:   weights (e², e¹, e⁰) = (7.39, 2.72, 1), sum 11.11 → 0.665, 0.245, 0.090

T = 0.5:   weights (e⁴, e², 1) = (54.6, 7.39, 1), sum 62.99 → 0.867, 0.117, 0.016

T = 2:   weights (e¹, e^0.5, 1) = (2.72, 1.65, 1), sum 5.37 → 0.506, 0.307, 0.186

for example at T = 1: p₁ = 7.39/11.11 = 0.665

A lower temperature shifts the probability towards the best candidate (at T → 0 it is always that one), a higher one spreads it to less likely words too — just as annealing at a high temperature accepts worse routes as well.

10. Summary

• An optimization problem looks for the solution with the best value of the objective function; local search moves through the neighbourhood of the current solution.
• Hill climbing always goes to a better neighbour and gets stuck in a local minimum — on the regional capitals in 39 out of 100 starts. Random restarts help with small problems.
• Simulated annealing also accepts worse steps, with probability exp(−Δ/T); as the temperature drops, it moves from exploration to descent.
• On the regional capitals it found the optimum in 98 out of 100 runs; on a larger problem it beat hill climbing with the same budget.
• The same Boltzmann formula lives on in the temperature of language models, and the idea of cooling in the learning-rate schedules of neural networks.

Want to get your hands on it? Have an AI agent write annealing for a route of your own — say through the places you want to visit this summer — and see what cooling too fast does.

Do you see it differently? Write to support@coden-app.com.