Algoritmi metaeuristici - curs 7 1
Alte metaeuristici inspirate de natură
§ Swarm Intelligence – comportamentul inteligent al mulțimilor (inteligența roiurilor)
§ ACO - Ant Colony Optimization - Modelul coloniei de furnici
§ PSO - Particle Swarm Optimization - Modelul ansamblului de particule (sau a stolului de păsări)
§ ABC - Artificial Bee Optimization – Modelul roiului de albine
Algoritmi metaeuristici - curs 7 2
Swarm intelligence (inteligență colectivă)
• Swarm intelligence = domeniu care cuprinde tehnici inteligente bazate pe comportamentul colectiv al unor sisteme cu auto-organizare și fără control centralizat
• Termen introdus în 1989 de Gerardo Beni si Jing Wang in contextul sistemelor de roboți
• Tehnicile din “swarm intelligence” se bazează pe mulțimi de agenți caracterizati prin:
– Reguli simple de “funcționare”– Interacțiuni locale – Absența unor structuri de control centralizat
Algoritmi metaeuristici - curs 7 3
Swarm intelligence (inteligență colectivă)
• Exemple de sisteme naturale având astfel de caracteristici:
– Colonii de furnici– Roiuri de albine– Stoluri de păsări– Bancuri de pești
• Reprezintă modele pentru tehnici de rezolvare a unor probleme de optimizare sau de analiză a datelor
Imagini de la http://www.scs.carleton.ca/~arpwhite/courses/95590Y/notes/SI%20Lecture%203.pdf
Algoritmi metaeuristici - curs 7 4
Modelul coloniei de furniciSursa de inspirație: comportarea furnicilor în procesele de • Căutare a hranei -> rezolvarea unei probleme de optimizare:
identificarea drumului optim între sursa de hrană și cuib
• Organizare a coloniei -> rezolvarea unei probleme de grupare a datelor: separarea hranei de corpurile furnicilor moarte sau a larvelor după dimensiuni sau segregarea furnicilor aparținând unor specii diferite
Elemente cheie:• Comunicare indirectă prin intermediul unor substanțe chimice numite
feromoni; acest proces de comunicare este denumit stigmergie
• Stabilirea similarității dintre furnici pe baza mirosului (o furnică recunoaște dacă o altă furnică face parte din același cuib sau nu)
Algoritmi metaeuristici - curs 7 5
Modelul coloniei de furniciRolul feromonilor: experimentul podului dublu [Deneubourg, 1990]Specia de furnici analizată: Argentine
- Două căi de acces între cuib și sursa de hrană
- Inițial furnicile aleg la întâmplare una dintre căi
- La fiecare parcurgere a drumului furnicile depun feromoni
- Drumul mai scurt este parcurs de mai multe ori așa că va acumula o cantitate mai mare de feromoni
Algoritmi metaeuristici - curs 7 6
Modelul coloniei de furniciRolul feromonilor: experimentul podului dublu
- Dacă există diferență între cantitatea de feromoni depusă pe cele două trasee, furnicile vor prefera traseul marcat mai intens
- Treptat din ce în ce mai multe furnici vor alege traseul cu mai mulți feromoni contribuind și mai mult la sporirea cantității de feromoni (feedback pozitiv)
Algoritmi metaeuristici - curs 7 7
Modelul coloniei de furniciRolul feromonilor: experimentul podului dublu
- Cantitatea de feromon nu crește permanent ci poate și să scadă ca efect al unui proces de evaporare
- Procesul de evaporare este util în cazul aparițiilor unor schimbări în mediu
Ilustrare: http://www.nightlab.ch/downloads.php
Algoritmi metaeuristici - curs 7 8
Modelul coloniei de furniciRezolvarea unei probleme de optimizare – Ant Colony Optimization
Idee: soluția problemei este identificată folosind o mulțime de furnici artificiale (agenți) care schimbă informații privind calitatea soluției
Exemplu: problema comis-voiajorului
Intrare: graf etichetat corespunzator conexiunilor dintre orașe și costurilor corespunzătoare parcurgerii unei comexiuni
Ieșire: o ordine de parcurgere a orașelor caracterizată prin cost total minim
Algoritmi metaeuristici - curs 7 9
Modelul coloniei de furniciACO pentru problema comis voiajorului:
- Se utilizează o populație de furnici care sunt implicate într-un proces iterativ
- La fiecare iterație fiecare furnică parcurge câte un traseu în graful asociat problemei. La parcurgerea traseului furnicile respectă următoarele reguli:- Nu trec de două ori prin același nod - Decizia de a alege o muchie este aleatoare, iar probabilitatea de
selecție depinde atât de costul muchiei cât și de cantitatea de feromon asociată muchiei
- După construirea traseelor se actualizează cantitatea de feromoni corespunzătoare muchiilor astfel încât muchiilor ce fac parte din trasee de cost mic să li se asocieze o cantitate mai mare de feromoni.
Algoritmi metaeuristici - curs 7 10
Modelul coloniei de furniciStructura generală a algoritmului
Notații: tmax = număr iterații; a=număr agenți (furnici); ip = indice nodP = probabilitate de tranziție, L = cost traseu, tau = concentrație
feromoni
Algoritmi metaeuristici - curs 7 11
Modelul coloniei de furniciVariante:
Obs: variantele diferă între ele în principal prin modul de calcul al probabilității de tranziție și regula de actualizare a concentrației de feromoni
Algoritmi metaeuristici - curs 7 12
Modelul coloniei de furniciParticularități ale variantei inițiale (Ant Systems)Problema comis voiajoruluiReprezentarea soluției: (i1,i2,…,in) permutare a mulțimii de indici ai
orașelorProbabilități de tranziție (furnica k trece la momentul t de la orașul i la orașul j)
Lista oraselor nevizitate încă defurnica k și care sunt conectate cu orasul i
Concentrația de feromon corespunzătoare arcului (i,l) Factor invers proporțional
cu costul arcului (i,l)
Algoritmi metaeuristici - curs 7 13
Modelul coloniei de furniciVarianta tradițională pt TSP (AS - Ant Systems)
Actualizarea concentrației de feromoni(la sfârșitul fiecărei iterații)
altfel0
j)(i, parcurgek furnica daca
)()1()1(1
kkij
m
k
kijijij
LQ
tt
Notatii:ρ = rată de evaporareQ>0 = constantăLk = cost al ultimului traseu parcurs de furnica k
Varianta:
Concentrația de feromoni se actualizează utilizând doar informațiile corespunzătoare celui mai bun traseu:
altfel0
j)(i, contine daca
)()1()1(
**
*
T*LQ
tt
ij
ijijij
Algoritmi metaeuristici - curs 7 14
Modelul coloniei de furniciParticularități ale altor variante:
Max-Min Ant System (MMAS):- concentrația de feromoni corespunzătoare fiecărui arc este limitată la valori cuprinse într-un interval
- la sfârșitul fiecărei iterații se modifică concentrația de feromoni doar pentru arcele corespunzătoare celui mai bun traseu
Ant Colony System (ACS) - utilizează și o ajustare locală a concentrației de feromoni aplicată
ori de câte ori este vizitat un arc (pe lângă ajustarea globală similară cu cea ce la variantă Max-Min):
valoarea initiala a concentratiei
Algoritmi metaeuristici - curs 7 15
Modelul coloniei de furniciExemple de aplicatii
Algoritmi metaeuristici - curs 7 16
Modelul coloniei de furniciAplicații în probleme reale:
- Probleme de rutare în rețele de telecomunicații (optimizare în medii dinamice)
- Probleme de stabilire a rutelor pentru vehicule- Probleme de planificare a task-urilor
Companii care au aplicat ACO în rezolvarea problemelor:
www.eurobios.com (routing/schedule of airplane flights, supply chain networks)
www.antoptima.com (vehicle routing)
Algoritmi metaeuristici - curs 7 17
Modelul coloniei de furniciUtilizare în gruparea datelor.
Folosește ca sursă de inspirație
- procesul prin care furnicile separă larvele după dimensiuni sau furnicile moarte (Lumer &Faieta, 1994)
- Modul în care furnicile identifică furnicile aparținând altei specii care pătrund în cuibul lor (AntClust – Labroche, 2002)
Algoritmi metaeuristici - curs 7 18
Modelul coloniei de furniciAntClust – algoritm pentru gruparea datelor [Labroche, 2002]
Colonia de furniciq Furnicaq Cuib (furnici de acelasi tip)q Tip de mirosq Intalnirea a doua furniciq Crearea unui cuibq Migrarea furnicilor intre cuiburiq Eliminarea unei furnici din cuib
Proces de grupare a datelorq Dataq Cluster (clasa de date similare)q Prag de similaritateq Compararea a doua dateq Initierea unui clusterq Transfer de date de la un cluster la altul q Eliminarea unei date dintr-un cluster
Algoritmi metaeuristici - curs 7 19
Modelul coloniei de furniciq Pentru gruparea a n date sunt folosite n furnici fiecare caracterizată prin:
qO dată asociată, xqO etichetă corespunzătoare clusterului, LqUn prag de similaritate, TqUn contor al întâlnirilor cu alte furnici, AqO măsură a dimensiunii cuibului (percepția proprie), MqO măsură a gradului de acceptare de către celelalte furnici, M+
q Structura algoritmului AntClustq Faza de învățare a pragului de similaritateq Faza întâlnirilor q Faza de rafinare a clusterilor
Algoritmi metaeuristici - curs 7 20
Modelul coloniei de furniciq Faza de învățare a pragului:
q Pt fiecare furnică, pragul T se calculează pe baza similarității medii și a celei maxime cu celelalte date
2)),((avg)),((max jiSjiS
T jji
n
kkk
kj
ki
xxxx
njiS
1 minmax||
11),(
Arii de similaritate
Date
Algoritmi metaeuristici - curs 7 21
Modelul coloniei de furniciq Faza întâlnirilor aleatoare:
q Se selectează aleator kM perechi de furniciq Când furnica i întâlnește furnica j, se
calculeaza similaritatea S(i,j) și se analizează:
If S(i,j)>Ti and S(i,j)>Tj then furnicile se accepta reciproc altfel se resping
q Se aplică un set de reguli pe baza cărora se modifică eticheta furnicii și valorile mărimilor care exprimă percepția furnicii în privința cuibului din care face parte
Situatie de respingere
Situatie de acceptare
Algoritmi metaeuristici - curs 7 22
Modelul coloniei de furniciq Reguli de acceptare:
Regula 1:Daca se intalnesc doua furnici
neetichetate ele vor forma un nou cuib
Regula 2:Daca o furnica neetichetata
intalneste una etichetata atunci este inclusa in acelasi cuib
Regula 2
Regula 1
Algoritmi metaeuristici - curs 7 23
Modelul coloniei de furniciq Reguli de acceptare:
Regula 3:La întâlnirea a două furnici din același cuib se
incrementează parametrii M și M+
Regula 5:La întâlnirea a două furnici din cuiburi diferite
furnica având M mai mic este atrasă în celălalt cuib iar parametrii M ai ambilor furnici sunt decrementați.
vv )1()(inc
vv )1()(dec
Incrementare
Decrementare
)1,0(parametru
M si M+ apartin lui [0,1)
Algoritmi metaeuristici - curs 7 24
Modelul coloniei de furniciq Regula de respingere:
Regula 4:
Dacă se întâlnesc două furnici din același cuib care se resping atunci:
q Furnica cu valoare mai mica pentru M+ este eliminată din cuib iar parametrii săi sunt resetați
q parametrul M al celeilalte furnici este mărit iar parametrul M+ este micșorat
Algoritmi metaeuristici - curs 7 25
Modelul coloniei de furniciq Structura algoritmului
Algoritmi metaeuristici - curs 7 26
Modelul coloniei de furnici
q Exemplu
-4 -2 0 2 4
-4
-2
0
2
4
-4 -2 0 2 4
-4
-2
0
2
4
AntClust KMeans
Algoritmi metaeuristici - curs 7 27
Modelul ansamblului de particule
q Tehnica Particle Swarm Optimization (PSO) a fost propusă de către James Kennedy şi Russell Eberhart pentru optimizarea funcţiilor neliniare (1995)
q Sursa de inspirație:
q comportarea stolurilor de păsări, bancurilor de pești, roiurilor de albineq acestea sunt asimilate unui ansamblu de particule care se deplasează
în spațiul de căutare pentru a identifica optimul
q Biblio: http://www.particleswarm.info/
Algoritmi metaeuristici - curs 7 28
Modelul ansamblului de particuleIdee:q Se folosește un ansamblu de particule
(elemente) a căror poziții sunt din domeniul funcției obiectiv și care sunt modificate printr-un proces iterativ
q La fiecare iterație se stabilește noua poziție a fiecărei particule în funcție de:q Poziția curentă a particuleiq Cea mai bună pozitie întâlnită de către
particulă (local best)q Cea mai buna poziție întâlnită de către
ansamblu (global best)
Structura generală:
Inițializare poziții particuleInițializare deplasamente inițialeREPEAT calcul deplasamente (viteze) actualizare poziții evaluare actualizare lista cu cele mai bune
elemente UNTIL
Ilustrare: http://www.projectcomputing.com/resources/psovis/index.html
Obs: nu se folosește selecție ci doar mutație direcționată (înspre cele mai bune elemente ale populației
Algoritmi metaeuristici - curs 7 29
Modelul ansamblului de particuleq Regula de ajustare a poziției particulelor se bazează pe două etape:
q Ajustare deplasamente (viteze)q Aplicarea deplasamentelor
)()()1())()()(())()()(()()1( 11
tvtxtxtxtptrctxtptrctvtv
ji
ji
ji
ji
jbest
ji
ji
ji
ji
Algoritmi metaeuristici - curs 7 30
Modelul ansamblului de particuleq Regula de ajustare a poziției particulelor
Componenta j a poziției particulei i la momentul t
Componenta j a “vitezei” particulei i la momentul (t+1)
Cea mai bună poziție a particulei i
Cea mai bună poziție a ansamblului de particule
Valori aleatoare din (0,1)
)()()1())()()(())()()(()()1( 2211
tvtxtxtxtptrctxtptrctvtv
ji
ji
ji
ji
jbest
ji
ji
ji
ji
Algoritmi metaeuristici - curs 7 31
Modelul ansamblului de particuleq Variante
q Introducerea unui factor de inerție (b) și a unui factor constrictiv pentru a limita creșterea vitezei (a)
q Utilizarea vecinătăților pentru calculul celui mai bun element (pbest se determină luând în considerare doar vecinii lui i). q Exemplu de topologie: circulară
)()()1()))()()(())()()(()(()1( 2211
tvtxtxtxtptrctxtptrctvbatv
ji
ji
ji
ji
jbest
ji
ji
ji
ji
Algoritmi metaeuristici - curs 7 32
Modelul roiului de albineq Artificial Bee Colony (ABC) [Karaboga, 2005]
http://mf.erciyes.edu.tr/abc/links.htm
q Sursa de inspirație: comportamentul inteligent al albinelor în procesul de identificare a surselor de hrană (nectar)
q Utilizează o populație de “albine” constituită din trei categorii:
q Albine “alocate” unei surse de hrană (lucrătoare)q Albine observatoareq Albine cercetașe
Algoritmi metaeuristici - curs 7 33
Modelul roiului de albineq Albine “lucratoare” (employed foragers)
q Sunt asociate unei surse de hrană (miere) pe care o exploatează q Posedă informație privind calitatea sursei de hrană (pe care o transmit și
unora dintre albinele observator)q Albine “observator” (onlookers):
q Colectează informații de la albinele lucrătoare și după ce identifică o sursă de hrană devin albine lucrătoare
q Albine “cercetaș” (scouters)q Explorează în mod aleator spațiul de căutare pentru a identifica noi surse
de hrană
Algoritmi metaeuristici - curs 7 34
Modelul roiului de albineq Pas 1: Se inițializează aleator locațiile din spațiul de căutare unde sunt
plasate albinele lucrătoareq Pas 2: Cât timp e satisfacută condiția de continuare se execută:
q Albinele lucrătoare transmit informații privind calitatea locației în care se află către albinele observator; fiecare albină observator selectează o locație; selecția se bazează pe o distribuție de probabilitate determinată de valorile scorurilor asociate;
q Albinele lucrătoare explorează vecinătatea locației în care se află și se mută într-o altă locație vecină dacă aceasta este mai bună; dacă o albină lucrătoare nu descoperă într-un număr limită de pași o configurație mai bună atunci ea este relocată într-o poziție determinată de o albină cercetaș
q Albinele cercetaș își schimbă aleator poziția
Algoritmi metaeuristici - curs 7 35
Modelul roiului de albine
NB
jj
ii
xf
xfxP
1)(
)()(
njtxtxtxv jkjiij
ji
ji ,1 )),()(()(
Detalii:q Notații: NB = număr de albine lucrătoare, NO = număr de albine observator, f = funcția scor, n = dimensiunea problemeiq Alegerea noii locații de către o albină observator se face prin selecție
proporțională folosind distribuția de probabilitate
q Modificarea pozitiei unei albine lucrătoare i se bazează pe:
ijunde k este indicele unei albine lucrătoare aleasă aleator, este un parametru aleator in [-1,1]
Algoritmi metaeuristici - curs 7 36
Modelul roiului de albine
Detalii:q Dacă configurația vi este mai bună decât xi(t) atunci xi(t+1) va fi vi, altfel
rămâne xi(t)
Observație. Intr-un algoritm ABC există mai multe tipuri de selecție:
• Selecție globală (bazată pe distribuția de probabilitate definită pe slide-ul anterior) folosită de catre albinele observator pentru a identifica regiuni promițătoare
• Selecție locală (bazată pe calculul și analiza unei configurații “vecine” vi) realizată atât de albinele lucrătoare cât și de către albinele observator
• Selecție aleatoare realizată de către albinele cercetaș care sunt relocate în poziții stabilite aleator
Algoritmi metaeuristici - curs 7 37
Modelul licuricilor
Firefly algorithm (Yang, 2008)Sursa de inspirație: interacțiunile dintre licurici bazate pe semnalele luminoase
pe care le emit
Idee principală de implementare• Fiecare element al populației corespunde poziției unui licurici• Fiecărui licurici îi este asociat un grad de luminozitate (corelat cu valoarea
funcției obiectiv asociate elementului corespunzător din populație)• Deplasarea licuricilor este ghidata atât de distanța dintre pozițiile lor cât și de
valoarea luminozității - Poziția xi este deplasată către poziția xj (dacă xj are luminozitatea mai mare)
folosind relația de mai jos (alpha, beta și gamma sunt parametri de control iar epsilon este o valoare aleatoare cu distribuție normală)
)())()()))((),((exp()()1( 2 ttxtxtxtxdtxtx iijjiii
Algoritmi metaeuristici - curs 7 38
Alte metode inspirate de natură
• Bat algorithm [X.S. Yang, 2010]• Cuckoo search [X.S. Yang, 2009]• Cat swarm algorithm [S.C. Chu, 2006]• Biogeography optimization [D. Simon, 2008,
http://embeddedlab.csuohio.edu/BBO/]• Krill herd optimization [Gandomi, 2012]• Monkey search [A. Mucherino, 2007]• Fruit-fly optimization algorithm [Pan, 2011]....
Observație – proliferarea metodelor bio-inspirate nu este neapărat benefică pentru dezvoltarea domeniului întrucât o parte dintre metode se bazează pe operatori similari, independent de metafora biologică
Sorensen, 2012: Metaheuristics: the Metaphor ExposedMichalewicz, 2012: Quo-Vadis Evolutionary Computing
Algoritmi metaeuristici - curs 7 39
In loc de concluzii