Hill climbing (greedy local search) is a primitive local search algorithm. It’s premised on being greedy by moving to a neighbouring state with the highest possible value, i.e., the direction with the steepest ascent (or descent, depending on the problem). When a neighbour has no higher value (i.e., at a local maximum), the algorithm terminates.
There are a few problems with hill climbing. In particular, it can get stuck at local maxima, at plateaus (i.e., where there are no improvements).
Some variants of hill climbing are meant to change how the problems function:
- Stochastic hill climbing randomly chooses an uphill move where the probability varies with the steepness. This usually converges slower than regular steepest ascent but can find better solutions.
- First-choice hill climbing implements stochastic hill climbing by randomly generating next states until one is better than the current state.
- Random-restart hill climbing does multiple hill climbing searches from random initial states until an optimal goal is found.