Citizendia
Your Ad Here

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. heuristic (hyu̇-ˈris-tik is a method to help solve a problem commonly an informal method Computing is usually defined like the activity of using and developing Computer technology Computer hardware and software. In Computing, a procedural parameter is a parameter of a procedure that is itself a procedure The name combines the Greek prefix "meta" ("beyond", here in the sense of "higher level") and "heuristic" (from ευρισκειν, heuriskein, "to find"). Greek (el ελληνική γλώσσα or simply el ελληνικά — "Hellenic" is an Indo-European language, spoken today by 15-22 million people mainly Meta (from Greek: μετά = "after" "beyond" "with" "adjacent" is a prefix used in English in order to indicate a concept

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. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation 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. Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of Feasible solutions is discrete or can be reduced Boolean algebra (or Boolean logic) is a logical calculus of truth values, developed by George Boole in the late 1830s

Contents

Overview

Legend: E=unequivocals, I=implicits, D=directs.
Legend: E=unequivocals, I=implicits, D=directs.

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. A bit array (or bitmap, in some cases is an Array Data structure which compactly stores individual bits ( Boolean values. In several fields of Mathematics the term permutation is used with different but closely related meanings The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function 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.

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. In Mathematics, especially in Order theory, an upper bound of a Subset S of some Partially ordered set ( P, &le

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.

Timeline

Timeline of main metaheuristics.

 

Meta-heuristics concepts

Some well-known meta heuristics are

Innumerable variants and hybrids of these techniques have been proposed, and many more applications of metaheuristics to specific problems have been reported. Random optimization is the name applied to a class of Algorithms which can be used to solve optimization problems In Computer science, local search is a Metaheuristic for solving computationally hard optimization problems A greedy algorithm is any Algorithm that follows the Problem solving Metaheuristic of making the locally optimum choice at each stagewith the hope In Computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. In Computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. Best-first search is a Search algorithm which explores a graph by expanding the most promising node chosen according to some rule A genetic algorithm (GA is a Search technique used in Computing to find exact or Approximate solutions to optimization and Search Simulated annealing (SA is a generic probabilistic Meta-algorithm for the Global optimization problem namely locating a good approximation to the Tabu search is a mathematical optimization method belonging to the class of local search techniques The ant colony optimization Algorithm (ACO introduced by Marco Dorigo in 1992 in his PhD thesis is a probabilistic technique for solving computational The greedy randomized adaptive search procedure (also known as GRASP) is a Metaheuristic algorithm commonly applied to Combinatorial optimization problems Stochastic Diffusion Search (SDS was first described in 1989 as a population-based pattern-matching algorithm 1989 Harmony search (HS is a Metaheuristic algorithm (also known as Soft computing algorithm or Evolutionary algorithm) mimicking the improvisation process In Computer science, A* (pronounced "A star" is a best-first, Graph search algorithm that finds the least-cost path from a given initial This is an active field of research, with a considerable literature, a large community of researchers and users, and a wide range of applications.

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.

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). Further, the No-free-lunch theorem has proven that over the set of all mathematically possible problems, each optimization algorithm will do on average as well as any other. This figure contradicts the text of the article and uses terms that are not defined in the article 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, the more advanced metaheuristics rely on auxiliary user-given black-box producers, mutators, etc. 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 heuristic 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 particular class of problems — in particular, better than brute force search, or the following "banal metaheuristic":

  1. Call the user-provided state generator. In Computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique
  2. Print the resulting state.
  3. Stop.

Finally, all metaheuristic optimization techniques are extremely crude when evaluated by the standards of (continuous) nonlinear optimization. In Mathematics, a continuous function is a function for which intuitively small changes in the input result in small changes in the output In Mathematics, nonlinear programming ( NLP) is the process of solving a system of equalities and Inequalities, collectively termed constraints 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. In Mathematics, the Hessian matrix is the Square matrix of second-order Partial derivatives of a function. If the function is given as a black-box procedure, then one must call it about n2/2 times, and solve an n by n system of linear equations, before one can make the first useful step towards the minimum. In Mathematics, a system of linear equations (or linear system) is a collection of Linear equations involving the same set of Variables For example 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". In Vector calculus, the gradient of a Scalar field is a Vector field which points in the direction of the greatest rate of increase of the scalar But gradient-descent can be inefficient for non-linear optimization and it is generally agreed upon that second order derivatives are necessary to yield efficient optimization methods.

Addition: meta-heuristics are best and typically used when one has no access to analytical tools, including Hessians and derivatives, for example if the objective function is not even differentiable, or when it does not have an analytical closed form (for example when it is determined as the output of another algorithm). Besides, even when such tools are available, recent work on hybrid Genetic algorithms for instance, incorporates techniques from classical optimization such as local search and gradients together with metaheuristic search to achieve a much faster and more accurate metaheuristics.

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. A genetic algorithm (GA is a Search technique used in Computing to find exact or Approximate solutions to optimization and Search Problem domains falling into this category are often problems of combinatorial optimization and include the design of sorting networks, and evolved antennas, among others. Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of Feasible solutions is discrete or can be reduced A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers Evolved antennas are antennas designed fully or substantially by an automatic design procedure mimicking Darwinian Evolution.

See also

References

  1. ^ Robbins, H. Search-based software engineering ( SBSE) is an approach to apply Metaheuristic search techniques like Genetic algorithms, Simulated annealing and Monro, S. , A Stochastic Approximation Method, Annals of Mathematical Statistics, vol. 22, pp. 400-407, 1951
  2. ^ Barricelli, Nils Aall, Esempi numerici di processi di evoluzione, Methodos, pp. 45-68, 1954
  3. ^ Rechenberg, I. , Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation, 1965
  4. ^ Fogel, L. , Owens, A. J. , Walsh, M. J. , Artificial Intelligence through Simulated Evolution, Wiley, 1966
  5. ^ W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika, volume 57, Template:Numéro1, pages 97-109, 1970
  6. ^ Holland, John H. , Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975
  7. ^ Smith, S. F. , A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh), 1980
  8. ^ S. Kirkpatrick, C. D. Gelatt et M. P. Vecchi, Optimization by Simulated Annealing, Science, volume 220, Template:Numéro 4598, pages 671-680, 1983
  9. ^ V. Černý A thermodynamical approach to the travelling salesman problem : an efficient simulation algorithm Journal of Optimization Theory and Applications, volume45, pages 41-51, 1985
  10. ^ Fred GLover, Future Paths for Integer Programming and Links to Artificial Intelligence, Comput. & Ops. Res. Vol. 13, No. 5, pp. 533-549, 1986
  11. ^ J. D. Farmer, N. Packard and A. Perelson, The immune system, adaptation and machine learning, Physica D, vol. 22, pp. 187--204, 1986
  12. ^ F. Moyson, B. Manderick, The collective behaviour of Ants : an Example of Self-Organization in Massive Parallelism, Actes de AAAI Spring Symposium on Parallel Models of Intelligence, Stanford, Californie, 1988
  13. ^ Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. United States Patent 4,935,877. Filed May 20, 1988. Issued June 19, 1990
  14. ^ Goldberg, David E. , Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA. , 1989
  15. ^ P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, 1989.
  16. ^ M. Dorigo, Optimization, Learning and Natural Algorithms, Thèse de doctorat, Politecnico di Milano, Italie, 1992.
  17. ^ Feo, T. , Resende, M. , Greedy randomized adaptive search procedure, Journal of Global Optimization, tome 42, page 32--37, 1992
  18. ^ Eberhart, R. C. et Kennedy, J. , A new optimizer using particle swarm theory, Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan. pp. 39-43, 1995
  19. ^ Kennedy, J. et Eberhart, R. C. , Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995
  20. ^ Mülhenbein, H. , Paaß, G. , From recombination of genes to the estimation of distribution I. Binary parameters, Lectures Notes in Computer Science 1411: Parallel Problem Solving from Nature, tome PPSN IV, pages 178--187, 1996
  21. ^ Rainer Storn, Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, Journal of Global Optimization, volume 11, Template:Numéro4, pages 341-359, 1997
  22. ^ Rubinstein, R. Y. , Optimization of Computer simulation Models with Rare Events, European Journal of Operations Research, 99, 89-112, 1997
  23. ^ Stefan Boettcher, Allon G. Percus, "Extremal Optimization : Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)
  24. ^ Takagi, H. , Active user intervention in an EC Search, Proceesings of the JCIS 2000

Further reading

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic