Cum ne ușurează furnicile viața

Acum câteva zile a fost publicat un articol care conținea un scurt documentar despre inteligența și hărnicia furnicilor, care, din punctul meu de vedere, ne-a dat o lecție de viață despre lucrul în echipă (cu indivizi de ordinul milioanelor). Și nu este singurul exemplu pe care ni-l oferă aceste mici vietăți.

Pentru că omul, din cele mai vechi timpuri, a fost fascinat și inspirat de natură, de comportamentul animalelor, am să subliniez pe scurt în acest material influența micilor arhitecți care și-au lăsat amprenta asupra noilor tehnologii informatice.

“Metoda este inspirată din comportamentul furnicilor, mai exact din procesul de căutare a hranei. Observațiile au fost făcute în urma unui experiment cu o colonie de Iridomyrmex humilis.

Furnicile au avut acces la hrană printr-un drum cu două ramuri de lungimi diferite care plecă de la propriul cuib. S-a observat că toate furnicile au tins să meargă pe drumul cel mai scurt. 

Prin observarea comportamentului furnicilor, cercetătorii au început să înțeleagă mijloacele lor de a comunica.

În timp ce se deplasează, acestea depun o substanţă numită feromon pentru a comunica între ele pentru găsirea celei mai scurte rute.

Cu cât sunt mai multe furnici care urmează aceeași cale, cu atât acea cale devine mai atractivă. 

Furnicile navighează ‘orbește’ de la mușuroiul propriu către sursa de mâncare.
Când apare obstacolul, trebuie să decidă dacă să meargă la stânga sau la dreapta, iar alegerea se face în mod aleator.

Acumularea de feromon este, însă, mai rapidă pe drumul mai scurt.

Diferența de cantitate de feromon creată în timp între cele două drumuri determină furnicile să aleagă calea mai scurtă.

În concluzie, cea mai scurtă cale este descoperită prin urmele de feromon:

– fiecare furnică se deplasează inițial la întamplare;

– depozitează feromon pe calea urmată;

– furnicile determină apoi calea cea mai urmată și tind să o urmeze tot pe aceasta;

– mai mult feromon pe un drum mărește probabilitatea ca acel drum să fie urmat.”

În urma acestor analize, au fost puse bazele unui algoritm ACO (Ant Colony Optimization) care se folosește de un sistem multiagent (furnici artificiale) pentru a imita comportamentul furnicilor reale. Sistemul artificial se bazează pe cooperarea acestor indivizi pentru a obține o soluție fezabilă pentru o anumită problemă.

Aria de aplicare a acestui algoritm este foarte mare. Spre exemplu, este folosit în probleme de permutări, Clasificare, Învațare automată, Procesare de imagini, probleme de rutare a rețelelor, Testare Inteligentă, Proiectare circuite electrice etc.

Acest algoritm este arhicunoscut pentru eficiența lui în problemele de rutare (găsirea celui mai scurt drum într-un graf).

V-ați gândit vreodată ce algoritm se ascunde în spatele aplicatiei Google Maps?
Prin ce algoritm se găsește cel mai scurt drum între două orașe?

Nu știm sigur ce se ascunde în spatele acestei aplicații, dar vă asigur că ACO (Ant Colony Optimization) face același lucru. Pentru o hartă atât de complexă cum este Google Maps, implementarea unui simplu algoritm cum este ACO nu este suficient ca raportul returnat “cost timp/rezultate optime” să fie foarte bun, așa că cercetatorii au analizat de-a lungul timpului și alți algoritmi asemănători (ex: Tabu Search, Intelligent Water Drops, Swarm Intelligence).

Comparând rezultatele, au ajuns la concluzia că o hibridizare între algoritmi ar aduce un succes garantat și o îmbunătățire exponențială într-un timp mult mai scurt, astfel au dezvoltat noi algoritmi hibrizi cum sunt ACO-GA (cu algoritmi genetici), ACO-SA (cu simulated annealing), PSO-ACO, ACO-Tabu Seach etc.

Alți algoritmi

Un alt algoritm interesant inspirat din natură este Firefly Algorithm. Sunt sigur că toți suntem fascinați de licurici. Aceste insecte care nu sunt prea răspândite, se mai găsesc în Noua Zeelandă, Australia, Tasmania, Scoția și partea de Sud a Angliei. Licuricii trăiesc in peșteri, sub pietre și în special în zonele cu umiditate ridcată. Aceste insecte au organe în abdomen, în special în ultimele segmente, care conțin substanțe ce produc lumină printr-o reacție chimică. Doar femelele si larvele produc această lumină, care are scopul de a atrage mici insecte pentru hrană, dar și pentru a se apăra de inamici.

Cercetătorii au analizat comportamentul lor astfel: au ținut sub observație câteva zone unde se adunau coloniile de licurici, care în starea inițială luminau aleator. După o perioadă de timp s-a observant că licuricii au început să se sincronizeze, astfel au început toți să lumineze în același timp.

Algoritmul inspirat de modul de comunicare al licuricilor a fost folosit în unele Procesări și Compresări de Imagini, Problema Comis Voiajorului, Clasterizare etc.

La prima vedere, tindem să neglijăm aceste vietăți, dar oare ne-am gândit vreodată câte beneficii ne aduc nouă? Ce ar fi făcut omul dacă ar fi fost singur pe Pământ? Dacă ne gândim bine, foarte multe descoperiri științifice au la bază inspirația din natură, fie apele curgătoare, fie licuricii, albinele, furnicile, bancurile de pești, sunetele care redau muzica (Harmony Search) și multe altele.

Oare nu e un semn de întrebare că nimic nu este întâmplător? Că la baza tuturor este un Creator, un Designer care s-a gandit înaintea tuturor de cele trebuincioase nouă? Ne preocupăm de prea multe și uităm de cele simple. Tocmai în lucrurile simple au găsit cercetătorii cheia multor probleme.

Așa este, omul se impune și creează prin inteligența lui, dar oare inteligența lui ar da vreun rezultat dacă nu ar avea o sursă de inspirație?

Cât de minunate sunt lucrurile Tale, Doamne, toate cu înțelepciune le-ai făcut!

(Alexandru Andrei)

Biliografie (fragmente de text despre ACO si fotografii): http://inf.ucv.ro/~cstoean/courses/ia/c7.pdf