Updated March 28, 2023
Introduction to Hill Climbing Algorithm
Hill Climbing is a self-discovery and learns algorithm used in artificial intelligence algorithms. Once the model is built, the next task is to evaluate and optimize it. Hill climbing is one of the optimization techniques which is used in artificial intelligence and is used to find local maxima. Hill Climbing is an iterative search algorithm and starts the solution with the arbitrary defined initial state. Then, the algorithm progresses to find a better solution with incremental change. The idea is to see the neighbor state and compare it with the current state of the neighbor state is better; the neighbor state will become a current state, and the same cycle continues until no neighbor state is better than the current state.
Features of Hill Climbing Algorithm
- Simple in Nature: Hill climbing algorithm is an incremental algorithm and
tries a simple strategy by comparing the neighbor with the current state, and if the neighbor is heuristically better, it will accept the neighbor state. - Iterative: Hill Climbing is an iterative algorithm, and it starts with an arbitrary initial solution for a problem; it then tries to find a better solution than the current state by making an incremental change.
Types of Hill Climbing Algorithm
There are basically 3 types of Hill climbing algorithms
- Simple Hill Climbing:
- Steepest Ascent Hill Climbing
- Stochastic Hill Climbing
1. Simple hill climbing
As the name itself suggest, simple hill-climbing means step by step climbing the hill. One can climb the hill till there is the possibility of reaching a higher altitude than the current one. The same applies to simple hill climbing, it examines a neighboring state, and if it is having a higher cost than the previous one, it considers the new state as the current state.
Simple Hill climbing Algorithm:
Step 1: Initialize the initial state, then evaluate this with neighbor states. If it is having a high cost, then the neighboring state the algorithm stops and returns success. If not, then the initial state is assumed to be the current state.
Step 2: Iterate the same procedure until the solution state is achieved. The initial state is assumed as the current state and is compared with the neighboring state again. If the new current state is a desired or state, then the algorithm stops and returns success. Or If it is not, then it makes a new neighbor as its current state and compares it with neighbor states again and proceeds further. This iterative approach is continued until the solution or goal state is achieved.
Step 3: Return success and exit.
2. Steepest-Ascent Hill climbing
As the name suggests, it is the steepest means takes the highest cost state into account. This is the improvisation of simple hill-climbing where the algorithm examines all the neighboring states near the current state, and then it selects the highest cost as the current state. Thus, it is faster than simple hill climbing.
Simple Hill climbing Algorithm:
Step 1: Initialize the initial state, then evaluate this with all neighbor states. If it is having the highest cost among neighboring states, then the algorithm stops and returns success. If not, then the initial state is assumed to be a current state.
Step 2: Iterate the same procedure until the solution state is achieved. The initial state is assumed as the current state and is compared with all its neighboring states again. If the new current state is a desired or state, then the algorithm stops and returns success. Or If it is not, then it makes a new neighbor as its current state and again compares it with all possible neighboring states and finds a state with the highest cost among them and proceeds further. This iterative approach is continued until the solution or goal state is achieved.
Step 3: Return success and exit.
3. Stochastic hill climbing
This algorithm is another variant of a simple hill climbing algorithm. Stochastic does not evaluate with all the neighboring states to decide new which one to be a new state. Here the improvisation is random. It will select any of the neighbors to move forward. The question that arises here is why?
To answer that, let’s see the above two algorithms; simple hill-climbing just interacts with the first neighbor and if it’s better assumes it as the current state, and if not, it will give a result and exit. On the other hand, the steepest hill climbing is a greedy algorithm, and chances are there it will also be stuck in some local optima.
But the beauty of choosing random neighbors with high costs gives stochastic to avoid local optima.
The steps of the algorithm are almost the same, but it randomly selects neighbors.
Problems in Hill Climbing Algorithm
Hill climbing is an optimization technique, and problems with optimization techniques are to be trapped in local optima instead of global optima (the desired state). In hill climbing, basically, there are three main problems.
- Local maxima
- Plateau
- Ridges
1. Local Maxima
Consider simple hill-climbing, and see the line diagram shown below; we can see there are two local maxima and one global maximum. If the algorithm starts from the extreme left or right, it will be trapped in local optima.
<image>
2. Ridges
Ridges are also a common problem in the hill-climbing algorithm when any state of a ridge seems like a peak because, in all possible directions, the movement is downward only. Thus, once the algorithm encounters a ridge, it stops.
3. Plateau
This is also a classic problem in optimization problems when it looks like no neighbor is better and there is no way to move forward algorithm stops there only maybe there are other maxima, but it cannot move forward as neighbors are the same. For example, see the picture below, for some length, there is a plateau, and then there’s a climb
<image>
Conclusion
Hill Climbing is an optimization algorithm. And uses a basic technique and starts with an arbitrary initial state and improves incrementally. In the article, we have discussed 3 different hill climbing algorithms: Simple Hill Climbing, Steepest Ascent hill-climbing, and stochastic hill climbing. We also have discussed the problems associated with these algorithms.
Recommended Articles
This is a guide to the Hill Climbing Algorithm. Here we discuss the 3 different types of hill-climbing algorithms, namely Simple Hill Climbing, Steepest Ascent hill-climbing, and stochastic hill climbing. You may also have a look at the following articles to learn more –
