Introduction to Hill Climbing in Artificial Intelligence
Hill Climbing is a form of heuristic search algorithm which is used in solving optimization related problems in Artificial Intelligence domain. The algorithm starts with a non-optimal state and iteratively improves its state until some predefined condition is met. The condition to be met is based on the heuristic function. The aim of the algorithm is to reach an optimal state which is better than its current state. The starting point which is the non-optimal state is referred to as the base of the hill and it tries to constantly iterate (climb) untill it reaches the peak value, that is why it is called Hill Climbing Algorithm.
Hill Climbing Algorithm is a memory-efficient way of solving large computational problems. It takes into account the current state and immediate neighbouring state. The Hill Climbing Problem is particularly useful when we want to maximize or minimize any particular function based on the input which it is taking. The most commonly used Hill Climbing Algorithm is “Travelling Salesman” Problem” where we have to minimize the distance travelled by the salesman. Hill Climbing Algorithm may not find the global optimal (best possible) solution but it is good for finding local minima/maxima efficiently.
Key Features of Hill Climbing in Artificial Intelligence
Following are few of the key features of Hill Climbing Algorithm
- Greedy Approach: The algorithm moves in the direction of optimizing the cost i.e. finding Local Maxima/Minima
- No Backtracking: It cannot remember the previous state of the system so backtracking to the previous state is not possible
- Feedback Mechanism: The feedback from the previous computation helps in deciding the next course of action i.e. whether to move up or down the slope
State Space Diagram – Hill Climbing in Artificial Intelligence
- Local Maxima/Minima: Local Minima is a state which is better than its neighbouring state, however, it is not the best possible state as there exists a state where objective function value is higher
- Global Maxima/Minima: It is the best possible state in the state diagram. Here the value of the objective function is highest
- Current State: Current State is the state where the agent is present currently
- Flat Local Maximum: This region is depicted by a straight line where all neighbouring states have the same value so every node is local maximum over the region
Problems in Hill Climbing Algorithm
Here ve discuss the problems in the hill-climbing algorithm:
1. Local Maximum
The algorithm terminates when the current node is local maximum as it is better than its neighbours. However, there exists a global maximum where objective function value is higher
Solution: Back Propagation can mitigate the problem of Local maximum as it starts exploring alternate paths when it encounters Local Maximum
2. Ridge
Ridge occurs when there are multiple peaks and all have the same value or in other words, there are multiple local maxima which are same as global maxima
4.5 (4,150 ratings)
View Course
Solution: Ridge obstacle can be solved by moving in several directions at the same time
3. Plateau
Plateau is the region where all the neighbouring nodes have the same value of objective function so the algorithm finds it hard to select an appropriate direction.
Solution: Plateau obstacle can be solved by taking making a big jump from the current state which will land you in non-plateau region
Types of Hill Climbing Algorithm in Artificial Intelligence
Here we discuss the types of a hill-climbing algorithm in artificial intelligence:
1. Simple Hill Climbing
It is the simplest form of Hill Climbing Algorithm. It only takes into account the neighbouring node for its operation. If the neighbouring node is better than the current node then it sets the neighbour node as the current node. The algorithm checks only one neighbour at a time. Following are few of the key feature of Simple Hill Climbing Algorithm
- Since it needs low computation power, it consumes lesser time
- The algorithm results in sub-optimal solutions and at times the solution is not guaranteed
Algorithm
1. Examine the current state, Return success if it is a goal state
2. Continue the Loop until a new solution is found or no operators are left to apply
3. Apply the operator to the node in the current state
4. Check for the new state
- If Current State = Goal State, Return success and exit
- Else if New state is better than current state then Goto New state
- Else return to step 2
5. Exit
2. Steepest-Ascent Hill Climbing
Steepest-Ascent hill climbing is an advanced form of simple Hill Climbing Algorithm. It runs through all the nearest neighbour nodes and selects the node which is nearest to the goal state. The algorithm requires more computation power than Simple Hill Climbing Algorithm as it searches through multiple neighbours at once.
Algorithm
1. Examine the current state, Return success if it is a goal state
2. Continue the Loop until a new solution is found or no operators are left to apply
Let ‘Temp’ be a state such that any successor of the current state will have a higher value for the objective function. For all operators that can be applied to the current state
- Apply the operator to create a new state
- Examine new state
- If Current State = Goal State, Return success and exit
- Else if New state is better than Temp then set this state as Temp
- If Temp is better than Current State set Current state to Target
3. Stochastic Hill Climbing
Stochastic Hill Climbing doesn’t look at all its neighbouring node to check if it is better than the current node instead, it randomly selects one neighbouring node and based on the pre-defined criteria it decides whether to go to the neighbouring node or select an alternate node.
Advantage of Hill Climbing Algorithm in Artificial Intelligence
Advantage of Hill Climbing Algorithm in Artificial Intelligence is given below:
- Hill Climbing is very useful in routing-related problems like Travelling Salesmen Problem, Job Scheduling, Chip Designing and Portfolio Management
- It is good in solving the optimization problem while using only limited computation power
- It is more efficient than other search algorithms
Hill Climbing Algorithm is a very widely used algorithm for Optimization related problems as it gives decent solutions to computationally challenging problems. It has certain drawback associated with it like its Local Minima, Ridge and Plateau problem which can be solved by using some advanced algorithm.
Recommended Articles
This is a guide to Hill Climbing in Artificial Intelligence. Here we discuss the introduction and key features hill-climbing algorithm along with advantages and its types. You can also go through our other suggested articles to learn more –
