Dr. Jelasity Márk
Mesterséges Intelligencia I. (I602, IB602) harmadik (2008. szeptember 15-i) előadásának jegyzete
Készítette:
Papp Tamás PATLACT.SZE KPM V.
HEURISZTIKUS FÜGGVÉNYEK ELŐÁLLÍTÁSA Nagyon fontos a jó és elfogadható (konzisztens) heurisztika. A kérdés az, hogy hogyan kaphatunk ilyeneket? 1,Relaxálás Ha van egy nehéz feladatunk, és ennek nem tudjuk a költségét, akkor találjunk ki egy egyszerűbb feladatot, ami bizonyíthatóan egyszerűbb, mint az eredeti feladat és akkor ennek számítsuk ki a költségét. Egy egyszerűbb feladat esetében ezt könnyebben meg tudjuk tenni. Mivel a feladatot egyszerűsítettük a költség kisebb lesz, mint az eredeti feladaté, és az így kapott értéket tudjuk alkalmazni a heurisztikához. Relaxált probléma optimális megoldása = h() relaxáció: feltételek elhagyása Pl.: A 8-as kirakó játékban
Szóba jöhető heurisztikák: h1: rossz helyen lévő számok száma (itt h1 = 8 ilyen van, mivel az összes számot legalább egyszer mozdítani kell, hogy jó helyre kerüljön) h2: „Manhattan-távolság” vagy háztömb-távolság (itt h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18) Azt számolja meg, hogy egy adott állapotból hány darab mozgatást kell elvégeznem, hogy eredeti helyükre tegyük a kockákat, de hagyjuk figyelmen kívül a többi kockát.
hopt: 26 (tényleges távolság) , így egyik heurisztikánk sem becsüli túl a megoldás igazi költségét. Az első esetben (h1) minden számot rögtön a helyére tolhatunk, mindenféle korlátozás nélkül, azaz minden kockát egy lépésben teszünk a helyére. A második esetben (h2) kevesebbet egyszerűsítünk. Ez azt mondja, hogy tologassuk a számokat úgy, ahogyan az eredeti feladatban van, viszont hagyjuk figyelmen kívül, hogy melyik pozíció van elfoglalva. Nyugodtan betolhatjuk foglalt pozíciókba is a kockákat. Megj.: ∀n: h1(n) ≤ h1(n) , azaz h2 dominálja h1-et. A h2 a h1 további relaxálása. Relaxált probléma optimális költsége mindig kisebb, vagy egyenlő mint az eredeti. Ezt egy elfogadható heurisztikának tekintjük az eredeti problémára. Mivel a számított heurisztika a relaxált problémára egy pontos költség, teljesítenie kell a háromszög egyenlőtlenséget is, és ebből kifolyólag konzisztens is. 2, Automatizált relaxálás Ha a feltételek formális nyelven adottak, akkor a relaxált problémákat automatikusan előállíthatjuk. Például: 8-as kirakójáték feltételei: a, egy kockát egy szomszédos pozícióba mozgathatsz ÉS b, egy kockát csak üres pozícióba mozgathatsz Ha a, és b, feltételt elhagyjuk akkor a h1 esetet kapjuk. Ha b, feltételt elhagyjuk akkor h2 esetet kapjuk. 3, Heurisztikák kombinálása h(n) = max (h1(n), ... , hk(n)), => hi konzisztens, => h konzisztens 4., Mintaadatbázisok Részproblémákat vetünk fel, amelyek költségeit eltároljuk. Például a 8-as kirakóban "korábban megállunk", és csak 1-4ig vizsgáljuk az elemeket. Megj.: Önmagában is konzisztens heurisztika
Több részproblémát is felvehetek. (pl.: 3-7ig) Ezek a részproblémák egyenként könnyen kiszámolhatóak, ezután vesszük a maximumukat. A kis részproblémák megoldásait adatbázisban tárolhatjuk. 5., Független részproblémák A költségek összeadhatóak. Például: 1,2,3,4; és csak azokat számolja amiket mozgatunk 1-4ig. LOKÁLIS KERESÉS, OPTIMALIZÁLÁS A keresés modelljét kicsit megváltoztatjuk: 1, állapotok 2, operátorok (~cselekvések): állapotátmenetek lehetőségei: szomszédok 3, célfüggvény, f az állapotokhoz értelmezve, nincs jelentősége hogyan jutottunk el oda 4, célállapotok: pl.: globális maximum állapotok {x | f(x)} = max f(y)} 5, kezdőállapot: általában nincs, vagy véletlenül generált. Nincs igazán jelentősége, ugyanis a célhoz vezető út érdektelen. Az aktuális állapotot vesszük figyelembe, és annak a szomszédait. Pl.: 8-királynő probléma : a királynők végleges felállása számít, és nem az a sorrend ahogy az újabb királynőket felhelyezzük. Megj.: Egyik állapotból eljuthatunk egy másikba; az állapotátmenetnek nincs költsége. Az állapot szomszédai elérhetőek valamilyen operátor segítségével. Célállapot mindig van. Célállapotok halmaza-> ahol a célfüggvény maximum.
Néhány globális optimalizálási fogalom Lokális maximum:(ha nem globális): ha a „szomszédainak” célfüggvényei kisebbek, azaz f(x) ≥ max f(y) (ahol y, x szomszédja) Globális maximum: egyben lokális is, és nincsen nála magasabb "csúcs", azaz f(x) = max f(y') Plató: szomszédok értékei ugyanazok (sok lehet) Lokális keresők Egy állapotot tárol, csak az aktuálisat, és általában ennek a szomszédjaira lépnek át. Előnye, hogy memóriaigénye gyakorlatilag nulla, és nagy keresési térben is elfogadható megoldást nyújtanak. Nem garantálják a globális maximum megtalálását Hegymászó keresés Csak felfelé "halad". Lokális maximumnál megáll, ugyanis megállítja az első optimum. Mohó keresésnek is hívják, a siker általában nem garantált. Algoritmus: 1, aktuális állapot ← véletlen állapot (vagy kezdő állapot, ha van)
2, szomszéd ← egy maximum értékű szomszédja aktuális-nak 3, ha f(szomszéd) ≤ f(aktuális) then return aktuális 4, aktuális ←
szomszéd
5, goto 2 Jó példa erre a 8 királynő probléma: (sakktáblára tegyünk fel úgy 8 királynőt, hogy ne üssék egymást) Keresési tér: lehetséges felrakások száma Állapotok: {1,2..8}8 , pl.: (1,2,3,4,5,6,7,8): melyik sorba tegyük az i. királynőt ami az i. oszlopban van Operátorok: egy királynő adott pozíciójának megváltoztatása → 8*7=56 operátor bármely állapotban Keresési függvény: számoljuk azokat a párokat amelyek ütik egymást Célfüggvény: minimumot keresünk, tehát a párok száma, amelyek ütik egymást, azoknak az értéke legyen 0 => h(x) = 0 : x célállapot Az esetek 14%-ban talál megoldást. Sokszor elakad, mert – lokális optimum, vagy plató megállítja – ha maximum 100 db oldallépést megengedünk (azaz elfogadjuk az új állapotot, ha legalább olyan jó mint a régi) => 94%-ban talál megoldást
Hegymászás javításai: A hegymászó algoritmus számos változatát fejlesztették ki. Sztochasztikus hegymászó: Véletlen szomszédot választ, azok körül amelyek jobbak. Minél több véletlen szomszédot alkalmazunk annál biztosabban megtalálja az optimumot. Hosszabb futási idejű, de ritkábban akad el. Elsőnek-választott hegymászás: Ha sok szomszéd van, vegyük az elsőt ami jobb. Ez jó stratégia, ha egy állapotnak sok követője van. Véletlen újraindított hegymászás: Ha nem sikeres a keresés, indítsuk újra egy véletlen pontból. Ez a keresési tér struktúrájától
függően, nagyon jól futó algoritmust ad. Pl.: 3 millió királynő megoldása kevesebb mint egy perc alatt . Az NP teljes, komplexebb problémáknál már nem az igazi. A problémák 3 csoportja: – sok megoldás – nincs megoldás, túl sok korlát – kevés megoldás Szimulált hűtés: Alapötlete a fémöntés technikájának az analógiáján nyugszik. Algoritmus: 1, aktuális ← véletlen állapot; t ← 0 2, t ← t + 1; T ← hűtési terv [t] 3, if T = 0 then return aktuális 4, szomszéd ← véletlen szomszédja az aktuális-nak 5, ∆E = f(szomszéd) – f(aktuális) 6, if ∆E > 0 then aktuális ← szomszéd 7, else aktuális ← szomszéd exp(∆E/T) valószínűséggel 8, goto 2 Lokális optimumot úgy kerüli el, hogy néha rosszabb megoldásokat is elfogad, mint az aktuális. Ha a hőmérséklet lassan csökken, megtalálja a globális optimumot. A hűtési terv fontos, de problémafüggő. Pl.: TK+1 = αTK , α= 0,95 Mottó: „Lassú hűtés a jó.” Populáció alapú lokális keresés: Több aktuális állapotot is felvehetünk, nem csak egyet. Lokális nyaláb keresésnek is szokták emlegetni. Algoritmus: 1, K véletlen állapot generálás 2, Az összes K állapotnak az összes szomszédját generáljuk 3, ebből vesszük a legnagyobb K-t a következő aktuális állapotoknak 4, Ha bármelyik célállapot , return 5, goto 2 Nem úgy működik, mint K darab hegymászó, mert a K párhuzamos szál megosztja az információt
és gyorsabban fókuszál. Ennek eredményeképpen gyorsabban be is ragadhat. Egyik variánsa a sztochasztikus választás. Evolúciós algoritmusok A sztochasztikus nyaláb keresés egy variánsa, és hegymászó algoritmust általánosítja. Evolúciós algoritmus: a nyaláb keresés általánosításához „szexuális” operátorokat vezetünk be. Algoritmus: 1, K véletlen állapot generálása 2, szülők választása 3, új állapotok generálása rekombinációval a szülőkből 4, új állapotok mutációja 5, K állapot kibontása az új állapotok és a régiek uniójából 6,goto 2 Kisszótár az evolúciós szubkultúrához – állapot = megoldás = egyed (individual) – mutáció = operátor = cselekvés – rekombináció = keresztezés(crossover) = 2 változós operátor A x A → A (A : állapotok) – fitness = célfüggvény érték – szülő = aktuális állapotok közül választott állapot (2.sor) – utód = új állapot (3. , 4. sor) – populáció = az aktuális állapotok halmaza – operáció = a populáció egy adott időben – túlélők = megoldások az új populációban (5.sor) – az új komponens a rekombináció – ezenkívül a szülők és a túlélők kiválasztásának is számtalan módja van Genetikus Algoritmus – állapottér: véges betűkészletű sztringek (gyakran {0,1}) pl.: 8 királynő probléma ilyen – mutáció: pl.: egy betű megváltoztatása pl.: a 8 királynőhöz használt operátor ilyen – rekombináció: keresztezési pontnál vágás és csere
– szülő szelekció: pl.: válasszunk K/2 darab párt a fitnesszel arányosan fitnesszel, vagy véletlen párosítással – túlélő szelekció: pl.: válasszunk a K legjobbat, vagy véletlenül a fitnesszel arányosan, stb. – számos változat, pl.: evolúciós stratégiák (német „iskola”) valós terekben, vagy genetikus programozás (programok evolúciója) – Hype faktor: (hasonló az MI-hez; az „evolúció” is „szexi”) – érdekes algoritmusok (lásd differenciál evolúció alább) Folytonos terek Eddig diszkrét terekben (kombinatorika) gondolkodtunk, de a célfüggvény lehet akár folytonos Rd → R => ∞ szomszédos állapot. A hegymászó algoritmus különböző verziói itt is működnek: Hegymászó: legmeredekebb lejtő (emelkedő) módszere, csak ha deriválható a célfüggvény f => – határozzuk meg a maximálisan emelkedő irányt – lépjünk egy ε nagyságút arrafelé (vagy véletlen nagyot, pl. (0,ε)-ból, stb.) Sztochasztikus hegymászás: véletlen irány, ha jó, akkor elfogadhatjuk. Differenciál evolúció (differential evolution) (1997, Storm & Price): a populáció: x1 , ….., xk eleme Rd szülő választás : minden egyed szülő is egyben rekombináció: minden xi {i=1, ..,k}- hoz választunk három véletlen egyedet: xr1, xr2, xr3. Legyen: v = xr1 + F [ xr2-xr3 ] + κλ[ yg – xr1] ahol yg az eddigi legkisebb megoldás amit ismerünk. Megj.: v nem függ xi -től, mutáció: nincs (ill. néha mutációnak hívják a fentit) v-t keresztezzük a xi -vel: (v1 , v2, …. ,vd)
(u1, u2, …, ud)
(xi1 , xi2, …. ,xid)
ahol az uj = xij CR valószínűséggel, vj egyébként paraméterek: pl F~0,8 CR ~ 0,9, λ ~ 0,9 túlélők: u-val helyettesítjük xi-t ha f(u)> f(xi) lényeg: az operátorok automatikusan adaptálódnak a populáció kiterjedéséhez és alakjához
KORLÁTOZÁS KIELÉGÍTÉSI FELADATOK A keresési problémák fontos alosztálya; állapot és célállapot illeszkedik egy speciális belső struktúrájú reprezentációhoz. Általános célú heurisztikák használatával nagy problémák megoldását is lehetővé teszi. Definíció: állapottér: D= D1 x D2 x … x Dn
( Di az i. változó (xi) lehetséges értékei)
Korlátozások: C1, …, Cm , ahol Ci ⊆ D A következő hozzárendelések konzisztensek (megengedettek): C1 ∩ C2 ∩ …. ∩ Cm Egy hozzárendelést konzisztensnek nevezünk, ha nem sért meg egyetlen korlátozást sem. A célállapotok a megengedhető állapotok és néhány korlátozás kielégítési probléma az is igényli, hogy a megoldás célfüggvényt maximalizáljon. Általában egy Ci, a változók egy részhalmazára tartalmaz megszorítást, gyakran változópárra. Például.: gráfszínezési probléma: G(V,E), gráf n = |V| n változó: n ország (V), D1 =D2 = …. = Dn : a lehetséges színek e∈E egy Ce korlátozás, amely kizárja az azonos színű hozzárendeléseket az adott élen. Kényszergráf: ha Ci párokra vonatkozik, adott, ha nem, akkor segédváltozók bevezetésével átalakítható. A gráf csomópontjai a probléma változóinak, élei pedig a korlátoknak felelnek meg. A keresési teret inkrementálisan is definiálhatjuk: kezdeti állapot: {} (üres halmaz), azaz egyik változónak sincs értéke. szomszédok: valamely hiányzó változóhoz rendeljük értéket amely nem okoz konfliktust
út költség: konstans költség mindegyik lépésre Inkrementális definíciós algoritmus Korábban tanult algoritmusok jól használhatóak (mélységi, szélességi, stb.), de a mélységi különösen jó, mert kevés memóriaigénye,és kicsi fa- magassága. Hátránya viszont az informálatlan keresés. Megoldás lehet: – változók és értékeinek sorrendje fontos a fa bejárásánál – kiterjesztéskor azt a változót választjuk amihez legkevesebb lehetséges megengedett érték maradt – ha ez nem egyértelmű (pl.: kezdés), akkor azt amire a legtöbb korlátozás vonatkozik – a választott változó értékeiből azt rendeljük hozzá, amelyik a legkevésbé korlátozza a következő lépések lehetséges számát Ezek lépések jelentős javulást hoznak általában, de még számos más optimalizálás is elképzelhető a bejárás során.
