Grafuri Orientate

2. Fundamentarea teoretică

2.1. Elemente de teoria grafurilor

Teoria grafurilor studiază grafurile și proprietățile acestora, atât în matematică, pe cât și în informatică. Numim graf o mulțime de obiecte (noduri) conectate între ele printr-o mulțime de muchii cărora le putem atribui direcții (în acest caz avem graf orientat, despre care vom vorbi mai detaliat în continuare). Un graf poate fi reprezentat sub forma unor figuri geometrice formate din puncte (vârfuri) și linii drepte sau curbe (arce, muchii) care unesc aceste puncte.

Teoria grafurilor este una dintre disciplinele matematice, care și-a găsit o aplicație largă la soluționarea problemelor practice din diferite domenii: fizică, chimie, economie etc.

2.1.1. Grafuri orientate

Definiția 2.1. Din punct de vedere matematic, se numește graf orientat o pereche de mulțimi G= (X, U), unde: X este o mulțime finită și nevidă, ale cărei elemente se numesc noduri (vârfuri), iar U este o mulțime formată din perechi ordonate (x, y), x, y∈ X, numită mulțimea arcelor (muchii). Dacă (x, y) ∈U, x se numește extremitatea inițială (originea) a arcului, iar y, extremitatea finală (extremitatea).

Exemplu de graf orientat: G=(X, U) unde: X={ 1,2,3,4,5} U={(1,2), (1,3),(1,5),(3,1),(4,2)}

Fig.2.1. Graf orientat

Grafurile permit modelarea unui număr mare de situații (Henry-Labordere, 1995).

Exemple de grafuri:

În unele problemele de sortare și căutare – elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf.

O rețea rutieră (doar sens unic) – vârfurile sunt intersecțiile, iar arcele sunt drumurile.

În problemele de routare

În scrierea aplicațiilor GPS

Definiția 2.2. Se numește drum într-un graf orientat un șir de arce D = {u1,…uk|uiU , i=} cu proprietatea că extremitatea finală a arcului ui coincide cu extremitatea inițială a arcului ui+1 , i =.

În cazul în care extremitatea inițială a arcului u1 coincide cu extremitatea finală a arcului uk atunci drumul se numește circuit. Circuitul format dintr-un singur arc se numește bucla, iar dacă nodurile arcelor drumului sunt distincte două câte două, drumul se numește elementar.

Definiția 2.3.

Un nod x dintr-un graf orientat G se numește precedentul altui nod y din G dacă exist (x, y)∈U .

Un nod y dintr-un graf orientat G se numește succesorul altui nod x din G dacă există arcul (x, y)∈U .

Un nod x dintr-un graf orientat G se numește ascendentul altui nod y din G dacă există un drum de origine x și extremitate y.

Un nod y dintr-un graf orientat G se numește descendentul altui nod x din G dacă există un drum de origine x și extremitate y.

Definiția 2.4. Fie G= (X, U) un graf orientat. Se numește graf parțial, al grafului G, graful orientat G1= (X, U1) unde U1⊆ U.Cu alte cuvinte, un graf parțial, al unui graf orientat G= (X, U), are aceeași mulțime de vârfuri ca și G, iar mulțimea arcelor este o submulțime a lui U sau chiar U.

Fie G= (X, U) un graf orientat. Un graf parțial, al grafului G, se obține păstrând vârfurile și eliminând eventual niște arce.

Definiția 2.5. Se numește graf tare conex, graful în care pentru orice perechi de vârfuri x, y∈ X există un drum din x plecând la y.

Definiția 2.6. Se numește arborescență un graf tare conex și fără cicluri, orientat, a cărui orientare este astfel încât fiecare vârf al său cu excepția unuia singur, numit rădăcină, este extremitatea terminală a unui arc și numai unul.

Definiția 2.7. Se numește graf ponderat sa i se notează G=(X, U, l) un graf (X, U) căruia i se asociază o funcție numită ponderea arcelor.

Definiția 2.8 (Drumuri in graf) Se dă un graf orientat G= (X, U). Un drum în graful G este o succesiune de arce cu proprietatea că extremitatea terminală a unui arc coincide cu extremitatea inițială a arcului următor din drum.Cu alte cuvinte, un drum este o succesiune de vârfuri cu proprietatea că oricare două vârfuri consecutive sunt unite printr-un arc.

Un drum intr-un arc poate fi :

Simplu,daca nu foloseste de doua ori un acelasi arc

Compus

Elementar,daca nu trece de doua ori prin acelasi varf

Eulerian

Hamiltonian

Circuit

2.1.2. Grafuri neorientate

Definitia 2.9. Se numește graf neorientat perechea de mulțimi G=(X,U), unde: X este o mulțime finită și nevidă, iar U este o mulțime de perechi neordonate (x, y) cu x, y∈X . Elementele lui X se numesc vârfurile (nodurile) grafului, iar elementele lui U se numesc muchiile (arcele) grafului. Dacă u= (x, y)∈U , x și y se numesc extremitățile muchiei u.

Fig.2.2 Graf neorientat

Definitia 2.10. Un graf G=(X, U), în care, dacă (x, y)∈U atrage (y, x)∈U , se

umește graf simetric.

Definitia 2.11. Un graf neorientat, G=(X, U), se numește graf complet dacă

pentru (∀)x, y∈ X avem (x, y)∈U .Cu alte cuvinte Graful G se numește graf complet, dacă oricare două vârfuri distincte ale sale sunt adiacente.

Fie graful G=(X, U) unde : X={1, 2, 3, 4, 5}

U={[1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2, 5], [3,4], [3,5], [4,5]}

Fig.2.3 Graf neorientat complet

Definitia 2.12. Într-un graf neorientat, perechea G=(X,U), se numește lanț o mulțime de

vârfuri L= {x1,…,xk|xi ∈ X , i=} cu proprietatea că oricare două vârfuri

consecutive sunt adiacente, adică (xi,xi+1) ∈ U. Vârfurile x1, xk se numesc extremitățile lanțului, iar numărul de muchii care intră în componența sa se numește lungimea lanțului.

Dacă x1,…,xk sunt distincte două câte două, lanțul se numește elementar, altfel se numește neelementar.

Definitia 2.13. Un graf G=(X,U) se numește simplu conex sau conex dacă pentru orice pereche de vârfuri x, y∈ X există un lanț de extremități x și y .

Definitia 2.14. Se numește ciclu într-un graf G= (X, U), un lanț L= {x1,…,xk|xi ∈ X , i=} cu proprietatea că x1=xk și muchiile (x1, x2),…, (xk-1, xk) sunt distincte două câte două.

Definitia 2.15. Un lanț, un drum, ciclu sau circuit se numește hamiltonian dacă el trece o dată și numai o dată prin toate vârfurile grafului. Un lanț, drum sau ciclu se numește eulerian dacă trece o dată și numai o dată prin toate arcele grafului.

2.1.3. Algoritmul lui Dijkstra

Algoritmul lui Dijkstra este un algoritm utilizat pentru a calcula drumurile de cost minim de la un nod al unui graf la toate celelalte noduri ale grafului respective. A fost introdus pentru prima data de catre informaticianul olandez Edsger Dijkstra.

Algoritmul lui Dijkstra permite calcularea lungimilor celor mai scurte drumuri de la un vârf s la toate vârfurile x ale unui graf conex G= (X, U, l), dacă lungimile tuturor arcelor sunt nenegative.

Din punct de vedere matematic algoritmul poate fi descris astfel: fie lungimea celui mai scurt drum de la s la x. Fie S mulțimea vârfurilor pentru care se calculează.

Atunci, este egal, prin definiție, cu lungimea celui mai scurt drum de la s la x, care are toate vârfurile în S cu excepția lui x. Se notează cu Γ +(x) mulțimea arcelor care pornesc din nodul x, iar cu Γ -(x) mulțimea arcelor care ies din nodul x.În cazul unui graf neorientat avem relația :

Γ +(x) = Γ -(x) = Γ (x) = mulțimea arcelor incidente în nodul x.

Algoritmul Dijkstra:

Pasul 1: Inițializări

S :={s} ; s nodul de start,:=0 ;

Pentru orice x∈ X – S daca x∈Γ (x) atunci :=l(s,x) altfel :=+∞ ;

Pasul 2: Iterația curentă

Repetă

Determină y∈ X − S astfel încât =;

Dacă atunci S:=S{y};

Pentru z∈Γ+(y) :=min {,+l(z,y)}; până când S=X sau =

Pasul 3 : Stop

In general algoritmul lui Dijkstra se aplica pe grafuri ponderate si orientate (arcele sunt orientate de la un nod la altul, nu se poate merge invers, și au asociate un anumit cost de care se va ține seama în determinarea drumului minim), dar se poate utiliza și asupra altor tipuri de grafuri.

Dacă graful este neponderat (arcele nu au costuri asociate) atunci drum minim între două noduri se consideră drumul alcătuit din număr minim de arce. Pe un graf neponderat, pentru a putea aplica algoritmul lui Dijkstra trebuie să transformăm graful într-unul ponderat, asociind fiecărui arc același cost.

Algoritmul lui Dijkstra funcționează atât pe grafuri conexe cât și pe grafuri neconexe. Conform definiției, un graf conex este un graf unde, plecând din orice nod al grafului se poate ajunge la oricare alt nod al grafului respective.

În comparație cu alți algoritmi utilizați pentru găsirea drumului optim, de exemplu algoritmul Ford care pentru găsirea valorii vârfului final, implicit al drumului optim (în algoritmul lui Ford se pleacă de la nodul inițial în toate direcțiile păstrând de fiecare dată vârfurile analizate, ceea ce duce la o risipă inutilă de timp, deoarece multe din vârfuri nu vor face parte din drumul optim), algoritmul lui Dijkstra încearcă să păstreze mulțimea minimă de vârfuri care să le conțină pe toate cele vor forma drumul optim la final. Un alt plus al algoritmului lui Dijkstra este că se poate aplica și în drumuri cu circuite, în schimb, un punct slab este faptul că se aplică doar la problemele de minim.

2.2. Swarm Intelligence

Noțiunea de swarm intelligence sau comportamentul intelligent al mulțimilor reprezintă o paradigmă computaționala, relativ nouă și inspirată din natură, care se bazează pe studiul comportamentului biologic colectiv în sistemele decentralizate și auto-organizate. Câteva exemple de sisteme studiate de către această disciplină ar fi coloniile de furnici și termite, bancurile de pești sau stolurile de păsări. Termenul de swarm intelligence introdus în anul 1989 de către cercetătorii Gerardo Beni și Jing Wang în contextual sistemelor de roboți

Bazele swarm intelligence sunt profund înrădăcinate în studiul insectelor care se autoorganizeza. Comportamentul colectiv al acestor insecte au generat numeroase teme de studio în acest domeniu încă în curs de dezvoltare.De la problemele de rutare al traficului în rețelele de telecomunicații la proiectarea și implementarea algoritmilor de control în robotică, toate și-au găsit soluționarea în metodele de rezolvare furnizate de studiul comportamental al insectelor.

La nivel individual, agenții nu sunt conștienți că rezolva o problemă și nu au intenția soluționării, dar privind de la un nivel superior, interacțiunea colectivă a acestora reprezintă rezolvarea problemei.Cu alte cuvinte, swarm intelligence studiază comportamentul colectiv al grupurilor (sistemelor) compuse din tr-un număr mare de indivizi și care prin interacțiunea lor conduc spre atingerea obiectivelor.

Un aspect interesant al coloniilor este că deși numărul de insecte variază de la un număr mic de indivizi la unul foarte mare, acestea combina eficiența cu flexibilitatea și robustețea. Aceste caracteristici se regăsesc și în algoritmii de inspirație naturală.

Alte proprietăți ale sistemelor Swarm Intelligence:

Sunt compuse dintr-un număr mare de indivizi

Sunt sisteme omogene (indivizii sunt de același fel)

Interacțiunile dintre indivizi se bazează numai pe reguli simple de comportament

Comportamentul general rezultat din interacțiunile indivizilor face că sistemul să fie unul autoorganizat

Această paradigmă oferă astfel un nou cadru pentru proiectarea și implementarea sistemelor multi-agent capabile să soluționeze problem cu un grad ridicat de complexitate.

Avantajele potențiale ale acestei abordări sunt:

Robustețea colectivă – eșecul individual nu afectează în mod semnificativ performanță. Datorită membrilor de același tip, interschimbabil și care nu dețin controlul, aceștia pot fi cu ușurință înlocuiți cu alți indivizi pe deplin capabili.

Simplitatea individuală – cooperarea comportamentală face posibilă reducerea complexității individuale

Scalabilitatea – mecanismele de control folosite nu sunt dependente de numărul de agenți. Cu alte cuvinte, sistemul își poate menține funcția și acțiunile sale cu toate că dimensiunea să crește, fără a fi nevoie de a-și redefini acțiunile. Comportamentul fiecărui individ este influențat într-o măsură nesemnificativa de către dimensiunea sistemului, deoarece în acest tip de sisteme interacțiune indivizilor este una care implică doar membrii vecini. Această caracteristică este una esențială în sistemele artificiale și algoritmi, deoarece un sistem scalabil poate crește performanta doar prin simplă creșterii a dimensiunii sale.

Paralelismul – acțiunile paralele, se referă la faptul că în sistemele de tip swarm intelligence, indivizii care compun populația, pot executa același tip de acțiuni în mai multe locuri, în același interval de timp. Această caracteristică face sistemul mai flexibil, capabil de autoorganizare în subsisteme care prin rezolvarea diferitelor problem în același timp pot duce la rezolvarea unei problem de o complexitate ridicată.

2.3. Ant Colony Optimization (ACO)

În mediul natural, furnicile și termitele se deplasează într-un mod aleator în acțiunea lor de găsire a hranei, iar dup ace găsesc sursa de hrană, se întorc la mușuroi lăsând urme de feromoni pe unde s-au deplasat. Feromonul nu este altceva decât o substanță specifică insectelor, folosită ca mijloc de semnalizare. Celelalte furnici cauta la rândul lor surse de hrană, iar dacă găsesc această urmă de feromon, ele țiind să o urmeze, lăsând la rândul lor și ele feromoni, “întărind” astfel concentrația acestuia pe drumul respective. Fiind o substanță chimică, odată cu trecerea timpului feromonul se evaporă, deci dacă drumul găsit de o furnică este foarte lung de la cuib la sursa de hrană, concentrația feromonului va fi mai slabă, iar dacă este o cale mai scurtă, cu o concentrație de feromon mai proeminentă, furnicile vor urma calea respective.

ACO este o metaeuristica bazata pe actiunile collective si comportamentul unui grup autoorganizat si decentralizat , folosita in rezolvarea problemelor complexe de optimizare.

Metaeuristica – termenul de metoda metaeuristica reprezintă un ansamblu de concept algoritmice care permit definirea unor metode euristice care pot fi aplicate mai multor tipuri de problem. Este un cadru de rezolvare general al problemelor care poate fi ușor adaptat pentru alte problem particulare.

Euristica – termenul de euristica sau metoda euristică face referire la o metodă de studio sau de cercetare care duce la descoperirea de fapte noi.

Metoda de optimizare folosind coloniile de furnici sau termine este o metodă de inspirație biologică, inspirată din comportamentul furnicilor reale în acțiunea lor de căutare a hranei. Algoritmul de optimizare folosind coloniile de furnici face parte din domeniul Swarm Intelligence și a fost introdus pentru prima dată de către cercetătorul Italian Marco Dorigo în lucrarea sa de doctorat, iar scopul algoritmului era de a căuta drumul optim într-un graf, algoritm inspirat din acțiunea furnicilor în găsirea celei mai scurte rute între mușuroi și sursa de mâncare.

Să aruncăm o privire asupra modului în care acționează furnicile, pentru a ne face o primă idee despre ce înseamnă ACO. Avem 3 cadre diferite în imagine (1,2,3).În primul cadru este prezentat drumul de la cuib la hrană, evident cu cai de lungime diferită. În cadrul doi, furnicile se deplasează aleator pe toate căile disponibile de la cuib la hrană, marcând drumul cu feromoni. Cum concentrația de feromon este mai puternică pe drumul cel mai scurt, observăm în cadrul al treilea că majoritatea furnicilor tind să urmeze aceeași rută.

Fig. 2.3. Selectarea rutei optime a furnicilor in natura

2.3.1. Selectarea rutei

După cum știm și am văzut în figură 2.3 furnicile sunt capabile să găsească drumul cel mai scurt de la mușuroi la sursa de hrană datorită feromonului. Același lucru se observă și în cadrul A al figurii 2.4, în care furnicile urmăresc aceeași rută mușuroi – sursa hrană. De asemenea furnicile sunt adaptabile la mediul înconjurător ; în cazul în care vechea ruta nu mai este accesibilă (cadrul B), a apărut un obstacol, furnicile nu mai pot urmări vechea ruta, astfel ele sunt puse în situația de a alege o nouă ruta, acest decizie este luată într-un mod aleator, o parte din furnici o vor lua la stânga, iar cealaltă parte la dreapta (cadrul C). Știind că furnicile aleg calea cu o concentrație mai proeminentă de feromon, într-un final, toate furnicile vor urma calea cea mai scurtă (cadrul D).

Fig. 2.4. Selectarea rutei in cazul in care apare un obstacol

2.3.2. Sistemul artificial

Experimentul inițial a fost realizat folosind o colonie de furnici din specia Iridomyrmex humilis. Sistemul artificial este compus de furnici artificiale, mutant ai furnicilor reale, care formează un sistem multiagent care simulează funcțiile observate în urma experimentului asupra coloniei de furnici. Sistemul artificial se bazează pe același tip de colaborare ca și sistemul natural, interacțiunea unui grup de furnici artificiale pentru a obține o soluție optimă pentru problema propusă.

Sistemul presupune o tranziție probalistica între nodurile grafului. Fiecare furnică artificială trebuie să stabilească cel mai scurt drum între nodul sursă și nodul destinație al grafului sub forma căruia a fost reprezentată problema. Soluția va fi constituită prin mutări succesive ale furnicii artificiale dintr-un nod în altul.

Fiecărui arc (i, j) al grafului i se asociază variabilă ij care codifică urmă de feromon asociata arcului. Acestei cantități de feromon îi vor acorda furnicile artificiale utilitatea folosirii arcului în constituirea soluției. La început toate arcele conțin aceeași cantitate inițială de feromon0.

Ca și în natură, feromonul este supus fenomenului de evaporare:

ij= (1-)*ij , (1)

unde este coeficientul de evaporare al feromonului, iar valoarea acestuia este cuprinsă în intervalul (0,1) și este setată de către noi.

Furnica curentă situată în nodul sursa (nodul i) va decide următoarea mutare (nodul destinație j) în mod probalistic, în funcție de valoarea parametrului ij .

Furnicile pornesc fiecare dintr-un nod al grafului, trec simultan prin diferite stări, iar când au terminat de construit de constituit o soluție (au ajuns la destinație) spunem că a trecut o generație.

Furnicile artificiale au suferit câteva îmbunătățiri față de furnicile reale. Ele în loc de memorie poseda o listă tabu care conține toți pașii parcurși (stări, noduri) până în momentul curent. Această listă este folosită de către furnicile artificiale pentru a găsi drumul înapoi de la sursa de hrană la mușuroi, dar și pentru a evita trecerea furnicilor în stări în care au mai fost (evită vizitarea de mai multe ori a aceluiași nod). În plus se mai utilizează o funcție euristică ij

care se refera la arcul (i, j), și care în mod normal se calculează după formula:

i j= (2)

Tabela de rutare de care dispune colonia de furnici se construiește treptat după formula:

, (3)

unde și sunt parametrii utilizați în controlul raportului importanței dintre urmele de feromoni și valorile euristice.

Dacă = 0 avem caz de exploatare (algoritm Greedy).

Dacă = 0 avem explorare , ceea ce inseamna ca intensitatea feromonului va fi singurul factor de decizie.

Probabilitatea ca o furnica din nodul i sa aleaga nodul j se calculeaza dupa formula:

Pij , (4)

După ce au ajuns la nodul destinație, furnica artificială parcurge drumul înapoi spre nodul sursă și depune feromon pe fiecare arc care constituie Soluția proporțional cu calitatea soluției generate de aceasta.

ij ij + , tabuk (5)

2.3.3. Particularități ale algoritmului. Aplicabilități ACO

Există câteva variante derivate din ACO, fiecare având propriile particularități. Principalele variante de algoritmi bazate pe coloniile de furnici sunt:

Ant System – a fost primul algoritm din familia ACO introdus de către Marco Dorigo ; principala caracteristică a acestui algoritm este că valorile feromonilor sunt actualizate de către toate furnicile care au terminat turul.

Ant Colony System – prima îmbunătățire majoră a algoritmului Ant System, îl are ca autor pe același Marco Dorigo ; algoritmul utilizează și o ajustare locală a concentrației de feromoni aplicată de fiecare dacă când este vizitat un arc.

Max-Min Ant System – Este o variantă îmbunătățită și diferită față de Ant System propusă de către cercetătorii Stutzle și Hoos ; concentrația de feromoni corespunzătoare fiecărui arc în parte este limitată de valori cuprinse într-un interval, iar la sfârșitul fiecărei iterații se modifica concentrația de feromoni doar pentru arcele care compun cel mai bun traseu.

Problema comisului voiajor reprezinta una dintre cele mai cunoscute problem de optimizare combinatoriala. Enuntul problemei suna astfel: “Se considera o multime O de orase, iar un comis voiajor care trebuie sa viziteze toate orasele, trecand doar o data prin fiecare oras, și să se întoarcă în orașul inițial, folosind cea mai scurtă ruta.

Din punct de vedere matematic, problema se reduce la stabilirea unui circuit Hamiltonian de cost minim într-un graf complet.

Algoritmul de optimizare folosind colonii de furnici se aplică cu succes asupra problemei comisului voiajor, de fapt, aceasta a fost motivația inițială a cercetătorilor. Pornind de la nodul inițial, fiecare furnică se mută iterative de la un nod la altul; furnica decide să viziteze un nod nevizitat la momentul de timp “t” cu o probabilitate dată de formula (3) la care îi adaugăm ca parametru suplimentar timpul “t”.

Pentru un număr mic de noduri, problema poate fi rezolvată exact, însă pentru un număr ridicat de noduri, nu există metode exacte eficiente. Problema comisului voiajor face parte din categoria problemelor NP-complete, ceea ce înseamnă că pentru dimensiuni, rezolvarea problemei necesită o metodă euristică.

Alte probleme care pot fi rezolvate cu ACO :

Problem de rutare în rețelele de telecomunicații

Probleme de stabilire a rutelor pentru vehicule

Probleme de planificare a taskurilor