Extras din curs

Un algoritm relativ nou, utilizat în domeniul optimizărilor discrete este inspirat din viaţa insectelor. Algoritmul se bazează pe capacitatea acestora de a acţiona în ansamblu pentru îndeplinirea unei sarcini, fiecare individ nefiind capabil să atingă singur acest obiectiv. Acest proces este un tip de mecanism de optimizare distribuită, întrucât fiecare furnică dă numai o foarte mică contribuţie.

Vom studia o colonie de furnici artificiale, capabilă să rezolve problema comis-voiajorului (TSP). Furnicile coloniei artificiale, sunt capabile să genereze succesiv tururi fezabile, din ce în ce mai scurte, utilizând informaţia acumulată sub formă de dâră de feromon, depozitată pe muchiile grafului unei probleme TSP. Colonia de furnici este capabilă să genereze soluţii bune, atât pentru instanţe simetrice cât şi asimetrice ale TSP. Metoda este un exemplu precum “simulated annealing”, “reţelele neuronale” şi “calculul evolutiv”, al utilizării cu succes a unor metafore din natură pentru a proiecta algoritmi de optimizare.

Furnicile reale sunt capabile să găsească cel mai scurt drum dintre o sursă de mâncare şi muşuroi (Goss, Aron, ş.a. 1989) fără să utilizeze contactul vizual. De asemenea ele sunt capabile să se adapteze la schimbările din mediu, de exemplu să găsească o nouă cale cea mai scurtă din momentul în care cea veche nu mai este disponibilă datorită apariţiei unui obstacol nou.

Considerăm Fig. 1.A: furnicile se mişcă pe linia dreaptă ce uneşte sursa de mâncare cu muşuroiul. Este bine cunoscut că principala metodă a furnicilor de a forma şi menţine linia este dâra de feromon. Furnicile depozitează o anumită cantitate de feromon atunci când se deplasează şi fiecare furnică preferă probabilistic să urmeze o direcţie mai bogată în feromon. Acest comportament al furnicilor reale poate fi utilizat pentru a explica cum acestea pot găsi drumul cel mai scurt care reconectează o linie întreruptă de apariţia bruscă a unui obstacol (Fig. 1.B).

În fapt, odată ce obstacolul a apărut acele furnici care se află în faţa obstacolului nu mai pot continua să urmărească dâra de feromon şi de aceea ele trebuie să alegă între a se întoarce la stînga sau la dreapta. În această situaţie ne aşteptăm ca jumătate dintre furnici să aleagă să se întoarcă la dreapta iar cealaltă jumătate la stânga. O situaţie similară poate fi găsită de cealaltă parte a obstacolului (Fig. 1.C). Este interesant de notat că acele furnici care au ales drumul mai scurt împrejurul obstacolului vor reconstitui mai rapid urma de feromon comparativ cu cele ce au ales drumul mai lung. Astfel drumul mai scurt va primi o cantitate mai mare de feromon pe unitatea de timp şi în punctul de întrerupere a vechiului drum, un număr mai mare de furnici vor alege drumul mai scurt. Datorită acestui proces de feedback pozitiv toate furnicile vor alege rapid calea mai scurtă (Fig. 1.D). Cel mai interesant aspect al acestui proces autocatalitic, este acela că, găsirea celui mai scurt drum în jurul obstacolului pare să fie o proprietate emergentă a interacţiunii dintre forma obstacolului şi comportamentul distribuit al furnicilor. Deşi toate furnicile se mişcă aproximativ cu aceeaşi viteză şi depozitează o dâră de feromon cu aproximativ aceeaşi rată este clar că, durează mai mult să înconjoare obstacolul pe partea mai lungă decât pe partea mai scurtă, ceea ce face ca dâra de feromon să se acumuleze mai rapid pe calea mai scurtă.