optional · interactive figures

Explore: local search and annealing

2-opt moves replayed from the reference solution, and an annealing run you can scrub through with its temperature.

optional: nothing in the lab depends on itback to the slides

26 · explore

2-opt, one move at a time

Try: step through the six cities, then the twelve from a random tour and from nearest neighbour; compare how many moves each needs. Static version: 2-opt on six cities.

What it shows. Every improving 2-opt move, in the order the reference two_opt(dist, tour, neighbours, dont_look=False) applies them: dashed red, the two edges removed; thick, the two added; then the stretch between is reversed. The replay calls the reference two_opt_move and _reverse, and slides/viz/traces/u26.py checks that it ends at the same length as two_opt itself. Distances are rounded Euclidean, neighbour lists of 5.

Six cities: the slide's crossing tour, one move, 24 → 20.
Twelve cities, random start: eleven moves, 473 → 235. Early moves remove long crossings and gain a lot; late ones gain a few units.
Twelve cities, nearest-neighbour start: two moves, 288 → 235, the same local optimum here. A good construction leaves local search little to do, which is why real codes start from one.

26 · explore

An annealing run, and its temperature

Try: drag the iteration slider through the hot run, then the cold one; set Δ to the mean edge (46) and watch its acceptance fall as T cools. Static version: one worsening move.

What it shows. One simulated-annealing run on twenty cities, 4 000 iterations, geometric cooling. The curve is the current tour length (sampled every 25 iterations), the grey curve the temperature on a log scale, and the tour on the left is the tour at the chosen iteration. The run replays the reference simulated_annealing's random draws with the reference accept and temperature, and the best length is checked against the reference function with the same seed.

Hot start ($T_0 = 100$, about twice the mean edge of 46): for the first quarter the length barely falls, because most worsening moves are accepted. It wanders, then settles.
Cold start ($T_0 = 1$): nearly plain descent, a handful of worsening moves accepted in the whole run. It gets to 347, the hot run to 348; on an instance this small plain 2-opt reaches 347 too, so the lesson here is the shape of the curves, not a winner.
The acceptance line is $e^{-\Delta/T}$ at the chosen iteration's recorded $T$, the Metropolis rule of the slides: at $T = 2$ a move costing 4 has probability 0.135.