Simulated Annealing (SciPy)

Thermodynamic-Inspired Global Optimizer

← Back to Optimizer Competition
Simulated Annealing (Kirkpatrick et al. 1983) is a probabilistic optimization technique inspired by metallurgical annealing. HumpDay's SimulatedAnnealing follows the two-stage pattern of scipy's dual_annealing:
  1. Stage 1 — multi-restart Metropolis SA explores globally with a geometric cooling schedule. Uphill moves are accepted with probability exp(-(f_new - f) / T); restarts give the algorithm multiple shots at finding the basin.
  2. Stage 2 — L-BFGS-B polish refines the SA best to high precision. scipy uses L-BFGS-B at this stage; HumpDay uses the same (with FD gradients).

HumpDay's SA at a glance

  • Budget split: 50% SA exploration, 50% L-BFGS-B polish. Tuned to match scipy.dual_annealing on Rosenbrock.
  • Cooling: geometric, computed so that T_final / T_initial = (final/initial)1/trials_per_restart. Starts at T=1.0, ends at T=1e-6.
  • Restart structure: max(3, sa_budget // 30) restarts. First restart starts near the cube centre; subsequent restarts start uniformly at random.
  • Proposal: step size scales with current temperature (step = 0.4 · T), uniform per coordinate.

Interactive 3D Visualization

See Simulated Annealing in action on 3D optimization surfaces:

Loading 3D visualization...

Requires WebGL support

Instructions: Choose a test function and algorithm, then click Start to watch the step-by-step optimization process.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.
  • Overhead tier 1: light (~100µs/iter). Eligible when measured eval_time ≥ 10 µs.
  • Dimensional cap: no cap — linear-in-dim or better.
  • Minimum trials: 10 — baseline minimum.

Implementation Details

Component Details Links
Original Algorithm Kirkpatrick, Gelatt & Vecchi
Probabilistic optimization inspired by statistical mechanics
Temperature-controlled acceptance of uphill moves
Published: 1983 		Original Paper
Reference Implementation SciPy optimize.dual_annealing
Dual annealing with generalized SA algorithm
scipy.optimize.dual_annealing()
Package: scipy 		SciPy Docs Source
HumpDay Python HumpDay SimulatedAnnealing
Multi-restart Metropolis SA with geometric cooling, then L-BFGS-B polish from the best SA point.
Pure Python; no required dependencies.
File: humpday/optimizers/evolutionary_algorithms.py 		Source
HumpDay JavaScript Browser SimulatedAnnealing
Mirrors the Python port: multi-restart SA + L-BFGS-B polish. Used in the contest and the in-browser visualizer.
Class: SimulatedAnnealing 		JS Port

Performance characteristics

  • Best for: Multimodal continuous objectives where temperature-controlled uphill moves matter. The L-BFGS-B polish closes the residual to scipy-level precision on smooth basins.
  • Worst for: Problems where global exploration is a waste and budget would be better spent on a single basin (PRIMA / CMA-ES territory).
  • Per restart: trials_per_restart Metropolis proposals. Each proposal is one evaluation; uphill accepts depend on temperature.
  • Relative to scipy.dual_annealing at n_trials=200, n_dim=2: ties on sphere; wins on Ackley; loses on Rosenbrock (scipy's polish is unbudgeted, ours is not). See SOTA status for the live numbers.

Educational Resources

Algorithm Components

  • Temperature Schedule: T(k) = T₀ × α^k (geometric cooling)
  • Metropolis Criterion: P(accept) = exp(-ΔE/T) if ΔE > 0
  • Neighborhood Function: Local perturbation strategy
  • Initial Temperature: T₀ set to accept ~80% of moves initially
  • Stopping Criteria: Temperature threshold or equilibrium detection

️ Cooling Schedules

  • Linear: T(k) = T₀ - α × k
  • Geometric: T(k) = T₀ × α^k (most common)
  • Logarithmic: T(k) = T₀ / log(1 + k)
  • Exponential: T(k) = T₀ × exp(-α × k)
  • Adaptive: Temperature adjusted based on acceptance rates

SA Variants

  • Classical SA: Single-point neighborhood search
  • Fast SA: Modified acceptance probability for faster cooling
  • Very Fast SA: Cauchy distribution for neighbor generation
  • Parallel SA: Multiple chains with periodic communication
  • Hybrid SA: Combined with local search or GA

Applications

  • Traveling Salesman: Classic combinatorial optimization
  • VLSI Design: Circuit layout and placement
  • Scheduling: Job shop and resource allocation
  • Image Processing: Image restoration and segmentation
  • Protein Folding: Molecular conformation prediction
  • Network Design: Communication and transportation networks

Theoretical Foundation

  • Statistical Mechanics: Boltzmann distribution and thermal equilibrium
  • Markov Chains: Detailed balance and ergodicity
  • Convergence Theory: Asymptotic convergence under logarithmic cooling
  • Finite-Time Analysis: Approximation guarantees for practical schedules

️ Parameter Tuning

  • Initial Temperature: Set to accept 80-95% of initial moves
  • Cooling Rate: α = 0.85-0.95 for geometric schedule
  • Markov Chain Length: Number of moves at each temperature
  • Final Temperature: Stop when T < 0.01 × initial cost variance