Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Local search: hill climbing, simulated annealing and local beam search

Local search methods (hill climbing, simulated annealing, local beam search) are iterative optimization algorithms used by engineers to find good solutions in large state spaces where complete search is infeasible.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Local search methods are used by engineers to solve large optimisation and combinatorial problems (scheduling, placement, circuit layout, parameter tuning) where the full state space is too large for exhaustive or systematic search. They are simple, use little memory, and can find good solutions quickly even when optimality is not guaranteed.

Key ideas

  • Local search: start from one or more states and repeatedly move to neighbouring states in hope of improving f(s). Local search does not keep a search tree; it keeps one or a few states and moves among them.

  • Hill climbing (basic algorithm): repeatedly move to a neighbour with higher objective value until no neighbour improves the current state. Formal definition:

    • A state s is a local maximum if for every s' in N(s), f(s') ≤ f(s).
    • The algorithm terminates at a state that is a local maximum (not necessarily the global maximum).

    Hill climbing variants:

    • Simple (greedy) hill climbing: choose the best neighbour each step.
    • Stochastic hill climbing: choose a randomly selected improving neighbour (probabilistic among improving moves).
    • Random-restart hill climbing: run greedy hill climbing from many random start states and keep the best final state seen.
    • First-choice hill climbing: sample neighbours in random order and move to the first better one found (reduces cost when neighbourhoods are large).
    • Hill climbing with sideways moves: permit moves to equal-valued neighbours (Δf = 0) up to a limit L steps to help traverse plateaux; specify L and stopping rules explicitly.
  • Failure modes for hill climbing: local maxima (stopping early), plateaux (where neighbouring states have equal value), and ridges (paths to global maximum require moves that temporarily decrease f).

  • Simulated annealing (SA): a probabilistic variant that sometimes accepts worse moves to escape local maxima, inspired by physical annealing. Key components:

    • A temperature parameter T ≥ 0 controls the probability of accepting worse moves. T is decreased over time according to a cooling schedule.
    • At each step, pick a random neighbour s' of current s. If f(s') ≥ f(s), accept s' (move). If f(s') < f(s) (worse), accept s' with probability P = exp((f(s') − f(s)) / T) when maximizing. (For minimizing use P = exp((f(s) − f(s')) / T) or equivalently absorb sign into f.)
    • As T → 0, the algorithm behaves like greedy hill climbing. With a carefully slow cooling schedule and certain technical assumptions (irreducible, aperiodic Markov chain over states), SA can converge with probability 1 to a global optimum.

    Important terms:

    • Cooling schedule: T(t), the temperature at time t (or iteration k). Common schedules: exponential T_k = α·T_{k−1} with α slightly less than 1; logarithmic T_k = c / log(1 + k) (used in theoretical guarantees).
  • Local beam search: keep k states (the beam). At each iteration, generate all neighbours of the k states (up to k·b where b is branching factor), pick the best k among them (ties broken arbitrarily or randomly), and repeat. It combines parallel exploration (k>1) with exploitation of good states. If k=1 it is hill climbing; if k is large enough that all generated successors are retained each step, it approaches exhaustive parallel expansion of the search graph at each iteration (it is not breadth-first search, which orders by depth rather than by objective value).

  • Stochastic beam / population methods: instead of deterministically picking the k best, pick k states randomly from the pool with probability proportional to their fitness (like selection in genetic algorithms). This reduces premature convergence.

  • Theoretical result (brief, precise statement): Under assumptions that the neighbour selection makes the Markov chain irreducible and aperiodic, and if the cooling schedule satisfies T_k ≥ c / log(k + 1) for suitable c > 0 (with c chosen at least as large as the problem’s critical depth/energy barrier), simulated annealing converges with probability 1 to the set of global optima.

  • Diagrams to draw (exam): draw a 1-D landscape: x-axis labelled "state index or parameter", y-axis labelled "objective value f". Sketch a curve with one tall global peak and a smaller local peak. Mark a point at the local peak and label it "local maximum (hill climbing stops)" and draw arrows showing downhill moves that would be required to reach the global peak. For simulated annealing, sketch a temperature curve T(t) decreasing over iterations.

Formulas

P_accept = 1 — means accept if f(s') ≥ f(s). Applies in greedy moves for maximization.

P_accept = exp((f(s') - f(s)) / T) — probability of accepting a worse neighbour s' (maximization), where f in arbitrary units, T is temperature (same units as f if Boltzmann constant is 1), applies in simulated annealing.

For minimization: P_accept = exp((f(s) - f(s')) / T) — equivalent when the objective is cost to minimize.

Stationary distribution π(s) ∝ exp(f(s) / T) — (for a Metropolis-style acceptance with symmetric proposal, maximizing case) the Markov chain has stationary probability proportional to exp(f(s)/T) assuming irreducibility and aperiodicity; as T → 0 mass concentrates on global maxima.

Memory (hill climbing) = O(1) — stores just current state and maybe best found.

Memory (local beam) = O(k) — stores k states.

Time per iteration (local beam) = O(k · b + selection_cost) — where b is average branching factor and selection_cost is cost of choosing best k from candidates (often O(k·b · log(k))).

Random-restart expected runs until success = 1 / p; expected number of restarts = 1 / p − 1 — where p is the probability that a random start leads (by hill climbing) to a global optimum; applies under the independence assumption of restarts.

Worked examples

Example 1 — hill climbing failure and random-restart (theory/model answer): Problem: States {A,B,C,D,E} with neighbours: A↔B, B↔C, C↔D, D↔E. Objective values f(A)=10, f(B)=20, f(C)=15, f(D)=30, f(E)=25. Start at C. Answer (step-by-step):

  1. Current C has f=15. Neighbours are B (20) and D (30).
  2. Greedy hill climbing moves to the best neighbour: D (30).
  3. At D, neighbours C (15) and E (25). Neither has f > 30, so D is a local maximum and algorithm stops.
  4. Global maximum in state set is D (30) so in this example hill climbing succeeded. To illustrate failure, modify the objective values to f(A)=10, f(B)=20, f(C)=25, f(D)=24, f(E)=30 (same neighbours, start at C). Greedy hill climbing stops at C (local maximum) because both neighbours B and D are worse, even though the global maximum is at E=30; reaching E requires a temporary decrease to D, which hill climbing does not allow. Random-restart hill climbing can start from other states (e.g., D) and increases the chance of reaching E.

Example 2 — simulated annealing numeric computation: Setup: Maximization problem. Current state s has f(s)=50. A randomly proposed neighbour s' has f(s')=48 (worse). Compute acceptance probability at two temperatures.

  1. Use formula P_accept = exp((f(s') - f(s)) / T).
  2. If T = 10: P_accept = exp((48 − 50)/10) = exp(−0.2) ≈ 0.8187 → with probability 0.819 accept the worse state.
  3. If T = 1: P_accept = exp(−2) ≈ 0.1353 → accept with probability 0.135. Conclusion: higher temperature makes acceptance of worse moves more likely, helping escape local maxima early. As T falls, algorithm becomes more greedy.

Example 3 — local beam search sketch answer (short model answer): Given k=3 and branching b=4, at one iteration we have 3 states; expand each to 4 neighbours (12 candidates); evaluate all 12, pick the best 3 by f, these become the beam for next iteration. State the time per iteration ≈ 12 evaluations plus sorting/selecting top 3.

Common mistakes

  • Forgetting the assumptions behind SA convergence (irreducibility, aperiodicity, very slow cooling). The practical cooling schedules do not guarantee theoretical convergence.
  • Using an acceptance probability formula but forgetting to reduce temperature; or reducing temperature too fast so algorithm behaves greedily and gets stuck.
  • For local beam search, failing to account for the cost of generating and evaluating all candidates (k·b) per iteration.
  • Numerical mistakes in computing exp() or not converting objective and temperature to consistent units if Boltzmann constant is considered.

For your exam

Kinds of questions you will see:

  • Definitions: define local search, neighbourhood, local maximum, plateau, ridge, hill climbing, simulated annealing, cooling schedule, local beam search.
  • Short notes: explain variants of hill climbing (stochastic, random-restart), explain SA and its acceptance rule, explain beam search and differences from genetic algorithms.
  • Derivations / proofs: show why SA has a stationary distribution π(s) ∝ exp(f(s)/T) under symmetric proposals; outline the conditions for convergence (state chain irreducible/aperiodic, logarithmic cooling schedule) — include assumptions.
  • Numericals: compute acceptance probabilities for given f values and T; calculate expected restarts given probability p; compute time/memory per iteration for beam search.
  • Diagrams: draw landscape showing local and global maxima and annotate where hill climbing stops vs SA escaping.

What to include for full marks:

  • Clear definitions (bold terms in your answer if permitted), precise algorithm steps or pseudocode, assumptions of the result you state, and for numericals show each formula and every arithmetic step. When discussing SA convergence, state the assumptions and give the cooling schedule form.

Quick check

  1. Define a local maximum in terms of neighbourhood N(s).
  2. Write the acceptance probability formula for simulated annealing in the maximization case.
  3. For local beam search with beam width k and branching b, what is the dominant cost per iteration in terms of evaluations? Answers: 1. A state s is a local maximum if for all s' in N(s), f(s') ≤ f(s). 2. P_accept = exp((f(s') − f(s)) / T) for a worse neighbour s'. 3. O(k · b) candidate evaluations (plus selection cost to pick top k).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?