Anshul Jain
22 Apr 2020
In our earlier discussions, we defined the various search algorithms used by Artificial Intelligence (AI) Agents to perform specified tasks and to provide the desired outcome. Today, we are going to introduce another important algorithm used in Artificial Intelligence and the role it plays in making machines intelligent. Known as Hill Climbing Algorithm, this algorithm is an optimization technique for solving computationally hard problems.
So, to understand 'what is hill climbing in AI?' Continue reading our hill climbing algorithm tutorial.
What is Hill Climbing in Artificial Intelligence?
Another important research area in the field of artificial intelligence, Hill Climbing algorithm in artificial intelligence is an important optimization and heuristic search technique, used to generate the most accurate and optimal solution for a given problem, leveraging the concept of iteration.
Also considered to be an iterative algorithm, the hill climbing algorithm is similar to the greedy local search algorithm, as it explores the search space until all possible solutions are generated and it reaches the expected goal state. Furthermore, it only considers the current states and not the future states, while searching for the optimal solution and hence requires fewer conditions than other search techniques.
Defining Hill Climbing Algorithm in Artificial Intelligence with Example:
The travelling salesman problem is the most common example used by people to define the concepts of the Hill Climbing Algorithm, wherein the target is to minimize the distance he travels. However, another example used to define the concepts of this algorithm is n-queens problems.
Wherein, different queens are positioned on an n × n board, with none of them sharing the same row, column, or diagonal. In short, the focus here is to place a number of queens on the board in such a manner that none of them are attacking each other. This can be accomplished by reducing the heuristic cost to zero and by calculating the cost of the board after each move.
Features of Hill Climbing Algorithm:
Often used in cases when a good heuristic function is available for evaluating different states, as well as when no other useful information or data is provided, the hill-climbing algorithm is further characterized by the following features:
- It is a heuristic approach for optimizing problem
- It only looks at the current state and the immediate future state.
- A variant of the generate and test algorithm.
- Uses a greedy approach to keep generating possible solutions, until it finds the expected output.
- Finds a better solution by making an incremental change to the solution.
Now that we understand the concepts of Hill Climbing Algorithm, let us move on to the workings of the hill-climbing algorithm.
Workings of Hill Climbing Algorithm:
The workings of the hill algorithm can be grouped into the following steps:
1. Initial State Evaluation:
The process is initiated by evaluating the initial state. If this state is the goal state, the process is ended here itself. However, if it isn’t the goal state, the process moves on to the next stage.
2. Select New State for Comparison:
As the current state was not the goal state, the process is kept in the loop, until a solution is found or no further options are left for comparison. However, if this state is near the goal state it becomes the current state.
2. Evaluate the New State: This evaluation can result in three conditions:
- If this is the goal state, the process is finally ended.
- If it is better than the current state then it becomes the current state.
- If it isn’t better than the current state, then the second stage is repeated.
In short, the focus of Hill Climbing is to reach the goal state, by directly evaluating the immediate/current state, until there are no more options left.
Variants of Hill Climbing Algorithm:
Here are the various types of Hill Climbing in AI:
1. Simple Hill Climbing:
The first type of hill climbing algorithm used in AI, simple hill climbing examines the neighboring nodes one by one and chooses the first neighboring node which optimizes the current cost as the next node.
2. Steepest Ascent Hill climbing:
Unlike the former, the Steepest Ascent hill-climbing first examines all the neighboring nodes and then selects a neighbor or the node closest to the solution state as of the next node. In short, this type of hill-climbing algorithm compares all successors and selects the one closest to the solution.
3. Stochastic Hill Climbing:
The third type of hill-climbing algorithm, stochastic hill-climbing randomly selects a neighboring node and based on the amount of the improvement decides whether or not to move to the next node.
4. Random-Restart Hill Climbing:
Considered to be a meta-algorithm which is built on top of the hill climbing algorithm, random-restart hill climbing or shotgun hill climbing performs the process iteratively with a random initial condition, in each phase.
Advantages of Hill Climbing Algorithm:
From being memory efficient to helping agents get accurate results, the advantages offered by the hill climbing-algorithm are various, like:
- It can be used in conversions and discrete domains.
- It requires fewer conditions than other search techniques.
- Helpful in solving pure optimization problems, where the focus is on finding the best state.
Problems of Hill Climbing Algorithm:
Though the benefits of the hill climbing algorithm are numerous, there are some issues or problems associated with it, which can impact the processing of the search. Therefore, here are the various problems of the hill climbing technique, which prevent the algorithm to reach the best state or the global maximum:
1. Local Maxima:
Local maxima or local maximum is where all neighboring states have values worse than the current state. This leads to the termination of the process, even if a better solution is available. To reach the solution, backtracking is used.
2. Ridges & Alleys:
In ridges and alleys, the process moves downwards in all possible directions, which makes it look like a peak and leads to the termination of the process. To avoid this, bidirectional search is used.
3. Plateau:
Here all neighbors share the same value, which makes it impossible to choose a direction as well as reach the goal state. To avoid this, a random state is selected which is far away from the current state.
Apart from these, other disadvantages offered by the hill-climbing algorithm are:
- It is not an efficient searching method.
- Not suitable for problems where the value of heuristic function drops suddenly.
- It is a local method, where the focus is on getting the immediate solution after considering the current state, rather than exploring all possible outcomes.
Conclusion:
From the above discussion, we can conclude the search algorithms like Alpha Beta Pruning are creating a revolution in the field of Artificial Intelligence and helping it pay a new and more efficient way of creating advanced approaches to solving such problems. Moreover, the alpha-beta pruning algorithm is a quality optimization over the min-max algorithm, and together with the minimax algorithm is becoming the foundation of the searching techniques.
