Mravlji algoritam
U informatici i operacionim istraživanjima je mravlji algoriam (engl. Ant colony optimization algorithms, ACO) probabilistička tehnika za rešavanje računarskih problema koji se mogu redukovati na nalaženje putanja kroz grafove.[1]
Istraživanja kolektivnog ponašanja mrava i pčela omogućila su naučnicima iz računarskih nauka da razviju razne metode za optimizaciju. Ovi algoritmi su se pokazali kao fleksibilni i robusni u dinamičkim okruženjima kakva se sreću kod svih vrsta saobraćaja: transporta vozila, kompjuterskih mreža ili telefonije.
Osnovna karakteristika kolektivnog ponašanja mrava je da svi članovi kolonije indirektno ili direktno razmenjuju informacije o svom okruženju, tj. prisutan je fenomen kolektivne inteligencije.[2][3] U prirodi je otkriveno da svaki mrav za sobom ostavlja trag, ispuštajući određenu količinu hemijske supstance koja se zove feromon. Što više mrava ide jednom putanjom, više je i feromona, a to je za svakog sledećeg mrava „pozitivna informacija“ o ispravnosti te putanje. Na ovaj način mravi posredno, preko feromona, međusobno komuniciraju. Primenom ovog principa kolonija mrava pronalazi najkraći put do hrane.
U prirodi je takođe primećeno:
- Ne biraju svi mravi putanju sa najviše feromona, već pojedini mravi biraju alternativne puteve. Utvrđeno je da svaki mrav bira putanju sa najviše feromona sa određenom verovatnoćom.
- Bitna karakteristika feromona, kao hemijske supstance, je da tokom vremena isparava. Tako ruta koju mravi ne koriste nakon nekog vremena ostaje bez feromona, i samim tim postaje manje „interesantna“ za ostale članove kolonije.
Jednu od primena mravlji algoritmi su našli u rešavanju problema rutiranja vozila.
Reference
[уреди | уреди извор]- ^ M. Dorigo et L.M. Gambardella, Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, volume 1, numéro 1, pages 53-66, 1997.
- ^ A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.
- ^ M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
Literatura
[уреди | уреди извор]- Marco Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
- Dorigo, M.; Maniezzo, V.; Colorni, A. (1996). „Ant system: Optimization by a colony of cooperating agents”. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 26 (1): 29—41. PMID 18263004. doi:10.1109/3477.484436..
- Dorigo, M.; Gambardella, L.M. (1997). „Ant colony system: A cooperative learning approach to the traveling salesman problem”. IEEE Transactions on Evolutionary Computation. 1 (1): 53—66. doi:10.1109/4235.585892..
- Dorigo, M.; Di Caro, G.; Gambardella, L. M. (1999). „Ant algorithms for discrete optimization”. Artificial Life. 5 (2): 137—172. PMID 10633574. S2CID 990370. doi:10.1162/106454699568728..
- E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
- M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3
- M. Dorigo, 2007. "Ant Colony Optimization". Scholarpedia.
- C. Blum, 2005 "Ant colony optimization: Introduction and recent trends". Physics of Life Reviews, 2: 353-373
- M. Dorigo, M. Birattari & T. Stützle, 2006 Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. TR/IRIDIA/2006-023
- Mohd Murtadha Mohamad,"Articulated Robots Motion Planning Using Foraging Ant Strategy",Journal of Information Technology - Special Issues in Artificial Intelligence, Vol.20, No. 4 pp. 163–181, December 2008, ISSN0128-3790.
- N. Monmarché, F. Guinand & P. Siarry (eds), "Artificial Ants", August 2010 Hardback 576 pp. ISBN 978-1-84821-194-0.
- Zbornik god. 27, Broj 18, страна 3815-3818 - Faculty of Technical Sciences - RUTIRANJE VOZILA PRIMENOM MRAVLJEG ALGORITMA ISSN0350-428X
Spoljašnje veze
[уреди | уреди извор]- Ant Colony Optimization Home Page
- „Ant Colony Optimization“ - Russian scientific and research community
- AntSim - Simulation of Ant Colony Algorithms
- Youtube - Ant Colony Optimization on Vehicle routing problem demonstration