Random-restart hill climbing is a meta-algorithm built on top of the hill climbing optimization algorithm.

Hill climbing attempts to maximize (or minimize) a function f(x), where x are discrete states. These states are typically represented by vertices in a graph, where edges in the graph encode nearness or similarity of a graph. Hill climbing will follow the graph from vertex to vertex, always locally increasing (or decreasing) the value of f, until a local maximum x_m is reached. Hill climbing can also operate on a continuous space: in that case, the algorithm is called gradient ascent (or gradient descent if the function is minimized).

Random-restart hill climbing simply runs an outer loop over hill-climbing. Each step of the outer loop chooses a random initial condition x₀ to start hill climbing. The best x_m is kept: if a new run of hill climbing produces a better x_m than the stored state, it replaces the stored state.

Random-restart hill climbing is a surprisingly effective algorithm in many cases. It turns out that it is often better to spend CPU time exploring the space, rather than carefully optimizing from an initial condition.

Contrast genetic algorithm; random optimization.

Reference

S. Russell and P. Norvig, Chapter 4, "Artificial Intelligence: A Modern Approach," Prentice-Hall, (1995), ISBN 0131038052