Mesterséges Intelligencia alapjai

Mesterséges Intelligencia alapjai Evolúciós algoritmusok - neurális hálózatok

Istenes Zoltán Eötvös Loránd Tudományegyetem Informatikai Kar Programozáselmélet és Szoftvertechnológiai Tanszék

2010 / Budapest

Istenes Zoltán (ELTE-IK-PSZT)

Mesterséges Intelligencia alapjai

2010

1 / 43

Genetikus - evolúciós algoritmusok

Genetikus - evolúciós algoritmusok...

kromoszóma reprezentáció költség (fitnessz) függvény kezdeti populáció kiválasztás (szelekció) reprodukció (keresztezés) mutáció leállási feltétel



2010

2 / 43


"Függvényanalízis"

Tartalom 1

Genetikus - evolúciós algoritmusok "Függvényanalízis" Térkép feliratozás Algoritmusok tanulása TSP Fogolydilemma ˝ Amoba "Rendezo˝ párok"

2

Neurális hálózat N.E.R.O. Hangya kolónia optimalizálás Framsticks Labirintus Autóvezetés tanulás... Istenes Zoltán (ELTE-IK-PSZT)


2010

3 / 43


"Függvényanalízis"

Spektroszkópia...

a keresett csúcsok (maximális) száma adott normál (Gauss) eloszlások összegével közelítés Istenes Zoltán (ELTE-IK-PSZT)


2010

4 / 43


Térkép feliratozás

Tartalom 1


2



2010

5 / 43


Térkép feliratozás

Genetikus algoritmusok használata térképek feliratozásában Adott n pont szeru˝ elem egy térképen. Mindegyik ponthoz tartozik egy ˝ rögzített, és négy alap téglalap alakú címke, melynek a mérete elore pozícióba írhatóak. A feladat a címkék egymást nem metszo˝ felhelyezése...



2010

6 / 43


Algoritmusok tanulása

Tartalom 1


2



2010

7 / 43


Algoritmusok tanulása

Truck backing problem A keresett függvény : u=g(x,y,cabt,trailert) PLUS(a,b) MINUS(a,b) MUL(a,b) DIV(a,b) ATG(a,b) IFLTZ(a,b,c)

a+b a-b a*b a/b, if b <> 0, else 1 atan2(a,b), if a<> 0, else 0 b, if a<0, else returns c

http://www.handshake.de/user/blickle/Truck/



2010

8 / 43


TSP

Tartalom 1


2



2010

9 / 43


TSP

Utazó ügynök

kromoszóma 1 gén = 1 város (a látogatás sorszáma) annyi gén ahány város "városszámok permutációja"

keresztezés permutáció megörzése pld. egypontos keresztezés nem jó...

mutáció kromoszómán belüli sorrend felcserélése

http://www.lalena.com/ai/tsp/ http://www.dna-evolutions.com/dnaappletsample.html



2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


TSP

Utazó ügynök







2010

10 / 43


Fogolydilemma

Tartalom 1


2



2010

11 / 43


Fogolydilemma

Fogolydilemma

Fogolydilemma - Prisoner’s dilemma ˝ Egy súlyos buntény ˝ kapcsán két gyanúsítottat letartóztat a rendorség. Mivel nem áll rendelkezésre elegendo˝ bizonyíték a vádemeléshez, ˝ ezért elkülönítik oket egymástól és mindkettejüknek ugyanazt az ajánlatot teszik. Amennyiben az elso˝ fogoly vall és társa hallgat, akkor ˝ az elobbi büntetés nélkül elmehet, míg a a másik, aki nem vallott, 10 év börtönt kap. Ha az elso˝ tagadja meg a vallomást és a második vall, akkor az másodikat fogják elengedni és az elso˝ kap 10 évet. Ha egyikük sem vall, akkor egy kisebb buntényért ˝ 6 hónapot kapnak mindketten. Ha mindketten vallanak, mindegyikük 6 évet kap.



2010

12 / 43


Fogolydilemma

Fogolydilemma

Másik tagad Másik vall

Egyik tagad (Cooperate) Mindketten 6 hónapot kapnak Egyik 10 évet kap, másik szabad


Egyik vall (Defect) Egyik szabad, másik 10 évet kap Mindketto˝ 6 évet kap


2010

13 / 43


Fogolydilemma

Fogolydilemma

Cooperate Defect

Cooperate 3, 3 5, 0

Defect 0, 5 1, 1

A, B = a két "játékos" C = Cooperate (tagadás), D = Defect (beárulás, vallomás) PA, PB = "jó pontok" A D D C C

B D C D C

PA 1 5 0 3

PB 1 0 5 3


megjegyzés büntetés a közös beárulásért jó beárulni a tagadót... ...rossz beárulva lenni közös tagadás


2010

14 / 43


Fogolydilemma

Fogolydilemma

Mit tegyek, ha nem akarok börtönben ülni ? 1

ha a másik kooperál (hallgat), akkor érdemes vallani (beárulni) (5:0 a "javamra")

2

ha a másik vall (beárul), akkor érdemes nekem is vallani ˝ (1:1 mindkettonknek)

Bármit dönt a másik, nekem érdemesebb vallani (beárulni) !... És ha mégis mindketten kooperálnánk ?...



2010

15 / 43


Fogolydilemma

Ismételt fogolydilemma

ismételt fogolydilemma : 1950-ben Merrill Flood és Melvin Drescher 1979-ben egy amerikai politológus, Robert Axelrod verseny 14 versenyzo˝ ˝ gyoztes a szociálpszichológus, Anatol Rapoport programja 1982-ben egy második versenyt, amelyen az összes résztvevo˝ tisztában volt az elözo˝ eredményével. Anatol Rapoport ismét ugyanazt a pályázatot küldte be (Tit for Tat névre keresztelte), és ismét nyert vele.



2010

16 / 43


Fogolydilemma

Ismételt fogolydilemma stratégia

Genetikus algoritmus ? játék stratégia ? reprezentáció (kromoszóma) ?



2010

17 / 43


Fogolydilemma

Ismételt fogolydilemma stratégia Tit for Tat stratégia: ˝ o˝ játékban", akkor "ebben a körben"... Ha "eloz Ha C C, akkor C (kooperáljunk...) Ha C D, akkor D (ha beárultál, akkor most én is...) Ha D C, akkor C (kooperálásra hajlok...) Ha D D, akkor D (tartom a beárulást...) Elso˝ játékban kooperálok... fegyverkezési verseny "aranyszabály" nemek harca



2010

18 / 43


Fogolydilemma

Ismételt fogolydilemma stratégia - kromoszóma

Egy stratégia: ˝ o˝ játékra, és lépjünk az alapján... Emlékezzünk a 3 eloz Ha CC, CC, CC, akkor "C vagy D" Ha CC, CC, CD, akkor ... ... Ha DD, DD, DD, akkor ... kromoszóma : 64 bit (22 ∗ 22 ∗ 22 ) + pár bit az elso˝ játékokra



2010

19 / 43


Fogolydilemma

Ismételt fogolydilemma - költségfüggvény

Hogyan lehet egy stratégiáról megtudni hogy mennyire jó ? mindegyik stratégiával (egyeddel) játszunk több játékot (ismételt fogolydilemmát) a játékokban elért eredménye mutatja a "jóságát" a stratégiák játszhatnak egymás ellen, "különféle környezetben"...



2010

20 / 43


˝ Amoba

Tartalom 1


2



2010

21 / 43


˝ Amoba

˝ Amoba játékállás-kiértékelo˝ mószerek összehasonlító vizsgálata kétszemélyes játékok gépi játékosának gyakori megvalósítási módszere a játékfarészlet elkészítése és kiértékelése fontos része a játékállások "pontos" kiértékelése több különbözo˝ játékállás kiértékelo˝ függvény paraméter beállítás, mint egy populáció egyedei ezek az egyedek (paraméter beállítások) egymással versenyeznek, a ˝ paraméter beállításokat egy-egy amobát játszó program használja a programok egymás ellen játszanak. ˝ az egyedek körmérkozése megmutatta a sikeresebb, jobb paraméter beállításokat, amelyeket felhasználva, keresztezés és mutáció után, egy újabb populáció, generáció kapható ˝ több generáció után egyre jobb amoba játékállás kiértékelo˝ függvény paraméterek kaphatók Istenes Zoltán (ELTE-IK-PSZT)


2010

22 / 43


"Rendezo˝ párok"

Tartalom 1


2



2010

23 / 43


"Rendezo˝ párok"

Rendezés

Rendezés összehasonlítás-csere párokkal ˝ meghatározott A cél fix hosszúságú számsorozatok rendezése elore összehasonlítás-csere párok alapján. Kérdés a minimális összehasonlítás csere párok. Példák 4 hosszú számsorra : buborék : 1-2, 2-3, 3-4, 1-2, 2-3, 1-2 (6 pár) 1-2, 3-4, 1-3, 2-4 (4 pár)



2010

24 / 43


"Rendezo˝ párok"

Rendezés - összehasonlítás-csere párok reprezentációja

1011 0101 0111 1001 1110 0100 1010 1001 1011 0101 0010 0111 0011 1100 1010 1001 (11,5) (7,9) (2,7) (14,4) (3,12) (10,9) azonos kromoszóma részlet : homozigóta különbözo˝ kromoszóma részlet : heterozigóta



2010

25 / 43


"Rendezo˝ párok"

Rendezés - keresztezés szülo˝ 1. (diploid) 11 2222 33 4444

11 33

2222 4444

szülo˝ 2. (diploid) 555 666 777 888

keresztezés 555 666 777 888

gaméta 1. (haploid) 11 4444

gaméta 2. (haploid) 777 666

ivadék (diploid) 11 4444 777 666



2010

26 / 43


"Rendezo˝ párok"

Rendezés - költségfüggvény

kevés, mindig változó rendezendo˝ számsorozat rendezésének a sikeressége ˝ probléma : az elég jó rendezések nem fejlodnek tovább... "evolúciós nyomás kell... ˝ ötlet : a teszt esetek (rendezendo˝ számsorozatok) is fejlodjenek egy számsorozat akkor "sikeres" ha nehéz rendezni... "gazdák és paraziták"



2010

27 / 43


"Rendezo˝ párok"





2010

27 / 43


"Rendezo˝ párok"





2010

27 / 43


"Rendezo˝ párok"





2010

27 / 43


"Rendezo˝ párok"





2010

27 / 43


"Rendezo˝ párok"





2010

27 / 43

Neurális hálózat

Neurális hálózat

Tanulási paradigmák: felügyelt tanulás (pld. karakter felismerés) felügyelet nélküli tanulás (pld. csoportosítás) ˝ megerosítéses tanulás (pld. játékok) Istenes Zoltán (ELTE-IK-PSZT)


2010

28 / 43

Neurális hálózat

N.E.R.O.

Tartalom 1


2



2010

29 / 43

Neurális hálózat

N.E.R.O.

NERO

http://z.cs.utexas.edu/users/nn/nero/ Istenes Zoltán (ELTE-IK-PSZT)


2010

30 / 43

Neurális hálózat

N.E.R.O.

Neuro-Evolving Robotic Operatives 1/3

"ágensek" (robotok) 3D fizikai szimulációs környezet tanítható ágensek két játékfázis tanítás, "próbakörnyezetben" "harc"... Istenes Zoltán (ELTE-IK-PSZT)


2010

31 / 43

Neurális hálózat

N.E.R.O.

Neuro-Evolving Robotic Operatives 2/3

tanítás egyre komplexebb környezetekben



2010

32 / 43

Neurális hálózat

N.E.R.O.

Neuro-Evolving Robotic Operatives 3/3 Real-time Neuroevolution (rtNEAT) ágens "agy": neurális hálózat szenzorok a neurális háló bemenetei genetikus algoritmus, ˝ megerosítéses tanulás: egy populáció legjobbjai jutalmat, a legroszabbak büntetést kapnak a "jóságot" a felhasználó állítja be: különbözo˝ szempontoknak megfelelés (ellenfél megközelítése, célbatalálás, távolságok...) az "agy"at az életciklusa végén az algoritmus "kiértékeli".... N.E.R.O Neuro-Evolving Robotic Operatives : http://nerogame.org Istenes Zoltán (ELTE-IK-PSZT)


2010

33 / 43

Neurális hálózat

Hangya kolónia optimalizálás

Tartalom 1


2



2010

34 / 43

Neurális hálózat

Hangya kolónia optimalizálás

Hangya kolónia optimalizálás - ant colony optimization

gráfban legrövidebb út keresés véletlenszeru˝ vándorlás élelem találása esetén vissza a bolyba, közben feromon nyomok hagyása ha feromon nyomot talál, akkor (véletlen vándorlás helyett) inkább követi ˝ a feromon nyom idovel elpárolog a rövidebb úton jobban megmarad a feromon nyom... http://www.nightlab.ch/antsim/



2010

35 / 43

Neurális hálózat

Framsticks

Tartalom 1


2



2010

36 / 43

Neurális hálózat

Framsticks

Framsticks

Lények evolúciós képességeinek a vizsgálata 3D környezet genotípus ábrázolja a lényeket: fizikai szerkezet ("test") neurális hálózat ("agy")

˝ → agy → környezet → érzékelok beavatkozók → környezet operátorok: mutáció, keresztezés, javítás energia követelmények irányított (fitnessz függvény), és spontán evolúció Istenes Zoltán (ELTE-IK-PSZT)


2010

37 / 43

Neurális hálózat

Labirintus

Tartalom 1


2



2010

38 / 43

Neurális hálózat

Labirintus

Labirintusból kitalálás...

kromoszóma? mit reprezentál? költség függvény? operátorok: szelekció, keresztezés, mutáció? evolúció mukdése? ˝ Általános algoritmus

Egy adott labirintusból kromoszóma = útvonal ...


kromoszóma = "algoritmus" ...


2010

39 / 43

Neurális hálózat

Labirintus

Labirintusból kitalálás...

kromoszóma? mit reprezentál? költség függvény? operátorok: szelekció, keresztezés, mutáció? evolúció mukdése? ˝ Általános algoritmus

Egy adott labirintusból kromoszóma = útvonal ...


kromoszóma = "algoritmus" ...


2010

39 / 43

Neurális hálózat

Autóvezetés tanulás...

Tartalom 1


2



2010

40 / 43

Neurális hálózat


Autóvezetés tanulás

a vezeto˝ érzékeli a környezetét ezek alapján irányítja az autót... mit érzékel a vezeto˝ (algoritmus)? mit tartalmaz a kromoszóma / neurális hálózat? mi az evolúciós algoritmus / neurális hálózat bemenete és kimenente (eredménye)? hogyan muködik ˝ az evolúciós algoritmus / neurális hálózat? ...



2010

41 / 43

Neurális hálózat


˝ Elonyök - hátrányok, továbbfejlesztés Hátrányok ˝ Elonyök

ha kicsi / változó az állapottér

sok paraméterrel

ha kevés a paraméter

jól párhuzamosítható

ha bináris / drága költségfüggvény

több jó megoldás

nincs "biztos" optimum Továbbfejlesztés új operátorok : pld. öregedés... pontosabb evolúciós modell : több populáció egymásra hatása... tanulás beépítése... adaptálódó kódolás, és paraméterek hierarchikus modell, meta... Istenes Zoltán (ELTE-IK-PSZT)


2010

42 / 43

Neurális hálózat


Összefoglalás



2010

43 / 43

Mesterséges Intelligencia alapjai

Recommend Documents