Metaheuristics: Favorising Time over Quality

Humans have been inspired a lot by nature while developing several algorithms used in optimization and artificial intelligence. Indeed, nature shows many signs of intelligence as it can be witnessed while observing ants.

“Am I as admirable as that ant?” — Nobuyuki Fukumoto

In this article, I would like to share some insights on exceptional optimization algorithms called metaheuristics, especially their practical acumen for the operations research community.

Definitions

As per the Metaheuristics Network website, a metaheuristic is a set of concepts that can be used to define approximate methods that can be applied to a wide set of different problems. In other words, a metaheuristic can be seen as a general algorithmic framework that can be applied to different optimization problems with relatively few modifications to make them adapt to a specific problem. When removing the prefix meta, we obtain the word heuristics, which are specific algorithms developed for specific optimization problems.

Classifications

There exist several classifications of metaheuristics. For instance, we can make the difference between metaheuristics that are inspired by natural phenomena, and those that are not. We can also distinguish metaheuristics that work with a population of solutions from those that only handle one solution at a time. Methods that iteratively attempt to improve a solution are called local search methods. Let us retain the Population-based metaheuristics vs Local search Metaheuristics classification.

Local Search Metaheuristics

Local search methods consist of searching in local spaces instead of considering the whole space. They have in common a space S of points that can be visited during the search, a neighborhood N that gives the rules of movement in this space, and a function f that induces a topology on S. Among the famous metaheuristics in this class, we have the descent algorithm, the simulated annealing, the tabu search, the greedy randomized adaptive search procedure (GRASP), the variable neighborhood search (VNS), and the guided local search.

Population-based Metaheuristics

Population-based methods also called evolutionary methods, are based on populations of solutions and allow a population of individuals to evolve according to very specific rules. These methods alternate between periods of individual adaptation and periods of cooperation during which individuals exchange information. Among the famous metaheuristics in this class, we have the genetic algorithms, the scatter search, the adaptive memory method, the ant colony optimization, and the bees algorithm.

Matheuristics

Matheuristics can be defined as algorithms that combine metaheuristics and mathematical programming techniques. For instance, given a mixed integer linear programming problem, a metaheuristic can be used to generate a good feasible solution, which is then given as a warm-start (initial point) to an exact algorithm that seeks optimality.

Applications

For many real-life large-scale problems, finding optimal solutions is very costly. Thus, finding good feasible solutions within a limited amount of time is preferred. Metaheuristics come as efficient methods to find a sufficiently good solution in a decent amount of time. They are an alternative to exhaustive search, which would take exponential time. For instance, the ant colony optimization algorithm has been used to find good solutions for large instances of the traveling salesman problem, which is an NP-complete problem.

When faced with a complex optimization problem, one may think about solving it heuristically before shifting to more sophisticated methods. Metaheuristics allow the discovery of the problem as well as the generation of approximate solutions that can be exploited in exact methods.

What do you think about metaheuristics? I am looking forward to hearing your ideas :-)