Despite the title of this blog, the term metaheuristic is not
really well defined.
One of the first occurence of the term can (of course) be found in a paper
by Fred Glover[1]: Future Paths for Integer Programming and
Links to Artificial Intelligence[2]. In the section
concerning tabu search, he talks about meta-heuristic:
Tabu search may be viewed as a "meta-heuristic" superimposed on another
heuristic. The approach undertakes to transcend local optimality by a strategy
of forbidding (or, more broadly, penalizing) certain moves.
In the AI field, a heuristic is a specific method that help solving
a problem (from the greek for to find), but how must we understand the
meta word ? Well, in greek, it means "after", "beyond" (like in
metaphysic) or "about" (like in metadata). Reading Glover,
metaheuristics seems to be heuristics beyond heuristics,
which seems to be a good old definition, but what is the definition nowadays ?
The litterature is really prolific on this subject, and the definitions are
numerous.
There is at least three tendencies :
- one that consider that the most important part of metaheuristcs is
the gathering of several heuristics,
- one other that promotes the fact that metaheuristics are designed
as generalistic methods, that can tackle several problems without major changes
in their design,
- the last one that use the term only for evolutionnary algorithms when they
are hybridicized with local searches (methods that are called memetic
algorithms in the other points of vue).
The last one is quite minor in the generalistic litterature, it can mainly
be found in the field of evolutionnary computation, separate out the two other
tendencies is more difficult.
Here are some definitions gathered in more or less generalistic papers:
"iterative generation process which guides a subordinate heuristic by
combining intelligently different concepts for exploring and exploiting the
search space" (Osman and Laporte, 1996[3])
"(metaheuristics) combine basic heuristic methods in higher level frameworks
aimed at efficiently and effectively exploring a search space" (Blum and Roli,
2003[4])
"a metaheuristic can be seen as a general-purpose heuristic method designed
to guide an underlying problem-specific heuristic (...) A metaheuristic is
therefore a general algorithmic framework which can be applied to different
optimization problems with relative few modifications to make them adapted to a
specific problem." (Dorigo and Stützle, 2004[5])
"(metaheuristics) apply to all kinds of problems (...) are, at least to some
extent, stochastic (...) direct, i.e. they do not resort to the
calculation of the gradients of the objective function (...) inspired by
analogies: with physics, biology or ethology" (Dréo, Siarry, Petrowski
and Taillard, 2006[6])
One can summarize by enumerating the expected characteristics:
- optimization algorithms,
- with an iterative design,
- combining low level heuristics,
- aiming to tackle a large scale of "hard" problems.
As it is pointed out by the last reference, a large majority of
metaheuristics (well, not to say all) use at least one stochastic
(probabilistic) process and does not use more information than the solution and
the associated value(s) of the objective function.
Talking about combining heuristics seems to be appropriate for
Ant Colony Optimization, that specifically needs one (following
Dorigo's point of vue), it can be less obvious for Evolutionnary
Algorithms. One can consider that mutation, or even the method's
strategy itself, is a heuristic, but isn't it too generalistic to be called a
heuristic ?
If we forget the difficulty to demarcate what can be called a
heuristic and what is the scope of the term meta, one can
simply look at the use of the term among specialists. Despite the fact that the
definition can be used in several fields (data mining, machine learning, etc.),
the term is used for optimization algorithms. This is perhaps the best reason
among others: the term permits to separate a research field from others, thus
adding a little bit of marketing...
I would thus use this definition:
Metaheuristics are algorithms designed to tackle "hard" optimization
problems, with the help of iterative stochastic processes. These methods are
manipulating direct samples of the objective function, and can be applied to
several problems without major changes in their design.