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 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 xm
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 x0 to start hill climbing. The best xm is kept: if a new run of hill climbing produces a better xm 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.
Reference
S. Russell and P. Norvig, Chapter 4, "Artificial Intelligence: A Modern Approach," Prentice-Hall, (1995), ISBN 0131038052
|