Does simulated annealing always find the global optimum?

No practical finite-budget run has that general guarantee.

Is a higher temperature always better?

No. It permits more exploration but can also spend effort accepting poor moves.

Does it need derivatives?

The basic neighbor-and-acceptance procedure does not require objective derivatives.

AI Glossary / Graphs and symbolic AI / Intermediate

Simulated annealing

Definition

Simulated annealing is a randomized optimization method that sometimes accepts a worse candidate solution to escape local optima. A control parameter called temperature regulates this willingness. The temperature is reduced according to a cooling schedule, so the search usually becomes less accepting of worsening moves as it proceeds.

What it means

Many optimization tasks contain locally attractive solutions that are not globally best. If a search accepts only immediate improvements, it may become trapped because every nearby alternative is worse. Simulated annealing permits selected uphill cost moves, creating a chance to reach a better region later.
Temperature is a mathematical control parameter, not a physical temperature in the application being optimized. Its numerical scale must be interpreted relative to the objective's scale. The method can be applied to discrete choices or continuous parameters, but its effectiveness depends strongly on how neighboring candidates are proposed and how constraints are handled.

How it works

For a common minimization version, start with a feasible candidate and positive temperature T. Propose a neighbor and calculate Δ = new cost − current cost. Accept an improvement; for a worsening move, accept with probability exp(−Δ/T). Draw a random number to implement that probabilistic decision.
Repeat, lower the temperature according to the schedule, and stop under a specified budget or rule. Keep the best feasible solution seen separately from the current state. This description uses the standard simple acceptance rule; specialized proposal mechanisms and implementations can require additional details. The cooling schedule and neighborhood are part of the algorithm's specification.

Three practical examples

A scheduling prototype can swap job positions and occasionally accept a higher temporary penalty while seeking a better complete schedule.
A layout optimizer can move elements between feasible positions to explore arrangements beyond its initial local minimum.
A teaching model can compare strictly improving local search with a method that sometimes crosses a cost barrier.

Think of it this way

Think of exploring valleys in a landscape while sometimes climbing a ridge to investigate another valley. Early exploration tolerates larger climbs; later exploration becomes more cautious. The analogy is limited because a mathematical neighbor may be a rearranged schedule rather than a nearby physical position, and cooling does not guarantee a best result within a practical deadline.

Worked example

Consider an original four-state optimization landscape. States A, B, C, and D form a cycle A - B - C - D - A. Their costs are 10, 12, 5, and 13. From A, both neighbors are worse, so a strictly improving search stops at cost 10 even though C has cost 5.
Suppose simulated annealing proposes B from A at temperature T = 4. The cost increase is Δ = 2, giving acceptance probability exp(−2/4) = exp(−0.5), about 0.6065. A stipulated uniform random draw of 0.50 is below that probability, so the move is accepted. The current cost rises to 12, but the best-so-far cost remains 10.
Next suppose C is proposed from B. Its cost drops from 12 to 5, so it is accepted, and the best-so-far cost becomes 5. This trace illustrates escaping a local minimum; the random choices were chosen for explanation rather than reported as an experiment.
At temperature T = 1, the original A-to-B move would have acceptance probability exp(−2), about 0.1353. The same draw of 0.50 would then reject it. If all costs are multiplied by 10, multiplying temperature by 10 preserves the ratio Δ/T and therefore the same acceptance probability. Changing objective units without adjusting temperature changes search behavior.

Illustrative case study

In a fictional case, Willow Scheduling uses simulated annealing to arrange a demonstration production sequence. Its objective includes setup time and lateness penalties, while hard resource conflicts are excluded from feasible proposals.
The team compares several cooling schedules under the same evaluation budget and records the best feasible cost from every run. It also keeps a simple baseline schedule. One run's strong result does not become a guarantee for future workloads. The exercise illustrates evaluation discipline and contains no claimed real-world savings.

Common misconceptions and mistakes

Accepting a worse state is intentional exploration, not automatically a bug. However, it does not mean that any invalid solution should be accepted: hard constraints need an explicit treatment.
Cooling too quickly can leave the search trapped, while very slow cooling can exceed the available computation budget. Mathematical convergence statements rely on assumptions about the state space, moves, and schedule, and are not finite-time guarantees. The final current state is not necessarily the best state encountered. Also, “uphill” and “downhill” depend on whether the objective is being minimized or maximized.

Business use

For business optimization, first define the objective and distinguish hard feasibility rules from soft preferences. Evaluate the cost of computing a candidate, because expensive evaluations can dominate runtime.
Record the initial solution, proposal rule, temperature schedule, random seed, stopping condition, and best-so-far result. Compare several independent runs and alternatives under comparable budgets. If the objective combines penalties with different units, document their weights; otherwise a temperature setting may be difficult to interpret or reproduce.

Check your understanding

After accepting B at cost 12 in the example, what is the best-so-far cost?

Answer: It remains 10 until the search reaches C. The current state and the best recorded state are different records.

Related terms

Local search
Hill climbing
Global optimization
Objective function
local optimum
Metropolis acceptance rule
cooling schedule
stochastic optimization

Learn next

For a cost increase of 4 at temperature 2, compute exp(−4/2), approximately 0.1353. Compare it with the increase of 2 at temperature 1. Equal Δ/T produces equal acceptance probability in this rule.

Acceptance probability

Sources

Sources: Russell and Norvig, author-hosted AIMA chapter, simulated annealing discussion and pseudocode: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf . Kirkpatrick, Gelatt and Vecchi, Optimization by Simulated Annealing, original paper mirrored by Hedibert Lopes: https://hedibert.org/wp-content/uploads/2013/12/1983KirkpatrickGelattVecchi.pdf .

Previous: Simpson's paradox Next: Simulation-based optimization