Iterative Improvement Algorithms and Hill-Climbing

Hill-Climbing as an optimization technique

Iterative improvement algorithms apply to problems where each state can be evaluated using some function or metric to tell if one is getting closer to the desired goal state. This can guide searching and backtracking if the outcome is not improving based on the metric. The simplest algorithm in this category is called "hill climbing", but because this algorithm always chooses only the "best" solution at any stage, it can get stuck at local optima. This is a very simple but limited algorithm that will not always be optimal. Because it always chooses the immediately obvious "best" alternative, it is called a "greedy" search algorithm. It will tend to find local rather than global optima for this reason.

Hill climbing is an optimization technique for solving computationally hard problems. It is best used in problems with "the property that the state description itself contains all the information needed for a solution". The algorithm is memory efficient since it does not maintain a search tree: It looks only at the current state and immediate future states.

Hill climbing attempts to iteratively improve the current state by means of an evaluation function. "Consider all the [possible] states laid out on the surface of a landscape. The height of any point on the landscape corresponds to the evaluation function of the state at that point".

In contrast with other iterative improvement algorithms, hill-climbing always attempts to make changes that improve the current state. In other words, hill-climbing can only advance if there is a higher point in the adjacent landscape.

Source: Wikibooks, https://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Iterative_Improvement/Hill_Climbing
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.