Suppose every small change to a delivery route makes it longer, yet a much shorter route exists elsewhere. A downhill-only search cannot reach it without first accepting a worse route. Simulated annealing makes that uphill move possible: it explores candidate solutions randomly, accepts improvements, and sometimes accepts worse candidates. As its temperature falls, worsening moves become less likely, shifting the search toward refinement. section 17.1.1 section 17.1.3
Listing 17.1 A generic implementation of simulated annealing
function simulatedAnnealing(C, P0, T0, acceptance, maxSteps) #1
for k in {1..maxSteps} do #2
T ← temperature(T0, k, maxSteps) #3
P ← randomStep(P0.clone(), T) #4
if acceptance(C(P), C(P0), T) > randomFloat(0,1) then #5
P0 ← P
return P0
The generic loop takes a cost function, starting solution, initial temperature, acceptance rule, and step limit. Each iteration sets the temperature, proposes a candidate, compares costs, and probabilistically replaces the current solution. section 17.1.2
To adapt the loop to a problem, define and tune its moving parts:
- Choose a cost function that scores each candidate. Because it is evaluated repeatedly, an expensive score limits how many iterations are practical. section 17.1.6
- Define a valid random transition for the solution space. Favoring nearby moves can speed local refinement; retaining occasional long-range moves helps avoid trapping the search. section 17.1.2 section 17.1.4
- Accept lower-cost candidates; give higher-cost candidates a probability that depends on both the cost increase and temperature. Calibrate the rule so early exploration is permissive and late exploration is selective. section 17.1.3
- Set a cooling schedule and iteration budget. A common schedule periodically multiplies temperature by α, where 0 < α < 1; tune α and the update interval for the problem. section 17.1.4
Delivery routes as traveling-salesperson tours
Represent a tour as a permutation of stops and score it by summing consecutive edge weights, including the edge back to the start. Possible transitions include swapping adjacent stops, swapping any pair, or generating a new permutation. Adjacent swaps refine locally but may require several worsening moves to reach an improvement available in one unrestricted swap. Experiments with these transitions and cooling rates illustrate why the update rule must be measured rather than assumed best. section 17.2.4 section 17.2.5
Drawing a graph with fewer crossings
For a straight-line graph embedding, score a drawing by counting intersecting edges and propose a new drawing by moving a vertex within the allowed area. Begin with a simple movement rule, then measure whether changes improve convergence. A broader drawing objective can also combine crossing count with vertex spacing, edge lengths, and distance from the drawing boundary. section 17.3.1 section 17.3.2
Use simulated annealing when the search space is discrete, the cost is step-shaped or nondifferentiable, or local minima frustrate gradient descent. It generally takes more iterations than gradient descent on an easy landscape and does not guarantee an optimum; narrow valleys can also be hard to find. Keep the best solution seen if the final move might leave a better one behind. With a fixed iteration limit, work scales with the number of iterations times candidate generation and cost evaluation; storing the best candidate adds another solution state. section 17.1.6 section 17.1.5
