(kódování ISO-8859-2) ___________________ Genetické algoritmy ~~~~~~~~~~~~~~~~~~~ EVT - evoluční výpočetní techniky = heuristika pro řešení NP-úplných problémů - procházíme prostorem řešení a snažíme se najít uspokojivé řešení (s uspokojenou přesností a pravděpodobností, kterou obvykle známe) Genetické algoritmy G.J.Holland - biolog (1977), úplný popis však formalizoval nějaký informatik jedinec - kandidát na řešení, prvek v prostoru populace - G(t) = {Xt1 ... XtN}, množina jedinců, kde t = čas (generace) účelová funkce - fce rozhodující o tom, kteří jedinci jsou "kvalitnější" mutace - generická variabilita Algoritmus: 1. výchozí polupace 2. vyhodnotíme ji 3. pokud jsme našli výsledek (nebo překročili určitý počet kroků), pak konec 4. jinak proběhne selekce 5. dále reprodukce 6. proběhne křížení 7. provedeme mutaci 8. prvky ohodnotíme a přejdeme ke kroku 3 Toto je popis algoritmu SGA (simple genetic alg.) Snažíme se zachovat genetickou informaci jedince (provádíme kódování). Výsledkem toho kódování je chromozóm. To si můžeme představit jako pole genů (tzv. "alely" nebo také "pozice"). Geny obsahují prvky z určité abecedy Ai. pro každou a z A platí: a je z Ai Toto kódování nazýváme genotypem. Intepretací genotypu je fenotyp. Genotyp tedy určuje strukturu a kodování chromozomu a fenotyp popisuje, co který gen znamená (barva očí, cukrovka...) Př: Ai = {0, 1}, chromozom = 00011001, délka L = 8 fenotyp by mohl být jednak nějaký seznam genů (dvě ruce, tři hlavy, modré oči), ale klidně i třeba číslo (v tomto případě 25) Představme si, že chceme kódovat číslo v int. s přesností E. L = floor(log(abs(s-x)/E), 2) tj. <0, 127> = 7 (7 bitů) Křížení ~~~~~~~ Máme vždy 2 chromozomy (rodiče), ze kterých vytvoříme 2 chromozomy (potomky). Easy, isn`t it? Volba pozice probíhá náhodně. 1-bodové: rodiče: 01100|01 = 49 10001|00 = 68 (náhodně vyberu jednu pozici "|") potomci: 01100|00 = 48 10001|01 = 69 Mutace ~~~~~~ Rozšiřuje prostor hledání, zamezuje tomu, abychom se k nějakým prvkům nedostali. Ohodnocení ~~~~~~~~~~ Klíčová je účelová (fitness) funkce, která přiřazuje míru kvality jedinci. Obvykle obor hodnot fce je vždy kladný. Př: Hledání maxima, f(x). Hledání sqrt(c) -> y = abs(x^2 - c) -> f=1/(abs(x^2-c)+1) Selekce a reprodukce ~~~~~~~~~~~~~~~~~~~~ Základní princip: lepší jedinci mají větší pravděpodobnost reprodukce do další generace. P(i) = Kt * f(Xti), Kt - konstanta nebo také tzv průletovým kolem P(i) = f(Xi) / sum[i=1..N]( f(xi) ) Další druhy: a) turnajová b) podle pořadí - setřídím a vezmu "tu vlevo" Schémata a věta o schématech ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Abecedu rozšíříme o znak hvězdičky (*), uvažujme A`={0,1}, pak A={0,1,*}. Délka bude tedy 3^L. Řád schématu: o(H) = L-j (L-délka, j-počet hvězdiček) Každé schéma pokrývá 2^(L-o(H)) chromozomů (dá se to pěkne naznačit v grafu). Př: ch=(1,0), L=2 (1,0) ... o(H)=2 (*,0) ... o(H)=1 (1,*) ... o(H)=1 (*,*) ... o(H)=0 Definiční délka - největší řád schématu (u největším počtu hvězdiček): d(H) = <0, (L-1)> Př: (01**01*) ... d(H)=7 (2=5) Počet jedinců, kteří jsou pokryti schématem v daném čase t: m(H,t) Ptáme se, jak bude vypadat m(H, t+1): 1) uvážíme selekci: m(H,t+1) =asi= m(H,t) * (f`(H,t)/f`(t)) kde f` je průměr fitness populace 2) křížení pravděpodobnost, že dojde k rozbití (schéma se nezachová): Pxd(H) = d(H) / (L-1) a že se nezachová Pxs(H) = 1 - Pxd(H) a zohledníme také křížení schématu Pxs(H) = 1 - Px * Pxd(H) 3) mutace pravděpodobnost, že alela podlehne mutaci = Pm, nás ale zajímá pravděpodobnost zachování (nemutace) Pz = 1 - Pm každé schéma má specifikovaných bitů (neobs. *) tolik, kolik je řád schematu, takže to uvážíme: Pz = (1 - Pm) ^ o(H) =někdy_se_píše= 1-Pm*o(H) (protože Pm je malá) Věta o schématech: m(H,t+1) = m(H,t) * (f`(H,t)/f`(t)) * Pxs(H) * Pz Počet nadprůměrných schémat roste v dalších generacích exponenciálně. Výhody a nevýhody GA: ~~~~~~~~~~~~~~~~~~~~~ Genetické algoritmy se dají dobře paralelizovat. Avšak je nutno si hrát s koeficienty a nastavením, ale je to méně problematické než u neuronových sítí. Aplikace ~~~~~~~~ Komprese dat - snažíme se nalézt vhodné nastavení pro nějaký kompresní algoritmus. Elektrotechnika - optimalizování obvodů při návrhu plošných spojů. Strojírenství - optimalizace motoru Boeing. Identifikace zločinců - výběr tváře svědkem. Logistika - sklady, rozvoz zboží. Školy - tvorba rozvrhu (snažím se vylepšit rozvrh z minulého roku). Ekonomika - předpovídání vývoje na akciových trzích (a obecně časových řad - ono to ale není moc ideální). Generování hudby - GenJam. ______________________ Genetické programování ~~~~~~~~~~~~~~~~~~~~~~ Jonh Koza, konec 80. let Analogie GA, ale neslouží k hledání nějakých proměnných a výsledků, ale programu. Hledáme program. Základní principy jsou stejné, ale pochopitelně se to liší tím, jak reprezentujeme jedince. Reprezentace jednců: a) stromová b) lineární (používá se málo) Programy se tedy reprezentují jako stromy o uzlech (funkce nebo terminály). Podobnost se Schemem není čístě náhodná (výrazy v jazyku Scheme jsou totiž vlastně taky stromy :-) Seznam můžeme totiž chápat jako strom. Genotyp je tedy strom. A co je fenotyp? To je intepretace programu (vyhodnocená výrazu). Bohužel ale nemůžeme modelovat cykly, to prostě nejde, strom musí být konečný. Množina funkcí musí splňovat tyto požadavky: a) uzavřenost - všechny funkce musí akceptovat vše (nesmí nic skončit chybou) b) vyjádřitelnost - množina funkcí musí být úplná, abychom byli schopni vše modelovat (např pro boolovskou logiku nám stačí F={AND,NOT}) c) obecnost - funkce nemusíme volit jen standardní (IF), ale můžeme si je uzpůsobit potřebám řešení (NOTIF), ale tak, aby to bylo dostatečné (a jednoduché - čím míň, tím líp) Křížení ~~~~~~~ Př: rodiče: (if a b (not b)), (and (and a b) (not b)) křížení probíhá na libovolných dvou uzlech u obou rodičů potomci: (if (not b) b (not b)), (and (and a b) a) Mutace ~~~~~~ Náhodně vybere uzel, zruší jej a vygeneruje náhodně nějaký strom. Ohodnocení ~~~~~~~~~~ Máme trénovací množinu, jako vyhodnocení můžeme chápat: a) shoda žádaných výstupů (poč. správných výstupů / poč. test. příp.) b) je to kámen úrazu GP - malé změny v genotypu dělají zásadní změny ve fenotypu, rozhodnout, který funkce je lepší je velmi složité a obecně neřešitelné Př: logická funkce EQ: ABEQ 00 1 (if a b (not b)) 01 0 10 0 11 1 nyní provedeme malou změnu: (if a (not b) b), výsledkem ale je: ABEQ 00 0 01 1 10 1 11 0 chová se přesně opačně, tj. fitness první fce je 100 % a druhé 0 % daleko "kvalitnější" než naše druhá (upravená) funkce by byla však funkce (true x) mající fitness 50 % což ale není pravda, daleko lepší je zde funkce s malou změnou, která má však ohodnocení rovno nule Moc to tedy úspěšné není a efektivní to je pouze v případě, že množina funkcí je tak silná, že to je již vlastně téměř vyřešeno. Podfunkce ~~~~~~~~~ Je možné vytvářet takové struktury, které budou obsahovat několik pomocných funkcí (specifikujeme jejich počet). Hlavní větev (program) pak tyto podfunkce využívá. Využití ~~~~~~~ Elektrotechnika - optimalizace spojů. Hudba - tvorba melodií na základě generačních úprav známých vzorků. Hudba - hudební doprovod. # vim: set sw=4 ts=4 sts=4 sta et ai fenc=iso-8859-2 : #