Simulated annealing
Algorithms AIMech:SimulatedAnnealing DRAFT
A stochastic optimization procedure that explores candidate configurations with temperature-controlled acceptance of cost-increasing moves and progressively cools that acceptance process to concentrate search on low-cost configurations.
Identity Notes & Concept Scope
This record denotes the temperature-scheduled optimization procedure exemplified by Kirkpatrick, Gelatt and Vecchi. Its basic symmetric-proposal Metropolis step is distinguished from fixed-temperature target sampling, generic annealing metaphors, training signal annealing and a proof that a particular finite schedule reaches a global minimum. The 1983 article is a primary formulation, not a claim of exclusive invention. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 285 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 15 and 15 lines respectively. Every text hit was a prior candidate lead. Nine exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and seven native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
2 Claims
Mechanism
#method
Choose a representation of feasible configurations, an objective E to minimize, a random rearrangement proposal and an annealing schedule specifying temperatures and work at each temperature. At current configuration x, propose y and compute delta=E(y)−E(x). For the basic symmetric-proposal Metropolis rule at effective temperature T>0 measured in cost units, accept delta<=0 moves and accept delta>0 with probability exp(−delta/T); otherwise retain x. Repeat transitions at the current temperature, then lower temperature according to the schedule. High temperatures permit larger cost-increasing moves more frequently; cooling reduces that probability. The source motivates sufficient equilibration at each stage. Candidate representation, move set and schedule depend on the optimization problem; the returned low-cost configuration is a search result rather than a certified global minimizer.
Limitation
#proposal-and-temperature-scope
Curator qualification by substituting pi_T(x) proportional to exp(−E(x)/T) into Hastings’s Metropolis choice: when the target is proper and the ratio is defined, an asymmetric proposal requires acceptance min(1,exp(−delta/T)*q(x|y)/q(y|x)). The uncorrected exponential rule follows when the proposal ratio cancels. This fixed-temperature construction does not establish finite-schedule equilibration or annealing convergence.
⚠️ Curated Limitations & Negative Results
- The exp(−delta/T) expression is for positive effective temperature with the physical Boltzmann constant absorbed into its cost units. Zero temperature is a limiting or separately defined greedy rule, not evaluation of that quotient at T=0. Equal-cost moves are accepted in the displayed symmetric-proposal rule.
- At fixed T the Boltzmann interpretation requires a proper target and a valid transition construction. Arbitrary asymmetric proposals do not justify dropping the reverse-to-forward proposal ratio. Lowering T changes the target; stationarity for a fixed stage does not imply equilibrium throughout a finite cooling run.
- Positive-temperature uphill acceptance only permits escape through moves supported by the proposal. It does not ensure reaching every state, escaping a local basin in a chosen budget or tracking equilibrium. Rapid cooling can freeze search prematurely; schedule length, cost scale, move connectivity and constraints matter.
- The primary article’s heuristics and empirical scaling claims are not a finite-run global-convergence theorem or a universal complexity bound. The later mathematical conditions for asymptotic annealing convergence were not audited here. No electronic-design or traveling-salesman benchmark is reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MarkovChain
Markov Chain
|
related_match | Simulated annealing uses Metropolis transitions at a sequence of temperatures. The pinned AIO target denotes a stochastic process/model and is exported beneath Network; this algorithm-to-process relation is not equivalence or an is-a assertion. A fixed cooling schedule gives time-dependent transitions, and changing temperature does not preserve a single stationary Boltzmann target throughout the run. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi
|
primary paper
full_text
|
ID: doi:10.1126/science.220.4598.671
sha256:06f76ea70632…
|
proposal-scope
|
W. K. Hastings
|
primary paper
full_text
|
ID: doi:10.1093/biomet/57.1.97
sha256:dc620d3651d3…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T13:05:37Z
Updated: 2026-10-11T13:05:37Z
Source File:
data/curated/SimulatedAnnealing.yaml