What makes a metaheuristic meta?

Question

According to Wikipedia:

...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem...

So a metaheuristic is something like a shaman (master algorithm), who tries to heal a person (solve a mathematical problem) by mixing various spells and herbs (simple heuristics). But why is Evolutionary computation considered a metaheuristic, instead of a simple heuristic:

https://en.wikipedia.org/wiki/Metaheuristic#/media/File:Metaheuristics_classification.svg

What are the simple heuristics that evolutionary computation is composed of? Is it the crossover, mutation, fitness based selection? Are these the simple heuristics?

---

Also related: Difference between heuristic and approximation algorithm?

Answer 1

The distinguishing factor is that meta-heuristics are problem independent.

Look at something like Travelling Salesman. You have 2-OPT, 3-OPT, Nearest Neighbour heuristics. These are all things that really don't carry much meaning outside the specific problem of Travelling Salesman.

A Meta-heuristic, on the other hand, assumes no prior knowledge of the problem. It's not saying "this is something that's likely to produce a good solution to our problem," it's saying that "this is something that is likely to produce good search results in general."

For TSP, the heuristic is that similar solutions will have correlated fitness values. More precicely, the simple heuristic is that, given your current population, the best solutions will look similar to the best ones in your population.

This is where "meta" comes in. Your population is always evolving, which means your heuristic is evolving as your search continues.

When I learned about metaheuristics, they talked less about pure GAs and more about combined techniques, things like Genetic Local Search or Probabilistic Model-based GAs. For PMBAs, it's easier to see the heuristic evolving: you choose some probabilistic model (such as Baysean networks) modelling correlations between input bits and fitness. You search, but the heuristic for which nodes you look at next isn't something static determined beforehand, it's dynamic, based on your probability model. The model keeps evolving, which means the search keeps evolving.

The slides from the class I took are here, you might find them interesting.