Simulated Annealing

The core mechanism that differentiates Simulated Annealing from greedy algorithms like Hill Climbing. At each iteration, the algorithm may accept a new candidate solution that is worse than the current one, with a probability given by the Metropolis criterion: P(accept) = exp(-ΔE / T), where ΔE is the change in solution cost (or energy) and T is the current temperature. This stochastic acceptance allows the search to escape local optima by traversing through valleys in the energy landscape.

The temperature (T) is a control parameter that dictates the exploration-exploitation balance. A high initial temperature encourages widespread exploration (high probability of accepting worse moves). The cooling schedule is a deterministic function that gradually reduces the temperature over time, slowly shifting the algorithm's behavior from exploration to exploitation. Common schedules include:

• Geometric Cooling: T_{k+1} = α * T_k, where α is a constant (e.g., 0.95).
• Linear Cooling: T_{k+1} = T_k - β.
• Logarithmic Cooling: T_{k+1} = T_0 / log(k), which guarantees convergence to the global optimum but is impractically slow.

Under specific theoretical conditions, Simulated Annealing can be proven to converge to the global optimum with probability 1. This guarantee requires an infinitely slow cooling schedule, such as the logarithmic schedule T(k) ≥ C / log(1 + k), where C is a problem-dependent constant. While impractical for finite-time computation, this property establishes it as a global optimization method, unlike purely local search algorithms. In practice, faster cooling schedules are used to find high-quality solutions efficiently.

The algorithm's performance is heavily dependent on how a neighbor is defined for a given solution. The neighborhood structure is the set of all states reachable from the current state by applying a small, predefined perturbation (e.g., swapping two cities in a TSP tour, flipping a bit in a binary string). A well-designed neighborhood should:

• Be efficiently computable.
• Allow the search to traverse the entire state space.
• Provide a smooth gradient for the algorithm to follow. Poor neighborhood design can render the temperature schedule ineffective.

While classically applied to combinatorial optimization problems (e.g., Traveling Salesperson Problem, job scheduling, circuit placement), variants exist for continuous domains. For continuous optimization, the neighborhood move is typically a random step in parameter space, often drawn from a Gaussian distribution. The step size can be annealed alongside the temperature. This makes it a versatile tool for optimizing agent policies, neural network weights, or hyperparameters where gradient information is unavailable or unreliable.

Simulated Annealing is fundamentally linked to MCMC sampling methods. At a fixed temperature T, the sequence of states visited by the algorithm forms a Markov chain whose stationary distribution is the Boltzmann distribution π(s) ∝ exp(-E(s) / T). This means the algorithm spends more time in low-energy (high-quality) states. Annealing can be viewed as running a series of MCMC chains at progressively lower temperatures, gradually focusing the sampling on the deepest minima. This statistical mechanics perspective provides a robust theoretical foundation.

Hill Climbing is a simple local search algorithm and a direct conceptual precursor to Simulated Annealing. It iteratively moves to a neighboring state that improves the objective function value, akin to always climbing uphill.

• Key Difference: Unlike Simulated Annealing, it never accepts worse moves. This makes it highly efficient but极易陷入 local optima from which it cannot escape.
• Use Case: Ideal for convex or simple optimization landscapes where the global optimum is easily reachable from many starting points.
• Variants: Include Stochastic Hill Climbing (randomly selects a better neighbor) and Random-Restart Hill Climbing (runs the algorithm multiple times from different start points).

Tabu Search is another metaheuristic designed to escape local optima by using memory. It maintains a tabu list—a short-term memory of recently visited states or moves—that are forbidden (tabu) for a number of iterations.

• Mechanism: This enforced "forgetting" prevents cycling and encourages exploration of new regions of the search space. It can accept worsening moves if they are not tabu.
• Contrast with SA: While SA uses probabilistic acceptance and a cooling schedule, Tabu Search uses deterministic rules guided by memory. Tabu Search often requires careful tuning of the tabu list size and aspiration criteria (rules that override the tabu status).
• Application: Extensively used in scheduling, routing, and other combinatorial optimization problems.

Genetic Algorithms (GAs) are population-based metaheuristics inspired by natural selection. Instead of iteratively improving a single solution (like SA), GAs maintain a population of candidate solutions.

• Core Operators: Solutions are combined and mutated using crossover and mutation operators to create a new generation. Selection pressure favors fitter solutions.
• Exploration vs. Exploitation: The population allows for parallel exploration of the search space. Crossover exploits building blocks of good solutions, while mutation introduces exploration.
• Comparison: GAs are inherently parallel and can handle complex, multi-modal landscapes well. They are less directly analogous to physical processes than SA but share the goal of global optimization. They often require defining a genetic representation (encoding) of the problem.

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm for optimal decision-making, famous for its success in Go. It combines tree search with random sampling.

• Four-Step Process: 1) Selection: Traverse the tree using a policy (e.g., UCB1) to select a node. 2) Expansion: Add a child node. 3) Simulation: Run a random playout (rollout) to a terminal state. 4) Backpropagation: Update the node statistics with the result.
• Stochastic Element: Like SA's random acceptance of worse states, MCTS uses random simulations to estimate the value of states, which provides a broad, exploratory view of the search space.
• Domain: Primarily used in sequential decision-making problems like games and planning, whereas SA is typically applied to static optimization problems.

Local Beam Search is a variant of hill climbing that maintains not one, but k current states (the beam width) simultaneously. At each iteration, it generates all successors of all k states, then selects the k best from the combined set.

• Parallel Hill Climbing: It can be seen as running k hill climbs in parallel, with limited information sharing (only the best successors are kept).
• Difference from SA: It is a deterministic, greedy algorithm within the beam. It lacks SA's explicit mechanism (probabilistic acceptance) to escape local optima, though a stochastic beam search variant selects successors probabilistically.
• Trade-off: It uses more memory than hill climbing but can explore a slightly broader area. It can still converge all beams to the same local optimum.

The Metropolis-Hastings Algorithm is a Markov Chain Monte Carlo (MCMC) method for sampling from a probability distribution. Simulated Annealing is directly derived from it.

• Foundational Logic: Given a current state x, propose a new state x'. Accept the move with probability min(1, P(x')/P(x)). This generates a Markov chain whose stationary distribution is P(x).
• Connection to SA: Simulated Annealing adapts this for optimization by treating P(x) as exp(-f(x)/T), where f(x) is the cost function and T is the temperature. The cooling schedule gradually reduces T, making the distribution increasingly concentrated on low-cost states.
• Significance: This formal probabilistic foundation is what allows SA to asymptotically converge to a global optimum with a sufficiently slow cooling schedule, providing theoretical guarantees not present in simpler heuristics.