Hill Climbing search in Artificial Intelligence is like finding the highest point on a hill in a simplified manner to solve problems. Imagine you are on a hilly landscape, and your goal is to reach the top of the highest hill. In the Artificial Intelligence world, this “hill” represents the best solution to a problem.
Table of Contents
How Hill Climbing Search in Artificial Intelligence Works?
Hill climbing is basically a local search algorithm which is used for solving mathematical optimization problems. The basic idea is to iteratively move towards the direction of increasing elevation (or decreasing, depending on the optimization goal) until a peak or valley is reached.
Here is an explanation of how Hill Climbing search works:
- Starting Point: Begin at a random point on the hill. This point represents a solution to the problem, although not necessarily the best one.
- Evaluating Moves: Look around at neighbouring points on the hill. Each of these points represents a different solution. Evaluate how good or bad these solutions are compared to your current position.
- Choosing the Best Move: Pick the neighbouring point that seems to be an improvement over your current solution. This is like deciding to take a step uphill to get closer to the top.
- Repeating Steps: Repeat the process from your new position. Keep making small steps uphill until you can’t find a better solution. At this point, you have reached the top of the hill, which represents the best solution the algorithm could find.
Hill Climbing Algorithm Example
Now that you understand the logic behind the hill climbing algorithm, here is a simple example of a hill climbing algorithm applied to the Travelling Salesman Problem (TSP).
Imagine a salesman who needs to visit a set of cities and return to the starting city. All the while, he was aiming to minimize the total distance travelled.
Hill Climbing Search Algorithm
- Start Position: The salesman starts at a random city. Let’s say they start at A.
- Evaluate Neighbours: Look at the neighbouring cities to the current position. These represent potential moves. For city A, neighbours are B, C, and D.
- Choose the Best Move: Evaluate the total distance for each move and choose the city that minimises the total distance. Suppose moving to city B results in the shortest total distance.
- Move and Repeat: Move to city B and repeat the process from this new city. Now, the neighbours are A, C, and D.
- Choose Again: Evaluate the total distance for each move and choose the city that minimises the total distance. Move to city C, as it provides the shortest total distance.
- Repeat until No Improvement: Keep repeating this process until there is no move that reduces the total distance further. The salesman might explore different routes until reaching a local minimum in terms of total distance.
Example Steps of the Hill Climbing Search:
- Start at A
- Neighbours: B, C, D, Move to B (total distance: 10)
- Neighbours: A, C, D, Move to C (total distance: 25)
- Neighbours: A, B, D, Move to D (total distance: 45)
- Neighbours: A, B, C, Move to A (total distance: 57)
Learn Artificial Intelligence with Be10x AI tool Workshop.
Types of Hill Climbing in Artificial Intelligence
There are several types of Hill Climbing algorithms, each with its own way of selecting and evaluating moves:
- Steepest Ascent Hill Climbing
- Stochastic Hill Climbing
Steepest Ascent Hill Climbing Search
Steepest-Ascent Hill Climbing, also known as Best-First Search, is a type of Hill Climbing algorithm used in Artificial Intelligence. It’s a more systematic approach compared to Simple Hill Climbing.
It begins at a random or initial solution in the search space. This solution could represent a configuration or state in a problem-solving context. Then it examines all neighbouring solutions or states reachable from the current position. These Neighbours represent potential moves.
Advantages of Steepest-Ascent Hill Climbing Search are:
It has a systematic approach which evaluates all Neighbours and selects the best. Tends to move toward the direction of the steepest ascent, potentially reaching optimal solutions.
Limitations of Steepest-Ascent Hill Climbing Search are:
It may still get stuck in local optima if the search space has many peaks. Further, it can be computationally expensive if the search space is large.
Stochastic Hill Climbing Search
Stochastic Hill Climbing is a type of search algorithm used in Artificial Intelligence (AI) and optimization problems. Unlike deterministic approaches, stochastic algorithms introduce an element of randomness into the decision-making process.
In Stochastic Hill Climbing, when faced with multiple possible moves or choices, the algorithm doesn’t always select the best or most promising one. Instead, it makes random choices based on some probability distribution. This introduces variability into the search process.
Advantages of Stochastic Hill Climbing Search are:
It introduces randomness for broader exploration of the solution space. This search algorithm is less likely to get stuck in local optima due to random choices.
Limitations of Stochastic Hill Climbing Search are:
Stochastic algorithms generally take longer to converge to an optimal solution compared to deterministic counterparts. The randomness introduces variability, and the algorithm may require more iterations to find the best solution. Further, Properly tuning the probability distributions for random choices can be challenging. Striking the right balance between exploration and exploitation requires careful consideration, and suboptimal tuning may hinder performance.
Random Restart Hill Climbing Search
Random Restart Hill Climbing search is an optimization technique that involves repeatedly applying the Hill Climbing algorithm from multiple random starting points. This approach is designed to overcome the limitations of standard Hill Climbing, particularly the risk of getting stuck in local optima.
- Start with Multiple Initial Solutions: Instead of starting from a single random point, the algorithm initiates multiple random starting points.
- Apply Hill Climbing from Each Starting Point: Apply the Hill Climbing algorithm independently from each of the random starting points. Each run of the Hill Climbing algorithm proceeds until a termination condition is met, such as reaching a local optimum.
- Evaluate Best Solutions: After all runs are complete, compare the solutions obtained from each run and identify the best one. This solution is considered the final output of the Random Restart Hill Climbing search algorithm.
- Termination: The algorithm terminates when a specific condition is met, such as reaching a predefined number of iterations or achieving a satisfactory solution.
Example of Random Restart Hill Climbing search:
Let us say we have five starting points: A, B, C, D, and E. The Hill Climbing search algorithm is applied from each starting point, and it converges to local optima. This resulted in peak heights: 25, 28, 24, 27, and 26, respectively.
- A: Peak at 25
- B: Peak at 28
- C: Peak at 24
- D: Peak at 27
- E: Peak at 26
In this example, starting point B led to the highest peak (28). Therefore, the Random Restart Hill Climbing search algorithm would consider the solution obtained from the Hill Climbing run initiated from starting point B as the final output.
Advantages of Random Restart Hill Climbing search are:
By starting from multiple random points, the algorithm explores a larger portion of the solution space. Further, the likelihood of getting stuck in a local optimum is reduced because the algorithm has multiple chances to find different regions of the solution space.
Limitation of Random Restart Hill Climbing search are:
Random Restart Hill Climbing may be computationally expensive, especially if the Hill Climbing algorithm is complex or the solution space is vast. Some parts of the solution space may be explored more than once and this leads to redundancy.
Be10x AI Course: Best Artificial Intelligence Online Course for Beginners
Are you looking to change the way you work and boost your career with AI? Be10X brings you a unique opportunity to master AI tools through our exclusive AI course. Our Artificial Intelligence course is designed for everyone, whether you’re a seasoned professional or just a beginner. In the 3 hours long live artificial intelligence workshop, you will learn to use AI tools efficiently and cut down your daily workload. Imagine completing tasks in just 10 minutes that used to take you hours.
In Be10x Artificial Intelligence Online Course, you will learn:
- AI Tools for LinkedIn
- AI Tools for Microsoft Excel
- AI Tools for Building Presentations
- AI Tools for Interview Skills
- AI Tools for Report Building (Research)
- AI Tools for Coding/Programming
Not just that, you will also receive a certification from Be10X to showcase your AI tool capabilities on your resume. Now, you can stand out among professionals by highlighting your proficiency in AI tools.
Register before in the Be10x’s AI workshop and get bonuses worth Rs.10,500.