Winning Kaggle the Reproducible Way

Chapter 54

Combinatorial Optimization

Calibrate the starting temperature from sampled moves, and compare schedules and starts under one budget.

A fixed tour is scored directly, so the work is search. One demonstration anneals 150-city tours under a fixed budget of evaluated moves and measures how the starting temperature, solved from a target acceptance, and the starting tour change the final length.

Every example is constructed for teaching. Its numbers come from running the chapter activity's code, not from a competition result.

Demonstration 1 of 1

Simulated annealing under a fixed budget: starting temperature and starting tour

With a fixed number of evaluated moves, does a hotter starting temperature or a better starting tour give the shorter final tour?

Annealing accepts a worsening move with probability exp(-delta/T). From a nearest-neighbour tour, which is already decent, a hot start throws away that quality and the fixed budget is too short to rebuild it, so colder is better. From a random tour the search must build structure itself: the two low settings (0.01 and 0.1) end within noise of each other, and every hotter start wastes more of the budget. Setting T from the mean worsening delta, rather than solving for the acceptance, misses the target, most of all at cold settings.

Equation: the probability of accepting a move is the minimum of 1 and e to the power of minus delta over T; the mean acceptance a of T is the average over m sampled worsening deltas of e to the power of minus delta s over T

Scroll sideways for the whole equation

delta is the increase in tour length of a worsening move, T the temperature and a the mean acceptance probability of sampled worsening moves. The score divides the final length by the nearest-neighbour tour length, so values below 1 mean the search improved on the constructive tour.

Predict first. Starting simulated annealing from the nearest-neighbour tour, which target acceptance gives the shortest final tour under 60,000 moves?

Your prediction

Choose an example

Scroll sideways for the whole figure

Figure: Simulated annealing under a fixed budget: starting temperature and starting tour. Left: final tour length relative to the nearest-neighbour tour at a target acceptance of 0.50, 0.904 from a random start and 0.925 from the nearest-neighbour start. Right: the target acceptance 0.50 against the acceptance 0.536 that setting T from the mean worsening delta gives.
Target starting acceptance of a worsening move: 0.5
Constructed example: eight seeded random 150-city instances, annealed with 2-opt moves under a fixed budget, measured by the chapter activity.

Calculated values

Random start, final / NN length
0.904
Nearest-neighbour start, final / NN length
0.925
Saving of the better start
0.096
Naive-T acceptance
0.536
Solved T0, random start
4.21 edges

With a target acceptance of 0.50 and 60,000 moves, annealing from a random tour ends at 0.904 of the nearest-neighbour length and from the nearest-neighbour tour at 0.925, so the random start is shorter and 1 - 0.904 = 0.096 is the saving over no search. The temperature solved for this acceptance is 4.21 mean edge lengths for the random tour and 14.80 for the nearest-neighbour tour. Setting T from the mean worsening delta gives an acceptance of 0.536 instead of 0.50.

Worked steps

  1. Random start against nearest-neighbour start: 0.904 - 0.925 = -0.021 (negative means random is shorter).
  2. Saving of the better start over no search: 1 - 0.904 = 0.096.
  3. Naive temperature: acceptance 0.536 - target 0.50 = +0.036.
  4. Solved temperature for the random and the nearest-neighbour start: 4.21 and 14.80 mean edges.

Use the idea

Sample worsening moves from the starting tour, solve the temperature for a chosen acceptance, then compare a few acceptances and both starts under the same evaluation budget before spending more compute on one.

Where the conclusion applies

Constructed random Euclidean instances of 150 cities, 2-opt moves only and one cooling shape (geometric to a fixed final temperature); a longer budget, Or-opt moves or a different final temperature would move every number. Lengths are relative to the nearest-neighbour tour, a named reproducible baseline, since no proved optimum is computed here. Only the coldest start is close to plain greedy 2-opt descent. The nearest-neighbour construction itself (about 11,000 distance lookups, roughly the cost of 2,800 move evaluations) is not charged to the budget.

Check your understanding: What does solving the temperature for a target acceptance buy, and why does the nearest-neighbour start still need a lower target?
A temperature is in units of tour length, so a copied constant means different things on different instances; an acceptance is scale-free. It is not neutral across starts, though: random moves sampled from a good tour break short edges and are large, so the same acceptance of 0.5 solves to 14.8 mean edge lengths from the nearest-neighbour tour against 4.2 from a random one. The nearest-neighbour start therefore needs a much lower target acceptance to keep the quality it starts with.

Chapter 54 source: section "Simulated Annealing: The Most Robust Starting Point".