Ant colony optimization

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
费米子讨论 | 贡献2020年4月8日 (三) 20:19的版本
跳到导航 跳到搜索

Chronology of ant colony optimization algorithms.

  • 1959, Pierre-Paul Grassé invented the theory of stigmergy to explain the behavior of nest building in termites;[1]
  • 1983, Deneubourg and his colleagues studied the collective behavior of ants;[2]
  • 1988, and Moyson Manderick have an article on self-organization among ants;[3]
  • 1989, the work of Goss, Aron, Deneubourg and Pasteels on the collective behavior of Argentine ants, which will give the idea of ant colony optimization algorithms;[4]
  • 1989, implementation of a model of behavior for food by Ebling and his colleagues;[5]
  • 1991, M. Dorigo proposed the ant system in his doctoral thesis (which was published in 1992[6]). A technical report extracted from the thesis and co-authored by V. Maniezzo and A. Colorni[7] was published five years later;[8]
  • 1994, Appleby and Steward of British Telecommunications Plc published the first application to telecommunications networks[9]
  • 1995, Gambardella and Dorigo proposed ant-q, [10] the preliminary version of ant colony system as first estension of ant system; [8].
  • 1996, Gambardella and Dorigo proposed ant colony system [11]
  • 1996, publication of the article on ant system;[8]
  • 1996, Hoos and Stützle invent the max-min ant system;[12]
  • 1997, Dorigo and Gambardella proposed ant colony system hybrized with local search;[13]
  • 1997, Schoonderwoerd and his colleagues published an improved application to telecommunication networks;[14]
  • 1998, Dorigo launches first conference dedicated to the ACO algorithms;[15]
  • 1998, Stützle proposes initial parallel implementations;[16]
  • 1999, Gambardella, Taillard and Agazzi proposed macs-vrptw, first multi ant colony system applied to vehicle routing problems with time windows, [17]
  • 1999, Bonabeau, Dorigo and Theraulaz publish a book dealing mainly with artificial ants[18]
  • 2000, special issue of the Future Generation Computer Systems journal on ant algorithms[19]
  • 2000, first applications to the scheduling, scheduling sequence and the satisfaction of constraints;
  • 2000, Gutjahr provides the first evidence of convergence for an algorithm of ant colonies[20]
  • 2001, the first use of COA algorithms by companies (Eurobios and AntOptima);
  • 2001, Iredi and his colleagues published the first multi-objective algorithm[21]
  • 2002, first applications in the design of schedule, Bayesian networks;
  • 2002, Bianchi and her colleagues suggested the first algorithm for stochastic problem;[22]
  • 2004, Dorigo and Stützle publish the Ant Colony Optimization book with MIT Press [23]
  • 2004, Zlochin and Dorigo show that some algorithms are equivalent to the stochastic gradient descent, the cross-entropy method and algorithms to estimate distribution[24]
  • 2005, first applications to protein folding problems.
  • 2012, Prabhakar and colleagues publish research relating to the operation of individual ants communicating in tandem without pheromones, mirroring the principles of computer network organization. The communication model has been compared to the Transmission Control Protocol.[25]
  • 2016, first application to peptide sequence design.[26]
  • 2017, successful integration of the multi-criteria decision-making method PROMETHEE into the ACO algorithm (HUMANT algorithm).[27]

References

  1. P.-P. Grassé, La reconstruction du nid et les coordinations inter-individuelles chez Belicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie : Essai d’interprétation du comportement des termites constructeurs, Insectes Sociaux, numéro 6, p. 41-80, 1959.
  2. J.L. Denebourg, J.M. Pasteels et J.C. Verhaeghe, Probabilistic Behaviour in Ants : a Strategy of Errors?, Journal of Theoretical Biology, numéro 105, 1983.
  3. 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.
  4. S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, volume 76, pages 579-581, 1989
  5. M. Ebling, M. Di Loreto, M. Presley, F. Wieland, et D. Jefferson,An Ant Foraging Model Implemented on the Time Warp Operating System, Proceedings of the SCS Multiconference on Distributed Simulation, 1989
  6. 引用错误:无效<ref>标签;未给name属性为M. Dorigo, Optimization, Learning and Natural Algorithms的引用提供文字
  7. Dorigo M., V. Maniezzo et A. Colorni, Positive feedback as a search strategy, rapport technique numéro 91-016, Dip. Elettronica, Politecnico di Milano, Italy, 1991
  8. 8.0 8.1 8.2 引用错误:无效<ref>标签;未给name属性为Ant system的引用提供文字
  9. Appleby, S. & Steward, S. Mobile software agents for control in telecommunications networks, BT Technol. J., 12(2):104–113, April 1994
  10. L.M. Gambardella and M. Dorigo, "Ant-Q: a reinforcement learning approach to the traveling salesman problem", Proceedings of ML-95, Twelfth International Conference on Machine Learning, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, pp. 252–260, 1995
  11. L.M. Gambardella and M. Dorigo, "Solving Symmetric and Asymmetric TSPs by Ant Colonies", Proceedings of the IEEE Conference on Evolutionary Computation, ICEC96, Nagoya, Japan, May 20-22, pp. 622-627, 1996;
  12. 引用错误:无效<ref>标签;未给name属性为T. Stützle et H.H. Hoos的引用提供文字
  13. 引用错误:无效<ref>标签;未给name属性为M. Dorigo et L.M. Gambardella的引用提供文字
  14. R. Schoonderwoerd, O. Holland, J. Bruten et L. Rothkrantz, Ant-based load balancing in telecommunication networks, Adaptive Behaviour, volume 5, numéro 2, pages 169-207, 1997
  15. M. Dorigo, ANTS’ 98, From Ant Colonies to Artificial Ants : First International Workshop on Ant Colony Optimization, ANTS 98, Bruxelles, Belgique, octobre 1998.
  16. T. Stützle, Parallelization Strategies for Ant Colony Optimization, Proceedings of PPSN-V, Fifth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, volume 1498, pages 722-731, 1998.
  17. L.M. Gambardella, E. Taillard, G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows", In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, London, UK, pp. 63-76, 1999.
  18. É. Bonabeau, M. Dorigo et G. Theraulaz, Swarm intelligence, Oxford University Press, 1999.
  19. M. Dorigo , G. Di Caro et T. Stützle, Special issue on "Ant Algorithms", Future Generation Computer Systems, volume 16, numéro 8, 2000
  20. W.J. Gutjahr, A graph-based Ant System and its convergence, Future Generation Computer Systems, volume 16, pages 873-888, 2000.
  21. S. Iredi, D. Merkle et M. Middendorf, Bi-Criterion Optimization with Multi Colony Ant Algorithms, Evolutionary Multi-Criterion Optimization, First International Conference (EMO’01), Zurich, Springer Verlag, pages 359-372, 2001.
  22. L. Bianchi, L.M. Gambardella et M.Dorigo, An ant colony optimization approach to the probabilistic traveling salesman problem, PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Springer Verlag, Berlin, Allemagne, 2002.
  23. M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press, 2004.
  24. 引用错误:无效<ref>标签;未给name属性为Zlochin model-based search的引用提供文字
  25. B. Prabhakar, K. N. Dektar, D. M. Gordon, "The regulation of ant colony foraging activity without spatial information ", PLOS Computational Biology, 2012. URL: http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fjournal.pcbi.1002670
  26. 引用错误:无效<ref>标签;未给name属性为:0的引用提供文字
  27. Mladineo, Marko; Veza, Ivica; Gjeldum, Nikola (2017). "Solving partner selection problem in cyber-physical production networks using the HUMANT algorithm". International Journal of Production Research. 55 (9): 2506–2521. doi:10.1080/00207543.2016.1234084.