Hill Climbing Algorithm

The hill climbing algorithm is a local search method for solving optimization problems. It begins from any arbitrary solution and, iteratively, moves to the neighbor that most improves the objective function, repeating that jump until no neighbor beats the current state, at which point it stops.

Hill climbing is a greedy algorithm: at each step it takes the best immediate improvement without looking any further ahead. It also uses very little memory, since it only needs to remember the current state and evaluate its neighbors, keeping neither the path traveled nor a frontier of nodes. Russell and Norvig, in «Artificial Intelligence: A Modern Approach», present it as the canonical example of local search.

How it works and why it is efficient

Picture a function that assigns every solution a «height», meaning its quality. Hill climbing behaves like a hiker who can only look down at their feet: it inspects the neighboring solutions, steps toward the one that climbs the most, and looks again. When every neighbor lies lower, it concludes it has reached a peak and halts.

The classic version, steepest-ascent hill climbing, evaluates all neighbors and picks the best one. Its appeal is simplicity and cost: it maintains no open lists and rebuilds no routes, so it scales gracefully to vast spaces where an exhaustive search would be hopeless. That is why it turns up in tasks such as component placement, parameter tuning, and route planning, where a good enough solution, found fast, is all you need.

The catch: local optima, plateaus, and ridges

Its strength is also its Achilles heel. Because it never accepts a downhill step, the algorithm gets trapped in local optima: minor summits from which every move descends, even when a taller mountain rises across the valley. The analogy is climbing in fog while always heading up: you may crown a small hillock and believe it is the top of the world.

Two more terrains stall it. Plateaus are flat regions where all neighbors score the same and the algorithm has no clue which way to go. Ridges are narrow, slanting crests that rise diagonally: since the method only tries moves aligned with the axes, it inches forward in tiny zigzags or stops altogether, unable to follow the edge.

Variants: random restart, stochastic, and simulated annealing

Several variants dodge these traps. Stochastic hill climbing picks at random among the moves that improve, rather than always the steepest; the first-choice version generates neighbors at random until one improves, handy when there are too many to enumerate. Yet the most effective technique, for how simple it is, is random-restart hill climbing: launch many searches from different starting points and keep the best peak found.

When even that falls short, the answer is simulated annealing, which does sometimes accept downhill moves —with a probability that shrinks over time— to escape local optima before settling. For all its limits, hill climbing remains the gateway to understanding local search and a practical tool whenever a good solution in little time is enough.