Hill climbing


Hill climbing

In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is relatively simple to implement, making it a popular first choice. Although more advanced algorithms may give better results, in some situations hill climbing works just as well.

Hill climbing can be used to solve problems that have many solutions, some of which are better than others. It starts with a random (potentially poor) solution, and iteratively makes small changes to the solution, each time improving it a little. When the algorithm cannot see any improvement anymore, it terminates. Ideally, at that point the current solution is close to optimal, but it is not guaranteed that hill climbing will ever come close to the optimal solution.

For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much better route is obtained.

Hill climbing is used widely in artificial intelligence, for reaching a goal state from a starting node. Choice of next node and starting node can be varied to give a list of related algorithms.

Mathematical description

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 (or local minimum) 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).*.

Variants

In simple hill climbing, the first closer node is chosen, whereas in steepest ascent hill climbing all successors are compared and the closest to the solution is chosen. Both forms fail if there is no closer node, which may happen if there are local maxima in the search space which are not solutions. Steepest ascent hill climbing is similar to best-first search, which tries all possible extensions of the current path instead of only one.

Random-restart hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It is also known as Shotgun hill climbing. It iteratively does hill-climbing, each time with a random initial condition x_0. 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, than carefully optimizing from an initial condition. Or|date=September 2007

Problems

Local maxima

A problem with hill climbing is that it will find only local maxima. Unless the heuristic is convex, it may not reach a global maximum. Other local search algorithms try to overcome this problem such as stochastic hill climbing, random walks and simulated annealing. This problem of hill climbing can be solved by using random hill climbing search technique.

Ridges

A ridge is a curve in the search place that leads to a maximum, but the orientation of the ridge compared to the available moves that are used to climb is such that each moves will lead to a smaller point. In other words, each point on a ridge looks to the algorithm like a local maximum, even though the point is part of a curve leading to a better optimum.

Plateau

Another problem with hill climbing is that of a plateau, which occurs when we get to a "flat" part of the search space, i.e. we have a path where the heuristics are all very close together. This kind of flatness can cause the algorithm to cease progress and wander aimlessly.

Pseudocode

Hill Climbing Algorithm currentNode = startNode; loop do L = NEIGHBORS(currentNode); nextEval = -INF; nextNode = NULL; for all x in L if (EVAL(x) > nextEval) nextNode = x; nextEval = EVAL(x); if nextEval <= EVAL(currentNode) //Return current node since no better neighbors exist return currentNode; currentNode = nextNode;

Contrast genetic algorithm; random optimization.

ee also

* gradient descent
* greedy algorithm

References

*Russell Norvig 2003| pages=111-114

External links

* [http://paradiseo.gforge.inria.fr/ ParadisEO] is a powerful C++ framework dedicated to the reusable design of metaheuristics, included local search algorithms as the Hill-Climbing, the tabu-search ...


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Hill-Climbing — Montée impossible La montée impossible (origine anglophone Hill Climbing) est une course motocycliste individuelle où le compétiteur s affronte à une côte naturelle, non revêtue, extrêmement difficile (plus de 45% de dénivelé en général), ou… …   Wikipédia en Français

  • Hill Climbing — Montée impossible La montée impossible (origine anglophone Hill Climbing) est une course motocycliste individuelle où le compétiteur s affronte à une côte naturelle, non revêtue, extrêmement difficile (plus de 45% de dénivelé en général), ou… …   Wikipédia en Français

  • hill climbing — ekstremumo paieška statusas T sritis automatika atitikmenys: angl. hill climbing vok. Extremumsuche, f rus. поиск экстремума, m pranc. recherche de l extremum, f …   Automatikos terminų žodynas

  • Hill-climbing — Dieser Artikel befasst sich mit einer Motorradsportart. Für die Autosportart siehe Bergrennen (engl. Hillclimbing) und für das Optimierungsverfahren siehe Bergsteigeralgorithmus. Hillclimbing Obersaxen 2003 Hillclimbing ist eine Motorradsportart …   Deutsch Wikipedia

  • Hill Climbing — Dieser Artikel befasst sich mit einer Motorradsportart. Für die Autosportart siehe Bergrennen (engl. Hillclimbing) und für das Optimierungsverfahren siehe Bergsteigeralgorithmus. Hillclimbing Obersaxen 2003 Hillclimbing ist eine Motorradsportart …   Deutsch Wikipedia

  • Stochastic hill climbing — is a variant of the basic hill climbing method. While basic hill climbing always chooses the steepest uphill move, stochastic hill climbing chooses at random from among the uphill moves. The probability of selection may vary with the steepness of …   Wikipedia

  • Climbing Hill (Iowa) — Climbing Hill Lugar designado por el censo de los Estados Unidos …   Wikipedia Español

  • hill climb — a racing event for motorcycles or automobiles in which competitors drive up a hilly course one at a time, the winner having the fastest time. [1900 05] * * * ▪ motor race  short distance race for automobiles or motorcycles up mountain roads, with …   Universalium

  • hill climb — noun : a road race over a hilly course held by an automobile or motorcycle club * * * a racing event for motorcycles or automobiles in which competitors drive up a hilly course one at a time, the winner having the fastest time. [1900 05] * * *… …   Useful english dictionary

  • hill climb — 1. noun A sporting event, during which vehicles are driven or ridden up a steep incline. The goal is to reach the highest level on the slope. 2. verb To attempt to ascend a steep slope using a motor vehicle …   Wiktionary


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.