Concept Architecture
Concept
Theoretically, Simulated Annealing is a stochastic global optimisation algorithm inspired by the physical annealing process used in metallurgy, whereby a material is heated and slowly cooled to achieve a low-energy crystalline state. It is founded on statistical mechanics and probabilistic optimisation, allowing occasional acceptance of inferior solutions to escape local optima during the search process. The method exists to solve complex optimisation problems with large, nonlinear, discontinuous or multimodal solution spaces in which deterministic optimisation methods may become trapped in local optima. In health economics, it is used for model calibration, parameter estimation and resource allocation problems involving complex objective functions.
Mathematically, simulated annealing formulates optimisation as a stochastic search process in which candidate solutions are generated iteratively. Inferior solutions are accepted with a probability determined by the Metropolis acceptance criterion, which decreases as the temperature parameter is gradually reduced according to a cooling schedule. As the temperature approaches zero, the algorithm increasingly favours improvements and converges towards a near-optimal solution.
In practice, simulated annealing is implemented by defining an objective function, selecting an initial solution, specifying a cooling schedule and neighbourhood search strategy, and iteratively evaluating candidate solutions until convergence criteria are satisfied. In health economics it is applied to calibrating disease progression models, fitting transmission models, optimising healthcare resource allocation, estimating model parameters and solving complex decision-analytic optimisation problems.
Purpose
Used to identify near-global optimal solutions for complex health economic optimisation problems by combining stochastic search with controlled probabilistic acceptance of inferior solutions.
Mathematical Formulae
Primary Formula
Metropolis acceptance probability:
P(accept) = exp(??E/T)
where:
- ?E = f(x??w) ? f(xc??????) is the change in the objective function
- T = current temperature
For minimisation, if ?E � 0, the new solution is accepted unconditionally.
Supporting Formulae
Cooling schedule:
T??? = �T?, 0 < � < 1
Objective function:
min? f(x)
Related Mathematical Methods
- Stochastic optimisation
- Global optimisation
- Numerical optimisation
- Metaheuristic optimisation
- Particle swarm optimisation
- Genetic algorithms
- Markov chain Monte Carlo
- Model calibration
Example
A health economist calibrates a disease transmission model by minimising the sum of squared differences between observed and predicted infection counts.
The initial objective function value is
f(x) = 18.6.
A candidate solution produces
f(x) = 19.4,
so
?E = 0.8.
If the current temperature is
T = 5,
the acceptance probability is
P = exp(?0.8/5) = 0.852.
The inferior solution is therefore accepted with probability 0.852, allowing the search to escape local optima. As the temperature decreases, acceptance of inferior solutions becomes progressively less likely until convergence is achieved.
Excel Implementation
| Function | Example Formula | Health Economics Application |
|---|---|---|
| EXP | =EXP(-(B2-C2)/D2) | Calculates the Metropolis acceptance probability. |
| RAND | =RAND() | Generates random numbers for probabilistic acceptance decisions. |
| IF | =IF(RAND()<EXP(-(B2-C2)/D2),""Accept"",""Reject"") | Determines whether a candidate solution is accepted. |
| Solver Add-in | Compares deterministic optimisation results | Benchmarks optimisation performance against simulated annealing. |
VBA (Optional)
A VBA procedure can automate simulated annealing by generating candidate solutions, applying the cooling schedule, evaluating acceptance probabilities and recording the best solution throughout the optimisation process.
Sources
- Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by Simulated Annealing. Science. 1983;220(4598):671?680.
- ?ern? V. Thermodynamical Approach to the Travelling Salesman Problem. Journal of Optimization Theory and Applications. 1985;45(1):41?51.
- Briggs A, Claxton K, Sculpher M. Decision Modelling for Health Economic Evaluation. Oxford University Press.
- Drummond MF, Sculpher MJ, Claxton K, Stoddart GL, Torrance GW. Methods for the Economic Evaluation of Health Care Programmes. Oxford University Press.
- NICE. Health Technology Evaluation Manual.
- ISPOR Good Practice Reports on decision-analytic modelling.
Related Concepts (2)
Library
Publications
1
A Taxonomy of Model Structures for Economic Evaluation of Health Technologies — Brennan, Chick & Davies, Vol. 15, No. 12 ed., 2006 (Health Economics)
An influential paper classifying decision-analytic model structures along axes of expected value vs randomness, entity heterogeneity, and Markovian vs non-Markovian structure — providing a framework for choosing between decision trees, Markov cohort models, microsimulation, discrete event simulation and system dynamics.
Journal ArticleView source →
Frequently Asked Questions (6)
What is simulated annealing?
An optimisation technique modelled on slowly cooling metal, occasionally accepting worse solutions during search to avoid becoming trapped in a poor local solution.
Source: Kirkpatrick, Gelatt & Vecchi 1983
What is simulated annealing modelled on?
The method is modelled on the way a metal is cooled slowly to reach a low-energy, well-ordered state. Heating lets atoms move freely, and gradual cooling lets them settle into a stable arrangement rather than freezing into a flawed one. The algorithm imitates this by allowing its search to move to worse solutions often at first and less as a notional temperature falls, so it can escape poor local solutions early and settle near a good one later. Kirkpatrick and colleagues (1983) introduced it.
Source: Kirkpatrick et al. 1983
How does simulated annealing work?
Simulated annealing works by starting from an initial solution and a high temperature, then repeatedly proposing random changes: a change that improves the objective is always accepted, while one that worsens it is accepted with a probability that depends on how much worse it is and on the current temperature. As the search proceeds, the temperature is gradually lowered, so worse moves become less likely to be accepted. This cooling schedule lets the method explore widely at first and converge toward a good solution as it settles.
Source: Kirkpatrick, Gelatt & Vecchi 1983
Why does simulated annealing accept worse solutions?
Simulated annealing accepts worse solutions occasionally to avoid becoming trapped in a local optimum, which methods that only ever improve can fall into. By sometimes moving to a worse solution, it can climb out of a local optimum and reach a better region of the space. The probability of accepting worse moves is high early, allowing broad exploration, and falls as the temperature decreases, so the search increasingly favours improvement. This controlled acceptance of worse moves is what lets it seek a global rather than merely local optimum.
Source: Kirkpatrick, Gelatt & Vecchi 1983
What is the role of the cooling schedule in simulated annealing?
The cooling schedule in simulated annealing controls how the temperature, and hence the probability of accepting worse moves, decreases over the search. A high initial temperature permits wide exploration, and gradual cooling narrows the search toward improvement as it proceeds. The schedule matters: cooling too fast can trap the search in a local optimum, while cooling too slowly wastes computation. Choosing an appropriate cooling schedule balances thorough exploration against efficient convergence, and it is important to the method's success.
Source: Kirkpatrick, Gelatt & Vecchi 1983
When is simulated annealing used?
Simulated annealing is used for difficult optimisation problems with many local optima, where methods that only improve would get stuck, and where a good global solution is sought. It is derivative-free, using only objective values, so it suits problems that are non-smooth, combinatorial, or defined by a simulation. It is applied to scheduling, layout, and other complex combinatorial problems, and in modelling to search difficult landscapes. Its ability to escape local optima makes it valuable where simpler methods fail, at the cost of many evaluations.
Source: Kirkpatrick, Gelatt & Vecchi 1983
Trust Record
Verified by Dr Darrin Baines
British health economist
Professional identity: darrinbaines.org
Verification date: 3 Oct 2025
Content version: 1.0.0
Canonical Identity
- Persistent URI
- https://healtheconomics.wiki/concept/simulated-annealing
- Term code
- HE-EM-DM-090
Stable URI · Machine-readable · Resolvable · CC BY 4.0