Post on 20-Jun-2015
description
transcript
Artificial LifeAdam Abonyi
Artificial Life• 1986 - Christopher Langton poprvé pojmenoval
obor zvaný „Artificial Life“ na Mezinárodní konferenci o Syntéze a Simulaci živých systémů.
• Alife je obor (i druh umění) studující systémy spojené s životem, jeho procesy a evolucí za použití simulací počítačových modelů, robotiky a biochemie.
Artificial Life• Tři druhý Alife podle přístupu:
o Soft (software)o Hard (hardware)o Wet (biochemická)
• Snaží se napodobit klasickou biologii tak jak jí známe
• Nejčastěji se pojmem artificial life myslí soft alife
Artificial Life• Studuje logiku „živých“ systémů v umělých
prostředí. A snaží se pochopit, co se v nich děje.
• Agentní systémyo studium chování skupiny agentů
Artificial Life – filozofie
modelování• „Life as we know it“
o Biologický model, zachycuje jen nejdůležitější parametry
• „Life as it could be“o Jednoduché principy, které používá v simulacícho Lze analyzovat nové (i neočekáváné) systémy
Artificial Life• Christopher Langton
"Artificial life is the study of man-made systems that exhibit behaviors characteristic of natural living systems. By extending the empirical foundation upon which biology is based beyond the carbon-chain that has evolved on Earth, Artificial Life can contribute to theoretical biology by locating life-as-we-know-it within the larger picture of life-as-it-could-be."
• Daniel Dennett„... evolution will occur whenever and wherever three conditions are met: replication, variation (mutation), and differential fitness (competition)“
Techniky• Celulární automaty
o Provopočátky, Conway’s Game of Life o 1969 - Konrad Zuse – Calculating Space
• Žijem ve vesmíru určeném deterministickým výpočtem na velkém celulárním automatu
• Neuronové sítěo Mozek agenta o Simulace dynamiky populace, která je schopná učenío Vliv okolí mění chování agenta
• Evoluční algoritmyo Organismy se replikujío Schopnost a efektivita replikace určena fitness jedinceo Interakce s prostředím
Core Wars• Napsaná v zjednodušeném assembleru
• Programy (vojáci) soupřeí o místo v paměti
• Vítězí program, který ukončí všechny procesy soupeře (zavolá instrukci ukončení, či dělí nulou)
• Strategieo Replicator, Bomber, Scanner,..
• Rasmusseno Přidal mutacio Kolaps systému,
přepisováním programu - znemožněna replikace
Tierra• 1990 – Thomas S. Ray (ekolog)
• První úspěšný systém
• Replikující se, mutující a evolvující se programy spolu soupeřío O životní prostor (paměť)o O prostředky (CPU time)
Tierra• Evoluce neobsahuje fitnes funkci, program žije
nebo umře• Umožňuje „open-end“ evoluci. Vliv prostředí se
může měnit• Později se ukázalo, že se programy v Tierra-like
systémech časem přestanou evolvovat (nebo se zacyklí) – open end se nekoná
Avida• Inspirované Tierrou
Charles Ofria, Chris Adami, C. Titus Brown (1993)
• Jedinci mají vlastní CPU, ale využívají ho různou rychlostí, simulace paralelního vývoje
• Komplexnější životní prostor
• Evoluce řešení matematických problémů bez předem určeného postupu
Creatures• Učíte Norny mluvit, jíst, bránit se...
• Každý Norn má vlastní DNA
• Norny lze křížit. (genetika se chová jinak než jak jí známe)
• První komeční program, který koduje alife od genetické úrovně výš. Za použití biochemie a mozku z neuronových sítí.
Tierra - jedinec• Každý jedinec má svůj proces
o Pointer na instrukcio Registryo Zásobník a pointr na zásobníko ...
• Instrukční sadao Výpočetně úplnáo Program bude vždy korektní (chybné instrukce ignorovány)o Instrukce atomickéo Adresování pomocí šablon
Tierra – genetická operace
• MutaceA. Podle vzniku
• Replikace, kopírování – vyšší ppst.• „Kosmické záření“ – nižší ppst.
B. Podle typu• Změna jednoho bitu instrukce• Náhodná výměna jedné instrukce
• Kombinace genůo Během vytváření jedince
A. Křížení B. VloženíC. Vymazání
Tierra – další operace• Chyby
o Simulují občasnou nesprávnou funkci
• Přírodní katastrofao Lze v určitých intervalech zlikvidovat část populace
Tierra – virtualní stroj• Operační systém
o Slicer – kruhová fronta procesů, který dostáváj procesorový čas
o Reaper – fronta procesů, řídí životní cyklus• Při replikaci je jedinec posunut dozadu• Při chybě je posunut dopředu• Zabijení jedinců podle pořadí ve frontě + náhodně• Kód mrtvých jedinců ponechán v paměti
o Alokátor paměti – přidělení paměti k vytvoření potomka• Právo zapisovat do své paměti má jen samotný jedinec či rodič• Jiní jedinci mohou cizí paměť číst či vykonávat
Tierra – prostředí• Cyklycký, pevně omezený lineární prostor• Jedinci soupeří o prostor v paměti a procesorový
čas• Schopnost přežít závisí i na okolních jedincích
• Na počátku do paměti umístěn jedinec schopný replikace
• Paměť se postupně naplňuje jedinci, dochází k mutacím
• Preference krátkých gen. kódů
Tierra• Parazité
o Krátký kód – nejsou schopni se sami replikovat, k replikaci používají kód jiných jedinců
• Imunita, rezistence prazitů vůči imunitě• Hyperparasitismus
o Parazit donucen replikovat kód jedince místo svého vlastního kóduo Vede k homogenní populaci jedinců vyvijejících se bez přirozeného
nepříteleo Vede k sociálnímu chování
• Sociální chovánío Kooperace při replikacio Noví parazité zneužívají kooperující jedince (homogení jedinci jsou silně
náchylní k novému druhu parazita)
Tierra – vývoj parazitů
Jedinci(červení) převažují Parazité(žlutí) se začínaj množit
Immuní jedinci(modří) se začínaj množit
Immuní jedinci převládají. Původní jedinci pomalu mizí,
parazité brzou vyhladoví
Avida• Lineární paměť nahrazena 2D mřížkou (toroid)
o Umožňuje lokální vývoj, vede k větší diverzitěo 8 sousedů, preferovaný směr při hledání šablony při skocícho Při dělení edince je potomek umístěn na některé ze sousedních míst
Avida - jedinec• Menší instrukční sada – 26 instrukcí
o Instrukce atomické, neexistence atomického programu (stejné)o Skoky pomocí šablono Některé další modifikace vykonávaných funkcí
• Genomo Cyklycký seznam instrukcío Virtuální stroj
Avida – virtuální stroj
Avida – jedinec• Replikace
o Alokace paměti pro potomka s právem zapisovato Okopírování jedinceo Oddělenío Uvedení rodiče i potomka do počátečního stavu
Avida - jedinec• Mutace
o Během kopírovánío Během oddělování potomka – vložení nebo vymazání části genetického
kóduo Bodové mutace – i během vykonávání programu, čím déle program
běží, tím je náchylnějšío Implicitní mutace – nesprávný algoritmus replikace
Avida• Fenotyp
o Interakce s prostředím – čísla, operace s čísly a vypisování výsledkůo Počet kroků nutný k vytvoření potomkao Čas přidělený jedinci (rychlost procesoru)o Celkový procesorový čas přidělený celé populaci je pevně omezen
• Genotyp - diferenciace
Avida• Parasitismus
o Parazité jako u Tierry nejsou povolenio Vložení kódu do sousedního jedince
• Využití procesorového času daného jedincea) Využití celého času – zabití hostiteleb) Využití části času – pomalejší šíření, zachování hostitelského
organismu
Avida – evoluce komplexních
funkcí• Darwin – evoluce složitějších systémů probíhá
postupně, od jednodušších přes různé přechodné stavy
• Jedinci získávají energiio Časové jednotky pro vykonávání instrukcí
• Úměrně délce genomu• Odměny za vykonávání logických operací
o Mezi instrukcemi jediný logický operátor nando Odměnu lze získat jen jednou (za každou operaci)
• Evoluce operace rovnosti (bitové porovnání dvou čísel)o Nejsložitější logická operace. Max dva vstupyo Nejkraší napsaný kód – 19 instrukcí
Avida – evoluce komplex. fcí
• Počáteční jedinec – replikace, 50 instrukcí............16 tisíc generací............Dominantní jedineco 83 instrukcío Všechny logické operace včetně rovnosti
Avida – evoluce komplex. fcí
• Prozkoumání prvního jedince, u kterého se objevil výpočet rovnostio 103 jednoduchých, 6 dvojtých a 2 trojité mutaceo 45 mutací zvýšilo fitness, 48 neutrálních, 18 škodlivých (vůči rodiči)o Dvě z mutací snížily fitness o víc než 50% vyžazení NAND, pouze dva
jedinci v populacio Další mutace vedla bezprostředně k operaci rovnosti
• Odstranění této mutace vedlo k nefunkčnosti• Fatalní nedostatek vedl k bezkonkurenční výhodě v další generaci
o 35 instrukcí pro rovnost, 22 pro jednodušší funkce, 3 nutné zároveň pro replikaci
• Celkem 50 pokusů, stejné podmínky• Rovnost ve 23 případech (různé metody)
o 49 – 356 instrukcí
Avida – evoluce komplex. fcí.
• Omezení prostředío Jedna nebo dvě jednodušší logické funnkce nebyly odměňovány – ve
34% populací se rovnost vyvinula• Žádná z log. funkcí nebyla přímo nutná k evoluci rovnosti
o 50 populací bez odměňování jednodušších funkcí• Rovnost se neobjevila ani v jednom případě• Zmenšování genomu, rychlá replikace
• Komplexní funkce se vyvijejí z jednoduššícho Jednodušší funkce prospěšné samy o sobě
• Evoluce nepostupuje přímočaře k lepším jedincům
Evoluce• Evoluce „s otevřeným koncem“
o Některé formy života evolučně stabilní, jiné se vyvijejío Nárůst komplexity, reakce na měnící se prostředío Nutná koevoluce více druhů
Evoluční dynamika• Bedau, Packard - Evoluční dynamika biologikcých
systémů je odlišná od dynamiky alife
• Evitao Systém podobný Aviděo Omezená interakce jedinců, zakázaný parazitismus