Metaheuristic

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.[1][2][3][4][5][6][7]

Contents

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.,[8] genetic algorithms by Holland et al.,[9] ant colony optimization by Dorigo,[10] scatter search[11] and tabu search[12] 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,[13] differential evolution by Storn and Price[14] and evolution strategies by Rechenberg[15] and Schwefel.[16]

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

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:

Criticism

Mathematical analyses of metaheuristics have been presented in the literature, see e.g. Holland's schema theorem[9] for the genetic algorithm, Rechenberg's work[15] on evolution strategies, the work by Trelea,[59] amongst others, for analysis of particle swarm optimization, and Zaharie[60] 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,[41] 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:

Sub-fields of metaheuristics include:

Other fields of interest:

References

  1. ^ a b Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers. ISBN 0201157675. 
  2. ^ Luke, S. (2009). Essentials of metaheuristics. http://cs.gmu.edu/~sean/book/metaheuristics/. 
  3. ^ Talbi, E-G. (2009). Metaheuristics: from design to implementation. Wiley. ISBN 0470278587. 
  4. ^ Glover, F.; Kochenberger, G.A. (2003). Handbook of metaheuristics. 57. Springer, International Series in Operations Research & Management Science. ISBN 978-1-4020-7263-5. 
  5. ^ Mucherino, A.; Seref, O. (2009). "Modeling and Solving Real Life Global Optimization Problems with Meta-Heuristic Methods". Advances in Modeling Agricultural Systems 25: 1–17. doi:10.1007/978-0-387-75181-8_19. 
  6. ^ Blum, C.; Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. 35. ACM Computing Surveys. pp. 268–308. 
  7. ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. 
  8. ^ 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. 
  9. ^ a b c Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 0262082136. 
  10. ^ a b Dorigo, M. (1992). Optimization, Learning and Natural Algorithms (Phd Thesis). Politecnico di Milano, Italie. 
  11. ^ a b Glover, Fred (1977). "Heuristics for Integer programming Using Surrogate Constraints". Decision Sciences 8 (1): 156–166. 
  12. ^ 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. 
  13. ^ a b Kennedy, J.; Eberhart, R. (1995). "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942–1948. 
  14. ^ a b Storn, R.; Price, K. (1997). "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces". Journal of Global Optimization 11 (4): 341–359. doi:10.1023/A:1008202821328. 
  15. ^ a b Rechenberg, I. (1971). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD Thesis). ISBN 3772803733. 
  16. ^ Schwefel, H-P. (1974). Numerische Optimierung von Computer-Modellen (PhD Thesis). 
  17. ^ a b Taillard, Eric; Voss, Stephan (1999). "POPMUSIC: Partial Optimization Metaheuristic Under Special Intensification Conditions". Technical Report (Institute for Computer Sciences, heig-vd, Yverdon). http://mistic.heig-vd.ch/taillard/articles.dir/popmusic.pdf. 
  18. ^ Robbins, H.; Monro, S. (1951). "A Stochastic Approximation Method". Annals of Mathematical Statistics 22 (3): 400–407. doi:10.1214/aoms/1177729586. 
  19. ^ Davidon, W.C. (1991). "Variable metric method for minimization". SIAM Journal on Optimization 1 (1): 1–17. doi:10.1137/0801001. 
  20. ^ Barricelli, N.A. (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68. 
  21. ^ 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. 
  22. ^ Matyas, J. (1965). "Random optimization". Automation and Remote Control 26 (2): 246–253. 
  23. ^ Rechenberg, I. (1965). Cybernetic Solution Path of an Experimental Problem. Royal Aircraft Establishment Library Translation. 
  24. ^ Nelder, J.A.; Mead, R. (1965). "A simplex method for function minimization". Computer Journal 7: 308–313. doi:10.1093/comjnl/7.4.308. 
  25. ^ Fogel, L.; Owens, A.J.; Walsh, M.J. (1966). Artificial Intelligence through Simulated Evolution. Wiley. ISBN 0471265160. 
  26. ^ 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. 
  27. ^ Cavicchio, D.J. (1970). "Adaptive search using simulated evolution". Technical Report (University of Michigan, Computer and Communication Sciences Department). hdl:2027.42/4042. 
  28. ^ Kernighan, B.W.;Lin, S. (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal 49 (2): 291–307. 
  29. ^ Mercer, R.E.; Sampson, J.R. (1978). "Adaptive search using a reproductive metaplan". Kybernetes (The International Journal of Systems and Cybernetics) 7 (3): 215–228. doi:10.1108/eb005486. 
  30. ^ Smith, S.F. (1980). A Learning System Based on Genetic Adaptive Algorithms (PhD Thesis). University of Pittsburgh. 
  31. ^ Farmer, J.D.; Packard, N.; Perelson, A. (1986). "The immune system, adaptation and machine learning". Physica D 22 (1-3): 187–204. doi:10.1016/0167-2789(86)90240-X. 
  32. ^ Grefenstette, J.J. (1986). "Optimization of control parameters for genetic algorithms". IEEE Transactions Systems, Man, and Cybernetics 16 (1): 122–128. doi:10.1109/TSMC.1986.289288. 
  33. ^ US 4935877 
  34. ^ Koza, J.R. (1992). Genetic Programming : on the programming of computers by means of natural selection. MIT Press. ISBN 0262111705. 
  35. ^ Moscato, P. (1989). "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms". Technical Report C3P 826 (Caltech Concurrent Computation Program). 
  36. ^ Fonseca, C.M.; Fleming, P.J. (1993). "Genetic Algorithms for Multiobjective Optimization: formulation, discussion and generalization". Proceedings of the 5th International Conference on Genetic Algorithms (Urbana-Champaign, IL, USA): 416–423. 
  37. ^ Battiti, Roberto; Gianpietro Tecchiolli (1994). "The reactive tabu search." (PDF). ORSA Journal on Computing 6 (2): 126–140. http://rtm.science.unitn.it/~battiti/archive/TheReactiveTabuSearch.PDF. 
  38. ^ Battiti, Roberto; Gianpietro Tecchiolli (1995). "Training neural nets with the reactive tabu search." (PDF). IEEE Transactions on Neural Networks 6 (5): 1185–1200. http://rtm.science.unitn.it/~battiti/archive/rts-nn.pdf. 
  39. ^ Srinivas, N.; Deb, K. (1994). "Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms". Evolutionary Computation 2 (3): 221–248. doi:10.1162/evco.1994.2.3.221. 
  40. ^ Wolpert, D.H.; Macready, W.G. (1995). "No free lunch theorems for search". Technical Report SFI-TR-95-02-010 (Santa Fe Institute). 
  41. ^ a b Wolpert, D.H.; Macready, W.G. (1997). "No free lunch theorems for optimization". IEEE Transactions on Evolutionary Computation 1 (1): 67–82. doi:10.1109/4235.585893. 
  42. ^ Mülhenbein, H.; Paaß, G. (1996). "From recombination of genes to the estimation of distribution I. Binary parameters". Lectures Notes in Computer Science: Parallel Problem Solving from Nature (PPSN IV) 1411: 178–187. 
  43. ^ Hansen; Ostermeier (1996). "Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation.". Proceedings of the IEEE International Conference on Evolutionary Computation: 312–317. 
  44. ^ Rubinstein, R.Y. (1997). "Optimization of Computer simulation Models with Rare Events". European Journal of Operations Research 99 (1): 89–112. doi:10.1016/S0377-2217(96)00385-2. 
  45. ^ Geem, Z.W.; Kim, J.H.; Loganathan, G.V. (2001). "A new heuristic optimization algorithm: harmony search". Simulation 76 (2): 60–68. doi:10.1177/003754970107600201. 
  46. ^ Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. (2002). "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation 6 (2): 182–197. doi:10.1109/4235.996017. 
  47. ^ Nakrani, S.; Tovey, S. (2004). "On honey bees and dynamic server allocation in Internet hosting centers". Adaptive Behavior 12. 
  48. ^ Krishnanand, K.; Ghose, D. (2009). "Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions". Swarm Intelligence 3 (2): 87–124. doi:10.1007/s11721-008-0021-5. 
  49. ^ Krishnanand, K.; Ghose, D. (2006). "Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications". Multiagent and Grid Systems 2: 209–222. 
  50. ^ Krishnanand, K.; Ghose, D. (2005). "Detection of multiple source locations using a glowworm metaphor with applications to collective robotics". Proceedings of IEEE Swarm Intelligence Symposium. pp. 84–91. 
  51. ^ Karaboga, D. (2005). "An Idea Based On Honey Bee Swarm For Numerical Numerical Optimization". Technical Report-TR06 (Erciyes University, Engineering Faculty, Computer Engineering Department). 
  52. ^ Haddad, O. B. et al.; Afshar, Abbas; Mariño, Miguel A. (2006). "Honey-bees mating optimization (HBMO) algorithm: a new heuristic approach for water resources optimization". Water Resources Management 20 (5): 661–680. doi:10.1007/s11269-005-9001-3. 
  53. ^ Wierstra, D.; Schaul, T.; Peters, J.; Schmidhuber, J. (2008). "Natural Evolution Strategies". Proceedings of the IEEE Congress on Evolutionary Computation (CEC). Hong Kong, China. pp. 3381-3387. http://www.idsia.ch/~tom/publications/nes.pdf. 
  54. ^ Yang, X.-S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press. ISBN 1905986289. 
  55. ^ Yang, X.-S.; Deb, S. (2009). Cuckoo search via Levy flights, in: World Congress on Nature & Biologically Inspired Computing (NaBIC 2009).. IEEE Publication, USA. pp. 210–214. 
  56. ^ Shah-Hosseini, Hamed (2011). "Principal components analysis by the galaxy-based search algorithm: a novel metaheuristic for continuous optimisation.". International Journal of Computational Science and Engineering 6 (1/2): 132–140. doi:10.1504/IJCSE.2011.041221. 
  57. ^ Tamura, K.; Yasuda, K. (2011). "Primary Study of Spiral Dynamics Inspired Optimization". IEEJ Transactions on Electrical and Electronic Engineering 6 (S1): S98–S100. http://onlinelibrary.wiley.com/doi/10.1002/tee.20628/abstract. 
  58. ^ Tamura, K.; Yasuda, K. (2011). "Spiral Dynamics Inspired Optimization". Journal of Advanced Computational Intelligence and Intelligent Informatics 15 (8): 1116–1122. http://www.fujipress.jp/finder/xslt.php?mode=present&inputfile=JACII001500080020.xml. 
  59. ^ Trelea, I.C. (2003). "The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection". Information Processing Letters 85 (6): 317–325. doi:10.1016/S0020-0190(02)00447-7. 
  60. ^ Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67. 

External links

Metaheuristics for combinatorial problems
Metaheuristics for real-valued problems