Evoluční algoritmy a umělý život

Evoluční algoritmy a umělý život Roman Neruda Ústav informatiky AVČR [email protected] Olomouc, červen 2012

Od Darwina a Mendela ...

... k inteligentním agentům.

Umělý život

Odkazy: ●

Steven Levy: Artificial life. Pantheon books, New York, 1992.

●

http://www.alife.org

●

http://www.his.atr.co.jp/~ray/

●

http://dllab.caltech.edu/avida/

●

http://biota.org/ksims/

●

http://www.frams.alife.pl/

●

http://www.cs.brandeis.edu/~zippy/alife-library.html

Podstata života ? 

Kombinace 4 elementů  Voda,

vzduch, oheň, zem (Empedokles)



Duše/psyche/anima  (Demokritos) 3

 

duše (Aristoteles)

Nic (Descartes) Élan vital (Bergson)  Elektřina

(M. Shelly)

Dnešní biologie 

Živé organismy … lze charakterizovat jako strukturálně vysoce složité, hierarchicky uspořádané, termodynamicky otevřené a autoregulující se nukleoproteinové soustavy, jejichž podstatnými vlastnostmi jsou metabolismus, autoreprodukce a schopnost vyvíjet se. (Rozsypal a kol, 1994)







Things with the capacity for metabolism and motion. Life is a self-sustained chemical system capable of undergoing Darwinian evolution. Life is matter that can reproduce itself and evolve as survival dictates.

Artificial life ●

… reprodukce

A-life, život jaký by mohl být 





Studuje základní rysy, procesy a zákony života Pomocí počítačových modelů, hardwarových robotů a biochemických technologií „Soft, hard, wet“

Silný a slabý ALife 

Umělý život Život je abstraktní proces, který nezávisí na médiu (Von Neumann)  Slabý: Život je jen biologický, sw a hw simulace nám objasňují jeho mechanismy.



 Silný:

Umělá inteligence  Silná:

cílem je stvořit umělý „myslící“ systém  Slabá: systémy, které se chovají v určitém kontextu „inteligentně“   

Umělé neuronové sítě Evoluční algoritmy Symbolické uvažování

Logika reprodukce

Celulární automaty 

Von Neumann:  Sebereplikující

se

roboti  Matematický model – CA  Studium chaotického chování, emergence 

Řád chaosu 

Lindenmayerovy systémy Popis rostoucích struktur pomocí formálních gramatik  Nástroj k modelování růstu rostlin, …  (X → F-[[X]+X]+F[+FX]X), (F → FF) 

Hejna, stáda, roje 

Craig Reynolds: boid Pohyb hejn ptáků se dá popsat 3 jednoduchými pravidly  Aplikace v počítačové grafice  Aplikace v řešení úloh umělé inteligence 



Mravenčí algoritmy: nepřímá komunikace

Evoluce a adaptace

Tierra, svět je operační systém 

T. S. Ray – simulace ekologických vztahů v počítači:  Živočich

= sebereplikující se software  Zdroje = paměť a čas procesoru  Evoluce = mutace, vymírání  Parazitismus

Karl Simms, operační systém je svět 

Karl Simms: 

 



vývoj abstraktních organismů s reálnými fyzikálními zákony Řízení neuronovou sítí Emergence chování – pohyb, plavání, …

V 90.letech superpočítač, dnes PC (3DVCE)

Golem, roboti už jdou 





Spojení evoluce a 3D tiskárny Evoluce robotických „živočichů“ řízených umělou neuronovou sítí v SW simulátoru Realizace a testování v HW prototypu

Budoucnost patří bakteriím? 

Martyn Amos: DNA computing Zákodujme problém do DNA,  Nechme přírodu počítat 

 

Bio-počítač hraje piškvorky Řešení problému obchodního cestujícího pomocí svítící E.coli

Umělá inteligence

2 problémy ●

●

Umělá: –

člověk s čipem v mozku,

–

geneticky modifikované organismy

Inteligence: –

schopnost individua účelně jednat, rozumně myslet a efektivně se vyrovnávat se svým okolím

–

a. The capacity to acquire and apply knowledge.

–

b. The faculty of thought and reason.

Turingův stroj a test ●

Alan Turing – základy teorie výpočtů,

●

Turingův stroj

●

Turingův test:

●

Poznat muže/ženu

●

Poznat člověka/stroj

●

Eliza

●

Paradox čínského pokoje

Umělá inteligence ●

Inteligentní chování

●

Učení

●

Schopnost adaptace

●

–

●

● ● ●

Symbolická Expertní systémy, formální logika

“Výpočetní”

Řízení

–

Neuronové sítě

Plánování

–

Evoluční algoritmy

Rozpoznávání (řeč, písmo, obrázky)

–

Fuzzy logika

Evoluční algoritmy

Odkazy: ●

●

●

● ●

Holland: Adaptation in natural and artificial systems, MIT Press, 1992. Goldberg: Genetic algorithms in Optimization, Search and Learning, Addison-Wesley, 1989. Koza: Genetic Programming, I-III, MIT Press, 1992, 1994, 1999. Mitchell: Introduction to GA, MIT Press, 1996. Hitch-hiker's guide to EC: http://www.faqs.org/faqs/ai-faq/genetic/

Princip Genetických Algoritmů ●

Gen = zakódované řešení problému

●

Fitness

●

Populace genů

●

Selekce: –

Ruleta

–

Turnaje

●

Mutace

●

Křížení

Genetické programování ● ●

Evoluce programů Reprezentace syntaktickými stromy

●

S-expressions, LISP

●

Křížení,

●

Mutace,

●

Procedury

Proč evoluce funguje? ●

Mutace = náhodné změny

●

Selekce = ”pohyb správným směrem”

●

●

Věta o schématech: GA rekombinují kompaktní parciální řešení při hledání optima. Nadějná řešení se množí exponenciálně. Implicitní paralelismus: GA s n jedinci v populaci pracuje zhruba jako n3 izolovaných hledačů.

●

Křížení: výměna informací

●

Zabraňuje uvíznutí v lokálních minimech.

Umělé neuronové sítě

Odkazy: ● ●

●

●

●

Haykin: Neural Networks, Prentice-Hall, 1999. Hecht-Nielsen: Neurocomputing, Addison-Wesley, Boston, MA, 1989. Šíma, Neruda: Teoretické otázky neuronových sítí, Matfyzpress, 1996. http://www.gc.ssr.upm.es/inves/neural/ann1/anntut orial.html http://dsl.serc.iisc.ernet.in/~vikram/nn_intro.html

Perceptron ●

●

1943: McCulloch, Pitts: formální neuron 1958: Rosenblatt: perceptron –

Lineárně separabilní

–

Učící algoritmus

–

Důkaz konvergence

–

Hardware

XOR ●

1969: Minsky, Pappert: Perceptrons. –

Neumí XOR

–

Sítě s více vrstavmi asi nejde učit

–

Konec NS na 15 let

–

Kohonen, Hopfield, Grossberg, Amari, Rusové

Back Propagation ●

● ●

●

●

Učení sítě = nastavení hodnot vah dle tréningové množiny Učení s učitelem Nelineární optimalizace - minimalizace chyby Metoda největšího spádu, apod. Derivaci dE/dw lze odvodit

Roboti

Khepera (2000 př.n.l.)

Khepera (2000 n.l.)

Khepera HW ●

průměr 7cm, výška 3cm

●

váha 80g, uveze 250g

●

rychlost 0,02 m/s – 0,5 m/s

●

procesor Motorola 68331, 25MHz

●

512KB RAM

●

2 servo motorky

●

8 aktivních infra čidel (5cm dosah)

●

moduly (věže) pro komunikaci, zrak, hmat

Jak řídit Kheperu pomocí NS

Jak učit NS pomocí GA ●

Učitel nehodnotí každý krok (nejde to)

●

Evidují se 'správné' a 'špatné' typy chování

●

To je zakódováno v účelové funkci (fitness) GA

●

Hlavní problém GA v ER: volba fitness –

obecná vs. konkrétní

–

více kritérií najednou(multiobjective optimization)

●

Softwarová simulace

●

Desítky pokusů, stovky jedinců, tisíce generací

Úloha: Prohledávání bludiště ●

Nejprve malé bludiště

●

Dobré chování: –

Nenaráží do stěn

–

kolečka se točí (stejným směrem)

–

prohledává prostor

●

Vyvine se optimální strategie pohybu v bludišti

●

Není závislá na konkrétním prostředí

●

Robot si nic nepamatuje

Úloha: Dělejte to ve skupině ●

●

Více robotů se má koordinovaně pohybovat ve skupině Nenarážet do sousedů –

rozeznat jiného robota od stěny není pro krátkozrakou Kheperu jednoduché

–

musí proaktivně zkoumat z různých úhlů

●

Následovat vůdce (má na zádech žárovku)

●

Robustnost - všichni ve skupině mají stejný 'mozek'

●

Důležité: Kdokoliv může být vůdcem

Budoucnost ?

Inteligentní agenti

Wearable computing

Kyborgové?

●

●

●

V rámci umělé inteligence: hybridní metody –

Soft computing: EA+NS+Fuzzy

–

Soft + tradiční UI (symbolická)

–

Soft + hard computing (numerika, statistika)

V IT: inteligentní (adaptivní) agenti –

Autonomní software,

–

Mobilní, komunikativní, sociální

–

Nálady, emoce, model dle lidské mysli

Kolem nás: všudypřítomné počítače –

●

Smart devices, ubiquitus, wearable computing

V nás: Kyborgové, DNA computing (?)