Local Search Optimization: Hill Climbing & Simulated Annealing

When the path to the goal is irrelevant and only the final configuration matters (e.g., 8-Queens puzzle, VLSI circuit layout, traveling salesperson problem), Local Search Algorithms evaluate configurations without retaining search paths, operating in O(1) constant memory.

Landscape Topography & Failure Modes of Pure Hill Climbing:

1. Local Maxima: A peak that is higher than all neighboring states but lower than the global maximum. Greedy hill climbing halts permanently.

2. Plateaus: Flat regions where all neighboring states possess the identical objective value (flat local maxima or shoulders). Hill climbing wanders aimlessly in a random walk.

3. Ridges: Sloped areas where navigation requires simultaneous changes in multiple variables. Single-variable steepest-ascent oscillates back and forth, making negligible progress.

Inspired by the physical annealing process in metallurgy (where liquid metal is cooled slowly to form a crystal with minimal defect energy), Simulated Annealing escapes local optima by intentionally accepting worsening moves with a controlled probability.

The Metropolis Algorithm:

At each time step t, the algorithm selects a random neighbor s' of current state s.

Let \Delta E = f(s') - f(s) be the change in the objective function.

• If \Delta E > 0 (the neighbor is superior): The transition is accepted unconditionally (s ≤ftarrow s').

• If \Delta E ≤ 0 (the neighbor is inferior): The transition is accepted with probability:

$P = e^{\frac{\Delta E}{T}}$

Where T = T(t) is the temperature parameter dictated by an annealing cooling schedule.

Behavioral Dynamics Across the Cooling Schedule:

• When T \to \infty (early iterations): \frac{\Delta E}{T} \to 0 \implies e^0 = 1. The algorithm accepts almost all downhill moves, freely exploring the entire state landscape like a random walk.

• When T \to 0 (late iterations): \frac{\Delta E}{T} \to -\infty \implies e^{-\infty} = 0. The probability of accepting downhill moves approaches zero, smoothly degenerating into pure greedy hill climbing to settle into the local basin.