Visualization of Hill Climbing

Introduction:

Hill climbing is one of the Heuristic Search techniques. Hill Climbing strategies expand the current state in the search and evaluate its children. The best child is selected for further expansion and neither its siblings nor its parent are retained. Search halts when it reaches a state that is better than any of its children. Hill climbing is named for the strategy that might be used by an eager, but blind mountain climber, go uphill along the steepest possible path until you can go no further.

Problems in Hill Climbing:

A major problem of hill climbing strategies is their tendency to become stuck at foothills, a plateau or a ridge. If the algorithm reaches any of the above mentioned states, then the algorithm fails to find a solution.

Foothills or local maxima is a state that is better than all its neighbours but is not better than some other stses farther away. At a local maximum, all moves appear to make things worse. Foothills are potential traps for the algorithm.
A plateau is a flat area of the search space in which a whole set of neighbouring ststes have the same value. On a plateau, it i not possible to determine the best direction in which to move by making local comparisons.
A ridge is a special kind of local maximum. It is an area of the search space that is higher that the surrounding areas and that itself has a slope. But theorientation of the high region, compared to the set of available moves and the directions in which they move, makes it impossible to traverse a ridge by single moves. Any point on a ridge can look like peak because movement in all probe directions is downward.

Visualization of Hill Climbing Problems:

A java applet is used to visualize the above mentioned problems in hill climbing. The back ground of this applet is a hill and this hill is used for demonstrating the various problems faced in hill climbing search technique. When the applet is loaded, it shows the hill as a back ground and it also has a button for each of problems talked above. By clicking the respective button, the applet shows the search path that will be taken for each of the above mentioned problems. The search path is represented by a red line. This red line is obtained by joining all the solution states taken during the search. The blue lines show possible solution states around the current state. The green line indicates the best state obtained at each search point. The green circle at the top of the hill indicates the actual goal state that is to reached. The start and stop buttons are for starting and stopping the search. This applet helps the user to visualize and thus understand the hill climbing search technique and also understand the various problems faced by hill climbing search technique.