Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Modelování evolučních procesů Radek Pelánek Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Modelování změn v systémech Změny v systémech dosavadní modely měly statickou strukturu (pravidla) komplexní systémy se mění: vývoj, adaptace, učení, ... vztah k horizontu modelu vlk: reintrodukce, lov ve smečce epidemie Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Modelování změn v systémech Změny v systémech systém rychlost změn nervový systém sekundy až hodiny imunitní systém hodiny až dny firma měsíce až roky živočišný druh dny až století ekosystém roky až milénia evoluce – tato přednáška myšlení – další přednáška Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Modelování změn v systémech Smysl modelů adaptace 1 pochopení přírody jak funguje myšlení, evoluce, ... 2 lepší modely komplexních systémů obohacení modelů s agenty 3 řešení náročných algoritmických problémů modely jako výpočetní mechnismy Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce O evoluci Evoluce základní myšlenka evoluce je (alespoň zdánlivě) jednoduchá důsledky jsou však často komplikované a neintuitivní tato přednáška: výběr zajímavostí, principů témata se vztahem k výpočetním modelům rozhodně ne vyčerpávající pojednání o evoluci Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce O evoluci Evoluce: citáty Slepice je jenom způsob, jakým vajíčko vyrábí další vajíčko. (Samuel Butler) Přírodní výběr je mechanismus pro generování mimořádně velkého stupně nepravděpodobnosti. (Sir Ronald Fisher) Nothing in biology makes sense except in the light of evolution. (Theodosius Dobzhansky) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce O evoluci Vybrané historické poznámky cca 1800: Lamarck, vývoj s děděním získaných vlastností 1859: Darwin, Origin of species, změny + přírodní výběr 1865: Mendel, dědičnost poč. 20. stol: ’modern synthesis’ předchozích dvou 1953: struktura DNA 1976: Dawkins, Selfish gene Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Příklad můry evoluce je vesměs pomalá (rychlost ∼ generacím), nejde moc pozorovat známá výjimka: můry v okolí Manchasteru průběh: světlá kůra stromů → světlé můry znečištění → tmavá kůra → tmavé můry redukce znečištění → zpět světlá kůra → světlé můry NetLogo: Biology / Evolution / Peppered Moth, Bug Hunt Camouflage Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Genetická informace genetická informace uložena v DNA DNA = řetězec „základních bloků : adenine (A), cytosine (C), guanine (G), thymine (T) při reprodukci dochází ke kombinaci (křížení) DNA rodičů náhodné mutace Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Základy evoluce: poznámky vyvíjí se populace jako celek (nikoliv jednotlivci) diverzita je důležitá schopnosti získané během života se nepřenáší (až na detaily) srovnej: Lamarck, „kulturní evoluce (memy), simulovaná evoluce přirozený výběr ∼ usměrňování vývoje Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Přirozený výběr přežití nejsilnějších (survival of the fittest) nebo spíš přežití schopných reprodukce (survival of the reproducers) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Přirozený výběr přežití nejsilnějších (survival of the fittest) nebo spíš přežití schopných reprodukce (survival of the reproducers) triviální, ale zajímavé pozorování: Všichni naši předci žili tak dlouho, že se stihli reprodukovat. pozitivní zpětná vazba Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Koevoluce organismy se adaptují na měnící se okolí organismy současně i ovlivňují okolí „Red Queen effect (Alenka v říši divů): Now, here, you see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that! Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Koevoluce: biologické závody ve zbrojení netopýři mají sonar, kterým hledají můry (sonar je sám o sobě zapeklitě komplikovaný) můry vyvinuly měkké pokrytí těla, které absorbuje netopýří vysílání netopýři přešli na nové frekvence můry přišly s novým pokrytím a s „rušičkou (vlastní signál který interferuje s netopýřím) netopýři přišli s novými leteckými manévry a naučili se vypínat sonar (čímž dělají rušení méně efektivním) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Koevoluce: biologický citát Na počátku byla jemná křehká bylinka, kterou občas někdo sežral; na konci je trnitá a jedovatá obluda, kterou také občas někdo sežere. (J. Zrzavý, D. Storch, S. Mihulka) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Základní principy Koevoluce v IT viry a antivirová ochrana spamy a antispamová ochrana Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Typy evolučních modelů přežití nejsilnějších (bez vývoje) – „ekologické modely (např. Dilema vězně a třetí Axelrodův turnaj) přežití nejsilnějších + vývoj (křížení, mutace) genetické algoritmy evoluční programování genetické programování ... Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Interpretace evolučních principů Lze interpretovat různě: „nejsilnější mají největší šanci reprodukce učení se metodou pokus-omyl (a pamatování si úspěšných) nápodoba úspěšných není potřeba „racionalita agentů, uvědomění si, co přesně dělají (srovnej dedukce, příklad piráti) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Genetické algoritmy: základní přístup Vyber počáteční populaci P Opakuj dle potřeby: Vytvoř novou prázdnou populaci P Opakuj dokud P’ není plná: Vyber dva jedince z populace P v závislosti na kritériu zdatnosti Volitelně: křížení a nahrazení potomky Volitelně: mutace Přidej do populace P P := P Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Reprezentace jedinci ∼ řetězce (většinou binární) případně vyžadovány speciální vlastnosti řetězců (např. permutace čísel) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Výběr výběr založen na zdatnosti (fitness): absolutní zdatnost (např. optimalizační problémy) relativní zdatnost – necháme jedince spolu „soutěžit deterministický výběr nejlepších: ztráta diverzity uváznutí na lokálním minimu používá se proto náhodnostní výběr s přihlédnutím k zdatnosti (ruleta) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Výběr – ruleta https://github.com/carlosnasillo/Hybrid-Genetic-Algorithm Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Křížení variace: vícebodové křížení, zachování základních bloků někdy speciální formy křížení, abychom zachovali požadovanou vlastnost řetězců Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Mutace náhodná změna v řetězci, opět mohou být potřeba speciální úpravy většinou nevede ke zlepšení může pomoci překonat lokální optima používáno, ale s malou pravděpodobností Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Genetické algoritmy Praxe: volba parametrů základní princip genetického algoritmu jednoduchý avšak mnoho (skrytých) parametrů a voleb volba reprezentace, funkce zdatnosti, přesný mechanismus křížení, mutace, výběru podle zdatnosti, velikost populace, počet generací, pravděpodobnost mutace, ... není jednoduché to „rozchodit existují heuristiky pro volbu parametrů, např. pro velikost populace: velikost populace X počet generací > 100 000 velikost populace >> počet genů Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Ilustrační příklad: Hledání řetězce Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Demo příklady NetLogo Computer Science / Simple Genetic Algorithm Biology / Evolution / Sunflower biomorphs demo příklady na webu: „Genetic algorithm typická ilustrace: problém obchodního cestujícího (TSP, traveling salesman problem) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Robot sbírá jídlo NetLogo: Computer Science / Robby the Robot mřížka, zdi, jídlo vstup: robot vidí bezprostřední okolí výstup: přesun na vedlejší pole úkol: posbírat co nejvíce jídla genetický algoritmus zvládne vymyslet neintuitivní „finty Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Robby the Robot Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Robby the Robot Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Evoluce pohybu Karl Sims: Evolved Virtual Creatures www.karlsims.com/evolved-virtual-creatures.html www.youtube.com/watch?v=JBgG_VSP7f8 Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Evoluční Dilema vězně: Axelrodova studie otázka: jak moc byly výsledky turnajů ovlivněny tím, že lidé očekávali určité složení odeslaných strategií? strategie uvažující poslední 3 tahy, začíná z náhodných strategie, které se vyvinou připomínají charakteristiky TFT – tj. dominance principů, na kterých je TFT založena není způsobena lidskými očekáváními, kulturními hodnotami, ... Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Dilema vězně strategie zohledňující posledních k kol – snadná reprezentace řetězcem např. pro k = 1 řetězec 5 znaků: 1 tah v prvním kole 2 co dělat když minule: oba spolupracovali 3 co dělat když minule: já spolupracoval on zradil 4 co dělat když minule: já zradil on spolupracoval 5 co dělat když minule: oba zradili např. TFT je “SSZSZ” zdatnost = průměrný bodový zisk Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Dilema vězně G. Flake, The Computational Beauty of Nature Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Další aplikace genetických algoritmů optimalizační problémy: rozvrhy, protein folding učení a plánování: robotika, hry návrh: hardware, materiály Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Optimalizační problém Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Příklady Optimalizační problém Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Pojmy Evoluce a míra zdatnosti „přežití nejsilnějších – ale co to znamená „nejsilnější ? existuje absolutní míra zdatnosti? ne zdatnost organismu závisí na prostředí, ve kterém se nachází a které sám ovlivňuje (viz koevoluce) evolučně stabilní strategie Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Pojmy Evolučně stabilní strategie pokud by do populace tvořené čistě touto strategií přišla cizí strategie, tak by se nerozšířila zjemnění Nashova ekvilibria (teorie her) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Jestřáb a holubice agenti bojují o zdroje, úspěšní se množí, neúspěšní vymírají každý dodržuje jednu ze dvou strategií: jestřáb vždy útočí, ze souboje utíká jen při velkých poraněních holubice nikdy neútočí (vyčkává dokud to druhý nevzdá), ze souboje utíká Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Jestřáb a holubice: tabulka Model teorie her, průměrný zisk ze vzájemného setkání: jestřáb holubice jestřáb -2; -2 10; 0 holubice 0; 10 3; 3 konkrétní hodnoty nejsou příliš důležité, hlavní je uspořádání hodnot jde v podstatě o hru „Kuře (viz slidy Spolupráce) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Kdo je nejsilnější? Kdo je „silnější ? Co je výhodnější strategie: jestřáb nebo holubice? Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Kdo je nejsilnější? Kdo je „silnější ? Co je výhodnější strategie: jestřáb nebo holubice? nelze jednoduše odpovědět – záleží na složení populace převládají jestřábi ⇒ je lepší být holubice převládají holubice ⇒ je lepší být jestřáb Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Analýza hry podíl jestřábů v populaci je p (a podíl holubic tedy 1 − p) průměrný zisk jestřába je: zj = −2p + 10(1 − p) = 10 − 12p průměrný zisk holubice je: zh = 0p + 3(1 − p) = 3 − 3p převažují jestřábi (p je blízko jedné) ⇒ je výhodnější být holubicí (zh > zj ) převažují holubice (p je blízko nuly) ⇒ je výhodnější být jestřábem (zh < zj ) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Evolučně stabilní strategie jestřáb ani holubice nejsou evolučně stabilní jaká strategie je evolučně stabilní? Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Evolučně stabilní strategie jestřáb ani holubice nejsou evolučně stabilní jaká strategie je evolučně stabilní? mixovaná strategie: chovej jako jestřáb s pravděpodobností 7/9, chovej se jako holubice s pravděpodobností 2/9 odvetník: neútočí, ale útoky oplácí Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Jestřáb a holubice Analýza hry lze realizovat systémovou dynamikou (Stella) i pomocí agentů (NetLogo), viz např. http://ccl.northwestern.edu/netlogo/models/ community/GameTheory analýza pevných bodů, dynamiky jeden z námětů na projekty Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Altruismus a evoluce Může být altruismus (evolučně) výhodný? Jak se mohlo vyvinout a udržet altruistické chování při „výběru nejsilnějších ? Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Altruismus a evoluce Může být altruismus (evolučně) výhodný? Jak se mohlo vyvinout a udržet altruistické chování při „výběru nejsilnějších ? altruismus – silný, slabý; komplikovanější pojem než se zdá altruistické chování: zisk pro ostatní ztráta pro mě (nebo neutrální stav) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Altruismus a evoluce roli hraje více jevů, zde na modelech ilustrujeme dva: vliv podmínek prostředí populační viskozita (omezené šíření populace v prostoru) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Buněčný automat Altruismus – buněčný automat NetLogo: Social Science / Altruism 2D model, pravděpodobnostní buněčný automat každá buňka používá jednu ze dvou strategií: altruistická, sobecká výběr strategie na další kolo: losováním s přihlédnutím k úspěšnosti agentů v okolí („ruleta ) podmínky prostředí: nemoci, využitelnost Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Buněčný automat Altruismus: ohodnocení c „cena altruismu , jak moc mě altruistické chování stojí b „zisk z altruismu souseda , jak moc mi pomůže altruistické chování mého souseda NA počet altruistických buněk v okolí, včetně sebe samé zisk: pro sobeckou buňku: 1 + b · NA/5, pro altruistickou buňku: 1 − c + b · NA/5. Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Buněčný automat Altruismus: analýza modelu za dobrých podmínek prostředí dominuje sobecká strategie za zhoršených podmínek prostředí dominuje altruistická strategie Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Model s agenty Krávy: popis modelu NetLogo: Social Science / Cooperation základ standardní: krávy žerou trávu různá rychlost dorůstání trávy podle délky sobecké krávy: sežerou všechnu trávu, co je k dispozici spolupracující krávy: vždycky trochu trávy nechají (aby rostla rychleji) Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Model s agenty Chování podle podmínek prostředí vítězí buď sobecké či spolupracující rychlost růstu trávy energie trávy rychlost přesunu krav větší „populační viskozita ⇒ spolupráce Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Otevřená evoluce evoluce nesměřuje k předem danému „vrcholu koevoluce – každý se snaží „vylézt co nejvýš v aktuální krajině (která se však mění) modely evoluce (např. genetické algoritmy) – většinou dodáváme externí míru zdatnosti jak modelovat opravdu otevřenou evoluci? Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Tierra http://life.ou.edu/tierra/ model digitálních organismů prostředí = virtuální počítač organismy = jednoduché programy soutěží o dostupné zdroje: procesorový čas ∼ energie procesorová paměť ∼ materiál Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Programy sekvence jednoduchých instrukcí: 32 různých 5-bitových instrukcí v zjednodušeném assembleru prapředek – jednoduchý program, který kopíruje sám sebe (ručně vytvořen) dál klasický genetický algoritmus (křížení, mutace) kopírování a míra zdatnosti zadány implicitně – zdatný je ten, kdo se zvládne množit Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Dynamika paraziti využívají pro svoje kopírování zdrojový kód jiných programů jejich vlastní kód je kratší a tím jsou úspěšnější hyperparaziti zneužívají parazitů využijí toho, že parazit zavolal jejich kód, a pak už mu volání nevrátí zpět Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Ilustrace Následující ilustrace: červená: základní organismus žlutá: parazit modrá: imunní organismus video: https://www.youtube.com/watch?v=8jd9U8NtzxY Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Tierra: shrnutí bohatá a zajímavá dynamika existují rozšíření ale i tak se vývoj vždy zastaví nedochází tedy k opravdu otevřené evoluci Úvod Modelování evoluce Evolučně stabilní strategie Evoluce a altruismus Otevřená evoluce Tierra Shrnutí pojmy, principy: koevoluce evolučně stabilní strategie evoluce a altruismus otevřená evoluce modelovací přístupy: genetické algoritmy agenti teorie her matematické analýzy