Unde se întâlnesc informatica și furnicile?

Interesante

Super PowerPoint

Autori: prof. Maria și Adrian NIȚĂ În acest articol este prezentată o aplicație interesantă,...

Sortare topologică

Prof. Boca Alina GabrielaColegiul Național de Informatică „Tudor Vianu”, București

Algoritm low-memory pentru numere prime

Autor: Pirnog Theodor IoanColegiul Național “B. P. Hasdeu”, Buzău Determinarea primalității unui număr reprezintă...


Au fost realizate o serie de cercetǎri pentru a încerca o modalitate de a imita comportamentul extrem de organizat al muşuroaielor (roiurilor) de insecte şi, de cele mai multe ori, este dificil de oferit o definiţie algoritmicǎ a acestui tip de Inteligenţǎ Artificialǎ. Însǎ, potenţialul acestor metode este foarte mare, iar modalitatea de abordare se face în funcție de problemǎ.

Swarm Intelligence reprezintǎ o opțiune interesantă, fiind aplicatǎ pentru a îmbunǎtǎţi controlul și managementul pentru o rețea complexǎ de enititǎţi interactive, cum ar fi: rețele de comunicație, medii industriale, constelații de sateliți artificiali, ș.a.m.d. Conceptul a fost introdus de Gerardo Beni și Jing Wang în anul 1989 în lucrarea “Swarm Intelligence in Cellular Robotic Systems” [link].

Astfel este posibil controlul distribuit și managementul sistemelor complexe, formate din entitǎţi interactive, iar între ele şi la nivelul lor, procesul de control sǎ fie optimal, în cazul în care tehnicile de calcul tradiționale nu pot oferi un răspuns în timp real viabil.

Metodele de optim clasice pot întâmpina multe obstacole în cazul în care funcţia obiectiv este neliniarǎ şi conţine multe variabile reale, generând grafic o suprafaţǎ multidimensionalǎ cu multe vârfuri sau vǎi, corespunzǎtoare maximelor sau minimelor locale sau funcţii cu gradient nedefinit. De asemenea, pentru o funcţie cu mai mult de douǎ variabile este dificil de gǎsit un interval de incertitudine iniţial, graficul sǎu fiind imposibil de interpretat.

Ideea principalǎ se bazeazǎ pe observaţiile fǎcute asupra insectelor “sociale”. De exemplu, coloniile de furnici sau albine au interesanta proprietate de a-şi conduce la nivel înalt (numǎr imens de indivizi), într-un mod foarte ordonat, toate activitǎţile pentru a-şi asigura supravieţuirea. Paradoxal, aceste insecte par a utiliza un set foarte simplu de reguli de interacţionare. Acest fenomen este foarte similar cu alte metode, utilizate în cazul studiului complexitǎţii, cum ar fi: automatele celulare sau studiul haosului.

O serie de termeni au fost asociaţi cu SI, cum ar fi: emergent behavior, self-organized behavior, collective intelligence, dar nu existǎ încǎ o formǎ matematicǎ care sǎ reuneascǎ toate aceste noţiuni. De aceea, fǎrǎ o înţelegere completǎ, de multe ori duce la o serie de dificultǎţi în a obţine un anumit avantaj. Remediul pentru aceastǎ aparentǎ confuzie vine printr-o abordare nouǎ, care înglobeazǎ idei din tehnicile evolutive, anumite noţiuni de eficienţǎ şi adaptabilitate, toate grupate într-un mod formal, definind astfel comportamentul auto-organizat (self-organized behavior).

PRIMELE OBSERVAȚII

Coloniile de insecte au câteva modalitǎţi prin care îşi rezolvǎ o serie de probleme importante. Principalul mecanism îl reprezintǎ orientarea în spaţiu cu ajutorul feromonilor, o substanţǎ chimicǎ cu un miros specific, având proprietatea de a-şi pierde intensitatea în timp (fenomen de evaporare):

N = Nest (cuib), F = Food (hrană)

Imaginați-vă o matrice de adiacență pe un graf care are asociate valori ce rețin dinamic nivelul de feromoni… deja avem o idee care poate conduce spre o analiză a spațiul soluțiilor într-o altă manieră… cu cât intensitatea este mai ridicată, cu atât drumul este mai bun, nu?

Aceastǎ substanţǎ formeazǎ baza acestui comportament, aparent simplu şi inteligent, fiind un mod prin care se realizeazǎ comunicaţia şi se reţin informaţiile. Deoarece “parfumul” degajat de feromoni se diminueazǎ în timp, el genereazǎ un mecanism care implementeazǎ forme de feedback negativ sau pozitiv.

Ca un exemplu, considerǎm rezolvarea determinǎrii drumului cel mai scurt (aparent aleator) de la o sursǎ cǎtre destinaţie. Insectele aleg întotdeauna calea cea mai scurtǎ. Furnicile (multe furnici, agenții) pleacǎ la început în cǎutarea mâncǎrii pe cǎi diferite. De-a lungul drumului, ele lasǎ urme prin feromoni. Odatǎ ce este gǎsitǎ o sursǎ de mâncare, ele se întorc la cuib pe acelaşi drum, ghidaţi de substanţǎ.

EVITAREA UNUI OBSTACOL

De vreme ce multe grupuri de furnici sunt duse în cǎutare, cele care se întorc primele au gǎsit drumul cel mai scurt şi accesibil pentru întreaga colonie. În plus, drumul cel mai scurt are şi nivelul de intensitate al substanţei mult mai ridicat:

Informatica si furnicile | infobits Academy
https://www.fpri.org/2013/07/foreign-fighters-and-ants-how-they-form-their-colonies/

Feedback-ul pozitiv este reprezentat prin faptul cǎ dacǎ drumul optim este obstrucţionat (distrus) la un moment dat, este ales cel de-al doilea drum scurt, etc. Raportul dintre nivelul de feromoni duce la stabilirea redundanţei, robusteţei şi al adaptabilitǎţii.

MAI MULT …

Obţinerea informaţiilor se realizeazǎ cu ajutorul a trei tipuri de agenţi: exploratorii, alocatorii şi dealocatorii. Agenţii de tip explorer cautǎ drumul optim de la sursǎ la destinaţie, lasând urme de feromoni de-a lungul reţelei. Agentii alocatori traverseazǎ calea determinatǎ de explorer şi alocǎ (memoreazǎ) drumul. Similar, dacǎ un drum nu mai este necesar, agentul dealocator retrage (şterge – deci, feedback negativ) banda de transmisie pentru acea legăturǎ.

Puteți căuta pe Internet informații despre Ant Swarm Colony, algoritmi ACO (Ant swarm Colony Optimisation), ș.a.m.d.

UN EXEMPLU DE SIMULARE

O simulare interesantă a unui astfel de sistem, bazat pe agenți inteligenți, și implementată sugestiv în limbajul de programare C++ este oferită de John Buffer:

Codul său sursă îl puteți descărca de pe GitHub la adresa de mai jos:
https://github.com/johnBuffer/AntSimulator

Puteți observa potențialul imens al acestor tehnici de optimizare bazate pe algoritmi de calcul preluați din natură, deci STEM. De altfel, și recursivitatea o găsim adesea în jurul nostru, fie că este vorba despre un arbore sau o simplă cochilie, nu?


DESPRE FEROMONI

Feromonii sunt grupări chimice, molecule care au rolul de a transmite anumite semnale, mesaje diferitelor specii din mediul vegetal ori animal. De multe ori nu suntem conștienți de prezența lor, însă ne stimulează chiar și nouă intens organismul, fie că vorbim despre plante, parfumuri interesante, animale sau semenii noștri.

În mod normal, și noi secretăm feromoni, însă adesea ei sunt eliminați prin anumite măsuri de igienă corporală – nu au aromă sau miros, dar sunt suficient de puternici pentru a determina anumite reacții ale celor din jurul nostru. Mai mult, industria parfumurilor face apel la diverși feromoni puternici găsiți în natură pentru a stimula adesea atracția dintre noi ori plăcerea olfactivă.

- Reclamă -

Citește și ...

Super PowerPoint

Autori: prof. Maria și Adrian NIȚĂ În acest articol este prezentată o aplicație interesantă,...

Sortare topologică

Prof. Boca Alina GabrielaColegiul Național de Informatică „Tudor Vianu”, București

Algoritm low-memory pentru numere prime

Autor: Pirnog Theodor IoanColegiul Național “B. P. Hasdeu”, Buzău Determinarea primalității unui număr reprezintă...

O aplicație pentru partiții Fibonacci

Autori: Radu-Ioan MIHAI, Maria-Raluca STĂNESCUUniversitatea din București, Facultatea de Matematică și Informatică, Specializarea Informatică
- Reclamă -

Sortare topologică

Prof. Boca Alina GabrielaColegiul Național de Informatică „Tudor Vianu”, București Trebuie să vă îmbrăcați pentru...

Algoritm low-memory pentru numere prime

Autor: Pirnog Theodor IoanColegiul Național “B. P. Hasdeu”, Buzău Determinarea primalității unui număr reprezintă o sarcină de lucru pe...

O aplicație pentru partiții Fibonacci

Autori: Radu-Ioan MIHAI, Maria-Raluca STĂNESCUUniversitatea din București, Facultatea de Matematică și Informatică, Specializarea Informatică În acest articol este prezentată...

Analiza amortizată – utilizarea unei stive

Analiza amortizată este o metodă de evaluare a eficienței algoritmilor care operează asupra unor structuri de date. De obicei analiza amortizată e...

Mai multe articole

- Reclamă -