📈 #17 Solving complex problems made simple with metaheuristics

Effortlessly conquer optimization challenges with streamlined strategies

Honestly, I didn't think we'd get to this topic so soon, but here we are. This week on Feasible, I want to talk to you about metaheuristics:

• Advantages

• Limitations

• 2 specific examples

The main reason is that exact algorithms are the most typical when it comes to solving optimization problems, but they have a significant drawback: there is a class of practically interesting problems for which we don't know exact algorithms with reasonable execution times. Even if an algorithm exists to find solutions, it would take too much time to solve them.

And other techniques are needed, of course.

Once you know them, a new world of possibilities opens up when solving optimization problems.

In fact, I myself started right at this point, and it was what got me hooked on the field. But that's another story. Now...

Let's go for it!

Since I started talking about heuristics a few weeks ago until now, almost without realizing it, you have been advancing to more advanced techniques. The path was clear:

Heuristics → Local Search → Metaheuristics

And it makes more sense this way because these last techniques - metaheuristics - build on previous concepts, improving the solutions found with the techniques I have already presented.

But, what is a metaheuristic?

A high-level master procedure that guides and modifies other heuristics to explore solutions beyond simple local optimality.

Fred Glover, Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13:533 549, 1986.

Basically, they work by iteratively evolving a solution or a set of solutions until it is considered good enough that further search for other solutions is stopped.

When I talked to you about local search procedures, we saw that local search gets stuck in a local optimum. Well, metaheuristics come to solve that problem: they can move in the solution space to find a better solution. And they do it thanks to a key concept.

I'm sure you've heard of exploration vs exploitation, which is often discussed in Artificial Intelligence (especially in Reinforcement Learning)… Well, that's exactly what metaheuristics do. I've always known it as diversification vs intensification, but it's exactly the same concept:

• Diversification: the idea of moving in the solution space to find different solutions.

• Intensification: the idea of intensively exploring a specific area of the solution space to find a local optimum.

So, here are their advantages, limitations, and a couple of metaheuristics.

🚀 Advantages

Metaheuristics have two main advantages over other heuristics/local searches, but also over exact algorithms.