In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.
For example, hill climbing can be applied to the travelling salesman problem. It is easy to find an initial 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 shorter route is likely to be obtained.
Hill climbing is good for finding a local optimum (a solution that cannot be improved by considering a neighbouring configuration) but it is not guaranteed to find the best possible solution (the global optimum) out of all possible solutions (the search space). The characteristic that only local optima are guaranteed can be cured by using restarts (repeated local search), or more complex schemes based on iterations, like iterated local search, on memory, like reactive search optimization and tabu search, on memory-less stochastic modifications, like simulated annealing.
The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. It 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. Although more advanced algorithms such as simulated annealing or tabu search may give better results, in some situations hill climbing works just as well. Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems. It is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.
Read more about Hill Climbing: Mathematical Description, Variants, Pseudocode
Famous quotes containing the words hill and/or climbing:
“The hill farmer ... always seems to make out somehow with his corn patch, his few vegetables, his rifle, and fishing rod. This self-contained economy creates in the hillman a comparative disinterest in the world’s affairs, along with a disdain of lowland ways. “I don’t go to question the good Lord in his wisdom,” runs the phrasing attributed to a typical mountaineer, “but I jest cain’t see why He put valleys in between the hills.””
—Administration in the State of Arka, U.S. public relief program (1935-1943)
“An old, mad man still climbing in his ghost,
My fathers’ ghost is climbing in the rain.”
—Dylan Thomas (1914–1953)