47327396 inteligenta artificiala viata artificiala
DESCRIPTION
asxcvTRANSCRIPT
![Page 1: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/1.jpg)
Inteligenţă artificială
14. Viaţa artificială Florin Leon
Universitatea Tehnică „Gh. Asachi” Iaşi Facultatea de Automatică şi Calculatoare
http://florinleon.byethost24.com/curs_ia.htm
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 2: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/2.jpg)
2
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 3: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/3.jpg)
3
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 4: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/4.jpg)
4
Termenul “ALife”
Propus la un workshop organizat de Los Alamos National Laboratory, 1987
Domeniul încearcă să îmbine cercetările multidisciplinare cu privire la modelările şi simulările biologice
Aceste fenomene sunt neliniare, ceea ce poate conduce la: Haos: schimbări mici în condiţiile iniţiale produc
diferenţe mari la rezultate
Trăsături de nivel superior: emergenţă, atractori
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 5: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/5.jpg)
5
Caracteristicile simulărilor ALife
Abordare bottom-up
Control local
Reguli simple de acţiune
Modele multi-agent
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 6: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/6.jpg)
6
Viaţa naturală şi viaţa artificială
Dicţionarul Webster:
Viaţa este condiţia generală care distinge organismele de elementele anorganice şi de organismele moarte, manifestată prin:
creştere pe baza metabolismului
mijloace de reproducere
reglaj intern ca răspuns la mediu
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 7: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/7.jpg)
7
Scopurile vieţii artificiale
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 8: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/8.jpg)
8
VA şi IA
Viaţa artificială este pentru biologie ceea ce inteligenţa artificială este pentru psihologie
Simulările bazate pe agenţi sunt interesante şi pentru sociologie şi psihologie socială
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 9: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/9.jpg)
9
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 10: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/10.jpg)
10
Sisteme complexe
Sunt sisteme dinamice alcătuite din componente similare, cu o structură relativ simplă
Componentele interacţionează după reguli locale, de asemenea simple (uşor de înţeles)
Comportamentul global al unui astfel de sistem este emergent
Nu poate fi estimat apriori pe baza regulilor locale şi nu poate fi explicat uşor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 11: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/11.jpg)
11
Automate celulare
engl. “cellular automata”
Mediul este o latice, o mulţime discretă de celule alăturate
Timpul este de asemenea discret
Celulele au o serie de proprietăţi care se pot modifica în timp (au stare)
Starea unei celule la momentul t+1 depinde de starea proprie şi de starea altor celule vecine la momentul t
Actualizările stărilor se fac în paralel
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 12: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/12.jpg)
12
Exemplu
Automat celular unidimensional
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 13: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/13.jpg)
13
Exemplu
Automat celular bidimensional
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 14: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/14.jpg)
14
Tipuri de mediu
infinit
limite fixe, cu stări predefinite
limite reflective, influenţează numai celulele „interioare”
periodic
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 15: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/15.jpg)
15
Exemplu
XOR
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 16: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/16.jpg)
16
Rezultate
Configuraţie simetrică, 128 de paşi
Configuraţie iniţială aleatorie, apar totuşi modele în evoluţie
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 17: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/17.jpg)
17
Jocul vieţii
engl. “Game of Life”, Conway (1970)
Automat celular bidimensional
Fie n numărul de vecini vii ai unei celule
Reguli:
Dacă n < 2, celula moare de singurătate
Dacă n > 3, celula moare de supra-aglomerare
Dacă n = 3, celula renaşte (se naşte o nouă celulă)
Altfel, celula îşi păstrează starea anterioară
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 18: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/18.jpg)
18
Modele emergente
Modele statice
Modele oscilante
Modele glisante
Modele de dezvoltare
Modele instabile (neperiodice)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 19: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/19.jpg)
19
http://florinleon.byethost24.com/home/prog_jt.htm
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 20: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/20.jpg)
20
Proprietatea de calcul universal
Capacitatea de a putea calcula tot ce poate fi calculat Maşina Turing
Automatele celulare Memorie: modelele statice
Numărătoare: modelele oscilante
Flux de informaţii: modelele glisante
Nu se poate spune dacă o anumită configuraţie va genera în timp configuraţia nulă sau va evolua într-o configuraţie stabilă sau periodică Problema opririi la Maşina Turing: nu se poate prezice dacă
pentru o anumită intrare, un algoritm se va termina sau va rula la infinit
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 21: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/21.jpg)
21
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 22: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/22.jpg)
22
Sisteme Lindenmeyer
engl. “Lindenmeyer systems”, “L-systems”
Propus iniţial ca formalism matematic pentru modelarea creşterii plantelor (Aristid Lindenmeyer, biolog, 1968)
Sistem de producţie
+ roteşte dreapta
- roteşte stânga
[ salvează poziţia şi unghiul
] reface poziţia şi unghiul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 23: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/23.jpg)
23 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 24: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/24.jpg)
24
LOGO
“Turtle graphics”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 25: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/25.jpg)
25
Exemple
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 26: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/26.jpg)
26
Exemple
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 27: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/27.jpg)
27
Modele 3D
mentă traista ciobanului
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 28: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/28.jpg)
28
Fractali
Structuri auto-similare la scări multiple
O porţiune mică dintr-un fractal arată la fel ca întregul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 29: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/29.jpg)
29
Exemple
Ferigă fractală Model al sistemului vascular
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 30: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/30.jpg)
30
http://florinleon.byethost24.com/home/prog_gf.htm
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 31: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/31.jpg)
31
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 32: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/32.jpg)
32
Albinele: căutarea hranei
Colectarea hranei depinde de timpul de aşteptare la livrarea hranei în stup
Dacă stupul are deja multă hrană, albinele care o depozitează au nevoie de mai mult timp pentru a găsi celule goale
Timpul de aşteptare mai mare determină albinele colectoare să caute hrană de calitate mai bună, mai greu de găsit şi care necesită deci mai mult timp
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 33: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/33.jpg)
33
Viespile: diferenţierea rolurilor
Organizarea: un singur şef, un grup de căutători de hrană şi un grup de îngrijitori ai larvelor
Toate rolurile sunt ocupate de viespi identice din punct de vedere genetic
Fiecare viespe are doi parametri:
Forţă – determină mobilitatea
Pragul de căutare – probabilitatea de a merge să caute hrană (prag mai mic ⇒ probabilitate mai mare)
Larvele au un parametru Cerere, care stimulează căutătorii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 34: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/34.jpg)
34
Viespile: diferenţierea rolurilor
Când 2 viespi se întâlnesc, are loc o confruntare, cu probabilitatea de succes:
Când larvele primesc hrană, Cererea scade
Căutarea hranei scade Cererea şi deci şi stimularea de a căuta hrană
Şeful se plimbă prin cuib şi confruntă alte viespi, astfel încât echilibrează variabilele din cadrul populaţiei
Auto-organizare prin interacţiuni repetate:
Căutători: Forţă mare şi Prag de căutare mic
Îngrijitori: Forţă mică şi Prag de căutare mare
Şef: Forţă mare şi Prag de căutare mare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 35: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/35.jpg)
35
Termite: construirea muşuroiului
Termitele depun resturi de metabolizare, care conţin feromoni
Alte termite vor depune resturi lângă grămezile cu feromoni mai puternici
Concentraţia de feromoni scade în timp
La început apar depozite distribuite aleatoriu
Apoi apar coloane
Coloanele se unesc prin arce
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 36: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/36.jpg)
36
Furnicile: sortarea
Furnicile au tendinţa să grupeze hrana, larvele Dacă se distribuie conţinutul unui muşuroi pe o suprafaţă
plană, lucrătoarele încep să sorteze hrana şi larvele
Reguli: Furnicile văd numai obiectele apropiate din faţă
Dacă un obiect este departe de altele, probabilitatea de a fi ridicat este mare; dacă sunt prezente şi alte obiecte, probabilitatea este mică
Probabilitatea de a pune jos un obiect creşte dacă în apropiere sunt şi alte obiecte similare
f este fracţiunea de obiecte similare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 37: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/37.jpg)
37
Rezultate timp
simulare furnici reale
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 38: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/38.jpg)
38
Cooperarea
Comportamentul cooperant al speciilor mai evoluate poate fi simulat ca o trăsătură emergentă a interacţiunilor individuale
Strategia unui individ de a da înapoi atât cât a primit de la altul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 39: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/39.jpg)
39
Optimizarea rutei
Stigmergie
O formă de comunicare indirectă prin modificarea mediului
Urme de feromoni
Probabilitatea de a alege o rută depinde de concentraţia de feromoni
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 40: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/40.jpg)
40
Ant-Based Control
Hewlett-Packard, British Telecom: aplicarea ideii pentru echilibrarea încărcării şi rutarea mesajelor în reţele de telecomunicaţii
Se creează în continuu agenţi / furnici în fiecare nod şi li se atribuie destinaţii aleatorii
Urmele de feromoni contribuie la actualizarea tabelelor de rutare
Probabilităţile de alegere a unui nod vecin
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 41: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/41.jpg)
41
Ant-Based Control
pentru nodul de unde a venit furnica
pentru celelalte intrări
furnicile îmbătrânesc şi depun mai puţini feromoni Δp scade în timp
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 42: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/42.jpg)
42
Ant Colony Optimization
„Optimizarea de tip colonie de furnici”
Metodă probabilistică pentru rezolvarea unor probleme care pot fi reduse la găsirea unor căi în grafuri
Caracteristici:
Mulţime de indivizi cooperanţi
Comunicare prin stigmergie
Indivizii descoperă calea de la starea iniţială la starea finală (soluţia problemei)
Deciziile sunt locale şi stohastice
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 43: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/43.jpg)
Parcurgerea grafului
Iniţial, m furnici sunt plasate aleatoriu în m noduri
În fiecare iteraţie t, fiecare furnică k se mută din nodul i în nodul j, reprezentând o soluţie intermediară mai completă
Alegerea este stohastică, pe baza nivelului de feromoni τij al arcului (i,j) şi a atractivităţii ηij a arcului
43 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 44: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/44.jpg)
Selecţia unui arc
ηij este în general o funcţie de lungimea arcului, de obicei ηij = 1 / dij
α ≥ 0, β ≥ 1
Nik este o vecinătate fezabilă a furnicii k,
adică mulţimea nodurilor nevizitate încă
44 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 45: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/45.jpg)
Actualizarea feromonilor
ρ este persistenţa urmei de feromoni iar (1 – ρ) este rata de evaporare, 0 ≤ ρ < 1
este cantitatea de feromoni depozitată de furnica k pe arcele traversate
Lk(t) este lungimea turului furnicii k
45
dacă arcul (i,j) este traversat de furnica k în iteraţia t
altfel
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 46: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/46.jpg)
46
Probleme tipice
Problema comis-voiajorului
Atribuirea cuadratică
“Job-shop scheduling”
Rutarea vehiculelor
Cea mai scurtă supersecvenţă comună
Colorarea grafurilor
Ordonarea secvenţială
Reţele de comunicaţii Pentru explicaţii, vezi suportul de curs
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 47: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/47.jpg)
47
Boids
Simulează un stol de păsări (Reynolds, 1987)
Reguli:
Apropierea de centrul de greutate al vecinilor
Evitarea coliziunilor cu vecinii
Potrivirea vitezei cu aceea a vecinilor
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 48: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/48.jpg)
48
Pseudocod
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 49: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/49.jpg)
49
Regula 1: Apropierea
se mută 1% înspre centru
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 50: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/50.jpg)
50
Regula 2: Evitarea coliziunilor
se dublează distanţa dintre 2 boids, separare lină
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 51: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/51.jpg)
51
Regula 3: Potrivirea vitezei
se adaugă o fracţie
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 52: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/52.jpg)
52
Comportament
Comportamentul de „stol” este emergent
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 53: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/53.jpg)
53
Particle Swarm Optimization
„Optimizarea de tip roi de particule”
Metodă de optimizare bazată pe indivizi care imită comportamentul stolurilor de păsări sau roiurilor de insecte (Kennedy & Eberhart, 1995)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 54: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/54.jpg)
54
Algoritmul PSO
Fiecare particulă are:
xi: poziţia curentă
vi: viteza curentă
yi: poziţia personală cea mai bună
y^i: poziţia cea mai bună a vecinătăţii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 55: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/55.jpg)
55
Iniţializarea
Pentru fiecare particulă, se iniţializează aleatoriu poziţiile xi şi vitezele vi
Iniţial, vitezele pot fi setate la 0
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 56: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/56.jpg)
56
Ajustările (I)
Se evaluează funcţia obiectiv a particulei, f(xi)
Se actualizează optimul personal
Problemă de minimizare
Se calculează optimul social (al vecinătăţii)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 57: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/57.jpg)
57
Ajustările (II)
Pentru fiecare dimensiune, se actualizează viteza
Se actualizează poziţia curentă
Se repetă paşii până este satisfăcut un criteriu de convergenţă
ponderea inerţiei componenta cognitivă componenta socială c1,2 - constante de acceleraţie r1,2 - numere aleatorii în (0,1)
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 58: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/58.jpg)
58
Variante
Varianta prezentată este globală: gbest
În varianta locală, lbest, se consideră mai multe vecinătăţi posibil suprapuse
Vecinătatea poate fi definită de indicii particulelor sau de poziţiile lor
y^i se calculează pentru fiecare vecinătate
Abordarea lbest conduce la o diversitate mai mare, dar este mai lentă decât abordarea gbest
Criterii de convergenţă
Număr maxim de iteraţii
Actualizări ale vitezelor apropiate de 0
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 59: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/59.jpg)
59
Parametrii
Ponderea inerţiei w defineşte compromisul între explorare şi exploatare
O valoare mai mică scade viteza particulelor mai multă exploatare
O valoare mai mare creşte viteza particulelor mai multă explorare
Pentru a asigura convergenţa algoritmului:
Viteza poate fi limitată la un Vmax
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 60: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/60.jpg)
60
PSO şi AE
Asemănări şi deosebiri între Particle Swarm Optimization şi Algoritmii evolutivi:
Indivizii din PSO au funcţii obiectiv
Ajustările sunt asemănătoare cu încrucişările
PSO este inspirat de comportamentul social, nu de selecţia naturală
Indivizii din PSO au „memorie”
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 61: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/61.jpg)
61
Avantaje
PSO este un algoritm continuu, AE pot fi discreţi
PSO este mai bun decât AE pentru unele probleme continue de optimizare şi în special pentru probleme de dimensiuni mari
Performanţele PSO nu depind de numărul de particule; trebuie doar să nu fie prea mic
PSO cu un număr redus de particule are performanţe comparabile cu AE cu populaţii mai mari
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 62: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/62.jpg)
62
Dezavantaje
Convergenţa prematură
PSO găseşte soluţiile mai rapid decât algoritmii evolutivi, dar de obicei soluţia nu se mai îmbunătăţeşte în timp
O particulă converge la un punct dintre optimul personal şi optimul social; acest punct poate să nu fie nici măcar optim local al problemei
Performanţele depind de problemă
Parametrii trebuie aleşi pentru fiecare problemă în parte
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 63: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/63.jpg)
63
Viaţa artificială
1. Introducere
2. Automate celulare
3. Sisteme Lindenmeyer
4. Inteligenţa colectivă
5. Simulări bazate pe agenţi
6. Concluzii
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 64: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/64.jpg)
64
Modelul Sugarscape
Mediul are cantităţi variabile de zahăr
Agenţii au metabolism şi consumă zahăr
La fiecare mişcare, agenţii consumă o cantitate de zahăr; când consumă tot zahărul, mor
Agenţii pot privi în direcţii paralele cu axele, dar nu în diagonală
Agenţii merg în celula cu cea mai mare cantitate de zahăr din câmpul lor vizual (la egalitate, cea mai apropiată celulă) şi o consumă
Agenţii pot depozita zahărul neconsumat
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 65: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/65.jpg)
65
Modelul Sugarscape
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 66: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/66.jpg)
66
Sugarscape, G∞
zahărul consumat se regenerează complet
într-un pas
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 67: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/67.jpg)
67
Sugarscape, G1
zahărul consumat se regenerează cu o unitate
la fiecare pas
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 68: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/68.jpg)
68
Evoluţia populaţiei
Populaţia se stabilizează la un număr de agenţi care pot fi hrăniţi de mediu
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 69: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/69.jpg)
69
Distribuţia „averii”
O mică parte din agenţi au cea mai mare parte din cantitatea de zahăr
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 70: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/70.jpg)
70
Diagonale de migraţie emergente
Agenţii individuali nu se pot mişca pe diagonală
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 71: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/71.jpg)
71
Economia: zahăr şi mirodenii
MRS = rata de substituţie marginală
preţul local
w – acumularea t – metabolismul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 72: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/72.jpg)
72
Modelul segregării al lui Schelling
Este un exemplu de comportament emergent puternic, care arată că într-o societate pot exista fenomene segregaţioniste evidente chiar dacă indivizii nu sunt neapărat foarte segregaţionişti
În model există agenţi de 2 culori
Fiecare agent este mulţumit dacă are n vecini de aceeaşi culoare
Dacă nu este mulţumit se mută aleatoriu în altă celulă
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 73: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/73.jpg)
73
Comunitatea lui Schelling
n=2
n=1
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 74: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/74.jpg)
74
Comunitatea lui Schelling
În primul caz, fiecare agent ar fi mulţumit dacă ar avea 2 vecini de aceeaşi culoare şi 2 vecini de altă culoare
La echilibru ar fi stabilă o situaţie ca aceea de mai jos
Apare totuşi un fenomen de segregare involuntar
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 75: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/75.jpg)
75
Modelul lui Hammond
Este un model al corupţiei sociale
Societatea are cetăţeni şi birocraţi, care pot fi corupţi (C) sau oneşti (O)
Interacţiuni posibile C + C recompensă pozitivă
C + O denunţ
O + O recompensă nulă
După un număr (necunoscut) de denunţuri, un corupt este arestat
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 76: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/76.jpg)
76
Modelul lui Hammond
Galben: corupţi
Albastru: oneşti
Roşu: arestaţi
Un agent ştie ce i se întâmplă lui şi prietenilor lui
Dacă mai mulţi prieteni sunt arestaţi, agentul va deveni mai cinstit
Presiunea socială (frica) determină creşterea numărului de indivizi oneşti
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 77: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/77.jpg)
77
Modelul lui Hammond
Dacă numărul de agenţi arestaţi este necunoscut, frica îi determină să devină oneşti
Când numărul arestaţilor din întreaga societate este cunoscut, presiunea nu mai este suficientă pentru a-şi schimba comportamentul
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 78: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/78.jpg)
78
Modelul lui Epstein
Coexistenţă paşnică
Genocid artificial
Când tensiunea socială depăşeşte un prag, un agent omoară alt agent de altă culoare
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 79: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/79.jpg)
79
SWARM: Heatbugs
Fiecare „gândac” generează o cantitate mică de căldură
Gândacii sunt mai fericiţi când au mai multă căldură
Rezultatul este gruparea acestora pentru a avea mai multă căldură împreună
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 80: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/80.jpg)
80
SWARM: Mousetrap
Model al fisiunii nucleare
Fiecare cursă de şoareci conţine două mingi de ping-pong
La început se aruncă o minge de ping-pong în mijlocul curselor
O cursă se închide şi aruncă cele două mingi la rândul ei, care determină închiderea altor curse
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 81: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/81.jpg)
81
Mousetrap Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 82: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/82.jpg)
NetLogo: Etnocentrism (Axelrod & Hammond)
82 Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 83: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/83.jpg)
83
Framsticks: creaturi evoluate artificial
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 84: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/84.jpg)
84
Framsticks
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 85: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/85.jpg)
85
Framsticks
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm
![Page 86: 47327396 Inteligenta Artificiala Viata Artificiala](https://reader031.vdocumente.com/reader031/viewer/2022012314/54860acdb4af9f780d8b4f6a/html5/thumbnails/86.jpg)
86
Concluzii
Viaţa artificială este un domeniu interdisciplinar care implică biologia, psihologia, ştiinţele cognitive şi matematica
Dezvoltarea de modele în biologia sintetică îşi găseşte aplicabilitatea în biomedicină, unde standardizarea componentelor biologice sintetizate şi formalizarea metodologiilor rămâne o problemă nerezolvată
Florin Leon, Inteligenta artificiala, http://florinleon.byethost24.com/curs_ia.htm