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 Artiﬁcial 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 уреди

[M._Dorigo_et_L.M._Gambardella-1] 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.

[2] 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-3] M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.

[1]

[2]

[3]