Cursuri RFIA

Introducere

Swarm Intelligence este o noua paradigma computationala bazata pe studiul comportamentului colectiv in sisteme decentralizate, auto-organizate. Rezolvarea de probleme are loc la un nivel superior unei colectii de agenti idealizati, fara intentia de rezolvare din partea individului. Altfel spus, agentii individuali nu sunt constienti ca rezolva o problema, dar interactiunea colectiva duce la rezolvarea ei. Schimbul de informatii dintre membrii aceleasi specii ofera un avantaj evolutiv: membrii grupului pot profita de pe urma descoperirilor si experientei anterioare a tuturor celoralalti membri.

Ant Colony Optimization (ACO) este inspirat din comportamentul furnicilor si este folosit pentru optimizarea diverselor probleme. Ideea principala consta in comunicarea indirecta dintre furnici, prin urmele de feromoni lasate, ceea ce le ajuta sa gaseasca un drum cat mai scurt intre locul in care se gaseste hrana si musuroiul lor.

Ant Colony Optimization (ACO)

In natura, furnicile umbla de obicei aleator iar la gasirea hranei se intorc la musuroi lasand urme de feromon (FEROMÓN, feromoni, s.m. (Biol.) = hormon eliminat mai ales de insecte, ca mijloc de semnalizare). Daca alte furnici gasesc aceste urme de feromoni, ele sunt norocoase deoarece nu trebuie sa mai caute hrana umbland la intamplare ci urmarind aceste urme de feromoni si intarindu-le in cazul in care gasesc si ele la randul lor hrana. Oricum, odata cu trecerea timpului, feromonul incepe sa se evapore. Cu cat unei furnici ii ia mai mult timp sa mearga de-a lungul urmei, sa gaseasca hrana si sa se intoarca, cu atat feromonul se va evapora mai repede (iar urma de feromon va fi mai putin proeminenta). Cu cat o dara este mai scurta, cu atat va fi vizitata de mai multe furnici iar densitatea de feromon va fi mai mare si va rezista un timp mai indelungat.

ACO este implementata ca o echipa de agenti inteligenti ce simuleaza comportamentul furnicilor, bazandu-se pe mecanismul de cooperare si adaptare. Algoritmul ACO necesita anumite conditii ce trebuie indeplinite:

- Problema trebuie sa fie reprezentata în mod corespunzător, ceea ce ar permite

furnicilor actualizarea soluţiilor, prin utilizarea unei reguli de tranziţie probabilistice, pe baza cantităţii de feromoni lasate pe traseu ;

- O functie euristica η ce măsoara calitatea componentelor ce pot fi adăugate la soluţia parţiala curenta ;

- Regula de modificarea a cantitatii de feromon τ ;

- O regula de tranzitie probabilistica bazata pe valoarea functiei euristice η si a cantitatii de feromon τ, ce va fi folosita pentru constructia iterativa a solutiei.

ACO a fost introdusa pentru prima data folosind Problema Comis-Voiajorului (Travelling Salesman Problem - TSP). Pornind de la nodul initial, o furnica se muta iterativ de la un nod la altul. Cand ajunge la un nod, o furnica alege sa viziteze un nod nevizitat la timpul t cu o probabilitate data de :

, unde :

- este cea mai fezabila vecinatate pentru antk (furnicak), dar din aceasta vecinatatea fac parte orasele care nu au mai fost vizitate pana atunci de antk

- este valoarea de feromon a arcului (i, j), la momentul t

- este ponderea feromonului

- este o informatie euristica apriori despre arcul (i, j), la momentul t

- este ponderea informatiei euristice

esre determinat de :

- este rata de evaporare a feromonului (0 < < 1)

- n este numarul de furnici

- Q este o constanta pentru actualizarea feromonului

O versiune a pseudo-codului pentru ACO cu aplicatie in TSP este ilustrata in algoritmul de mai jos :

Problema Comis Voiajorului folosind ACO

Problema Comis Voiajorului este intalnita in literatura engleza sub dennumirea de Travelling Salesman Problem (TSP) si se enunta astfel : dandu-se o multime de orase si costul calatoriei dintre oricare doua orase, comis voiajorul trebuie sa gaseasca drumul de cost minim astfel incat sa viziteze toate orasele si sa se intoarca in final in orasul din care a plecat, dar sa nu treaca de 2 ori prin acelasi oras.

In continuare, costul calatoriei dintre 2 orase se va traduce prin distanta fizica intre cele 2 orase. Deci costul minim va fi de fapt cel mai scurt traseu astfel incat sa se viziteze toate orasele, dar sa nu se treaca de 2 ori prin acelasi oras.