Hill Climbing

What you're looking at

The optimization problem

You're looking at a 2D fitness landscape — a surface where every (x, y) point has a height. The goal is to find the highest point, but the agent can only see its immediate neighborhood. It's like finding the tallest mountain in the dark with a flashlight that only illuminates a few feet around you.

Greedy hill climbing

Check the eight compass directions, move to whichever neighbor is highest. Fast and simple, but it stops the moment it reaches any peak — even a small bump. On a landscape with multiple peaks, it almost always gets stuck at a local optimum.

Steepest ascent

Instead of checking fixed directions, compute the gradient — the direction of steepest increase — and follow it. Smoother paths than greedy, but the same fundamental problem: it can't escape local optima. Once the gradient is zero, it's done.

Simulated annealing

Named after the metallurgical process. Early on, the "temperature" is high and the agent will accept downhill moves — random jumps that make things temporarily worse. As it cools, it becomes pickier, eventually only accepting improvements. This lets it escape local optima early and settle into good solutions late. The trick is the cooling schedule.

Random restarts

The brute force approach that's surprisingly effective: just run greedy hill climbing from many random starting points and keep the best result. No cleverness, no temperature schedules — just sample broadly and let probability do the work. On many landscapes, this beats sophisticated methods.

The real lesson

There's a theorem called "No Free Lunch" that says no optimization algorithm is universally best — averaged across all possible landscapes, they all perform the same. The right strategy depends on the structure of your problem. Smooth, few peaks? Gradient methods work great. Rugged, many peaks? You need exploration. Real problems are somewhere in between, which is why most practical optimizers combine exploitation (climbing) with exploration (randomness).