Contents of the page

On this page you’ll learn about heuristic algorithms, and how they can help to solve computational problems faster.

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.

Question: should a DFS or 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.

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 Lab 4, you probably have chosen to visit remaining vertices in the meta-graph as they come in your meta-graph structure like this:

def tsp (meta_graph, initial_vertex) :
...
for neighbor in meta_graph[vertex] :
if neighbor not in explored_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 pseudo-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 some score

def evaluate_neighbors (neighbors, ...) :
scores = create_structure()
for neighbor in neighbors :
score = heuristic(neighbor, ...)
push_to_structure(scores, (score, neighbor))
return scores

def tsp (meta_graph, initial_vertex) :
...
non_visited_neighbors = [neighbor for neighbor in     meta_graph[vertex] if neighbor not in explored_vertices]
scores = evaluate_neighbors(non_visited_neighbors, ...)
while len(scores) > 0 :
best_score, best_neighbor = pop_from_structure(scores)
# Explore that branch
...

Let us 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.

Here, we compare an exhaustive solution using that heuristic and an exhaustive solution without it (both with backtracking). An exhaustive solution without backtracking is also assessed:

for i in {1..10}; do echo $i; python pyrat.py --rat AIs/exhaustive.py -p$i --tests 100 --nodrawing --synchronous >> results_exhaustive.csv; done
for i in {1..10}; do echo $i; python pyrat.py --rat AIs/exhaustive_backtracking.py -p$i --tests 100 --nodrawing --synchronous >> results_exhaustive_backtracking.csv; done
for i in {1..10}; do echo $i; python pyrat.py --rat AIs/exhaustive_backtracking_heuristic.py -p$i --tests 100 --nodrawing --synchronous >> exhaustive_backtracking_heuristic.csv; done

Here, we choose to study the execution time as a function of the number of pieces of cheese present in the maze, and average the results over 100 random mazes:

This analysis suggests that the chosen heuristic is not very efficient (note the logarithmic scale) compared with a simple exhaustive solution with backtracking that processes vertices in a random order.

Metaheuristics

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

Metaheuristics makes 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 metaheuristic 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).

Metaheuristics 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 metaheuristic can be used to produce heuristics that respond to a very large number of problems.

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

Quiz

A heuristic algorithm is used to...
A good heuristic must...