Algoritmul furnicii

Literatura de specialitate mentioneaza numeroase si variate definitii ale notiunii de agent inteligent. De exemplu, unii autori considera ca sistemele de filtrare a postei electronice sunt agenti inteligenti. Cu toate acestea, majoritatea cercetatorilor sunt de acord ca elementul central al unui agent inteligent este adaptabilitatea sau capacitatea de a invata. Ca urmare, o definitie concisa ar putea fi urmatoarea: un agent inteligent este o entitate care percepe, invata si actioneaza intr-un anumit mediu.

Cateva dintre proprietatile remarcabile ale agentilor inteligenti sunt urmatoarele:

- autonomia descrie capacitatea agentilor de a lua decizii sau de a face alegeri pe baza propriei experiente, folosind si informatii si cunostinte din si despre mediul in care actioneaza:

- adaptabilitatea descrie capacitatea agentilor ca pe masura ce reactioneaza la stimuli sau interactioneaza cu mediul exterior, sa invete, imbunatatindu-si performantele in timp;

- capacitatea de colaborare asigura partajarea cunostintelor si experientelor consumate cu alti agenti;

- mobilitatea descrie capacitatea agentilor de a se deplasa in mediul exterior pe baza deciziei proprii.

Se poate spune ca un agent care raspunde cu succes tuturor acestor cerinte este un agent inteligent daca realizeaza intotdeauna acea actiune care maximizeaza indicatorul sau de performanta, in contextul unei secvente de cunostinte avuta la dispozitie pana in acel moment.

Una din directiile de dezvoltare ale agentilor inteligenti, care a fost initiata la inceputul anilor 1990, este cea cunoscuta sub numele de modelul de optimizare dupa musuroiul de furnici sau, pe scurt, algoritmul furnicii (AF). Cercetatorii din domeniul etiologiei si stiintelor comportamentale la animale au elaborat o serie de modele care sa explice unele aspecte particulare ale comportarii sociale a insectelor, cum ar fi de exemplu procesul de auto-organizare. Ulterior, inspirandu-se din aceste modele, alti cercetatori au elaborat o serie de algoritme specializate pentru rezolvarea unor probleme dificile din punctul de vedere al efortului de calcul.

Prima forma a AF a fost propusa de Marco Dorigo in 1992, autorul considerand ca acest algoritm face parte dintr-un concept mai larg, cel al inteligentei multimilor. (in engleza, swarm intelligence).

Principiul de functionare al algoritmului furnicii

Daca se urmareste comportarea furnicilor in natura, se constata ca acestea pot gasi drumul cel mai scurt de la adapost la sursa de hrana in absenta oricaror informatii vizuale si fara o comunicare directa intre ele. De asemenea, aceleasi furnici sunt apte sa se adapteze la schimbarile mediului inconjurator. AF incearca sa foloseasca aceste abilitati ale furnicilor reale in scopul rezolvarii anumitor tipuri de probleme de optimizare.

Urmarind o colonie de furnici, se constata ca fiecare din ele pare sa se miste la intamplare, fara un scop precis. Totusi, deodata, grupuri din ce in ce mai mari de furnici se concentreaza pe directii comune. Aceasta comportare pare sa indice formarea unei inteligente colective, ce are la baza comportarea fiecarui individ.

In natura, exista o multitudine de cai pe care furnicile ajung sa formeze o inteligenta colectiva. Dintre acestea, AF foloseste capacitatea furnicilor de a elibera feromoni, lasand o urma invizibila a traseului lor. Feromonii sunt substante chimice produse de un animal si servesc, in principal, ca stimuli pentru alti indivizi din aceeasi specie, pentru anumite raspunsuri comportamentale.

Pentru a intelege cum folosesc furnicile feromonii pentru cautarea drumului de lungime minima intre doua puncte oarecare, in prezenta obstacolelor, se considera cazul a doua grupuri de furnici, avand acelasi numar de membri (de exemplu, cate 3 furnici de fiecare grup). Cele doua grupuri trebuie sa se deplaseze intre punctele A si B, unde A reprezinta adapostul sau locul de depozitare a hranei, iar B - sursa de hrana (Fig. 1.a). Trebuie spus de la bun inceput ca, plecand din A, furnicile nu-si cunosc destinatia, deplasarea lor avand loc, fara o tinta prealabila, in cautarea hranei. Admitem insa ca singurul loc din vecinatatea adapostului A in care se gaseste hrana este punctul B.

In mod natural, furnicile vor cauta traseul pentru care deplasarea de la A la B si inapoi la A sa se faca in timpul cel mai scurt. Desigur, acest timp va corespunde distantei minime dintre punctele A si B. Furnicile nu cunosc lungimile celor doua cai intre punctele A si B, insa cele doua grupuri de furnici pornesc simultan din A, pe Calea 1 si Calea 2, catre B. Deoarece Calea 1 este mai scurta, primul grup va ajunge in B inaintea celui de-al doilea (Fig. 1.b). Pe acest drum cele trei furnici lasa o urma de feromoni intr-o concentratie proportionala cu numarul lor, la fel cum se intampla si cu furnicile din cel

(a) (b) (c)

Fig. 1 Cum folosesc furnicile feromonii pentru stabilirea traseului de lungime minima.

de-al doilea grup. Dupa ce au luat hrana din punctul B, furnicile primului grup pornesc pe drumul de intoarcere spre A, folosind aceeasi cale, si ajung in A la un moment in care cel de-al doilea grup de furnici se afla undeva pe Calea 2, la dus sau la intors (nu conteaza). Pe drumul de intoarcere furnicile din primul grup lasa o noua urma de feromoni, care se suprapune peste prima, astfel incat concentratia de feromoni pe Calea 1 se dubleaza (linia groasa din Fig. 1.c). In acest moment, din A pleaca alte grupuri de furnici care, dintre caile posibile (in general, pot fi oricate, nu doar doua ca in exemplul din Fig. 1), vor alege-o pe cea pe care concentratia de feromoni este maxima, adica Calea 1 (altfel spus, calea de lungime minima). Astfel, fara a utiliza inteligenta individuala, furnicile reusesc sa gaseasca calea de lungime minima si sa formeze o inteligenta colectiva.

Caracterul dus-intors al drumului urmat de furnici este esential in formarea acestui comportament, deoarece in momentul plecarii din adapost furnicile nu cunosc distanta pe care o au de parcurs, iar in momentul in care ajung la sursa de hrana nu pot transmite localizarea acesteia celorlalte furnici. Primele furnici plecate in cautarea hranei joaca de fapt rolul unor cercetasi. In ipoteza unui teren ,,virgin", fara urme de feromoni, acesti cercetasi isi aleg caile la intamplare. Atat timp cat nici unul din cercetasi nu a parcurs drumul complet, inapoi la adapost, alte furnici care ar porni pe urmele cercetasilor ar alege la intamplare una din caile deschise de acestia, in mod echiprobabil, deoarece concentratia de feromoni este aceeasi pe toate aceste cai. Abia in momentul in care unul dintre cercetasi revine la adapost, concentratia de feromoni de pe calea urmata de acesta se dubleaza, iar dintre furnicile ce pornesc la drum, o proportie mai