Random-restart hill climbing
|
|
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 <math>f(x)<math>, where <math>x<math> 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 <math>f<math>, until a local maximum <math>x_m<math> 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 <math>x_0<math> to start hill climbing. The best <math>x_m<math> is kept: if a new run of hill climbing produces a better <math>x_m<math> 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