A chronology of metaheuristics
By nojhan on Monday 3 March 2008, 14:33 - Bibliography - Permalink
At last, I found some time to translate my chronology of metaheuristics I have made for the french Wikipedia. I put it here for the records, but you will find a more up-to-date version on the english Wikipedia article about Metaheuristics.
Timeline
Detailled chronology
- 1952 : first works on stochastics optimization methods[1].
- 1954 : Barricelli carry out the firsts simulations of the evolution process and use them on general optimization problems[2].
- 1965 : Rechenberg conceives the first algorithm using evolution strategies[3].
- 1966 : Fogel, Owens et Walsh propose evolutionary programming[4].
- 1970 : Hastings conceive the Metropolis-Hastings algorithm, which can sample any probability density function[5].
- 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 algorithms[6].
- 1980 : Smith come through genetic programming[7].
- 1983 : refering to the work of Hastings, Kirkpatrick, Gelatt and Vecchi conceive the simulated annealing[8].
- 1985 : independently, Černý propose the same algorithm[9].
- 1986 : the first mention of the term meta-heuristic is done by Fred Glover, during the conception of tabu search[10]
- 1986 : Farmer, Packard and Perelson work on artificial immune systems[11].
- 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[12].
- 1988 : Koza register his first patent on genetic programming[13].
- 1989 : Goldberg publish one of the most known book on genetic algorithms[14].
- 1989 : Evolver, the first optimisation software using genetic algorithm, is released by the Axcelis company.
- 1989 : the term memetic algorithm appear[15].
- 1990 : the ant colony algorithms are proposed by Marco Dorigo, in its Ph.D. thesis[16].
- 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)[17].
- 1995 : Kennedy and Eberhart conceive the particle swarm optimization[18][19].
- 1996 : Mühlenbein and Paaß work on estimation of distribution algorithms[20].
- 1997 : Storn and Price propose a differential evolution algorithm[21].
- 1997 : Rubinstein works on the cross entropy method[22].
- 1999 : Boettcher propose the extremal optimization[23].
- 2000 : firsts interactive genetic algorithms[24].
References
- ↑ V. Angel, La rugosité des paysages : une théorie pour la difficulté des problèmes d’optimisation combinatoire relativement aux métaheuristiques, thèse de doctorat de l’université de Paris-Sud, Orsay, 1998.
- ↑ J. Dreo, J.-P. Aumasson, W. Tfaili, P. Siarry, Adaptive Learning Search, a new tool to help comprehending metaheuristics, to appear in the International Journal on Artificial Intelligence Tools.
- ↑ El-Ghazali Talbi, A taxonomy of hybrid metaheuristics, Journal of Heuristics, volume 8, no 2, pages 541-564, septembre 2002
- ↑ (en) exemples de fonctions de tests pour métaheuristiques d’optimisation de problèmes continus.
- ↑ W. Dullaert, M. Sevaux, K. Sörensen et J. Springael, Applications of metaheuristics, numéro spécial du European Journal of Operational Research, no 179, 2007.
- ↑ Robbins, H. and Monro, S., A Stochastic Approximation Method, Annals of Mathematical Statistics, vol. 22, pp. 400-407, 1951
- ↑ Barricelli, Nils Aall, Esempi numerici di processi di evoluzione, Methodos, pp. 45-68, 1954
- ↑ Rechenberg, I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation, 1965
- ↑ Fogel, L., Owens, A.J., Walsh, M.J., Artificial Intelligence through Simulated Evolution, Wiley, 1966
- ↑ W.K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications, Biometrika, volume 57, no 1, pages 97-109, 1970
- ↑ Holland, John H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975
- ↑ Smith, S.F., A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh), 1980
- ↑ S. Kirkpatrick, C. D. Gelatt et M. P. Vecchi, Optimization by Simulated Annealing, Science, volume 220, no 4598, pages 671-680, 1983
- ↑ V. Cerny, A thermodynamical approach to the travelling salesman problem : an efficient simulation algorithm Journal of Optimization Theory and Applications, volume45, pages 41-51, 1985
- ↑ Fred GLover, Future Paths for Integer Programming and Links to Artificial Intelligence, Comput. & Ops. Res.Vol. 13, No.5, pp. 533-549, 1986
- ↑ J.D. Farmer, N. Packard and A. Perelson, The immune system, adaptation and machine learning, Physica D, vol. 22, pp. 187--204, 1986
- ↑ 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
- ↑ Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. United States Patent 4,935,877. Filed May 20, 1988. Issued June 19, 1990
- ↑ Goldberg, David E., Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA., 1989
- ↑ P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts : Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, 1989.
- ↑ M. Dorigo, Optimization, Learning and Natural Algorithms, Thèse de doctorat, Politecnico di Milano, Italie, 1992.
- ↑ Feo, T., Resende, M., Greedy randomized adaptive search procedure, Journal of Global Optimization, tome 42, page 32--37, 1992
- ↑ 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
- ↑ Kennedy, J. et Eberhart, R. C., Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995
- ↑ 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
- ↑ Rainer Storn, Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces, Journal of Global Optimization, volume 11, no 4, pages 341-359, 1997
- ↑ Rubinstein, R.Y., Optimization of Computer simulation Models with Rare Events, European Journal of Operations Research, 99, 89-112, 1997
- ↑ Stefan Boettcher, Allon G. Percus, "Extremal Optimization : Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)
- ↑ Takagi, H., Active user intervention in an EC Search, Proceesings of the JCIS 2000
Comments
the PhD thesis of Dorigo is reference 21, not 16. Moreover ACO has been introduced in 1991, not 1990 (and anyway the thesis is 1992)
Indeed, the references numbering has a problem, due to the copy/paste of the HTML from Wikipedia (see the corresponding article for the correct links).
Concerning the date of the thesis, you are right: the technical report was submitted on nov, 15, 1991, published by IEEE TSMC in 1996. The thesis was completed in 1991 (date of the private presentation), but the official thesis date is 1992 (date of the official presentation).
Thanks for pointing out these mistakes, do not hesitate to correct Wikipedia, too.