The world’s leading publication for data science, AI, and ML professionals.

Hill Climbing Optimization Algorithm: A Simple Beginner’s Guide

The intuition behind one of the most popular optimization algorithms

Photo by Isaac Burke on Unsplash
Photo by Isaac Burke on Unsplash

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)_.

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).

An example of a function where there is both a local and global optimum. Diagram by author.
An example of a function where there is both a local and global optimum. Diagram by author.

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:

How To Solve Travelling Salesman Problem With Simulated Annealing

Tabu Search Simply Explained

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:

Plot generated by author in Python.
Plot generated by author in Python.
Plot generated by author in Python.
Plot generated by author in Python.

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:

Medium-Articles/Optimisation/hill-climbing at main · egorhowell/Medium-Articles

References & Further Reading

Another Thing!

I have a free newsletter, Dishing the Data, where I share weekly tips for becoming a better Data Scientist. There is no "fluff" or "clickbait," just pure actionable insights from a practicing Data Scientist.

Dishing The Data | Egor Howell | Substack

Connect With Me!


Related Articles