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

All in One Data Science Bundle(360+ Courses, 50+ projects)

Price
View Courses

360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (82,441 ratings)

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

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 the Hill Climbing Algorithm. It only takes into account the neighboring node for its operation. If the neighboring node is better than the current node then it sets the neighbor node as the current node. The algorithm checks only one neighbor at a time. Following are a few of the key feature of the 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 neighbor 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 neighbors 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 neighboring nodes to check if it is better than the current node instead, it randomly selects one neighboring node, and based on the pre-defined criteria it decides whether to go to the neighboring 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 drawbacks associated with it like its Local Minima, Ridge, and Plateau problem which can be solved by using some advanced algorithm.

Quiz Result
Total Questions	Correct Answers	Wrong Answers	Percentage