Introduction

The theory of evolution states that the different forms of life we see today are the result of millions of years of evolution, mutations, and adaptation. The specimens that developed mutations that gave them an advantage over the others prevailed, and that mutation was transmitted to the next generation. That’s how evolution explains the existence of complex life forms like ourselves.

We’re not going to start a debate about the theory of evolution, but this is an idea that’s used in the world of optimization. Evolution, as it’s described in Charles Darwin’s theory, is not a carefully designed process that should converge to the organisms we see today. It has no requirements to ensure convergence. It’s just a process that goes on for millions of years and produces a result as a consequence.

In optimization, we can do the same. Sometimes the functions are very complicated or even unknown, so we can’t assure any requirements or behavior. We can’t assure convergence. Then we just start trying with a lot of candidate points and see if we’re lucky enough to find the optimal solution.

That seems pretty outlandish. There are too many candidate points (maybe even an infinite amount of them) and maybe just one of them is the solution. Exploring all of them seems unfeasible, and it is. But we’re not going to explore naively. We’ll mimic the theory of evolution so good candidates will prevail and will produce even better candidates for the next generation of points. This way, we hope that at some point in that simulated evolution, we get the solution we’re looking for.

Heuristic

Until now, we’ve dealt with algorithms. They are a set of well-defined steps that, if specific requirements hold, will always give us the answer we’re looking for. An algorithm can be exact (like the analytical methods we saw in the “Derivatives and Gradients” chapter) or approximate (like the algorithms in the previous section when we defined an error tolerance).

Exact algorithms always give us the exact answer—they’re the stars of the show. But as we learned already, sometimes we can’t apply and/or afford them. They can have strong requirements or be computationally expensive. That’s why we use approximation algorithms in some cases. We don’t get the exact answer with these, but we can get a well-defined approximation. A well-defined approximation is one that we can measure and even manage. When we defined an error tolerance in the algorithms of the previous section, we were establishing how far we wanted to be from the exact solution. If we use a tolerance of $10^{-6}$, then our approximation is going to be wrong by a $10^{-6}$ margin, at most.

So far we can either solve problems with exact answers or with answers that can be as good as we want. But (surprise!) there are a lot of problems out there that can’t be solved with either class of algorithms. We need a new type of algorithm.

Heuristics are methods that don’t assure convergence at all. We can’t demonstrate that they’re going to give us an exact answer or an approximation with a specific error margin. But empirically, they make sense.

For example, suppose we want to go to a place but don’t know where it is. If we search on Google Maps, we get the exact (or sometimes approximate) direction we need to follow to get to that place. Google Maps give us an algorithm. Turn left at the next intersection, go straight ahead for three blocks, turn left, and we’ll arrive at our destination.

Now let’s suppose we’re offline and we don’t have a map or anything else to help us find our route. What do we do? Probably ask someone for directions. That person might give us the route to follow or might not. We can get lost again in the middle of the trajectory and we’ll need to ask another person again as we hope to reach our destination. Note that we can’t be sure about anything. Maybe there’s no one there to ask, or the person we ask doesn’t know anything about the place, or worse, they mislead us. Nevertheless, we’re going to ask and we’ll (almost) always find what we’re looking for.

In this scenario, we’re essentially using a heuristic. It’s been said that heuristics are algorithms in a clown costume. Note the important detail: our heuristic didn’t require that we have a map or internet connection. We were forced to use the heuristic because we didn’t have other options. In optimization, we have a similar situation.

Sometimes we can’t ensure that our problem fulfills the requirements of an exact or approximation algorithm. Sometimes the time and memory that the execution of those algorithms would demand are unaffordable for us. Then we have no choice: We need a heuristic to get our solution.

Population methods

We’re going to study a specific kind of heuristics. Population methods explore the space of all possible solutions. Of course, this space is very large; otherwise, there would be an exact algorithm that tries all the solutions and finds the best one.

To overcome the size of the solution space, population methods use some techniques that are usually a shortcut to a good solution. However, we can’t ensure that they’ll be a shortcut and we can’t know how good our solution would be.

We’re going to study population methods because they’re among the most used heuristics out there. They’ve also proved to be highly effective. We can know that a heuristic is good when we experimentally compare it with others. Even when we don’t know the exact or approximated solution to a problem, we can compare our solution with the one others have obtained so far. Also, we can compare the execution time, memory consumption, and other variables that could be significant when choosing a method to solve a problem.

Note: We might come across another term: metaheuristic. Heuristics work for specific problems while metaheuristics are problem-independent. We’re going to study metaheuristics since the methods we’re about to learn can be applied to any optimization problem. But we don’t want to use a lot of new words right now. This note is intended to help learners when they search for other resources out there.

As we said at the beginning of the lesson, population methods mimic evolution to find the best possible answer. It all starts with an initial population of solutions, and the heuristic controls how they evolve from one generation to the next. The process ends when some stop criterion is met. We’re going to study two population methods in depth: genetic algorithms and particle swarm optimization. But we’ll also talk about other population methods.

This section and the next one are perhaps the most practical ones in this course. After completing them, we’ll be able to face any optimization problem out there. We hope this encourages you to stay motivated!