Simulated Annealing

The core decision rule that determines whether a new candidate solution is accepted. If the new solution is better, it is always accepted. If it is worse, acceptance probability is calculated as:

P(accept) = exp(-ΔE / T)

• ΔE: The difference in objective function value (new_cost - current_cost)
• T: The current temperature parameter

At high temperatures, the algorithm accepts significantly worse solutions, enabling broad exploration. As T approaches zero, the probability of accepting an uphill move vanishes, and the search becomes a greedy descent.

The cooling schedule dictates how the temperature parameter T is reduced over time and is the most critical hyperparameter for convergence.

Common schedules include:

• Exponential decay: T_k = α * T_{k-1} where α is typically 0.85 to 0.99
• Logarithmic decay: T_k = T_0 / log(1 + k), proven to guarantee convergence to the global optimum given infinite time
• Linear decay: T_k = T_0 - η * k

A schedule that cools too quickly causes premature convergence to a local optimum (quenching). Cooling too slowly wastes computational resources.

The mechanism that generates a new candidate solution by perturbing the current state. The design of this function is problem-specific and must ensure the search space is connected.

For the Traveling Salesman Problem (TSP):

• 2-opt swap: Reverse a subsequence of the tour
• Node swap: Exchange the positions of two cities
• Insertion: Remove a city and reinsert it at a different position

The perturbation magnitude should be calibrated so that the expected change in objective value is comparable to the current temperature, maintaining a reasonable acceptance rate.

Simulated annealing is theoretically guaranteed to converge to the global optimum under specific conditions, proven via Markov chain analysis.

Required conditions for convergence:

• The neighborhood structure must be strongly connected (any state reachable from any other)
• The cooling schedule must satisfy T_k ≥ T_0 / log(1 + k) for sufficiently large T_0
• An infinite number of iterations at each temperature level

In practice, these conditions are relaxed, and the algorithm provides a high-quality approximate solution in finite time. The Boltzmann distribution governs the probability of occupying each state at thermal equilibrium.

Simulated annealing fundamentally differs from greedy local search by its ability to escape local optima.

Hill Climbing (Greedy Descent):

• Only accepts moves that improve the objective
• Traps at the first local optimum encountered
• Deterministic given a fixed starting point

Simulated Annealing:

• Accepts worsening moves probabilistically
• Can traverse valleys to reach better peaks
• Stochastic; multiple runs yield different paths

This makes simulated annealing suitable for rugged, non-convex fitness landscapes with many deceptive local optima, such as VLSI circuit placement and protein folding.

Effective deployment requires careful tuning of three interdependent parameters.

Key parameters:

• Initial temperature (T_0): Set high enough that approximately 80% of proposed moves are initially accepted. A common heuristic is to run a short pilot phase and set T_0 based on the observed distribution of ΔE values.
• Markov chain length: The number of iterations at each temperature step before cooling. Should be proportional to the neighborhood size.
• Termination criterion: Stop when the system appears frozen—typically when the acceptance ratio drops below a threshold or the objective value has not improved for several temperature steps.

Adaptive schedules dynamically adjust the cooling rate based on acceptance statistics, reducing the need for manual tuning.

A population-based metaheuristic inspired by natural selection. Unlike simulated annealing's single-solution trajectory, genetic algorithms maintain a population of candidate solutions, applying crossover (recombination) and mutation operators to evolve toward optima.

• Key Difference: Explores multiple regions of the search space simultaneously via parallel populations
• Strength: Naturally handles multi-objective optimization and discrete/continuous hybrid spaces
• Weakness: Requires careful tuning of selection pressure, crossover rate, and population size
• Example: Evolving optimal warehouse layouts where the fitness function evaluates throughput and storage density

The broader class to which simulated annealing belongs. Stochastic optimization methods deliberately inject randomness into the search process to escape local optima or handle objective functions corrupted by statistical noise.

• Random Restarts: Periodically resetting the search from new random starting points
• Stochastic Gradient Descent (SGD): Uses noisy gradient estimates from data batches
• Simulated Annealing: Uses thermal noise controlled by a cooling schedule
• Application: Optimizing supply chain parameters when demand forecasts have quantified uncertainty distributions

An exact algorithm for discrete and combinatorial optimization that systematically partitions the search space and computes upper and lower bounds on the objective. Unlike simulated annealing, it guarantees global optimality but may require exponential time.

• Bounding: Prunes entire subregions whose lower bound exceeds the current best-known solution
• Branching: Recursively divides the feasible region into smaller subproblems
• Contrast with SA: Exact but intractable for large instances; SA is approximate but scalable
• Example: Solving small to medium Vehicle Routing Problems to proven optimality for benchmarking heuristic methods

A sequential model-based approach for optimizing expensive black-box functions. It builds a probabilistic surrogate model (typically a Gaussian Process) of the objective and uses an acquisition function to decide where to sample next, balancing exploration and exploitation.

• Surrogate Model: Approximates the true objective and quantifies prediction uncertainty
• Acquisition Functions: Expected Improvement (EI), Upper Confidence Bound (UCB), Probability of Improvement (PI)
• Contrast with SA: Sample-efficient for costly evaluations; SA requires many cheap evaluations
• Application: Tuning hyperparameters of a deep demand forecasting model where each training run costs hours of GPU time

Algorithms that require first-order derivative information (gradients) of the objective function to iteratively move toward a local minimum. Includes Gradient Descent, Adam, and L-BFGS. Simulated annealing is derivative-free, making it applicable when gradients are unavailable, unreliable, or non-existent.

• Requirement: Objective must be differentiable and gradients computable
• Convergence: Fast local convergence to the nearest stationary point
• Limitation: Trapped by local minima in non-convex landscapes
• Hybrid Approach: Use gradient methods for fine-tuning after SA identifies a promising basin of attraction

A declarative paradigm where relations between variables are expressed as constraints, and a solver finds feasible solutions using propagation and search. Unlike simulated annealing's numerical objective landscape, CP excels at highly constrained combinatorial problems with logical relationships.

• Constraint Propagation: Deduces variable domain reductions from partial assignments
• Global Constraints: Specialized algorithms for common patterns like all_different or cumulative
• Complementary Use: CP finds feasible schedules; SA optimizes an objective over those schedules
• Example: Assigning delivery time windows while respecting driver hours-of-service regulations, then using SA to minimize total mileage