Hill Climbing Algorithm
It is a local search algorithm which continuously moves in the directions of increasing elevation/value to find the "peak of the mountain" or the best solution to the problem. It terminates on reaching the peak value where no neighbour is a higher value.
It is used for optimizing the mathematical problems (heuristic search)
A node of hill climbing algorithm has two components: state and value
Hill climbing can get stuck in local optima.
It can be considered to follow greedy approach.
It does not search the problem space thoroughly, which can limit its ability to find better solutions.
Heuristics
Heuristic search means that this search algorithm may not find the optimal solution to the problem. However, it will give a good solution in reasonable time.
A heuristic function is a function that will rank all possible alternatives at any branching step in the search algorithm based on the available information. It helps the algorithm to select the best route out of all possible routes.
Features of Hill Climbing
The following are the key features of the Hill Climbing algorithm:
-
Generate and test variant:
-
generate possible solutions
-
Test to see if this is the expected solution
-
If the solution has been found, quit, else go to step 1
-
-
Greedy approach: It moves in the direction which optimizes the cost. It does not consider the future consequences of the current state.
-
No backtracking: Does not backtrack the search space, as it doesn’t remember the previous states.
-
Deterministic Nature: Given some initial conditions and same problem configuration, it will always produce the same result.
-
Local Neighbourhood: Explores solutions that are closely related to the current state by making small, gradual changes.
State Space Diagram for Hill Climbing
A graphical representation of the the set of states this search algorithm can reach vs the value of the objective function.
Problems in Different Regions in Hill Climbing
-
Local maximum, where all neighbouring states have lower values than the current state. The search will get stuck here.
-
Plateau, where all neighbouring states have the same value as the current state. So, it is not possible to select the best direction to move.
-
Ridge, a region that is higher than its neighbouring states but itself has a slope.
Example: Solving 8 Puzzle Problem using Irrevocable Control
An example of irrevocable strategy can be applied to 8-puzzle using hill climbing.
We calculate the heuristic value of each state and select the state with the lowest heuristic value.
Here, the heuristic function is the number of tiles out of place in state \(n\) compared to the goal state.
Types of Hill Climbing
-
Simple Hill Climbing: It examines the neighbouring nodes one by one and selects the first neighbouring node which optimizes the current cost as the next node.
-
Steepest-Ascent Hill Climbing: It first examines all the neighbouring nodes and then selects the node closest to the goal state as the next node.
-
Stochastic Hill Climbing: It doesn’t examine all the neighbouring nodes before deciding which node to select. It just selects a neighbouring node at random and decides whether to move to that neighbour or to examine another.