metaheuristic
In plain wordsA general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
A general search recipe, not tied to any one problem, that steers simpler heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. toward good solutions of hard optimization problems, typically by balancing intensification (exploiting promising regions) against diversification (exploring new ones). Single-solution metaheuristics include simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends., iterated local search and variable neighborhood search; population-based ones include genetic algorithmsgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve. and other evolutionary algorithmsevolutionary computation, n.: Problem-solving by simulated evolution, much as breeders improve crops: keep many candidate answers, let the better ones produce slightly altered offspring, drop the worse, and repeat for many rounds., ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out. and particle swarm optimizationparticle swarm optimization, n.: An optimization method inspired by flocking birds: candidate solutions 'fly' through the space of possibilities, each pulled toward the best spot it has found and the best spot its neighbors have found.. Metaheuristics trade guarantees for flexibility: they rarely prove optimality, but they find near-optimal solutions to large scheduling, routing, design and configuration problems on which exact methods time out. Researchers have criticized a proliferation of supposedly novel metaphor-based metaheuristics that rename existing ideas.
Origin
Coined by Fred Glover in 1986, in the paper that introduced tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends., from Greek meta- ('beyond') and heuristic. The term spread through operations research in the 1990s.
Usage note
The no free lunch theoremno free lunch theorem, n.: A mathematical result saying that no learning or search method is best for every possible problem: any method that wins on some problems must lose on others. implies that no metaheuristic outperforms all others when averaged over all possible problems; performance depends on matching the method to problem structure.
Related
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
- simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops.
- tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.
- genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve.
- evolutionary computationevolutionary computation, n.: Problem-solving by simulated evolution, much as breeders improve crops: keep many candidate answers, let the better ones produce slightly altered offspring, drop the worse, and repeat for many rounds.
- swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems.
Sources
- Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers & Operations Research 13(5), 533–549.
- Sörensen, K. (2015). Metaheuristics — the Metaphor Exposed. International Transactions in Operational Research 22(1), 3–18.
Mentioned in
evolutionary computationevolutionary computation, n.: Problem-solving by simulated evolution, much as breeders improve crops: keep many candidate answers, let the better ones produce slightly altered offspring, drop the worse, and repeat for many rounds., genetic algorithmgenetic algorithm, n.: A problem-solving method that copies natural evolution: many candidate solutions compete, the best are 'bred' by mixing and randomly tweaking them, and over many generations the solutions improve., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., swarm intelligenceswarm intelligence, n.: The teamwork that appears when crowds of simple creatures or machines, such as ants, bees or small robots, each respond only to what is nearby, with nobody in charge, yet together solve problems., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added., ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out., local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., particle swarm optimizationparticle swarm optimization, n.: An optimization method inspired by flocking birds: candidate solutions 'fly' through the space of possibilities, each pulled toward the best spot it has found and the best spot its neighbors have found., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.