Video transcripts
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.
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 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.
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!
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!
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 5, 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 for the neighbor to evaluate
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
...
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.
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 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 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.
