Hill Climbing Algorithm in Artificial Intelligence
- Hill climbing algorithm is a local search algorithm which continuously moves in the direction of increasing elevation/value to find the peak of the mountain or best solution to the problem. It terminates when it reaches a peak value where no neighbor has a higher value.
- Hill climbing algorithm is a technique which is used for optimizing the mathematical problems. One of the widely discussed examples of Hill climbing algorithm is Traveling-salesman Problem in which we need to minimize the distance traveled by the salesman.
- It is also called greedy local search as it only looks to its good immediate neighbor state and not beyond that.
- A node of hill climbing algorithm has two components which are state and value.
- Hill Climbing is mostly used when a good heuristic is available.
- In this algorithm, we don't need to maintain and handle the search tree or graph as it only keeps a single current state.
Features of Hill Climbing:-
- Greedy approach:Hill-climbing algorithm search moves in the direction which optimizes the cost.
- No backtracking:It does not backtrack the search space, as it does not remember the previous states.
State-space Diagram for Hill Climbing:-
The state-space
landscape is a graphical representation of the hill-climbing algorithm which is
showing a graph between various states of algorithm and Objective
function/Cost.On Y-axis we have taken the function which can be an objective
function or cost function, and state-space on the x-axis. If the function on
Y-axis is cost then, the goal of search is to find the global minimum and local
minimum. If the function of Y-axis is Objective function, then the goal of the
search is to find the global maximum and local maximum.
- Local Maximum: Local maximum is a state which is better than its neighbor states, but there is also another state which is higher than it.
- Global Maximum: Global maximum is the best possible state of state space landscape. It has the highest value of objective function.
- Current state: It is a state in a landscape diagram where an agent is currently present.
- Flat local maximum: It is a flat space in the landscape where all the neighbor states of current states have the same value.
- Shoulder: It is a plateau region which has an uphill edge.
Types of Hill Climbing Algorithm:
1.Simple Hill Climbing:-
Simple hill climbing is the simplest
way to implement a hill climbing algorithm. It only evaluates the neighbor
node state at a time and selects the first one which optimizes current cost and
set it as a current state. It only checks it's one successor state, and if it
finds better than the current state, then move else be in the same state. This
algorithm has the following features:-Less time consuming,Less optimal solution
and the solution is not guaranteed
2.Steepest-Ascent hill climbing:-
The steepest-Ascent algorithm
is a variation of simple hill climbing algorithm. This algorithm examines all
the neighboring nodes of the current state and selects one neighbor node which
is closest to the goal state. This algorithm consumes more time as it searches
for multiple neighbors
3.Stochastic hill climbing:-
Stochastic hill climbing does not
examine for all its neighbor before moving. Rather, this search algorithm
selects one neighbor node at random and decides whether to choose it as a
current state or examine another state.
Problems in Hill Climbing Algorithm:
1.Local Maximum:
A local maximum is a peak state in the
landscape which is better than each of its neighboring states, but there is
another state also present which is higher than the local maximum.
Solution: Backtracking technique can be a solution of
the local maximum in state space landscape. Create a list of the promising path
so that the algorithm can backtrack the search space and explore other paths as
well.
2.Plateau:
A plateau is the flat area of the search space
in which all the neighbor states of the current state contains the same value,
because of this algorithm does not find any best direction to move. A
hill-climbing search might be lost in the plateau area.
Solution: The solution for the plateau is to take big
steps or very little steps while searching, to solve the
problem. Randomly select a state which is far away from the current
state so it is possible that the algorithm could find non-plateau region.
0 Comments
if u have any doubts please let me know,