Jump to content

Metaheuristic

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 150.135.222.234 (talk) at 22:41, 9 April 2013 (See also: Added List of metaheuristics, since most were removed from this article). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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: direct search, black-box, or indeed just heuristic optimizer. Several books and survey papers have been published on the subject.[1][2][3][4]

In a 2013 article in the International Transactions in Operational Research Kenneth Sörensen, professor of operations research at the University of Antwerp, stated critically:[5]

In recent years, the field of combinatorial optimization has witnessed a true tsunami of "novel" metaheuristic methods, most of them based on a metaphor of some natural or man-made process. The behavior of virtually any species of insects, the flow of water, musicians playing together – it seems that no idea is too far-fetched to serve as inspiration to launch yet another metaheuristic. In this paper, we will argue that this line of research is threatening to lead the area of metaheuristics away from scientific rigor. [...] At the same time, truly innovative research of high quality is being performed as well.

Applications

Different classifications of metaheuristics.

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 faster 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.,[6] genetic algorithms by Holland et al.,[7] scatter search[8] and tabu search[9] by Glover. Literature review on metaheuristic optimization,[10] suggested that it was Fred Glover who coined the word metaheuristics [11]

Contributions

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

See also

References

  1. ^ Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers. ISBN 0-201-15767-5.
  2. ^ Glover, F.; Kochenberger, G.A. (2003). Handbook of metaheuristics. Vol. 57. Springer, International Series in Operations Research & Management Science. ISBN 978-1-4020-7263-5.
  3. ^ Blum, C.; Roli, A. (2003). "Metaheuristics in combinatorial optimization: Overview and conceptual comparison". 35 (3). ACM Computing Surveys: 268–308. {{cite journal}}: Cite journal requires |journal= (help)
  4. ^ Talbi, E-G. (2009). Metaheuristics: from design to implementation. Wiley. ISBN 0-470-27858-7.
  5. ^ Sörensen, Kenneth. "Metaheuristics—the metaphor exposed" (PDF). International Transactions in Operational Research. doi:10.1111/itor.12001.
  6. ^ a b Kirkpatrick, S.; Gelatt Jr., C.D.; Vecchi, M.P. (1983). "Optimization by Simulated Annealing". Science. 220 (4598): 671–680. doi:10.1126/science.220.4598.671. PMID 17813860.
  7. ^ a b Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0-262-08213-6.
  8. ^ a b Glover, Fred (1977). "Heuristics for Integer programming Using Surrogate Constraints". Decision Sciences. 8 (1): 156–166.
  9. ^ a b Glover, F. (1986). "Future Paths for Integer Programming and Links to Artificial Intelligence". Computers and Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.
  10. ^ X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).
  11. ^ Glover F., (1986). Future paths for integer programming and links to artificial intelligence, Computers and Operations Research,13,533-549 (1986).
  12. ^ Robbins, H.; Monro, S. (1951). "A Stochastic Approximation Method". Annals of Mathematical Statistics. 22 (3): 400–407. doi:10.1214/aoms/1177729586.
  13. ^ Barricelli, N.A. (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
  14. ^ Rastrigin, L.A. (1963). "The convergence of the random search method in the extremal control of a many parameter system". Automation and Remote Control. 24 (10): 1337–1342.
  15. ^ Matyas, J. (1965). "Random optimization". Automation and Remote Control. 26 (2): 246–253.
  16. ^ Nelder, J.A.; Mead, R. (1965). "A simplex method for function minimization". Computer Journal. 7: 308–313. doi:10.1093/comjnl/7.4.308.
  17. ^ Fogel, L.; Owens, A.J.; Walsh, M.J. (1966). Artificial Intelligence through Simulated Evolution. Wiley. ISBN 0-471-26516-0.
  18. ^ Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". Biometrika. 57 (1): 97–109. doi:10.1093/biomet/57.1.97.
  19. ^ Cavicchio, D.J. (1970). "Adaptive search using simulated evolution". Technical Report. University of Michigan, Computer and Communication Sciences Department. hdl:2027.42/4042.
  20. ^ Kernighan, B.W.;Lin, S. (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal. 49 (2): 291–307.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  21. ^ Mercer, R.E. (1978). "Adaptive search using a reproductive metaplan". Kybernetes (The International Journal of Systems and Cybernetics). 7 (3): 215–228. doi:10.1108/eb005486. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  22. ^ Smith, S.F. (1980). A Learning System Based on Genetic Adaptive Algorithms (PhD Thesis). University of Pittsburgh.

Template:Metaheuristics for combinatorial problems Template:Metaheuristics for real-valued problems