Simulated annealing (SA) is a stochastic optimization algorithm inspired by the metallurgical process of annealing, where a material is heated to a high temperature and then slowly cooled to reach a low-energy crystalline state. In optimization terms, SA explores a search space by accepting both improving and worsening moves early on (at “high temperature”), then gradually tightening acceptance to converge toward a global optimum. This ability to escape local optima makes SA especially valuable for non-convex, combinatorial, and black-box optimization problems where gradient-based methods cannot be applied.
First introduced by Kirkpatrick, Gelatt, and Vecchi in their landmark 1983 Science paper “Optimization by Simulated Annealing,” the algorithm has become one of the foundational metaheuristics in computer science. For AI engineers, SA is directly relevant to hyperparameter tuning, quantization configuration search, neural architecture search, expert routing optimization, and any setting where the objective function is expensive to evaluate and the search space is discrete or mixed.
SA sits at the intersection of classical optimization and modern AI engineering. It is simple to implement, requires no gradients, and can be applied to virtually any problem where you can define a cost function and a neighborhood structure. While more sophisticated methods (Bayesian optimization, evolutionary strategies) have surpassed SA for some applications, SA remains a practical baseline and a powerful component in hybrid optimization pipelines.
SA maintains a single candidate solution and iteratively proposes modifications. At each step, it decides whether to accept or reject the proposed change based on the change in cost and the current “temperature”:
# Simulated Annealing pseudocode
import math, random
def simulated_annealing(initial_solution, cost_fn, neighbor_fn,
T_start=100.0, T_min=1e-4, alpha=0.995,
steps_per_temp=100):
current = initial_solution
current_cost = cost_fn(current)
best, best_cost = current, current_cost
T = T_start
while T > T_min:
for _ in range(steps_per_temp):
candidate = neighbor_fn(current)
candidate_cost = cost_fn(candidate)
delta = candidate_cost - current_cost
# Accept if better, or with probability exp(-delta/T) if worse
if delta < 0 or random.random() < math.exp(-delta / T):
current, current_cost = candidate, candidate_cost
if current_cost < best_cost:
best, best_cost = current, current_cost
T *= alpha # Cool down
return best, best_costThe probability of accepting a worse solution is P(accept) = exp(−ΔE / T), derived from statistical mechanics. At high temperature, exp(−ΔE / T) ≈ 1, so nearly all moves are accepted (broad exploration). As T → 0, the probability drops to zero and only improving moves are accepted (pure hill climbing). This temperature-controlled transition from exploration to exploitation is the heart of SA.
The cooling schedule determines how temperature decreases over time and is the most critical design choice in SA. Common schedules include:
T(t+1) = α × T(t), where α ∈ [0.9, 0.999]. Most widely used due to simplicity. A typical choice is α = 0.995.T(t) = T₀ − β × t. Simple but can cool too fast in the early stages when exploration is most valuable.T(t) = T₀ / ln(1 + t). Theoretically guarantees convergence to the global optimum (Hajek 1988), but impractically slow.The initial temperature T₀ should be high enough that roughly 80–90% of proposed moves are accepted at the start, ensuring thorough exploration. A practical approach: run a short warm-up phase, compute the average cost difference Δ̄ over random moves, and set T₀ = −Δ̄ / ln(0.8) to achieve ~80% initial acceptance.
The neighbor_fn defines how candidate solutions are generated from the current one. Good neighborhoods produce moves that are “close” in the search space but can reach any solution through a sequence of steps. Examples:
Gradient descent follows the steepest downhill direction and gets trapped in the nearest local minimum. SA can escape local minima by accepting uphill moves with a probability that decreases over time. This makes SA suitable for problems where the loss landscape is rugged, multimodal, or where gradients are unavailable (black-box optimization). The tradeoff: SA is much slower than gradient descent for smooth, differentiable objectives.
SA can efficiently search large, mixed (continuous + discrete + conditional) hyperparameter spaces. Unlike grid search (exponentially expensive) or random search (no exploitation), SA balances exploration and exploitation. In practice, SA-based hyperparameter search often finds good configurations in fewer evaluations than random search, though Bayesian optimization (e.g., Optuna’s TPE sampler) is now more common for this use case.
When quantizing a model, different layers may tolerate different bit-widths. Finding the optimal per-layer quantization config (e.g., which layers get 4-bit vs. 8-bit) is a combinatorial problem with an expensive evaluation function (measuring perplexity). SA is well-suited here: the search space is discrete, the objective is non-differentiable, and each evaluation is costly — exactly the conditions where SA’s controlled exploration pays off.
SA can navigate the space of network architectures (number of layers, hidden dimensions, activation functions, skip connections) to find efficient architectures. While evolutionary methods and reinforcement learning are more common for NAS, SA provides a simpler baseline that requires tuning fewer meta-parameters.
In Mixture of Experts models, the assignment of tokens to experts during inference can be framed as a combinatorial optimization problem. SA-inspired approaches have been explored for optimizing load balancing across experts, particularly in offline batch-inference scenarios where the entire batch is known ahead of time.
SA remains a strong baseline for classic NP-hard problems: Traveling Salesman (TSP), graph coloring, job-shop scheduling, VLSI circuit placement, and vehicle routing. Many commercial logistics and scheduling solvers include SA as a core component or as a diversification mechanism within larger hybrid algorithms.
α ∈ [0.99, 0.999] is the practical default.