Hill Climbing Optimization Algorithm: A Simple Beginner’s Guide
The intuition behind one of the most popular optimization algorithms
Background
Many industrial and research problems require some form of optimization to arrive at the best solution or result. Some of these problems come under the combinatorial optimization category which means they often can’t be solved by brute force in a reasonable amount of time. Therefore, we turn to heuristic and meta-heuristic algorithms which don’t guarantee finding the best global solution but often compute a sufficient solution in a reasonable amount of time.
One such meta-heuristic algorithm is the hill climbing algorithm, which is the topic of this article. We will dive into the theory, advantages vs disadvantages and finish by implementing the algorithm to solve the famous traveling salesman problem (TSP).
But first, make sure to subscribe to my YouTube Channel!
Click on the link for video tutorials that teach you core data science concepts in a digestible manner!
Hill Climbing Algorithm
Overview
Hill climbing is a meta-heuristic iterative local search algorithm. It aims to find the best solution by making small perturbations to the current solution and continuing this process until no better solution is found. Additionally, it is a greedy algorithm as it only cares about making local optimal moves, so it can often get stuck in a local optimum (see diagram below).
Algorithm
The general flow of the hill climbing algorithm is as follows:
- Generate an initial solution, which is now the best solution.
- Select a neighbour solution from the best solution.
- If the neighbour solution is better than the best solution, set the best solution to be equal to the neighbour solution.
- Repeat the above two steps until the neighbour solution is not better than the best solution or some other termination condition is met such as a number of iterations.
If this still seems quite vague don’t worry! We will apply the above algorithm to a real-life example in Python later on.
Types
There are sundry types and variations of the hill climbing algorithm. Listed below are the most common:
- Simple Hill Climb: Considers the closest neighbour only.
- Steepest Ascent Hill Climb: Considers all neighbours and selects the best.
- Stochastic Hill Climb: Picks one neighbour at random.
The steepest ascent version would lead to more optimal performance but requires more compute resource.
Pros & Cons
Let’s briefly list the main pros and cons of the hill climbing algorithm:
Pros:
- Very intuitive and easy to explain to peers, stakeholders, etc.
- Can be applied to both continuous and discrete objective functions and problems.
- Able to solve a variety of different problems.
Cons:
- Likely to get stuck in local minima/maxima, so can’t guarantee to find the best global solution.
- Plateaus can occur where all neighbours have the same objective score.
There are more complex algorithms such as simulated annealing and tabu search, similar to the hill climb, but don’t get stuck in local minima and greater explore the search space. To learn more about these algorithms, checkout my previous posts here:
Python Implementation Example
Travelling Salesman Problem
We will now code the hill climbing algorithm to solve the traveling salesman problem (TSP). However, before that, let’s briefly state and explain what we are trying to solve in the TSP.
TSP is a classic problem in optimization and poses the question:
‘What is the shortest route to visit a given list of cities once and returning to the starting point?’
The problem sounds very simple, however, solving it by brute force becomes computationally intractable due to the combinatorial explosion that occurs as the number of cities increases. For example, for 10 cities there are ~300,000 possible routes!
Number of possible routes as a function of the number of cities n is (n-1)!/2. So, its computational complexity is O(n!).
At about 20 cities is when the brute-force approach becomes infeasible to solve with it taking ~2,000 years to compute! Astonishingly, for 61 cities it is a wapping 10⁶⁷ years!
Hill Climbing For TSP
Let’s briefly list the pseudo-code that we will use to implement the hill climbing to solve the TSP. We will be using the steepest ascent version:
- Generate an initial tour and set it as our best solution.
- Produce a list of neighbour solutions by swapping two cities from the current best solution.
- Get the best neighbourhood solution (shortest distance) from these neighbourhood solutions and set it to the current solution.
- Compare the current solution to the best solution. If it is shorter, then set the best solution equal to the current solution.
- Repeat this process until the current solution is worse than the best solution.
Python Code
Below is a boilerplateHillClimb class for the above algorithm we just ran through:
Let’s now run the class and plot the results of the initial and best found solutions for 20 synthetically generated cities:
As we can see the hill climb has found a better solution than the initial solution, however it clearly isn’t the global minimum. Nonetheless, it found a sufficient solution and it didn’t take 2,000 years!
Summary & Further Thoughts
In this post, we have discussed the meta-heuristic local search hill-climbing algorithm. This algorithm makes small incremental perturbations to the best solution until we reach a point where the changes do not lead to a better solution. This algorithm produced sufficient performance for the traveling salesman problem, however it got stuck in a local minimum which is the main con of this optimization algorithm.
The full code used in this article can be found at my GitHub here:
Another Thing!
I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist, and the latest AI news to keep you in the loop. There is no “fluff” or “clickbait”, just pure actionable insights from a practicing Data Scientist.
References & Further Reading
Connect With Me!
(All emojis designed by OpenMoji — the open-source emoji and icon project. License: CC BY-SA 4.0)
