Added to Favorites

Popular Searches

Definitions

Nearby Words

A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user-given black-box procedures—usually heuristics themselves—in a hopefully efficient way. The name combines the Greek prefix "meta" ("beyond", here in the sense of "higher level") and "heuristic" (from ευρισκειν, heuriskein, "to find").## Overview

The goal of combinatorial optimization is to find a discrete mathematical object (such as a bit string or permutation) that maximizes (or minimizes) an arbitrary function specified by the user of the metaheuristic. These objects are generically called states, and the set of all candidate states is the search space. The nature of the states and the search space are usually problem-specific.## Timeline

## Meta-heuristics concepts

Some well-known meta heuristics are ## General criticisms

While there are many computer scientists who are enthusiastic advocates of metaheuristics, there are also many who are highly critical of the concept and have little regard for much of the research that is done on it. ## Pragmatics

Independently of whether those criticisms are valid or not, metaheuristics can be terribly wasteful if used indiscriminately (so would be classical heuristics). Since their performance is critically dependent on the user-provided generators and mutators, one should concentrate on improving these procedures, rather than twiddling the parameters of sophisticated metaheuristics. A trivial metaheuristic with a good mutator will usually run circles around a sophisticated one with a poor mutator (and a good problem-specific heuristic will often do much better than both). In this area, more than in any other, a few hours of reading, thinking and programming can easily save months of computer time. On the other hand, this generalization does not necessarily extend equally to all problem domains. The use of genetic algorithms, for example, has produced evolved design solutions that exceed the best human-produced solutions despite years of theory and research. Problem domains falling into this category are often problems of combinatorial optimization and include the design of sorting networks, and evolved antennas, among others.
## See also

## References

## Further reading

## External links

Metaheuristics are generally applied to problems for which there is no satisfactory problem-specific algorithm or heuristic; or when it is not practical to implement such a method. Most commonly used metaheuristics are targeted to combinatorial optimization problems, but of course can handle any problem that can be recast in that form, such as solving boolean equations.

The function to be optimized is called the goal function, or objective function, and is usually provided by the user as a black-box procedure that evaluates the function on a given state. Depending on the meta-heuristic, the user may have to provide other black-box procedures that, say, produce a new random state, produce variants of a given state, pick one state among several, provide upper or lower bounds for the goal function over a set of states, and the like.

Some metaheuristics maintain at any instant a single current state, and replace that state by a new one. This basic step is sometimes called a state transition or move. The move is uphill or downhill depending on whether the goal function value increases or decreases. The new state may be constructed from scratch by a user-given generator procedure. Alternatively, the new state be derived from the current state by a user-given mutator procedure; in this case the new state is called a neighbour of the current one. Generators and mutators are often probabilistic procedures. The set of new states that can be produced by the mutator is the neighbourhood of the current state.

More sophisticated meta-heuristics maintain, instead of a single current state, a current pool with several candidate states. The basic step then may add or delete states from this pool. User-given procedures may be called to select the states to be discarded, and to generate the new ones to be added. The latter may be generated by combination or crossover of two or more states from the pool.

A metaheuristic also keep track of the current optimum, the optimum state among those already evaluated so far.

Since the set of candidates is usually very large, metaheuristics are typically implemented so that they can be interrupted after a client-specified time budget. If not interrupted, some exact metaheuristics will eventually check all candidates, and use heuristic methods only to choose the order of enumeration; therefore, they will always find the true optimum, if their time budget is large enough. Other metaheuristics give only a weaker probabilistic guarantee, namely that, as the time budget goes to infinity, the probability of checking every candidate tends to 1.

- 1952: first works on stochastics optimization methods.
- 1954: Barricelli carry out the first simulations of the evolution process and use them on general optimization problems.
- 1965: Rechenberg conceives the first algorithm using evolution strategies.
- 1966: Fogel, Owens et Walsh propose evolutionary programming.
- 1970: Hastings conceives the Metropolis-Hastings algorithm, which can sample any probability density function.
- 1975: John Holland proposes the first genetic algorithms.
- 1980: Smith describes genetic programming.
- 1983: based on Hastings's work, Kirkpatrick, Gelatt and Vecchi conceive simulated annealing.
- 1985: independently, Černý proposes the same algorithm.
- 1986: first mention of the term "meta-heuristic" by Fred Glover, during the conception of tabu search :

- 1986: Farmer, Packard and Perelson work on artificial immune systems.
- 1988: the first conference on genetic algorithms is organized at the University of Illinois at Urbana-Champaign.
- 1988: works on the collective behaviour of ants finds an application in artificial intelligence.
- 1988: Koza register his first patent on genetic programming.
- 1989: Goldberg publishes one of the best known books on genetic algorithms.
- 1989: Evolver, the first optimisation software using the genetic algorithm, is released by the Axcelis company.
- 1989: The term "memetic algorithm" is first used by Moscato.
- 1991: the ant colony algorithms are proposed by Marco Dorigo, in his Ph.D. thesis.
- 1993: The journal Evolutionary Computation begins to be published by the MIT.
- 1995: Feo and Resende propose the greedy randomized adaptive search procedure.
- 1995: Kennedy and Eberhart conceive particle swarm optimization.
- 1996: Mühlenbein and Paaß work on estimation of distribution algorithms.
- 1997: Storn and Price propose a differential evolution algorithm.
- 1997: Rubinstein works on the cross entropy method.
- 1999 : Boettcher propose the extremal optimization.
- 2000: First interactive genetic algorithms.
- 2001: Geem, Kim, and Longanathan propose harmony search.
- 2004: Nakrani and Tovey describe the honey bee algorithm.
- 2008: Yang describes the firefly algorithm.
- 2008: Karaboga and Basturk describe the artificial bee algorithm.

- Random optimization
- Local search
- Greedy algorithm and hill-climbing
- Random-restart hill climbing
- Best-first search
- Genetic algorithms
- Simulated annealing
- Tabu search
- Ant colony optimization
- GRASP
- Stochastic Diffusion Search
- Generalized extremal optimization
- Harmony search
- Variable Neighbourhood Search
- A*

Innumerable variants and hybrids of these techniques have been proposed, and many more applications of metaheuristics to specific problems have been reported. This is an active field of research, with a considerable literature, a large community of researchers and users, and a wide range of applications.

Those critics point out, for one thing, that the general goal of the typical metaheuristic — the efficient optimization of an arbitrary black-box function—cannot be solved efficiently, since for any metaheuristic M one can easily build a function f that will force M to enumerate the whole search space (or worse). Indeed, the "no-free-lunch theorem" says that over the set of all mathematically possible problems, each optimization algorithm will do on average as well as any other. Thus, at best, a specific metaheuristic can be efficient only for restricted classes of goal functions (usually those that are partially "smooth" in some sense). However, when these restrictions are stated at all, they either exclude most applications of interest, or make the problem amenable to specific solution methods that are much more efficient than the meta-heuristic.

Moreover, all metaheuristics rely on auxiliary procedures (producers, mutators, etc.) that are given by the user as black-box functions. It turns out that the effectiveness of a metaheuristic on a particular problem depends almost exclusively on these auxiliary functions, and very little on the metaheuristic itself. Given any two distinct metaheuristics M and N, and almost any goal function f, it is usually possible to write a set of auxiliary procedures that will make M find the optimum much more efficient than N, by many orders of magnitude; or vice-versa. In fact, since the auxiliary procedures are usually unrestricted, one can submit the basic step of metaheuristic M as the generator or mutator for N. Because of this extreme generality, one cannot say that any metaheuristic is better than any other, not even for a specific class of problems. In particular, no meta-heuristic can be shown to be better for any specific problem than brute force search, or the following "banal metaheuristic":

- Call the user-provided state generator.
- Print the resulting state.
- Stop.

Finally, all metaheuristic optimization techniques are extremely crude when evaluated by the standards of (continuous) nonlinear optimization. Within this area, it is well-known that to find the optimum of a smooth function on n variables one must essentially obtain its Hessian matrix, the n by n matrix of its second derivatives. If the function is given as a black-box procedure, then one must call it about n^{2}/2 times, and solve an n by n system of linear equations, before one can make the first useful step towards the minimum. However, none of the common metaheuristics incorporate or accommodate this procedure. At best, they can be seen as computing some crude approximation to the local gradient of the goal function, and moving more or less "downhill". But gradient-descent is can be extremely inefficient for non-linear optimization. For example, consider the problem of finding a pair of numbers x,y that minimizes the quadratic function Q(x,y) = 1000000(x + y - 1000)^{2} + (x - y - 10)^{2}. Gradient-descent methods will generally take a very long time to reach the minimum from, say, (1000,0); whereas Hessian-based methods will reach it in one step. Unfortunately, "narrow valley" functions like this one are increasingly likely to occur as the dimension of the space increases.

Even though meta-heuristics are often used for discrete or non-differentiable functions, or black-box functions whose derivatives are not available, they cannot be expected to be of any value unless there is some correlation between goal function values at nearby candidate solutions—in other words, unless the goal function has a globally smooth continuous component more or less hidden by the jumps and bumps created by the discreteness constraints. Yet none of the popular meta-heuristics uses the know-how of continuous optimization when trying to exploit that continuous component. For example, if the problem is to find two integers that minimize the Q function above, known meta-heuristics (including genetic ones) will fail to notice the overall quadratic behavior of Q, and will essentially behave as a random local search—or worse. (Note that this remark refers to the global behavior of the goal function, not the local smoothness of a continuous goal function with many local minima. Such local smoothness is most effectively exploited by using continuous optimization methods inside the generator/mutator procedures, so that the meta-heuristic only sees a discrete search space consisting of the local minima.)

- C. Blum and A. Roli (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268–308.
- Geem Z. W., Kim J. H., and Loganathan G. V., A new heuristic optimization algorithm: harmony search, Simulation, vol. 76, 60 (2001)
- Yang X. S., Firefly algorithm (chapter 8) in: Nature-inspired Metaheuristic Algorithms, Luniver Press, (2008).
- Karaboga D. and Basturk B., On the performance of artificial bee colony algorithm, Applied Soft Computing, vol. 8, 687 (2008).

- ParadisEO: a C++ framework dedicated to the reusable design of metaheuristics, as well as hybrid, parallel and distributed metaheuristics.
- EU/ME EU/ME (the EURO chapter on metaheuristics) is the largest working group on this topic. The website of EU/ME is the main platform for communication among metaheuristics researchers.
- DGPF A distributed framework for randomized, heuristic searches like GA and Hill Climbing which comes with a specialization for Genetic Programming and allows to combine different search algorithms.
- MHTB A toolbox of metaheuristic algorithms for MATLAB. It offers single-solution, population-based and hybrids metaheuristics. With this toolbox you can solve optimization problems defined in the MATLAB language using metaheuristic algorithms implemented in C++ and Java.
- jMetal jMetal is an object-oriented Java-based framework aimed at facilitating the development of metaheuristics for solving multi-objective optimization problems (MOPs).
- Metaheuristic / Stochastic Local Search Forum A forum where practitioners and researchers can discuss and share knowledge about metaheuristics and stochastic local search algorithms.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 03:35:11 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 03:35:11 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.