Kolonije mrava

By   /  12. marta 2018.  /  Komentari su isključeni na Kolonije mrava

Autor: Ivan Stambolić

 Uvod

Kolonije mrava i druge više-socijalne organizacije insekata predstavljaju visoko struktuirane i visoko funkcionalne socijalne organizacije, uprkos jednostavnosti njihovih izdvojenih jedinki (slika 1). Kao rezultat ovakve organizacije, kolonije mrava mogu da reše kompleksne zadatke, koji daleko premašuju mogućnosti jedinke. Mravi koordinišu svoje ponašanje stigmergijom, način indirektne komunikacije izmenom okoline. Na primer, ostavljanjem isparljivih jedinjenja (feromona) na zemlji kuda su prošli, što povećava verovatnoću da će drugi mravi pratiti baš taj trag. Biolozi su primetili da se mnoga ponašanja na nivou kolonije mogu objasniti jednostavnim modelima, u kojima je prisutna samo stigmergijska komunikacija. Drugim rečima, biolozi su pokazali da je obično dovoljno da se posmatra samo stigmergijska komunikacija, za objašnjavanje kako socijalni insekti postižu visoku samo-organizaciju. Ova ideja se koristi za pravljenje veštačke stigmergije za koordinisanje društava veštačkih agenata. Različiti aspekti ponašanja kolonije mrava, su inspirisala nekoliko različitih algoritama. Inicijalni algoritam, predložio je 1992. godine u svojoj doktorskoj tezi Marko Dorigo (Marco Dorigo). Taj algoritam je imao za cilj pronalaženje optimalnog put grafika, a zasnovan je na ponašanju kolonije mrava. Ovaj algoritam je danas razvijen za rešavanje velikog broja numeričkih problema.


Slika 1. Kolonija Safari mrava, vrsta Dorylus, Kenija

Eksperiment dvostrukog mosta
Ponašanja određenih vrsta mrava, na primer, I. Humilis (Goss et al, 1989), Linepithema humile i Lasius niger(Bonabeau et al, 1997) zasnovana su na stigmergijskoj komunikaciji. Prilikom dolaska iz kolonije do hrane i obrnuto, mravi ostavljaju feromone praveći put feromona. Mravi mogu da namirišu ove markere, pri čemu biraju onaj put koji ima jači miris. Deneubourg i kolege (Deneubourg, Aron, Goss, Pasteels, 1990; Goss et al, 1989) izvele su seriju eksperimenata, povezujući dvostrukim mostom koloniju i hranu, Argentiskog mrava I. Humilis
U prvom eksperimentu, dva mosta su bile jednake dužine (slika 2a). Na početku eksperimenta, mravi su se slobodno kretali po oba mosta, idući do hrane i nazad. Međutim, tokom vremena, svi mravi su birali isti most.


Slika 2. Eksperiment dvostrukog mosta. a) Oba mosta su iste dužine; b) Mostovi su različitih dužina.

Ovaj rezultat se može objasniti time, što u početku, nema feromona ni na jednom od mostova, pa je i jednaka verovatnoća da mravi izaberu jedan ili drugi put. Kako se mravi kreću, u jednom trenutku biće svega par mrava više preko jednog mosta, što za posledicu ima da sve više sledećih mrava izabere ovaj most zbog jačeg mirisa feromona. Konačno, svi mravi će prelaziti samo jedan most. 
U drugom eksperimentu, jedan most je povećan, tako da sada mostovi nisu jednakih dužina (slika 2b). Posle određenog vremena, svi mravi su izabrali kraći put. Rezultat ovog eksperimenta se može objasniti slično kao i rezultat prethodnog. 
U trećem eksperimentu, prvo je postavljen samo jedan (duži) most, a tek nakon što su svi mravi prelazili preko ovog mosta, postavljen je kraći most (slika 3). Mravi su i dalje nastavili da se kreću dužim mostom, iz razloga što je duži most već bio obeležen feromonima. Na ovaj način, kolonija je bila „zarobljena“ na dužem mostu, iako je bliže rešenje bilo dostupno.


Slika 3. Eksperiment dvostrukog mosta. Drugi most je dodat nakon što su svi mravi prešli jedini most.

Algoritam zasnovan na ponašanju kolonije mrava
Algoritam kolonije mrava je algoritam za pronalaženje optimalnih puteva, a zasniva se na ponašanju mrava u potrazi za hranom. 
U početku, mravi se kreću nasumično. Kada jedan mrav pronađe hranu, vraća se u koloniju ostavljajući markere (feromone) koji pokazuju put do hrane. Kada drugi mravi „nanjuše“ ove markere, pratiće ovaj put do hrane sa određenom verovatnoćom. Ukoliko prate put, pojačaće miris ostavljajući svoje markere. Kako sve više mrava pronalazi markere, miris na putu će se pojačavati sve dok ne nastane nekoliko „tokova“ mrava koji prenose hranu nazad do kolonije iz nekoliko različitih izvora. 
Kako mravi pri svakom prolazu ostavljaju markere, kraći putevi će imati jače mirise, pa ovo predstavlja „optimizaciju“ rešenja. U međuvremenu, nekoliko mrava i dalje nasumično pretražuje okolinu za bliže izvore hrane. Sličan pristup se koristi u pronalaženju optimalnog rešenja za problem putujućeg trgovca (problem u teorija grafova; najkraće rastojanje koje putujući trgovac mora da pređe u svakom ciklusu, svih gradova u kojima prodaje). Kada se sva hrana sa jednog izvora prenese, mravi će prestati da ostavljaju markere i time će miris polako početi da slabi. 
Kako kolonija mrava radi na veoma dinamičkom sistemu, algoritam radi dobro u graficima promenljive topologije. Primeri upotrebe ovog algoritma su računarske mreže i veštačke inteligencije. 
Teorijski hemičari su prilagodili ovaj algoritam i on se danas upotrebljava u hemiji na razne načine. Između ostalog, koristi se za pronalaženje optimalne geometrije molekula, reakcionog puta, skeniranje potencijalnih površina, optimizaciju funkcija, dizajniranje lekova, modeliranje metal-porfirinskih i drugih kompleksa prelaznih metala, zatim za izučavanje dinamike molekula, QSAR (odnos strukture i aktivnosti) i QSPR (odnos strukture i osobina) analize, kao i veliki broj drugih simulacija.

Reference:

  1. Dorigo M, Stützle T,Ant Colony Optimization, MIT Press, 2004
  2. Weiyang C, Bo L, Wen Z, Xuyu X,Multiple sequence alignment algorithm based on a dispersion graph and ant colony algorithm, Journal of Computational Chemistry, Wiley InterScience, 200930 (13), pp 2031 – 2038
  3. Macura, Wiktor K. „Ant Colony Algorithm.“ From MathWorld–A Wolfram Web Resource, created by Eric W. Weisstein.http://mathworld.wolfram.com/AntColonyAlgorithm.html
  4. Mathur M, Karale B. S, Priye S, Jayaraman V. K, and Kulkarni B. D,Ant Colony Approach to Continuous Function Optimization, Ind. Eng. Chem. Res., 200039 (10), pp 3814–3822
  5. Korb O, Stützle T, Exner TE,An Ant Colony Optimization Approach to Flexible Protein-Ligand Docking, Swarm Intelligence, 20071 (2), pp 115-134
  6. Korb O,Efficient Ant Colony Optimization Algorithms for Structure- and Ligand-Based Drug Design, PhD Thesis, University of Konstanz, 2008
  7. In Ant Colony Optimization and Swarm Intelligence, 5th International Workshop, ANTS 2006, LNCS 4150 Edited by: Dorigo M, Gambardella LM, Birattari M, Martinoli A, Poli R, Stützle T, 2006, pp 247-258
  8. Mehmet Karatay, Safari Ants,http://en.wikipedia.org/wiki/File:Safari_ants.jpg

RSS
%d bloggers like this: