Hill Climbing Algorithm in Artificial Intelligence

In this page we will learn about What is Hill Climbing Algorithm in Artificial Intelligence?, Features of Hill Climbing, State-space Diagram for Hill Climbing, Different regions in the state space landscape, Types of Hill Climbing Algorithm, Simple Hill Climbing, Algorithm for Simple Hill Climbing, Steepest-Ascent hill climbing, Algorithm for Steepest-Ascent hill climbing, Stochastic hill climbing, Problems in Hill Climbing Algorithm, and Simulated Annealing.

What is Hill Climbing Algorithm in Artificial Intelligence?

The hill climbing algorithm is a local search algorithm that proceeds in the direction of rising elevation/value in order to find the mountain's peak or the best solution to the problem. When it hits a peak value, it stops since no neighbor has a greater value.
The hill climbing algorithm is a strategy for optimizing mathematical problems. The Traveling-salesman algorithm is one of the most well-known examples of a hill climbing algorithm. We have a problem where we need to reduce the salesman's trip distance.
It's also known as greedy local search because it just considers its good immediate neighbor state and nothing else.
A node of 'hill climbing algorithm' has two aspects which are state and value.
When a decent heuristic is available, hill climbing is usually used.
We don't need to maintain or handle the search tree or graph in this technique because it simply preserves a single current state.

Features of Hill Climbing:

Some main features of Hill Climbing Algorithm are:

Generate and Test variant: Hill Climbing is a Generate and Test method variant. The Generate and Test methods generate input that aids in determining which way to move in the search space.

Greedy approach: The hill-climbing algorithm searches in the direction that saves the most money.

No backtracking: There is no backtracking in the search space because it does not recall the prior states.

State-space Diagram for Hill Climbing:

The state-space landscape is a visual portrayal of the hill-climbing algorithm that depicts a graph between the program's many stages and the Objective function/Cost.

On the y-axis, we have the function, which might be an objective or cost function, and on the x-axis, we have state-space. If the Y-axis function is cost, the purpose of the search is to discover the global and local minimums. The purpose of the search is to discover the global and local maximum if the Y-axis function is Objective function.

Different regions in the state space landscape:

Local Maximum: A local maximum is a state that is better than its neighbors, but it is also higher than another state.
Global Maximum: The best conceivable state of the state space landscape is global maximum. It has the greatest objective function value.
Current state: A state in a landscaping diagram where an agent is currently present is known as the current state.
Flat local maximum: A flat space in the landscape with the same value for all neighbor states of present states.
Shoulder: This is a plateau with an upward incline.

Types of Hill Climbing Algorithm:

1. Simple hill Climbing
2. Steepest-Ascent hill-climbing
3. Stochastic hill Climbing

1. Simple Hill Climbing

The simplest approach to create a hill climbing algorithm is to use simple hill climbing. Only one neighbor node state is evaluated at a time, and the first one that optimizes current cost is chosen as the current state. It just checks one successor state, and if it finds it to be better than the present state, it moves to that state. Otherwise, it stays in the current state. The following are the characteristics of this algorithm:

Less time consuming
The optimal solution is less and the solution is not guaranteed

Algorithm for Simple Hill Climbing:

Step 1: Assess the current state; if it is a goal state, return success and stop.

Step 2: Create a loop until a solution is found or no new operators are available.

Step 3: Choose an operator and apply it to the current state.

Step 4: Check the new state:

If the new state is the goal state, return success and quit.
If the new state is better than the present state, it will be assigned as the current state.
Else if not better than the current state, then return to step2.

Step 5: Exit.

2. Steepest-Ascent hill climbing:

A version of the simple hill climbing algorithm is the steepest-Ascent algorithm. This algorithm analyses all of the current state's nearby nodes and chooses the one that is closest to the goal state. Because it searches for numerous neighbors, this method takes longer.

Algorithm for Steepest-Ascent hill climbing:

Step 1: Asses the initial state, if it is goal state, return success and then stop, else make current state as initial state.

Step 2: Loop until a solution is found or the current state does not change.

Let SUCC be a state as that any successor of the current state will be better than this.
For each operator that applies to the current state:
1. Apply the new operator and generate a new state.
2. Evaluate the new state.
3. If it is goal state, then return it and quit, else compare it to the SUCC.
4. If it is better than SUCC, then set new state as SUCC.
5. If the SUCC is better than the current state, then set current state to SUCC.

Step 3: Exit.

3. Stochastic hill climbing:

Stochastic hill climbing does not check for all of its neighbors before moving. Rather, this search method chooses one neighbor node at random as the current state and decides whether to study another state.

Problems in Hill Climbing Algorithm:

1. Local Maximum: In the landscape, a local maximum is a peak state that is better than each of its nearby states, yet there is another state that is higher than the local maximum.

Solution: Backtracking is a technique that can be used to solve the local maximum in a state space landscape. Make a list of the potential paths so that the algorithm can go back in time and expand the search space and other paths.

2. Plateau: A plateau is a flat portion of the search space in which all of the neighbor states of the current state have the same value, indicating that the algorithm has failed to determine the optimum path to take. In the plateau area, a hill-climbing search could be lost.

Solution: The solution to the plateau is to take large or small steps while seeking for a solution to the problem. Select a state at random that is far distant from the present state so that the algorithm can discover a non-plateau region.

3. Ridges: A ridge is a type of local maximum that is distinct from the others. It has a higher surface area than its surroundings, but it is also on a hill and cannot be reached in a single movement.

Solution: We may improve this problem by using bidirectional search or travelling in different directions.

Simulated Annealing:

A hill-climbing algorithm that never moves towards a lower value is certain to be incomplete because it can get trapped on a local maximum. And if the process uses a random walk to move a successor, it may be complete yet inefficient. Simulated Annealing is a method for obtaining both efficiency and completeness.

Annealing is a mechanical term for the process of hardening a metal or glass to a high temperature and then gradually cooling it to achieve a low-energy crystalline state. Simulated annealing employs the same approach, with the algorithm selecting a random move rather than the optimum. If the random motion improves the situation, it will continue on its current path. If not, the algorithm will not work. Otherwise, the algorithm takes the option with the lowest probability or continues downhill and chooses a different path.