Metaheuristic methods represent a large group of approaches for a range of optimization and constraint satisfaction problems. They are called metaheuristic because they are based on heuristic principles, which are not problem- or domain-specific but more or less general.
Performance and the Lack of Guarantees
Metaheuristic methods tend to be better at escaping local optima in comparison to local methods as exemplified e.g. by gradient-based approaches. There are several reasons for this, one of them being that metaheuristic methods typically operate on populations of candidate solutions so there is a greater chance that at least one of them will eventually end up in the vicinity of the global optimum. Metaheuristic approaches typically come without strong performance guarantees, but in practice they can often produce reasonably good results in a reasonable amount of time.
Most metaheuristic methods are inspired by natural phenomena such as the survival of the fittest, genetics, the behaviour of swarms, etc. To give a few instances:
- Genetic programming: Candidate solutions are represented using artificial genetic code. The initial population is generated randomly. Then over multiple generations the candidates are evaluated and the best are given the greatest chance to reproduce. During reproduction, pairs of candidates undergo crossover, where their genes are mixed. Each candidate also undergoes mutation, where its code is randomly modified with some small probability.
- Evolutionary strategies: Not unlike genetic programming in its fundamental principles. Puts more emphasis on auto-adaptive principles: e.g. parameters of some genetic operators are made part of the genetic code.
- Ant colony optimization: An algorithm inspired by the way ants use pheromones to mark tracks leading to food when collectively exploring the environment and foraging.
- Particle swarm optimization: Inspired by the behaviour of swarms of insects. The candidate solutions are represented by particles, which collectively inform each other’s movement.
- …
Genetic algorithms: the principle.
Flexibility
As regards applicability, metaheuristic methods are generally very flexible: much more so than other classes of optimization methods. For instance, many of them put almost no requirements on the complexity of the candidate solutions and they are also very flexible w.r.t. the objective function: for instance, it does not need to be differentiable since these methods do not rely on gradients.
Candidate solutions can range from simple numeric vectors to complex structures, e.g. abstract syntax trees used to represent programs in genetic programming. The only requirement is that one must be able to provide well-defined operators, e.g. implement crossover and mutation applicable to the candidates.
Scalability
Metaheuristic approaches tend to be computationally scalable because many of them have good support for parallel and distributed execution. However, where evaluation of candidates is very time consuming and hard to parallelize, metaheuristic methods may not be the best choice.
Being rather problem-agnostic, they are also not good at making effective use of all information available about the task. For instance, some problems may require extended simulation to evaluate candidates and this yields a wealth of information, but a metaheuristic method will compress all that into a single scalar value. This necessarily leads to poor sample efficiency (a huge number of evaluations may be needed), which hurts scalability in some contexts.
Use in Multi-objective Optimization
In multi-objective optimization, the goal is to discover the full range of trade-off points among several different criteria of optimality. Given that metaheuristic methods already operate on populations of candidates, they are particularly well suited to this kind of task.