# Local Search: Hill Climbing and Simulated Annealing — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/s-local

> Improve a solution step by step.

## 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.

```python
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.

**Quiz:** Why can hill climbing return a poor solution?

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

*Answer:* It stops at a local optimum when no neighbour is better. Accepting some worse moves helps escape.