Metaheuristics – when good enough beats perfect

Most people have a strong idea of the incredible performance of today’s computers. In some way, rightly so, because each of us carries their own supercomputer in their pocket — a mobile phone — that is able to perform a huge number of operations at the same time. However, only a small minority realize that there are many problems in the field of mathematics that still pose some kind of computational challenge for computers.

When one more makes a big difference

Such a computational challenge is best shown by the example of an optimization problem. The traveling salesman problem is one such problem and assumes that there is a given map on which cities are marked with given distances between them. The task of the traveling salesman is to leave one city, visit all the others — each of them only once — and return to the starting point, with the total distance traveled to be as short as possible.

It sounds easy, but, unfortunately, the brute-force method does not apply here. The number of combinations depending on the number of cities \(n\) is \(\frac{(n−1)!}{2}\), so the number grows very fast. For example, let’s take a network of 10 cities. Based on the given formula, we get 181,440 possible paths, of which we need to find the shortest one. If we add one more city to our network, the number will increase to 1,814,400, and if we add another one, we get 19,958,400 paths to check! 

As presented, the smallest increase in the number of cities noticeably translates into an increase in the number of available combinations. Searching the entire pool of available solutions, depending on the number of connections, can take from several seconds to several years. Therefore, at the expense of solution accuracy, the right approach is to look for a “good enough” solution instead of a perfect one.

Metaheuristics and heuristics

Heuristic algorithms are those that abandon the ambition to find the best solution, but promise to find a fairly good one in a satisfactory time. Thanks to heuristics, we can limit the number of searched solutions, resulting in a faster and less computationally expensive solution. Unfortunately, they do not guarantee to find the solution closest to the optimum, but they do allow to find a solution close to the optimum in a satisfactory time.

We can divide heuristics into two types. The first one is constructive heuristics, which create a solution step by step and when the program ends, the discovered solution to the problem is returned. 

The other one is improvement heuristics, which start their operation with knowledge of an acceptable solution, which is not the optimal one. In the next steps of their operation, improvement heuristics modify the input solution to obtain the most satisfactory result.

Metaheuristics are an example of improvement heuristics. Their flow is very often inspired by observations of nature, physical or social phenomena.

Observation of nature 

Nature has always been a great inspiration for humans. The same is true in algorithms. Observation of nature has given ideas for approaches to resolving not only the traveling salesman problem, but also a lot of optimization or combinatorial problems.

The very process of evolution of species on Earth was the basis for a group of evolutionary algorithms assuming the creation of populations of solutions, crossing individuals with one another and introducing random mutations to obtain the next population with better solutions than the current ones. 

The population size of solutions considered by the algorithm is determined by external constraints (e.g. how much memory or processing power is available for our task). In every iteration (called ‘epoch’), the population creates new individuals, which are the basis for the new population. The units that make up the population shall be understood as the solutions to almost any optimization problem, but we need to bear in mind that this requires changes in operator implementations.

Ants also contribute to the development of metaheuristic algorithms — as one of herd (known also as ‘boids’) algorithms, the ant colony optimization algorithm takes inspiration from how ants communicate by leaving pheromone tracks, thanks to which they are able to find the shortest path between the anthill and food. Depending on what kind of problem we want to solve, the “path” could be interpreted in different ways — not only as a route for the traveling salesman problem that I described above, but it can also find solutions for many other types of problems, including edge detection in image processing! 

But not only living organisms contribute to the search for metaheuristics. The simulated annealing algorithm has its genesis in the process of metallurgy and the observation that the higher the temperature of the metal, the more ductile it becomes. Similarly, in the algorithm, the larger the parameter corresponding to temperature, the more the search is inclined to look for new, sometimes risky solutions; the smaller, the search sticks around the best known solution and doesn’t explore much. With a high temperature value, the probability of getting stuck in a local minimum of a solution to a given problem is lower at the cost of more solutions to be checked to find a good one. When the temperature of this parameter decreases with every iteration, the situation is reversed — the algorithm consistently returns good solutions, but with that, the probability of it getting stuck in a local minimum rises as well. That’s why it’s important to control the amount of time the algorithm stays in its “hot” and “cold” phase.

Summary

Very often the term “good enough” appears in our mind without any sign of satisfaction. We always have the feeling that it could have been better, that it could have been perfect. Some optimization or combinatorial problems are able to effectively change our way of thinking in this regard. Metaheuristics perfectly prove that “good enough” can mean “better” in many areas (such as running time or resource consumption) than this dreamed-up, perfect solution.