Local Search: Hill Climbing and Simulated Annealing

When the path does not matter

For optimisation problems where only the final state matters (schedules, layouts, parameter settings), local search keeps one current solution and moves to better neighbours. Hill climbing always moves uphill and stops at the first peak, which may be a local optimum. Simulated annealing sometimes accepts worse moves, with a probability that shrinks as a "temperature" cools, so it can escape local peaks early and settle later. Random restarts and genetic algorithms are other ways to explore more widely.

Hill climbing versus simulated annealing, run

I ran this with plain Python 3 (standard library only), with fixed random seeds where randomness is used. On a bumpy function with peaks near x = 1.6, 7.9 and 14.1, hill climbing from x = 1 stops at the first peak (f = 10.80). Simulated annealing with the same start finds x = 14.23, f = 17.07, the highest peak in the range.

import math, random
def f(x):  # a bumpy landscape with peaks near x = 1.6, 7.9 and 14.1 (the highest) on [0, 16]
    return math.sin(x) * 10 + x * 0.5
def hill_climb(x, step=0.1):
    while True:
        best = max([x - step, x + step], key=f)
        if f(best) <= f(x): return x
        x = best
def anneal(x, temp=10.0, cool=0.995, rng=random.Random(0)):
    best = x
    while temp > 0.01:
        nxt = min(16.0, max(0.0, x + rng.uniform(-4, 4)))
        if f(nxt) > f(x) or rng.random() < math.exp((f(nxt) - f(x)) / temp): x = nxt
        if f(x) > f(best): best = x
        temp *= cool
    return best
x0 = 1.0
h = hill_climb(x0); a = anneal(x0)
print(f"hill climbing from x={x0}: stops at x={h:.2f}, f={f(h):.2f} (a local peak)")
print(f"simulated annealing     : finds  x={a:.2f}, f={f(a):.2f}")

Output:

hill climbing from x=1.0: stops at x=1.60, f=10.80 (a local peak)
simulated annealing     : finds  x=14.23, f=17.07

Use restarts

Running a cheap local search from many random starts and keeping the best result is a strong, simple baseline.

त्वरित जाँच: Why can hill climbing return a poor solution?

• It stops at a local optimum when no neighbour is better
• It never moves
• It always picks random states
• It requires a goal test