Mravlji algoritam

U informatici i operacionim istraživanjima je mravlji algoriam (engl. , ACO) probabilistička tehnika za rešavanje računarskih problema koji se mogu redukovati na nalaženje putanja kroz grafove.^[1]

Ponašanje mrava je bilo inspiracija za metaheurističku optimizacionu tehniku

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:

1. 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.
2. 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.