Hill climbing is a variety of depth-first (generate - and - test) search. A feedback is used here to decide on the direction of motion in the search space. In the depth-first search, the test function will merely accept or reject a solution.

But in hill climbing the test function is provided with a heuristic function which provides an estimate of how close a given state is to goal state.

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.

Two variations of hill climbing are:

1. Simple hill climbing:

2. Steepest Ascent Hill Climbing.

Simple hill climbing: It is simple way to implement hill climbing:

Algorithm:

1. Evaluate the initial state. If it is a goal state, then return and quit; otherwise make it a current state and goto Step 2.

2. Loop until a solution is found or there are no new operators left to be applied.

a. Select and apply a new operator

b. Evaluate the new state:

i. If it is a goal state, then return and quit.

ii. If it is better than current state then make it a new current state.

iii. If it is not better than the current state then continue the loop, go to Step 2.

Steepest Ascent Hill Climbing:

This differs from the basic Hill climbing algorithm by choosing the best successor rather than the first successor that is better. This indicates that it has elements of the breadth first algorithm.

The algorithm proceeds

Steepest ascent Hill climbing algorithm:

1 Evaluate the initial state

2 If it is goal state then quit

Otherwise make the current state this initial state and proceed;

3 Repeat

Set Target to be the state that any successor of the current state can better;

For each operator that can be applied to the current state

Apply the new operator and create a new state

Evaluate this state

If this state is goal state then quit

Otherwise compare with Target

If better set Target to this value

If Target is better than current state set current state to Target

Until a solution is found or current state does not change

Both the basic and this method of hill climbing may fail to find a solution by reaching a state from which no subsequent improvement can be made and this state is not the solution

Else see whether it is closer to the goal state than the solution already generated. If yes, remember it else discard it.

1. Take the best element so far generated and use it as the next proposed solution.

This step corresponds to move through the problem space in the direction

Towards the goal state.

1. Go back to step 2.

Problems in Hill Climbing

Local maxima:

A surface with two local maxima. (Only one of them is the global maximum.) If a hill-climber begins in a poor location, it may converge to the lower maximum.

Hill climbing will not necessarily find the global maximum, but may instead converge on a local maximum.

This problem does not occur if the heuristic is convex. However, as many functions are not convex hill climbing may often fail to reach a global maximum. Other local search algorithms try to overcome this problem such as stochastic hill climbing, random walks and simulated annealing.

Ridges and alleys:

Ridges are a challenging problem for hill climbers that optimize in continuous spaces. Because hill climbers only adjust one element in the vector at a time, each step will move in an axis-aligned direction.

If the target function creates a narrow ridge that ascends in a non-axis-aligned direction (or if the goal is to minimize, a narrow alley that descends in a non-axis-aligned direction), then the hill climber can only ascend the ridge (or descend the alley) by zigzagging.

If the sides of the ridge (or alley) are very steep, then the hill climber may be forced to take very tiny steps as it zigzags toward a better position. Thus, it may take an unreasonable length of time for it to ascend the ridge (or descend the alley).

Another problem that sometimes occurs with hill climbing is that of a plateau. A plateau is encountered when the search space is flat, or sufficiently flat that the value returned by the target function is indistinguishable from the value returned for nearby regions due to the precision used by the machine to represent its value.

In such cases, the hill climber may not be able to determine in which direction it should step, and may wander in a direction that never leads to improvement.