In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, metaheuristics do not guarantee an optimal solution is ever found. Many metaheuristics implement some form of stochastic optimization.

Other terms having a similar meaning as metaheuristic, are: derivative-free, direct search, black-box, or indeed just heuristic optimizer. Several books and survey papers have been published on the subject.

Applications

Metaheuristics are used for combinatorial optimization in which an optimal solution is sought over a discrete search-space. An example problem is the travelling salesman problem where the search-space of candidate solutions grows more than exponentially as the size of the problem increases, which makes an exhaustive search for the optimal solution infeasible. Additionally, multidimensional combinatorial problems, including most design problems in engineering such as form-finding and behavior-finding, suffer from the curse of dimensionality, which also makes them infeasible for exhaustive search or analytical methods. Popular metaheuristics for combinatorial problems include simulated annealing by Kirkpatrick et al., genetic algorithms by Holland et al., ant colony optimization by Dorigo, scatter search and tabu search by Glover.

Metaheuristics are also used for problems over real-valued search-spaces, where the classic way of optimization is to derive the gradient of the function to be optimized and then employ gradient descent or a quasi-Newton method. Metaheuristics do not use the gradient or Hessian matrix so their advantage is that the function to be optimized need not be continuous or differentiable and it can also have constraints. Popular metaheuristic optimizers for real-valued search-spaces include particle swarm optimization by Eberhart and Kennedy, differential evolution by Storn and Price and evolution strategies by Rechenberg and Schwefel.

Metaheuristics based on decomposition techniques have also been proposed for tackling hard combinatorial problems of large size.

Main contributions

Timeline of main contributions.

Many different metaheuristics are in existence and new variants are continually being proposed. Some of the most significant contributions to the field are:

1952: Robbins and Monro work on stochastic optimization methods. 1952: Fermi and Metropolis develop an early form of pattern search as described belatedly by Davidon. 1954: Barricelli carry out the first simulations of the evolution process and use them on general optimization problems. 1963: Rastrigin proposes random search. 1965: Matyas proposes random optimization. 1965: Rechenberg proposes evolution strategies. 1965: Nelder and Mead propose a simplex heuristic, which was shown by Powell to converge to non-stationary points on some problems. 1966: Fogel et al. propose evolutionary programming. 1970: Hastings proposes the Metropolis-Hastings algorithm. 1970: Cavicchio proposes adaptation of control parameters for an optimizer. 1970: Kernighan and Lin propose a graph partitioning method, related to variable-depth search and prohibition-based (tabu) search. 1975: Holland proposes the genetic algorithm. 1977: Glover proposes Scatter Search. 1978: Mercer and Sampson propose a metaplan for tuning an optimizer's parameters by using another optimizer. 1980: Smith describes genetic programming. 1983: Kirkpatrick et al. propose simulated annealing. 1986: Glover proposes tabu search, first mention of the term ''metaheuristic''. 1986: Farmer et al. work on the artificial immune system. 1986: Grefenstette proposes another early form of metaplan for tuning an optimizer's parameters by using another optimizer.

1988: First conference on genetic algorithms is organized at the University of Illinois at Urbana-Champaign.

1988: Koza registers his first patent on genetic programming. 1989: Goldberg publishes a well known book on genetic algorithms.

1989: Evolver, the first optimization software using the genetic algorithm.

1989: Moscato proposes the memetic algorithm.

1991: Interactive evolutionary computation.

1992: Dorigo proposes the ant colony algorithm.

1993: The journal, ''Evolutionary Computation'', begins publication by the Massachusetts Institute of Technology.

1993: Fonseca and Fleming propose MOGA for multiobjective optimization. 1994: Battiti and Tecchiolli propose Reactive Search Optimization(RSO) principles for the online self-tuning of heuristics. 1994: Srinivas and Deb propose NSGA for multiobjective optimization. 1995: Kennedy and Eberhart propose particle swarm optimization. 1995: Wolpert and Macready prove the no free lunch theorems. 1996: Mühlenbein and Paaß work on the estimation of distribution algorithm. 1996: Hansen and Ostermeier propose CMA-ES. 1997: Storn and Price propose differential evolution. 1997: Rubinstein proposes the cross entropy method. 1999: Taillard and Voss propose POPMUSIC. 2001: Geem et al. propose harmony search. 2002: Deb et al. propose NSGA-II for multiobjective optimization. 2004: Nakrani and Tovey propose bee colony optimization. 2005: Krishnanand and Ghose propose Glowworm swarm optimization. 2005: Karaboga proposes Artificial Bee Colony Algorithm (ABC). 2006: Haddad et al. introduces honey-bee mating optimization.

2007: Hamed Shah-Hosseini introduces Intelligent Water Drops.

2008: Wierstra et al. propose natural evolution strategies based on the natural gradient. 2008: Yang introduces firefly algorithm.

2008: Mucherino and Seref propose the Monkey Search

2009: Yang and Deb introduce cuckoo search.

Criticism

Mathematical analyses of metaheuristics have been presented in the literature, see e.g. Holland's schema theorem for the genetic algorithm, the work by Trelea, amongst others, for analysis of particle swarm optimization, and Zaharie for analysis of differential evolution. These analyses make a number of assumptions in regard to the optimizer variants and the simplicity of the optimization problems which limit their validity in real-world optimization scenarios. Performance and convergence aspects of metaheuristic optimizers are therefore often demonstrated empirically in the research literature. This has been criticized in the no free lunch set of theorems by Wolpert and Macready, which, among other things, prove that all optimizers perform equally well when averaged over all problems. The practical relevance of the no free lunch theorems however is minor, because they will generally not hold on the collection of problems a practitioner is facing.

For the practitioner the most relevant issue is that metaheuristics are not guaranteed to find the optimum or even a satisfactory near-optimal solution. All metaheuristics will eventually encounter problems on which they perform poorly and the practitioner must gain experience in which optimizers work well on different classes of problems.

See also

Metaheuristic methods are, generally speaking, sub-fields of:

Optimization algorithms

Heuristic

Stochastic search

Sub-fields of metaheuristics include:

Local search

Evolutionary computing which includes, amongst others:

* Evolutionary algorithms

* Swarm Intelligence

Other fields of interest:

Reactive Search Optimization

Meta-optimization

Hyper-heuristics

References

External links

EU/ME forum for researchers in the field.

MetaHeur - Excel application to metaheuristic methods

Category:Applied mathematics Category:Operations research Category:Mathematical optimization Category:Heuristics

ca:Metaheurística de:Metaheuristik es:Metaheurística fa:الگوریتم های فراابتکاری fr:Métaheuristique ja:メタヒューリスティクス pl:Metaheurystyka pt:Meta-heurística ru:Метаалгоритм

Coordinates	37°46′45.48″N122°25′9.12″N
name	Richard Manning Karp
birth date
birth place	Boston, Massachusetts
nationality	American
field	Computer Science
work institution	University of California, BerkeleyIBM
alma mater	Harvard University
doctoral advisor	Anthony Oettinger
doctoral students	Narendra KarmarkarMichael LubyRajeev MotwaniBarbara Simons
known for	Edmonds–Karp algorithmKarp's 21 NP-complete problemsHopcroft–Karp algorithmKarp–Lipton theoremRabin–Karp string search algorithm
prizes	Turing AwardNational Medal of ScienceHarvey PrizeBenjamin Franklin MedalKyoto Prize
footnotes	}}

:''Not to be confused with Richard A. Karp, one of the developers of TCP.''

Richard Manning Karp (born January 3, 1935) is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

Biography

Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959.

He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group.

Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Work

He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.

In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete.

In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, still the fastest known method for finding maximum cardinality matchings in bipartite graphs.

In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).

In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm.

Turing Award

His citation for the Turing Award was as follows:

:''For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.''

References

External links

ACM Crossroads magazine interview/bio of Richard Karp

Karp's Home Page at Berkeley

Category:1935 births Category:Members of the United States National Academy of Sciences Category:Living people Category:Computer pioneers Category:American computer scientists Category:American mathematicians Category:Turing Award laureates Category:John von Neumann Theory Prize winners Category:National Medal of Science laureates Category:Harvard Centennial Medal recipients Category:Harvard University alumni Category:University of California, Berkeley faculty Category:Fellows of the Association for Computing Machinery Category:Operations researchers Category:Members of the French Academy of Sciences Category:People from Boston, Massachusetts Category:Theoretical computer scientists Category:Fellows of Society for Industrial and Applied Mathematics

bn:রিচার্ড কার্প de:Richard M. Karp es:Richard Karp fr:Richard Karp id:Richard M. Karp it:Richard Karp he:ריצ'רד קארפ ht:Richard Karp ja:リチャード・カープ no:Richard M. Karp pl:Richard Karp pt:Richard Karp ro:Richard Karp ru:Карп, Ричард Мэннинг sk:Richard Karp sr:Ричард Карп th:ริชาร์ด คาร์ป zh:理查德·卡普