Metaheuristic 774458 222075514 2008-06-27T13:09:09Z MrOllie 6908984 Reverted to revision 219178489 by [[Special:Contributions/Aitias|Aitias]]. ([[WP:TW|TW]]) A '''metaheuristic''' is a [[heuristic]] method for solving a very general class of [[computing|computational]] problems by combining user-given [[procedural parameter|black-box procedure]]s—usually heuristics themselves—in a hopefully efficient way. The name combines the [[Greek language|Greek]] prefix "[[meta]]" ("beyond", here in the sense of "higher level") and "heuristic" (from ευρισκειν, ''heuriskein'', "to find"). 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 algebra (logic)|boolean equations]]. == Overview == [[Image:Implicte vs explicite.svg|thumb|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 (mathematics)|function]] specified by the user of the metaheuristic. These objects are generically called ''states'', and the [[set (mathematics)|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 [[Upper and lower bounds|bound]]s 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. ==Timeline== <div class="thumb tright" style="width:210px"> <div class="thumbcaption"> <div class="magnify" class="internal"> <timeline> ImageSize = width:200 height:550 PlotArea = width:160 height:530 left:40 bottom:10 DateFormat = yyyy Period = from:1960 till:2005 TimeAxis = orientation:vertical ScaleMajor = unit:year increment:5 start:1960 Colors= id:fond value:white #rgb(0.95,0.95,0.98) id:marque value:rgb(1,0,0) id:marque_fond value:rgb(1,0.9,0.9) BackgroundColors = canvas:fond Define $dx = 7 # décalage du texte à droite de la barre Define $dy = -3 # décalage vertical Define $dy2 = 6 # décalage vertical pour double texte PlotData= bar:Leaders color:marque_fond width:5 mark:(line,marque) align:left fontsize:S from:1965 till:1965 shift:($dx,$dy) text:Evolution strategies from:1966 till:1966 shift:($dx,$dy) text:Evolutionary prog. from:1975 till:1975 shift:($dx,$dy) text:Genetic algorithms from:1983 till:1985 shift:($dx,$dy) text:Simulated annealing from:1986 till:1986 shift:($dx,$dy2) text:Tabu search from:1986 till:1986 shift:($dx,-$dy2) text:Artificial immunitary sys. from:1991 till:1991 shift:($dx,$dy) text:Ant colony optim. from:1995 till:1995 shift:($dx,$dy) text:Particle swarm optim. from:1996 till:1996 shift:($dx,$dy) text:Estimation of distribution from:1997 till:1997 shift:($dx,$dy2) text:Differential evolution from:1997 till:1997 shift:($dx,-4) text:Cross entropy </timeline> </div> Timeline of main metaheuristics. </div> </div> * 1952 : first works on stochastics optimization methods<ref>Robbins, H. and Monro, S., ''A Stochastic Approximation Method'', Annals of Mathematical Statistics, vol. 22, pp. 400-407, 1951</ref>. * 1954 : Barricelli carry out the firsts simulations of the [[evolution]] process and use them on general optimization problems<ref>Barricelli, Nils Aall, ''Esempi numerici di processi di evoluzione'', Methodos, pp. 45-68, 1954</ref>. * 1965 : Rechenberg conceives the first algorithm using '''[[evolution strategies]]'''<ref>Rechenberg, I., ''Cybernetic Solution Path of an Experimental Problem'', Royal Aircraft Establishment Library Translation, 1965</ref>. * 1966 : Fogel, Owens et Walsh propose '''[[evolutionary programming]]'''<ref>Fogel, L., Owens, A.J., Walsh, M.J., ''Artificial Intelligence through Simulated Evolution'', Wiley, 1966</ref>. * 1970 : Hastings conceive the [[Metropolis-Hastings algorithm]], which can sample any [[probability density function]]<ref> W.K. Hastings. ''Monte Carlo Sampling Methods Using Markov Chains and Their Applications'', Biometrika, volume 57, {{numéro}}1, pages 97-109, 1970</ref>. * 1970 : [[John Horton Conway]] works on the [[game of life]], the most known [[cellular automata]] nowadays. * 1975 : working on cellular automata, [[John Holland]] propose the firsts '''[[genetic algorithm]]s'''<ref>Holland, John H., ''Adaptation in Natural and Artificial Systems'', University of Michigan Press, Ann Arbor, 1975</ref>. * 1980 : Smith come through [[genetic programming]]<ref>Smith, S.F., ''A Learning System Based on Genetic Adaptive Algorithms'', PhD dissertation (University of Pittsburgh), 1980</ref>. * 1983 : referring to the work of Hastings, Kirkpatrick, Gelatt and Vecchi conceive the '''[[simulated annealing]]'''<ref>S. Kirkpatrick, C. D. Gelatt et M. P. Vecchi, ''Optimization by Simulated Annealing'', Science, volume 220, {{numéro}} 4598, pages 671-680, 1983</ref>. * 1985 : independently, Černý propose the same algorithm<ref>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</ref>. * 1986 : the first mention of the term '''meta-heuristic''' is done by [[Fred Glover]], during the conception of '''[[tabu search]]'''<ref>Fred GLover, Future Paths for Integer Programming and Links to Artificial Intelligence, Comput. & Ops. Res.Vol. 13, No.5, pp. 533-549, 1986</ref> : :{{citation|La recherche avec tabou peut être vue comme une "méta-heuristique", superposée à une autre heuristique. L'approche vise à éviter les optimums locaux par une stratégie d'interdiction (ou, plus généralement, de pénalisation) de certains mouvements.}} * 1986 : Farmer, Packard and Perelson work on '''[[artificial immune system]]s'''<ref>J.D. Farmer, N. Packard and A. Perelson, ''The immune system, adaptation and machine learning'', Physica D, vol. 22, pp. 187--204, 1986</ref>. * 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]]<ref>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</ref>. * 1988 : Koza register his first patent on genetic programming<ref>Koza, John R. ''Non-Linear Genetic Algorithms for Solving Problems''. United States Patent 4,935,877. Filed May 20, 1988. Issued June 19, 1990</ref>. * 1989 : Goldberg publish one of the most known book on genetic algorithms<ref>Goldberg, David E., ''Genetic Algorithms in Search, Optimization and Machine Learning'', Kluwer Academic Publishers, Boston, MA., 1989</ref>. * 1989 : ''Evolver'', the first optimisation software using genetic algorithm, is released by the ''Axcelis'' company. * 1989 : the term ''[[memetic algorithm]]'' appear<ref>P. Moscato, ''On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms'', Caltech Concurrent Computation Program, C3P Report 826, 1989.</ref>. * 1991 : the '''[[ant colony algorithm]]s''' are proposed by [[Marco Dorigo]], in his Ph.D. thesis<ref>M. Dorigo, ''Optimization, Learning and Natural Algorithms'', Thèse de doctorat, Politecnico di Milano, Italie, 1992.</ref>. * 1993 : the term "[[evolutionary computation]]" is spreading itself, with the publication of the eponymous journal, published by the [[Massachusetts Institute of Technology]]. * 1995 : Feo and Resende propose the [[Greedy randomized adaptive search procedure]] (''GRASP'')<ref>Feo, T., Resende, M., ''Greedy randomized adaptive search procedure'', Journal of Global Optimization, tome 42, page 32--37, 1992</ref>. * 1995 : Kennedy and Eberhart conceive the '''[[particle swarm optimization]]'''<ref>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</ref><ref>Kennedy, J. et Eberhart, R. C., ''Particle swarm optimization'', Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995</ref>. * 1996 : Mühlenbein and Paaß work on '''[[estimation of distribution algorithm]]s'''<ref>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</ref>. * 1997 : Storn and Price propose a [[differential evolution]] algorithm<ref>Rainer Storn, Kenneth Price, ''Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces'', Journal of Global Optimization, volume 11, {{numéro}}4, pages 341-359, 1997</ref>. * 1997 : Rubinstein works on the [[cross entropy method]]<ref>Rubinstein, R.Y., ''Optimization of Computer simulation Models with Rare Events'', European Journal of Operations Research, 99, 89-112, 1997</ref>. * 1999 : Boettcher propose the [[extremal optimization]]<ref>Stefan Boettcher, Allon G. Percus, "Extremal Optimization : Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)</ref>. * 2000 : firsts interactive genetic algorithms<ref>Takagi, H., ''Active user intervention in an EC Search'', Proceesings of the JCIS 2000</ref>. == Meta-heuristics concepts== Some well-known meta heuristics are *[[Random optimization]] *[[local search (optimization)|Local search]] *[[Greedy algorithm]] and [[hill-climbing]] *[[Random-restart hill climbing]] *[[Best-first search]] *[[Genetic algorithms]] *[[Simulated annealing]] *[[Tabu search]] *[[Ant colony optimization]] *[[Greedy randomized adaptive search procedure|GRASP]] *[[Stochastic Diffusion Search]] *[[Generalized extremal optimization]] *[[Harmony 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. ==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 &mdash; 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 in search and optimization|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. 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 &mdash; in particular, better 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 function|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 <math>n^2</math>/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 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. Problem domains falling into this category are often problems of [[combinatorial optimization]] and include the design of [[sorting networks]], and [[evolved antenna]]s, among others. ==See also== *[[Search-based software engineering]] == References == {{reflist}} == Further reading == * C. Blum and A. Roli (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ''ACM Computing Surveys'' 35(3) 268&ndash;308. ==External links== *[http://paradiseo.gforge.inria.fr/ ParadisEO]: a C++ framework dedicated to the reusable design of metaheuristics, as well as hybrid, parallel and distributed metaheuristics. *[http://www.metaheuristics.eu 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. *[http://dgpf.sourceforge.net/ 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. *[http://neo.lcc.uma.es/Software/MHTB/ 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. *[http://neo.lcc.uma.es/metal jMetal] jMetal is an object-oriented Java-based framework aimed at facilitating the development of metaheuristics for solving multi-objective optimization problems (MOPs). *[http://iridia.ulb.ac.be/sls-forum Metaheuristic / Stochastic Local Search Forum] A forum where practitioners and researchers can discuss and share knowledge about metaheuristics and stochastic local search algorithms. [[Category:Applied mathematics]] [[Category:Operations research]] [[Category:Optimization]] [[Category:Heuristics]] [[pt:metaheurística]] [[de:Metaheuristik]] [[es:Metaheurística]] [[fr:Métaheuristique]] [[ja:メタヒューリスティクス]]