Heuristics

Reading time15 min

In brief

Article summary

In this article, you will learn about heuristics. Such algorithm help approximating the solution to a problem that is too complex to be solved exactly.

Main takeaways

  • A heuristic allows to find approximate solutions to a problem.

  • It is a compromise between quality of the found solution and needed computation time.

  • It encodes an intuition on how to approximate a solution to a complex problem.

  • Sometimes, heuristics can find optimal solutions.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Information

Hi! Nice to see that you’ve made it to week 5. Let’s recap your heads.

In the last lesson, we saw that the travelling salesman problem (or the TSP) is complex to solve. However, it is possible to drastically reduce the complexity of the resolution algorithm, provided that the produced solution is not necessarily the optimal one, but a good enough one.

In this lesson, I’m going to introduce the notion of heuristic algorithm, which is a technique used to more quickly solve problems when the classical methods are too slow to find an exact solution. In other words, the objective of a heuristic is to produce a solution in a reasonable time frame that’s good enough for solving the problem at hand.

Usually, heuristics trade optimality, completeness, accuracy, or precision for speed. In a way, a heuristic can be considered a shortcut.

A heuristic most often translates an intuition that is not necessarily supported by formal arguments.

Example with graph traversal algorithms

By now, you should be familiar with several graph traversal algorithms, such as the BFS or DFS, the result of which is to obtain a tree covering a graph from a given vertex.

If you think about it, using one route rather than another can be in itself a heuristic.

For example, consider the following problem: from a Wikipedia page, for example the Wikipedia page on the traveling salesman problem, we want to arrive at another Wikipedia page, for example the Wikipedia page on the number 42, by following hypertext links.

Question: should a DFS or a BFS be used?

There’s no doubt that both methods will get the expected result, given the very high connectivity of the Wikipedia hyperlink graph, but they will certainly not get there in the same way.

What is a good heuristic?

So, what’s a good heuristic?

A heuristic is most often inspired by an intuition, and so it’s not easy to evaluate its quality beforehand.

A heuristic should have two important qualities: to provide a gain, and be limited in terms of complexity. Let’s examine these two features in some more detail.

Provide a gain

To provide a gain, a heuristic should improve the performance of an algorithm according to a given criterion and compared to other heuristics.

For example, imagine that I want to get from this classroom, the yellow X on the map, to the canteen, the red X on the map, in a minimum number of steps.

One possible heuristic to get there is to move in what I know to be the general direction of the canteen, ignoring the presence of walls or obstacles.

This heuristic is probably going to have a generally better outcome than if I use a random orientation.

But in some cases, I might find myself at a dead end, in which case the heuristic does not provide a gain, and even worse, does not provide a solution.

Limited complexity

With regards to the limited complexity characteristic, if using heuristics is as costly as exploring all the possibilities, then there’s no point, you might as well not use it!

Using the same example of me finding my way from this classroom to the canteen, let's assume that to find my way I have to explore all possible paths and count the number of steps for each of them. I can then of course choose the shortest path, but as I've had to explore every possibility before doing so, I will have had to walk much farther than if I'd chosen a simpler heuristic.

Assessing the quality

To assess the quality of a heuristic, it’s generally easier to perform this evaluation ex post. This means that a choice on the heuristic is made, implemented, and then tested on a large number of problem instances, and, finally, the results are compared to the results obtained with other heuristics.

Concluding words

This ends today’s lesson on heuristics. In the next video, you’ll learn how heuristic can help to provide good enough solutions to the TSP. Bye bye!

To go further

2 — Heuristics and optimal solutions

As stated before, the use of heuristics may lead to finding a correct solution to a problem, but not necessarily the optimal one. This is the case for instance of the greedy approach, that iteratively choses locally optimal solutions to estimate a global optimum.

Still, using a heuristic does not always make a solution non-optimal. Recall for instance the bruteforce algorithm with backtracking studied previously.

The efficiency of backtracking strongly depends on the order in which branches of the tree of solutions are explored. In the previous session, you probably have chosen to visit remaining vertices in the meta-graph as they come in your meta-graph structure like this:

​
def solve_tsp (graph, source):
    ...
    for vertex in graph.get_neighbors(current_vertex):
        if vertex not in current_visited_vertices:
            # Explore that branch
    ...

However, using a heuristic to encode an intuition on which neighbor should be explored first may be a good idea, as – if it is a good heuristic – it could lead to exploration of short paths quickly, thus leading to pruning numerous branches.

The following partial code is a possible solution, in which we propose to use a min-heap, that will contain all neighbors, with an associated value corresponding to the score given by the heuristic. Since it is a min-heap, the lower the score, the better the quality of the neighbor:

​
def heuristic (neighbor, ...):
    # Return a score for the neighbor to evaluate
    # In this example, the lower the better, but you could adapt the code to change that
    ...
    return XXX

def evaluate_neighbors (neighbors, ...):
    # Here, we use our heuristic to give a score to all candidate neighbors
    # Then, we use these scores to fill a min-heap
    scores = []
    for neighbor in neighbors:
        score = heuristic(neighbor, ...)
        heapq.heappush(scores, (score, neighbor))
    return scores

def solve_tsp (graph, source) :
    ...
    non_visited_neighbors = [neighbor for neighbor in graph.get_neighbors(current_vertex) if neighbor not in explored_vertices]
    scores = evaluate_neighbors(non_visited_neighbors, ...)
    while len(scores) > 0 :
        best_score, best_neighbor = heapq.heappop(scores)
        # Explore that branch in priority
    ...

You can for instance try to choose as a heuristic to return a score which is the distance between the vertex being explored and the candidate neighbor, i.e., the weight in the meta-graph.

3 — Meta-heuristics

The meta prefix indicates that the word it is associated with is set to a higher level of abstraction. In this case, a meta-heuristic is a heuristic that will itself be used to find heuristics to solve a problem.

Meta-heuristics make it possible to abstract the problem of finding the right heuristics, by considering heuristics as a solution to an optimization problem, whose objective is to maximize precision on the problem studied, while limiting complexity. Thus, a meta-heuristic is an algorithm that will go through the space of possible heuristics, and choose one that will be judged more optimal than the others according to certain criteria (hence the heuristic part in the word).

Meta-heuristics completely ignore the problem studied, considering that the heuristics sought is just a function that must be optimized to minimize a criterion. Thus, the same meta-heuristic can be used to produce heuristics that respond to a very large number of problems.

Some of the most well-known meta-heuristics are ant colonies, genetic algorithms, simulated annealing, etc.

To go beyond