Simulated annealing (SA) searches for a low-cost solution by making random moves from one solution to a neighboring one. Picture a hiker seeking the lowest valley without a map: moving uphill occasionally may reveal a lower valley beyond the ridge. SA always accepts an improving move but sometimes accepts a worsening move. Its temperature controls that chance: high temperature encourages exploration; gradual cooling makes the search increasingly selective. It is a single-trajectory, stochastic metaheuristic inspired by physical annealing. section 5.1 section 5.2.1 section 5.7
For a minimization problem, a basic SA run follows these steps:
- Choose an initial solution, an objective function, a way to generate neighboring solutions, an initial and final temperature, a cooling schedule, and iteration limits. section 5.2.2 section 5.2.5
- Generate a neighbor and calculate its cost change, Δf = candidate cost − current cost. Accept it if it improves the cost. section 5.2.2
- If Δf is positive, accept the worse neighbor when a random number from 0 to 1 is less than exp(−Δf/T). A larger cost increase is less likely to pass; a higher temperature makes it more likely. section 5.2.3
- Repeat moves at the current temperature, lower the temperature according to the schedule, and stop at the final temperature or iteration limit. section 5.2.2
Algorithm 5.1 The SA algorithm
Objective function f(x), x = (x_1, . . . , x_p)^T
Initialize initial temperature T_o, initial guess x_o, iteration counter n=0 and iteration per temperature counter k=0
Set final temperature T_f, kmax maximum number of iterations per temperature and max number of iterations N
Define cooling schedule
Begin
While T > T_f and n < N do
While k<k_{max}
Move randomly to a new location/state x_{n+1}
Calculate Δf = f_{n+1}(x_{n+1}) – f_n(x_n)
If the new solution if better then
Accept the new solution
Else
Generate a random number r
Accept if exp(−Δf/T)>r
k=k+1
End
Update T according to the cooling schedule
n = n + 1
End
Return the final solution
The pseudocode puts neighbor generation, the improving-move test, probabilistic acceptance, cooling, and stopping conditions in one loop. section 5.2.2
A hand-worked continuous search
Minimize f(x) = (x − 6)² for 0 ≤ x ≤ 31. Start at x = 2, with cost 16 and temperature T = 5. A Gaussian-generated neighbor x = 2.25 costs 14.06, so accept it. The next candidate, x = 1.18, costs 23.23: its acceptance probability is exp(−(23.23 − 14.06)/5) = 0.1597. A random draw of 0.37 rejects it. After two moves, geometric cooling with factor 0.85 lowers T to 4.25; the search continues from the last accepted solution. section 5.3
The objective and neighbor generator must fit the problem. A continuous variable can take a Gaussian perturbation; a traveling-salesman tour can swap two cities. Start with a relatively high temperature, then cool gradually, but experiment with the initial temperature, schedule, and moves per temperature: suitable settings depend on the problem. Reheating is an option when progress stalls. Python examples use optalgotools’ SimulatedAnnealing; SciPy’s dual_annealing is a separate available function, not the classical algorithm itself. section 5.2.5 section 5.3 section 5.5
From a five-city tour to delivery routing
In a five-city traveling-salesman example, a tour of length 28 becomes length 35 after a swap. That worse tour may be accepted with probability exp(−7/T); a later swap produces a length-18 tour, which is accepted outright. The same approach is applied to 52 Berlin locations and to a delivery route visiting 18 stores. For the delivery route, road-network distances and SA reduce the illustrated route from 593.88 km to 227.17 km. section 5.5 section 5.6
Accepting worse moves helps SA escape some local minima, unlike a search that accepts only improvements. It remains an approximate, derivative-free method: a run may find a useful solution at reasonable computational cost, but it does not guarantee feasibility or a particular degree of optimality. section 5.2.3 section 5.7
