# Zkouška

u zkoušky se objeví čtyři otázky; mrkni na [teorii, která se zkouší nejčastěji](zkousena-teorie.md)

## Úvod

- historie robotiky
	- automatizace už ve starověkém Řecku – když dohořela zápalná oběť, tak se otevřely dveře chrámu
	- biskup Albertus Magnus: kovový sluha
	- da Vinci: mechanický rytíř
	- Descartes: Ma fille Francine
	- mechanická kachna
	- R.U.R.
	- Elektro – robot pro světovou výstavu v New Yorku, 1939
	- pes Sparko
	- průmyslové manipulátory
	- Shakey – Stanford, 1960
	- Khepera – dá se použít i k hardwarové evoluci
		- e-Puck – varianta Khepery
	- Honda: robot ASIMO
- jak vypadá evoluční vývoj
	- máme robota, ten se pohybuje v nějakém světě
	- definujeme úlohu, např. má hledat nějaký objekt v tom světě
	- jeho řízení zakódujeme do chromozomů – jeden chromozom kóduje celý řídicí systém
	- tak jsme dostali nultou generaci
	- vyzkoušíme každý chromozom, ohodnotíme je fitness funkcí (podle toho, jakých dosahovali výsledků)
	- přechod k další generaci
		- selekce (vybereme ty nejlepší)
		- reprodukce (např. křížení)
		- mutace
- alternativy k evoluční robotice
	- behavior-based robotics (robotika založená na chování)
		- robot má sadu několika základních chování, ta mezi sebou interagují
			- příklady chování: plním konkrétní úkol, hledám potravu, …
			- dochází mi energie → musím hledat potravu (na úkor plnění úkolu)
		- chování spolu můžou soutěžit
			- kompetitivní koordinace – jeho řízení vítězí → subsumption method
			- kooperativní koordinace – jednotlivá řízení přispívají k celkovému výsledku
		- vnímání je těsně navázané na akce – při generování reakce se nepoužívá abstraktní reprezentace světa
		- hierarchie chování
	- robotické učení
		- řídicí systém se učí pomocí neúplných dat a generalizuje
		- typicky se učí zobrazení, které mapuje vstupy senzorů na výstupy motorů
		- týká se pouze řízení (kdežto evoluční robotika se může zabývat i návrhem konstrukce robota)
	- umělý život
		- simulace světa, kde se pohybuje více organismů
		- cílem je vyvinout systém, který se dokáže přizpůsobit změnám prostředí
		- vychází z teorie dynamických systémů – lokální interakce prvků na nižší úrovni vede ke globálnímu chování na vyšší úrovni
		- modely „umělého života“ jsou asi poměrně abstraktní – kdežto evoluční robotika se zaměřuje na reálné roboty
- k čemu by to mohlo být dobré
	- evoluce by nám mohla pomoct navrhnout řízení i morfologii robota, aby mohl řešit úlohu
	- můžeme se inspirovat přírodou a naopak – možná nějaké takové mechanismy zpětně objevíme v přírodě
	- přístupy k návrhu řídicích systémů – rozdělení na podúlohy
		- klasický – perception, planning, execution
		- behavior-based – rozdělení do jednotlivých základních chování
		- evoluční – necháme to na evoluci
	- příklad: chceme najít předmět v bludišti a zůstat tam
		- je snadné určit jednotlivé úlohy, které robot musí plnit, ale je těžké je zkombinovat
		- evoluční robotika tohle řeší (nehledají se podúlohy, pouze jedno globální chování)
	- evoluční robotika může čerpat z oborů, které popisují chování živočíchů na různých úrovních
		- superorganismus: evoluční biologie, ekologie, sociologie
		- organismus: psychologie, neurologie
		- suborganismus: anatomie/fyziologie, biologie buňky, genetika, molekulární biologie
	- biologie
		- přirozená evoluce – jak je možné, že se vyvinula taková spousta úspěšných forem života?
		- chceme vytvořit podobně úspěšnou umělou evoluci
		- v přírodě funguje jedno kritérium – přežití druhu (schopnost reprodukce)
- bootstrap problém (problém inicializace)
	- když náhodně vygenerujeme řídicí systémy, neřeší problém → skóre 0
	- evoluce se nemá čeho chytit
	- možná řešení
		- inkrementální evoluce
			- začneme s jednodušší úlohou, postupně přidáváme obtížnost, až se dostaneme k reálné úloze
			- je jednodušší upravovat výběrové kritérium (fitness funkci) než navrhovat přímo řízení
			- zvláštní případ: koevoluce
				- např. dravec a kořist
				- dravec se snaží ulovit kořist, kořist se snaží utéct před dravcem
				- vlastně závody ve zbrojení
				- neměníme kritérium, ale stejně dochází k postupnému zlepšování
		- celoživotní učení
			- jedinec umí využívat senzorické vjemy, učí se, adaptuje svoje řízení
			- evolucí můžou vzniknout dva druhy jedinců schopných dobře fungovat v proměnlivém prostředí
				1. plastic general (učenlivý) – nemá obecnou strategii, ale umí se přizpůsobit prostředí
				2. full general (umí všechno) – má obecnou strategii vhodnou pro různé typy prostředí → nemusí se přizpůsobovat
			- někdy se full general jedinec nedá vytvořit (nebo je moc složitý)
		- evoluce zobrazení z genotypu na fenotyp
			- v přirozené evoluci se to zobrazení evolučně vyvíjí, v umělé evoluci to obvykle zadává autor experimentu
- využití
	- nemusíme navrhovat každý detail, něco za nás řeší evoluce – někdy najde překvapivá řešení
	- může spolu interagovat biologie a robotika – např. v rojové robotice
	- evoluční biorobotika
		- biorobotika – stavění modelů, které se podobají živým organismům (např. mečoun)
		- pomocí evoluční robotiky se robot naučí řízení
	- vývojová robotika
		- jak se mládě vyvíjí v dospělce?
		- mohl by se podobně vyvíjet robot?
		- proces dospívání
		- snažíme se vyvinout robota, který je schopný se doučit, dorůst
	- evolučně-vývojová robotika (evo-devo-robo)
		- zkušení jedinci můžou ovlivňovat méně zkušené
		- v přírodě: postupná evoluce pohybu po souši
			- mládě se plazí, dospělec kráčí
			- později dojde k přeskočení plazení a jedinec rovnou kráčí
		- robotické organismy z krychlí s klouby
	- rojová robotika
		- koordinace robotů ve skupině
	- modulární robotika
		- moduly se můžou spojovat do větších celků podle potřeby
	- měkká robotika
		- kombinace pružných a pevných dílů, velká flexibilita pohybů
		- zvednutí vajíčka pomocí (pod)tlaku vzduchu

## Evoluční algoritmy

- genetické algoritmy
	- populace umělých chromozomů se cyklicky podrobuje selektivní reprodukci, která upřednostňuje výkonnější jedince, a náhodným změnám
	- umělý chromozom (genotyp) = řetězec symbolů kódující vlastnosti jedince (fenotyp)
		- může to být binární hodnota proměnné nebo posloupnost hodnot proměnných
		- mnoho typů kódování (binární, Grayův kód, reálná čísla)
			- Grayův kód – dvě čísla v posloupnosti se liší o jeden bit
				- je jednoduché ho sestavit (opíšu v opačném pořadí, doplním o nuly a jedničky)
				- příklady: 1, 0; 10, 00, 01, 11
		- abecedy – např. binární, ternární, …
	- fitness funkce – kritérium výkonosti (zobrazení: genotyp → reálné číslo)
	- obecný algoritmus
		- vytvoř populaci $N$ náhodně vygenerovaných chromozomů
		- opakuj: 1) dekóduj všechny chromozomy a spočítej jejich fitness, 2) vytvoř novou populaci
		- skončí, když se objeví hledaný jedinec (který plní úlohu) nebo když to trvá dlouho…
- Hillclimber – gradientní algoritmus
	- $N=1$
	- novou populaci tvoříme tak, že zmutujeme chromozom a nahradíme jim ten původní, pokud má lepší fitness
	- nemůže nastat zhoršení
	- $\mu$ … pravděpodobnost mutace
	- najde jenom lokální maximum
	- možná řešení
		- začít z různých pozic
		- dovolit zhoršení fitness (simulované žíhání)
	- simulované žíhání
		- velikost kroku i směr závisí na teplotě, která se postupně snižuje
		- pravděpodobnost přijetí zhoršení fitness (= teplota) se s časem zmenšuje
		- na začátku jsou kroky téměř náhodné
		- po ochlazení v podstatě deterministické
- jednoduchý genetický algoritmus (Goldberg)
	- víc než 1 chromozom v populaci
	- selektivní reprodukce, křížení, mutace
	- algoritmus
		- vytvoř populaci $N$ náhodně vygenerovaných chromozomů
		- opakuj
			- dekóduj všechny chromozomy a spočítej jejich fitness
			- vytvoř novou populaci selektivní reprodukcí
			- rekombinuj chromozomy (křížení)
			- mutuj chromozomy
		- skonči, když se objeví hledaný jedinec (který plní úlohu) nebo když fitness nejlepšího neroste
- jednoduchá selekce
	- čím lepší jedinec, tím více jeho kopií se může objevit v nové populace
	- reprodukce ruletou
		- každý jedinec dostane výseč kruhu úměrnou své fitness funkci (musí být nezáporná)
		- výseč ~ pravděpodobnost, že bude reprodukovaný
		- ruletou se otočí $N$-krát
	- problémy
		- všichni mají podobnou fitness → náhodné prohledávání (nic moc se neděje)
		- jeden jedinec (nebo dva) má obrovskou fitness → téměř všichni v populaci budou kopií toho stejného jedince
	- řešení
		- škálování – zvětšení nebo zmenšení rozdílů
		- selekce podle pořadí (rank based) – nezáleží na konkrétní hodnotě fitness
		- rank based s ořezáváním – nejlepších $M$ zkopírujeme $O$-krát, aby $N=M\times O$ (vlastně zahodíme spodní část seznamu)
		- turnajová selekce – náhodně se vyberou dva jedinci, ten lepší jedinec s určitou pravděpodobností vyhraje a bude zkopírován (jinak ten druhý)
	- elitismus – nejlepší jedinci se beze změny zkopírujou (abychom nepřišli o dosud nejlepší řešení)
		- podobný koncept (používá se v koevoluci): síň slávy (nejlepší jedinci ze všech předcházejících generací)
- křížení
	- jedinci jsou náhodně spárováni a každý pár je s danou pravděpodobností zkřížen
	- jednobodové nebo vícebodové křížení
- mutace
	- abychom měli možnost prohledat celý prostor
	- aby nám algoritmus nekonvergoval příliš brzo
	- uniformní mutace – každý znak každého jedince je s určitou pravděpodobností nahrazen náhodným znakem
- nedeterminismus
	- GA je nedeterministický, používá náhodné veličiny
	- typicky se sleduje průměrná a maximální fitness, aby se GA mohl ve vhodnou chvíli zastavit (nebo se zastavuje po dosažení určitého počtu generací)
	- GA se pouští opakovaně se stejnými nebo pozměněnými parametry
	- výsledkem je nejlepší jedinec vybraný z finálních generací ze všech běhů GA
- fitness krajina (fitness landscape)
	- tvar fitness funkce – v mnohadimenzionálním prostoru
	- chceme, aby se fitness postupně zvětšovala
- schémata
	- schéma – oproti chromozomu má jeho abeceda jeden prvek navíc (typicky hvězdičku $*$)
	- je to jakoby maska popisující víc chromozomů
	- schéma s $r$ hvězdičkami reprezentuje $k^r$ řetězců ($k$ je velikost původní abecedy)
	- každý řetězec délky $m$ je reprezentovaný $2^m$ schématy
	- $o(S)$ … řád schématu – počet pevných symbolů (různých od $*$)
	- $\delta(S)$ … definiční délka schématu – vzdálenost mezi první a poslední pevnou pozicí ve schématu
	- $\phi(S,t)$ … fitness schématu v čase $t$ (průměrná fitness řetězců reprezentovaných daným schématem)
	- $\xi(S,t)$ … počet řetězců v populaci $P(t)$, které jsou reprezentované schématem $S$
	- kolik jedinců určených daným schématem bude v dané populaci?
		- jak schéma ovlivní selekce?
			- $\xi(S,t+1)=\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}$
			- kde $\bar F(t)$ je průměrná fitness populace $P(t)$
			- tedy „nadprůměrné“ schéma pokryje v následující generaci více řetězců (jejich počet roste geometrickou řadou)
		- jak schéma ovlivní křížení?
			- když křížím jedince ze stejného schématu, tak jsou pokrytí i potomci
			- když je jeden rodič mimo schéma, tak potomek může být mimo schéma
				- ale záleží, kde se kříží (viz hvězdičkový prefix/suffix)
			- pravděpodobnost zničení schématu křížením je $\leq\frac{\delta(S)}{m-1}$
			- takže pravděpodobnost zachování příslušnosti ke schématu je $\geq 1-p_k\cdot\frac{\delta(S)}{m-1}$
		- co mutace?
			- musí se změnit jeden z pevných symbolů schématu
			- tj. pravděpodobnost, že mutace zachová schéma je $(1-p_m)^{o(S)}\approx 1-o(S)\cdot p_m$
				- aproximace funguje, protože $p_m$ je hodně malé (takže v součtu podle binomické věty budou dominantní první dva členy, kde figuruje $p_m^0$ a $p_m^1$)
		- tedy $\xi(S,t+1)\geq\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}\cdot (1-p_k\cdot\frac{\delta(S)}{m-1})\cdot (1-o(S)\cdot p_m)$
		- $\geq\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}\cdot (1-p_k\cdot\frac{\delta(S)}{m-1}-o(S)\cdot p_m)$
			- schéma $S$ přežívá dobře, pokud má malé $\delta,o$
	- věta o schématech
		- krátká nadprůměrná schémata s nízkým řádem pokrývají exponenciálně rostoucí počet řetězců v po sobě jdoucích generacích genetického algoritmu
		- pozor, máme omezenou velikost populace
	- hypotéza o stavebních blocích
		- genetický algoritmus hledá řešení blízké optimu řetězením krátkých schémat
		- evoluce nefunguje dobře, když se optimum nedá poskládat z krátkých bloků
		- *není to věta*
- jsou GA dobrou simulací biologické evoluce?
	- evoluce nekončí a nezačíná vždy od nuly (bootstrapping)
		- SAGA – proměnlivá délka genotypu; značně zkonvergovaná populace se mění postupnými mutacemi, ne křížením
		- neutrální sítě – drobné náhodné změny v genotypu nemusí měnit fitness, ale můžou populaci posunout jinam
	- další variace GA spojené s dospíváním a učením (fitness se mění v průběhu života jedince)
	- co se nemění – genetická reprezentace jedince, interakce s prostředím
- vylepšení GA
	- dělení na druhy
		- definuje se vzdálenost – míra podobnosti jedinců
		- křížení jenom v rámci druhu
		- ochrana nových druhů – jedinec má čas, aby se zdokonalil
			- po omezenou dobu od vzniku nového druhu se při selekci jedinců zohledňuje jenom fitness v rámci jejich vlastního druhu
	- proměnlivá velikost populace
		- optimální velikost populace se těžko určuje
		- stárnutí – jedinec je po určitém počtu generací vyřazen
			- těžko se nastavují parametry
	- kódování – různé přístupy
		- konečná doména – pevný počet bitů
			- potenciální problém: pro rozlišení pěti prvků potřebujeme tři bity, ale tím dostaneme osm prvků
		- celá čísla – binární, Grayův kód
		- reálná čísla – různá kódování (omezený rozsah, pevný počet desetinných míst, plovoucí desetinná čárka)

## Neuronové sítě

- umělá neuronová síť
	- soubor neuronů propojených ohodnocenými spoji, které přenášejí signály
	- neurony: vstupní, výstupní, skryté
		- pracují paralelně
	- různé aktivační (přenosové) funkce: lineární, skoková, sigmoida, ReLU
	- architektura: dopředné šíření, rekurentní
- učení
	- s učitelem, bez učitele
	- online (spřáhnuté) × offline (dávkové)
		- upravují se váhy rovnou na základě každého vstupu nebo až najednou pro celou dávku?
	- algoritmus zpětného šíření
	- na začátku náhodné hodnoty vah, pak gradient descent (případně se používá ještě momentum)
- rekurentní neuronové sítě (RNN)
	- posuvné okénko (tzn. síť předpovídá další prvek v řadě na základě minulých $k$ prvků pro fixní $k$) někdy nestačí – potřebujeme, aby si síť pamatovala informace
	- jak si se zpětnou hranou poradí algoritmus zpětného šíření?
		- neurony zdvojíme, vystačíme si s dopřednými hranami
		- při úpravě vah klonů upravujeme váhy původních neuronů
	- LSTM, GRU
	- někdy se používá reinforcement learning
	- základní architektury rekurentních sítí
		- Elman – uchovávají se stavy ze skrytých neuronů
		- Jordan – uchovávají se stavy z výstupních neuronů
- kombinace evoluce a NS
	- NS nám zajistí hladkost prohledávaného prostoru (malá změna váhy trochu změní výstup)
	- různé úrovně granularity
		- fylogenetická – jenom GA
		- vývojová – síť doroste
		- ontogenetická – síť se učí
	- přímočaré zobrazení „senzory → motory“
	- robustnost vůči šumu
- evoluce vah a parametrů učení
	- proč
		- GA zkoušejí celou populaci sítí – ne jen jednu síť
		- nejsme omezeni architekturou ani aktivační funkcí (nemusí být diferencovatelná)
		- nepotřebujeme detailně znát výstup sítě pro každý vzor
	- kódování vah
		- řetězec reálných čísel
		- řetězec binárních čísel – jako čísla s pevnou desetinnou čárkou se zadanou přesností
			- varianta: dynamické kódování – v průběhu učení zafixujeme vyšší bity a síť se učí jen ty nižší (tzn. zajistíme jistou kvalitu řešení)
	- příklad: k analýze sonarových signálů fungoval GA lépe než zpětné šíření
	- jiná strategie: kombinace evoluce a učení s učitelem
		- zpětné šíření je citlivé na počáteční nastavení vah – GA nám ho může najít
	- gen může kódovat i hyperparametry a typ architektury
		- naopak nemusíme kódovat váhy
		- přímé (kód obsahuje přesné váhy) vs. nepřímé kódování 
- evoluce architektury
	- genetický kód může obsahovat plán budování sítě
		- posloupnost segmentů = vrstev
		- jeden segment kóduje vlastnosti uzlů (počet neuronů, aktivační funkce, geometrické rozložení) a vlastnosti spojení (hustota, parametry učení)
		- pak se použije backpropagace
		- ve fitness se dá penalizovat počet spojů nebo počet cyklů učení
	- genotyp může kódovat přepisovací pravidla – výsledkem přepisování je binární matice sousednosti (spojení) mezi neurony
	- dozrávání – síť roste v době, kdy se robot pohybuje ve světě
		- genotyp kóduje pozici neuronu, směr růstu axonů, délku axonů
		- růst závisí i na aktivitě robota
	- taky se dá dělat evoluce pravidel učení

## Evoluce programů a robotů

- genetické programování
	- genetický řetězec nekóduje řešení problému, ale program řešící problém
	- typicky to vychází z LISPovské reprezentace programů
	- postup
		- zvolí se množina funkcí $F$ a terminálů $T$
			- funkce musí být uzavřené, tj. všude definované
		- náhodně se vygeneruje počáteční populace
		- dále jako genetický algoritmus
	- křížení – vezmeme dva jedince (stromy), prohodíme jejich větve
		- tak nám vzniknou syntakticky správné programy
	- mutace – zvolí se uzel a zruší se nebo se tam vytvoří nový podstrom
		- moc se nepoužívají
	- vylepšení: automaticky definované funkce (funkce nahrazuje celý podstrom)
		- chromozom obsahuje např. 3 stromy
		- první (hlavní) strom může obsahovat reference na ten druhý a třetí
		- druhý strom může obsahovat reference na ten třetí
- alternativní přístup: gramatická evoluce
	- evoluce programu v libovolném programovacím jazyce
	- používá to lineární genom (kdežto GP používá stromy)
	- zobrazení z genotypu na fenotyp se dělá podle gramatiky
	- jak se má uplatnit pravidlo? na to se používá kodon (číslo)
		- tzn. konkrétní prvek v genotypu slouží k výběru správné pravé strany přepisovacího pravidla
		- vždycky přepisujeme nejlevější neterminál
			- tudíž ten algoritmus vlastně generuje stromy, které se zanořují doleva
	- přesný postup
		- začneme s výchozím neterminálem
		- interujeme přes prvky genetického kódu
			- zvolíme nejlevější neterminál, tomu v naší gramatice odpovídá seznam pravidel
			- aktuální prvek genetického kódu nám říká, kolikáté pravidlo ze seznamu máme aplikovat
- evoluce robotů
	- problémy
		- mechanická odolnost
		- přívod energie
		- analýza – vyvinutý řídící systém může být hodně složitý
		- časová náročnost
		- návrh fitness funkce
	- přístupy
		- evoluce fyzických robotů – Khepera
		- simulovaná evoluce – pozor, často zneužívá rozdíl mezi simulací a realitou

## Schéma evolučního experimentu

- přemístění
	- jedince umístíme na náhodné místo
	- kdybychom v simulaci recyklovali pozici, v níž skončil minulý jedinec, tak by to mohlo dalšímu jedinci ztížit podmínky
	- kdybychom používali vždycky stejnou výchozí pozici, tak by se robot mohl naučit pevnou posloupnost kroků
- simulovaná evoluce
	- fyzická evoluce trvá dlouho a různí roboti se můžou chovat různě
	- dává smysl nejdřív použít simulovanou evoluci a pak vyzkoušet nejlepší jedince na reálných robotech (abychom si byli jistí, že to vůbec funguje)
	- je důležité zvážit, jak moc má simulace odpovídat realitě
- interakce robota s prostředím (jak to modelovat v simulaci)
	- senzory a motory můžou fungovat rozdílně, i když jsou identické
	- je potřeba nějak modelovat šum
	- tělo robota a charakteristiky prostředí musejí být přesně reprodukované (mřížka jako model prostředí často nestačí)
	- často chceme sestavit *minimální simulaci* – modelovat toho co nejmíň
		- tzv. *základní množinu charakteristik* (jak robot interaguje s prostředím) musíme modelovat přesně
			- mezi pokusy se přiměřeně mění, aby bylo řízení dostatečně robustní
		- simulace má pak ještě tzv. *implementační aspekty*
			- ty neodpovídají realitě, jsou to čistě vlastnosti simulace
			- musíme je mezi pokusy měnit, aby je robot nemohl použít k „podvádění“
- charakteristiky fitness funkce
	- funkcionální × behaviorální
		- funkcionální: měří mechanické komponenty nebo interní stavy, které se podílejí na výsledném chování (např. jaká je frekvence, s jakou robot kráčí)
		- behaviorální: měří celkové efekty / výsledky chování (např. jakou vzdálenost robot ujde)
	- explicitní × implicitní
		- explicitní: říká robotovi, jak řešit úkol – přísně ohraničuje chování pomocí pravidel, která musí být splněna (např. hýbej se dopředu, udržuj 10cm vzdálenost ode zdí, netoč se na místě)
		- implicitní: sdělíme robotovi cíl, aniž bychom mu řekli, jak ho má dosáhnout (např. jak dlouho vydržel pracovat)
	- externí × interní
		- externí: dá se měřit jenom zvenku (v simulaci lze snadno použít)
		- interní: je dostupná robotovi z jeho senzorů
	- jak zvolit fitness
		- „inženýrský přístup“ – FEE (funkcionální, explicitní, externí)
		- pro neznámé a nepředvídatelné prostředí potřebujeme BII
			- to je nejlepší kombinace (teoretický ideál) – neříkáme robotovi, jak má problém řešit; evoluce má volné ruce
			- problém s implicitní fitness: může být hodně těžká pro náhodného robota (bootstrapping problem)
		- subjektivní fitness (jedinci jsou hodnoceni člověkem) → BEE
- přímý pohyb s obcházením překážek
	- lze použít Braitenbergovo autíčko
		- motory jsou přímo spojené se senzory (pomocí vážených spojů)
		- pozor, existují rovnovážné body, kde se vstupy navzájem anulují – autíčko se zastaví (ten problém řeší rekurentní spoje, ale ty se špatně nastavují)
	- můžeme uvažovat neuronovou síť bez skrytých neuronů
		- 8 vstupních neuronů (infračervené snímače)
		- 2 výstupní neurony (motory, sigmoida zajišťuje vhodný rozsah výstupů)
		- další 2 „vstupní“ neurony přenášejí výstup z minulého kroku zpátky na vstup
	- teoreticky by robot mohl couvat, ale vždy preferoval směr, kde má více senzorů
	- fitness
		- $\phi=\frac 1n\sum_k \phi_k$
		- $\phi_k=V_k(1-\sqrt{\Delta V_k})(1-i_k)$
			- fitness za $k$-tý krok
		- $V_k=|l_k|+|r_k|$
		- $\Delta V_k=|l_k-r_k|$
		- $l_k,r_k$ … rychlosti motorů
		- $i_k$ … normalizovaná hodnota nejaktivnějšího infračerveného senzoru

## Vizuální navigace, readaptace, reaktivní inteligence

- vizuální navigace
	- jak zpracovat obraz
		- klasicky – předzpracování, segmentace, hledání vzorů…
		- evolučně
	- Harvey, 1994 – portálový robot („gantry robot“)
		- kamera je zavěšená z portálového jeřábu řízeného počítačem
		- obraz přes zrcadlo, má 64 pixelů
		- vývoj SAGA
		- současná evoluce neuronové sítě a *recepčních polí*
			- recepční pole jsou popsány pomocí polárních souřadnic
			- z celého pole se rovnoměrně vybere 25 pixelů, jejich jas se zprůměruje a převede na 4bitové číslo
		- řešené úlohy
			- vyhýbání se překážkám
			- sledování pohyblivých cílů
			- rozlišování objektů
		- bootstrapping (pro úlohu nalezení bílého trojúhelníku a vyhýbání se bílému obdélníku)
			- přímá evoluce neúspěšná
			- fungovala evoluce ve 3 stádiích s různými fitness funkcemi i prostředím
				1. najdi bílou stěnu
				2. najdi bílý obdélník
				3. cílová úloha
			- problém: inkrementální evoluci musí navrhnout experimentátor
- readaptace
	- jak modifikovat řídicí systém při změnách vnějších podmínek
	- dvě úrovně
		- jedinec – využije robustnost a generalizaci neuronových sítí
		- populace – využije se různorodost jedinců v populaci
			- readaptace po změně robota
				- např. místo Khepery použijeme Koalu, protože má silnější motory
				- Koala má víc IR senzorů, tak použijeme jenom půlku z nich
			- přechod ze simulace do reality
				- úspěch přechodu může záviset na tom, jak v simulaci modelujeme šum
				- přechod ze simulace do reality je také krokem inkrementální evoluce
	- evoluce robotů je kontinuální proces s otevřeným koncem
- reaktivní inteligence
	- reaktivní systémy – senzory jsou přímo připojené k motorům a na stejný stav senzorů systém reaguje stejně
		- systém může mít pomocné stavy, které slouží k určení motorických akcí
		- vtělené systémy – mají tělo, to má nějaké vstupy a výstupy
		- situační systémy – nacházejí se v externím prostředím a můžou reagovat s tímto prostředím
	- senzorově-motorická koordinace
		- nepotřebujeme vnitřní reprezentaci prostředí / složité vnitřní stavy
		- stačí nám koordinace vnímání a akcí
	- problém nejednoznačnosti vjemů
		- může se stát, že dva objekty generují stejné vjemy, ale vyžadují různé odezvy
		- řešení: vykonáme takové akce, které vjemy rozliší
			- tzv. *aktivní vnímání* – robot může jít vjemům „naproti“
	- může se stát, že se od sebe dva různé vjemy ze senzorů dají špatně rozlišit (ale chtěli bychom je umět rozlišit)
		- to může řešit překódování stavů senzorů – zesílí se užitečné příznaky
			- typicky to řeší skrytá vrstva v neuronové síti
		- nebo to taky můžeme řešit pomocí aktivního vnímání
		- příklad: válec/stěna
			- pohyblivý robot odjel, jakmile objekt správně klasifikoval
			- takže měl paradoxně méně vjemů, kde došlo ke správné klasifikaci
		- index geometrické separability
			- chtěli bychom, aby vjemy pro stejné třídy byly blízko sebe
			- zaznamenáme si vjemy v průběhu experimentu
			- každému vjemu přiřadíme třídu
			- spočítáme podíl vjemů, jejichž nejbližší jiný vjem má stejnou třídu
	- další možné řešení: atraktor chování
		- robot na signály senzorů reaguje takovým způsobem, že na určité pozici vznikne atraktor – robot se tam nakonec dostane a bude tam oscilovat
		- je to emergentní chování, vzniká pouze interakcí agenta s prostředím
- umělá evoluce využívá omezení modelu
	- příklad: krysy hledají potravu
	- Khepera – pohybuje se po zakřivené dráze a nutně najde dlouhou stěnu
	- když odebereme omezení prostředí – např. náhodně generujeme velikost arény – tak je úloha těžší, evoluce nemůže tato omezení zneužívat

## Moduly

- modulární architektura
	- v evoluční robotice nejsou moduly nutné, ale možná budou fungovat dobře
	- přizpůsobíme tomu architekturu
	- úlohy: sběr odpadu, navigace s návratem domů
- sběr odpadů
	- Khepera čistič s ramenem
	- dlouhá posloupnost akcí – najdi válec, seber ho, odvez ho za hranici arény (přitom se vyhýbej dalším válcům a stěnám…)
	- testování několika architektur
		- bez skryté vrstvy
		- se skrytou vrstvou
		- s rekurentními spojeními
		- s dvěma sadami výstupů – podle stavu chapadla
		- emergentní modulární architektura
			- místo jednoho výstupu uvažujeme několik modulů (např. 2)
			- každý modul sestává z arbitra a výstupu
			- arbitři spolu soutěží – použije se výstup vítězného modulu
	- aby evoluce fungovala lépe, tak se po uchopení válce robotovi objevil v cestě uměle přidaný válec, který musel objet
	- emergentní modulární architektura umožnila najít správné řešení rychleji než jiné architektury a umožnila vývoj robustnějšího řešení (pro přenesení na reálného robota výkon příliš nepoklesl)
		- ale arbitři nefungovali tak, jak bychom čekali – moduly se přepínaly velmi rychle, žádný neodpovídal nějakému základnímu chování
		- vypadá to, že hlavní úlohou modulů je zlepšení schopnosti rozlišování objektů – robot vlastně provádí *aktivní vnímání* pomocí přepnutí modulů
- roboti s vnitřní dynamikou
	- úloha: návrat domů k nabíječce
	- simulovaná baterie
	- třívrstvý perceptron, 5 neuronů ve skryté vrstvě s rekurentními spoji
	- nabíječka v jednom rohu společně se zdrojem světla
	- chceme, aby robot jezdil co nejrychleji mimo nabíječku – tomu odpovídal výpočet fitness
	- jeden skrytý neuron „monitoroval baterii“ – ovlivňoval vnímání prostředí v závislosti na stavu baterie
	- další krok experimentu: zkoumání readaptace
		- zdroj světla se přesunul do jiného rohu (takže už nebyl u nabíječky)
		- robot se rychle přizpůsobil
		- nejsnáze se přizpůsobil, když se světlo přesunulo do opačného rohu

## Učení a evoluce

- učení a evoluce
	- dvě různé formy biologické adaptace
	- evoluce – na populaci, operuje na genotypu
	- učení (ontogenetická adaptace) – v jednom jedinci po dobu jeho života, ovlivňuje jenom fenotyp
		- budeme uvažovat umělé neuronové sítě (učení vah)
	- konekcionismus rozlišuje
		- učení – změny synaptických vah
		- paměť – změny aktivačních stavů neuronů v rekurentních sítích
	- učení se zpětnou vazbou z prostředí pracuje rychleji než evoluce
		- ale výsledky učení se přímo nepřepisují do genotypu
- výhody učení
	- učení zjednodušuje přizpůsobení se rychlým změnám v prostředí
	- učení má bohatší zpětnou vazbu z prostředí než evoluce
	- i evolučně suboptimální jedinci můžou přežít, pokud se dovedou dobře učit
		- ale učení stojí čas, takže evoluce upřednostňuje jedince, kteří mají dané vlastnosti od narození
	- učení umožňuje vytvořit složité fenotypy z krátkých genotypů – část informací se extrahuje z prostředí
- nevýhody učení
	- ne vždy je možné naučit se, co je potřeba (když se nějaký podnět nevyskytne, tak na něj jedinec neumí reagovat)
	- učení trvá dlouho – dosud nenaučený jedinec se nechová optimálně
	- nenaučený jedinec si může ublížit
- jak učení pomáhá evoluci
	- učení dělá fitness funkci „hladší“
	- Hinton, Nowlan
	- kanalizační efekt
		- učení umožňuje prohledávání okolí kandidátů
		- zároveň když evoluce najde jedince s geny částečně fixovanými na správných hodnotách, tak jim začne dávat přednost oproti těm, které je fixované nemají (ale můžou se je naučit)
- učení a evoluce můžou mít různé cíle
	- pokud je fitness funkce evoluce definovaná jinak než chybová funkce učení
	- prostor učení a prostor evoluce pak vypadají jinak
	- příklad
		- evoluce je řízená schopností hledat potravu
		- neuronová síť
			- má jednu skrytou vrstvu
			- obsahuje mj. dva výstupní neurony, na nichž se snaží předpovědět další stav senzorů (po vykonání motorické akce)
				- zde může probíhat učení
			- výstupní neurony, které ovlivňují motorickou akci, se sice přímo neučí, ale skrytou vrstvu sdílí s učenými neurony (tzn. učení je také ovlivňuje)
		- jedinci, kteří se učí, umí potravu hledat lépe než ti, kteří se neučí
		- takže vysvětlení podle Hintona a Nowlana nestačí
	- ještě jiná interpretace učení (Harvey)
		- učení umožňuje napravit chyby způsobené mutací
- evoluce učení
	- Floreano, Mondala
	- genotyp kóduje architekturu a pravidla učení pro váhy (ne jejich hodnoty)
	- můžeme mít různé druhy učících pravidel – určují, jak se mění spoje mezi neurony v závislosti na jejich aktivaci
	- výsledky
		- vyvinuté váhy zodpovídaly za učení i chování
		- učení začalo až po chvíli pohybu robota
		- vyvinuté chování vzniklo interakcí s prostředím, váhy se vyvíjely jen u senzorů, kde byla nějaká aktivita
- sekvenční úloha – zapnutí světla vypínačem
	- Urzelai, Floreano, 2001
	- robot má stisknout vypínač (rozsvítí světlo), pak jít ke světlu a tam zůstat
	- učení jedinci si uměli poradit se změnou barvy stěn (jedinci s genetický kódovanými váhami nikoliv)
	- podobně si poradili se změnou polohy vypínače a světla
- adaptace na rychlé změny prostředí
	- Ackley, Littman, 1991
	- organismus se skládal ze dvou modulů
		- výkonný – určuje pravděpodobnost vykonání akcí
		- vyhodnocovací – poskytuje zpětnou vazbu na základě výstupu hodnotícího modulu
	- genetický algoritmus vyvíjel váhy obou modulů
	- učení měnilo jenom váhy výkonného modulu na základě zpětné vazby z vyhodnocovacího modulu
		- kladná hodnota zvyšuje váhu, záporná ji snižuje
		- finální váhy se do genotypu nazpět nepřepisují
	- organismy se můžou reprodukovat, když mají dostatek energie a blízko sebe partnera, který je také připraven k reprodukci
	- potomkové vznikají křížením a mutací
	- organismy umírají, když jsou staré nebo nemají energii
	- autoři porovnávali
		- evoluci bez učení
		- učení bez evoluce
		- evoluci s učením – nejvýkonnější
- proměnlivé stěny
	- Nolfi, Parisi
	- Khepera hledá cíl v aréně, kde stěny můžou měnit barvu
	- fitness je vyšší, čím dřív Khepera najde cíl
		- ale Khepera nepozná, že už ho našla
		- takže musí důkladně prozkoumat arénu
	- dvě prostředí: tmavé stěny nebo světlé stěny
	- tmavé stěny Khepera detekuje, až když je velmi blízko
		- takže Khepera musí poznat, v jakém prostředí se ocitla, aby mohla vhodně zvolit strategii
	- porovnání učení × neučení
		- vyvinutí učící se jedinci byli před učením horší než neučící a po učení lepší
		- vyvinutí učící se jedinci měli predispozice k učení – ne k chování
- učená může být i morfologie (stavba těla)
	- Peter Krčah
	- tělo z kvádrů spojených panty, pohyb pantů řízený NS
	- evoluční algoritmus NEAT
	- jedinci se měli co nejrychleji pohybovat v kapalinách s různou viskozitou
		- dvě úlohy: pohyb ve volné vodě, pohyb při dně
	- učení – hillclimbing s mutacemi rozměrů kvádrů
	- fitness = nižší z průměrných rychlostí v obou prostředích
	- 8 mutací s krátkými testy rychlosti (případně se změna vrátila zpět), pak dlouhé měření rychlosti

## Koevoluce, dravec-kořist

- kompetitivní koevoluce
	- současná evoluce dvou nebo více populací s provázanou fitness funkcí
	- „závody ve zbrojení“ – strategie se stávají složitější
	- dochází ke zlepšování, aniž bychom měnili prostředí nebo selekční kritéria
	- co když necháme fixní kořist a vyvíjíme dravce
		- strategie bude méně obecná – když se kořist změní, tak nemusí fungovat
		- pokud bude kořist dokonalá, tak nám u dravců nefunguje selekce, protože jsou všichni špatní
	- koevoluce může pomoct vyhnout se lokálním minimům
	- koevoluce nemusí vést ke zdokonalování jedinců – strategie se můžou pouze cyklicky opakovat
		- lze brzdit pomocí síně slávy – to ale neodpovídá přirozené evoluci a nemusí to vést k lepšímu výkonu
- jak sledovat vývoj?
	- když se zlepšuje jeden druh, tak se skoro jistě (relativně) zhoršuje druhý
	- takže se používá CIAO (current individual vs. ancestral opponents)
		- necháme nejlepšího jedince z aktuální generace utkat se s nejlepšími soupeři z minulých generací
		- generujeme bitmapu N×N, kde N je počet generací – pixel je černý nebo bílý podle toho, kdo vyhrál
		- ideálně by dravec z $i$-té generace měl porazit kořisti z všech předcházejících generací – matice by měla mít černou a bílou polovinu (podle hlavní diagonály)
	- po skončení evoluce můžeme uspořádat tzv. mistrovství – necháme nejlepšího z dané generace utkat se s nejlepšími ze všech generací (ideálně by křivka měla růst)
- aplikace koevoluce
	- třídicí sítě
		- cíl: třídící algoritmus pro data s určitými vlastnostmi (např. jsou částečně setříděné)
		- souboj: třídicí programy vs. testovací programy (unit testy)
	- hráč pro tic-tac-toe, Nim, zmenšenou verzi Go
- příklad: dravec-kořist s roboty
	- kořist vidí dravce, až když je velmi blízko
	- jedinec byl testovaný proti nejlepším soupeřům z předcházejících 10 generací
	- fitness kořisti = čas do kontaktu / maximální čas
	- fitness dravce = 1 – fitness kořisti
	- různé strategie, lze je pozorovat a popsat (ale těžko)
		- různí jedinci v populaci můžou mít různé strategie
	- fitness oscilovala, CIAO nepřehledné
	- aby se předešlo cyklení, dává smysl vybírat ze všech předchozích generací (ne jen z 10 předcházejících)
		- nedá se úplně zabránit cyklení strategií – těch tříd je konečně mnoho
		- metoda síně slávy fungovala líp – každý jedinec zápasí z 10 soupeřů náhodně vybraných z nejlepších jedinců ze všech předcházejících generací
			- metoda síně slávy vede na obecnější strategie
	- problematické třídy strategií (které se snadno cyklí)
		- dravec: pronásleduj kořist × sleduj kořist, zaútoč, až když je vůči tobě ve speciální pozici
		- kořist: stůj na místě krytá při stěně (dravec nechce narazit do stěny) × rychle se pohybuj (a vyhýbej se dravcovi i stěnám)
	- zkusili vylepšit kořist (dali jí vidění)
		- standardní koevoluce nebyla horší než síň slávy
	- experimenty s jednoduchou evolucí
		- evoluci se povedlo najít efektivní strategii proti jedné nejlepší strategii
	- experimenty bez vidění
		- jednoduchá evoluce dravce nefungovala, koevoluce fungovala lépe
		- jednoduchá evoluce pro kořist fungovala
	- existují úlohy, kde neexistuje úplně obecné řešení – pak je zacyklení strategií nevyhnutelné a optimální
	- experimenty s celoživotním učením
		- idea: jedinec se dokáže adaptovat na změnu strategie soupeře už v průběhu jedné generace
		- dva druhy úspěšných jedinců
			- úplně obecný – s jednou univerzální strategií
				- efektivnější, ale může být nedostupný
			- plasticky obecný – umí si vybrat vhodnou strategii z jednoduchých strategií
				- může být těžké ho najít
		- další experiment: genotyp kóduje taky pravidla učení
			- kořisti adaptace nepomáhala, měla slabé senzory (ve variantě, kde dravec viděl a kořist ne)
- koevoluce tvaru těla
	- Karl Sims
	- kvádry spojené klouby
	- organismy soupeří o kostku – vyhrává ten, kdo je k ní blíž
	- různé přístupy k soutěžím: každý s každým, napříč druhy, uvnitř druhů, …
- hra Tron
	- koevoluce stroj vs. člověk
	- programy byly reprezentované jako stromy, bylo použito genetické programování
	- poražení lidského protihráče → vyšší pravděpodobnost reprodukce
	- počítačové programy se zlepšovaly, lidská populace se nevyvíjela (lidé se učili jenom mezi po sobě jdoucími hrami)

## Zobrazení genotypu na fenotyp

- zobrazení genotypu na fenotyp
	- dosud 1:1
	- ale dekódování genotypu na fenotyp může být ovlivněno prostředím
		- tak je to v přirozené evoluci – chceme se jí přiblížit (jak kvůli zlepšení umělé evoluce, tak kvůli zkoumání přirozené evoluce)
	- výsledná fitness je daná fenotypem
	- jedinec se může vyvíjet postupně – mít vývojová stádia
- genetické kódování
	- přímé kódování
		- jednoduché na implementaci, ale chtěli bychom něco s větší vyjadřovací silou (na krátkém rozsahu)
	- co bychom chtěli
		- vyjadřovací sílu
			- aby se daly kódovat různé aspekty robota
		- kompaktnost
			- aby se opakující struktury daly snadno kódovat kratším kódem
		- možnost rozvoje
			- aby se kód mohl zlepšovat pomocí genetických operátorů
			- pleiotropie – jeden gen může ovlivňovat více fenotypických rysů
				- to bychom chtěli omezit (aby se robot zároveň v nějakých charakteristikách nezlepšoval a v jiných nezhoršoval)
			- vhodná je modulární organizace zobrazení genotypu na fenotyp
				- může to být způsob, jak bránit pleiotropii
- kódování instrukcí růstu axonů
	- Nolfi, Miglino, Parisi, 1994
	- soustava neuronů s axony v rovině
	- genotyp obsahuje pokyny pro růst a větvení axonů
		- když axon doroste k jinému neuronu, tak vznikne spoj
		- axon roste jen tehdy, když aktivita neuronu překročí určitou hranici (je daná geneticky) → prostředí také ovlivňuje růst axonů
	- genotyp je rozdělený na bloky kódující charakteristiky jednotlivých neuronů a instrukce pro růst axonů
		- celkově max. 32 neuronů (10 vstupních, 17 vnitřních, 5 výstupních)
		- blok obsahuje osm prvků
			- práh pro růst
			- pozici (dvě souřadnice)
			- úhel větvení axonu
			- délku segmentů axonu
			- váhu (všechny spoje vycházejícího z jednoho neuronu mají stejnou váhu)
			- práh neuronu
			- typ neuronu (např. jestli řídí levý nebo pravý motor – pak se průměrují neurony, které řídí ten stejný motor)
	- úloha: najít cíl náhodně umístěný v aréně, cílová oblast může (ale nemusí) být osvětlená
- adaptace architektury NS
	- příliš malé sítě se nedovedou naučit správné zobrazení
	- příliš velké sítě špatně generalizují
	- tři metody automatického návrhu topologie sítě *při učení*
		- růst
			- *kaskádový algoritmus učení korelací*
			- začíná se vstupními neurony přímo spojenými s výstupními
			- přidává další neurony (připojené na vstup a na výstup), žádné spoje neodebírá
		- prořezávání
			- začne se velkou sítí, postupně ruší spoje, dokud se chyba nezhorší
			- např. ruší spoje s váhami blízkými nule
		- dekompozice
			- máme skupinu podsítí s různou architekturou (ale stejnými vstupy a výstupy)
			- různé podsítě se naučí různé vzory
	- tyhle metody jsou založeny na učení s učitelem – potřebujeme mít dostatek trénovacích dat
- kódování na úrovni buněk
	- v přírodě roste nervová soustava postupně – buňky se dělí a diferencují (stanou se z nich neurony), přesunou se na správná místa, vyrostou spoje
	- Cangelosi (1994) – dělení buněk a migrace
		- počet dělení je geneticky shora omezený
	- Gruau (1994) – dělení a diferenciace
- Gruauova simulace šestinohého robota
	- genotyp: binární strom (14 různých symbolů, některé s parametrem)
	- přepis do fenotypu – založí se neuron odpovídající kořeni stromu
		- uzel popisuje operace, které se mají na buňce vykonat
	- vylepšená verze: terminální uzel se může odkazovat na jiný strom
		- ADNS (automatické definování neuronových podsítí)
	- aplikace: šestinohý robot
		- křížení – záměna podstromů
		- s ADNS fungoval lépe, genotyp obsahoval 3 stromy
	- fitness: ušlá vzdálenost
	- při evoluci použil 32 ostrovů na toroidu – pravděpodobnost spárování byla úměrná vzdálenosti na toroidu
	- s ADNS byly výsledné sítě dobře strukturované
- jednoduché geometricky orientované kódování buněk
	- Kodjabachian a Meyer, 1998
	- simulovaný šestinohý robot
	- opět z neuronů rostou axony
	- křížení – záměna podstromů jako v GP
	- genotyp – 6 instrukcí
	- fitness: ušlá vzdálenost + člen podporující pohyb nohou
	- stabilní genetický algoritmus
		- konstantní počet jedinců
		- při vytvoření nového jedince se z aktuální populace vybere nějaký jedinec, který se zahodí
		- dá se dobře paralelizovat – akorát se pak nedá jasně říct, kdy začíná a končí generace
	- jedinci jsou rozmístění na kružnici
		- náhodně se zvolí bod na kružnici
		- v blízkosti tohoto bodu zvolíme dva jedince, vyrobíme nového jedince
		- turnajem zvolíme souseda v blízkosti toho bodu, který bude nahrazen novým jedincem

## Kráčející stroje

- kráčející stroje
	- složitější než kolečka – noha potřebuje aspoň 2 stupně volnosti
		- trik: můžeme použít symetrie
		- ale všechny nohy se nemůžou pohybovat stejně
	- asi chceme využít symetrii, abychom si úlohu zjednodušili
	- statická × dynamická chůze – podle toho, jestli je těžiště stále nad mnohoúhelníkem dotyku noh
		- trojkrok – statická chůze
- první pokusy s kráčením
	- Brooks – každá noha má stejný (ručně sestavený) konečný automat
	- Maes, Brooks – koordinace noh se dá naučit metodou pokus-omyl
	- Beer, Gallagher – simulovaný šestinohý brouk
		- evoluce může najít systém chůze s minimem předem zadaných parametrů
		- noha
			- má dva stavy – dole (na zemi), nahoře (zvednutá)
			- může se hýbat nahoru a dolů a také se otáčet dopředu/dozadu
			- má senzor – úhel mezi nohou a tělem
			- 5 neuronů – 2 skryté, 3 ovládají pohyby
		- když ztratí rovnováhu, tak padá (obviously 🙃)
		- vždy se vyvinul trojkrok
		- 4 vypozorované fáze učení
			1. zatlačil všemi šesti nohami a spadl dopředu
			2. nekoordinované pohyby nohou, časté pády
			3. nejlepší měli statickou stabilní chůzi
			4. doladěný statický krok
- pokročilejší kráčející roboti
	- Lewis – fyzický šestinohý robot
		- každá noha s dvěma stupni volnosti
		- inkrementální evoluce a funkcionální dekompozice
			- evoluce řízení jedné nohy
			- koordinace nohou
		- genotyp – váhy v Grayově kódu
		- 2 neurony na jednu nohu – zdvih, švih
			- když oscilovaly s fázovým posunem 90°, tak noha dělala kroky
		- první fáze – evoluce řízení pro nohu
			- fitness se určuje vizuálně podle obrazovky počítače
		- druhá fáze – evoluce řízení oscilátorů
			- nejprve vlnění, pak trojkrok
		- robot nemá senzory
	- Gomi, Ide – 8nohý robot bez senzorů
		- celý vývoj na fyzickém robotu
		- nejprve vlnitá chůze, potom čtyřkrok
	- Jakobi – řízení pro stejného robota, ale formou minimální simulace, navíc měl robot senzory
		- oproti předchozím experimentů nebylo řízení tak robustní, bylo na hraně technických možností
	- Gruau – evoluce architektury (viz výše)
	- Ijspeert – na základě modelu mihule vyvinul model mloka, který uměl plavat i chodit
		- propojené generátory řídicích signálů (tzv. CPG, central pattern generator)
	- Sony – pes Aibo
	- Honda – humanoid ASIMO
- někteří roboti se dovedou přestavět – změnit svoji morfologii
	- např. rozdělit se na menší roboty nebo metamorfovat
	- ukázka s modulárními polokostkami/poloválci
	- M-TRAN – kombinace magnetů a paměťových pružin
	- zase generátory signálů – každý modul má svůj CPG, které spolu komunikují
		- realizované jako oscilující neurony
	- příklad robota popsaného tak, že se na něj dá použít evoluční algoritmus
		- genotyp – posloupnost segmentů
		- křížení jenom na hranici segmentů
		- mutace zamění celý segment

## Evoluční učení neuronových sítí

- mozek se vyvinul evolučně
	- když to dokáže mozek, tak by to mělo jít i s umělou neuronovou sítí v umělé evoluci
	- neuronové sítě jsou výkonné ve spoustě oblastí – především když neexistuje dobrá teorie
	- předpokládalo se, že neuroevoluce nahradí zpětné šíření chyby (tzn. při učení s učitelem)
		- ale zajímavějších výsledků neuroevoluce dosahuje v situaci, kdy nemáme správné výstupy (tzn. když nemůžeme jednoduše použít backpropagaci)
		- evoluční strategie jsou dosud nejlepší metodou, jak optimalizovat hyperparametry sloužící k učení NS
- sekvenční úlohy z rozhodování
	- skrytý Markovovský model (POMDP)
	- temporal difference reinforcement learning
		- Q-učení
		- těžké, když je stavový prostor rozsáhlý/spojitý a když má prostor skryté stavy (partial observability)
	- neuroevoluce je jiná
		- hledáme přímé nelineární zobrazení ze senzorů na akce
		- rozsáhlost/spojitost za nás řeší neuronová síť
		- skryté stavy můžeme řešit pomocí paměti (RNN)
- dva přístupy k neuroevoluci
	- dosud jsme měli optimalizaci vah a pevnou architecturu sítě = konvenční neuroevoluce
	- mohli bychom ale také optimalizovat architekturu
- základní metody neuroevoluce
	- máme pevnou topologii (obvykle pevné propojení)
	- evolučně se vyvíjejí váhy sítě (nepoužívá se algoritmus zpětného šíření)
	- genotyp – řetězec bitů nebo reálných čísel
		- pevná topologie
		- úplné propojení
		- náhodně generovaná počáteční populace
	- problémy
		- předčasná konvergence
		- příliš mnoho parametrů optimalizujeme naráz (tisíce vah)
		- různé kódy odpovídají stejným sítím (liší se jenom permutace neuronů)
			- křížení pak vytváří málo nových jedinců
			- tzv. permutační problém
- pokročilá neuroevoluce s pevnou architekturou sítě – metody
	- SANE
	- ESP
	- CoSyNE
- symbiotická adaptivní neuroevoluce (SANE)
	- jedna skrytá vrstva, vyvíjejí se jednotlivé skryté neurony
	- při vyhodnocení se z nich vybere $k$ neuronů a složí se síť
	- to se opakuje, aby byl každý neuron vyhodnocený aspoň 10×
	- fitness neuronu je průměrná fitness přes všechny testy, kde jsme ho použili
	- takže se neurony specializují a fungují v symbióze s ostatními
	- každý neuron má 5 spojů, ty můžou vést ze vstupní vrstvy nebo do výstupní vrstvy (o tom rozhoduje parametr, který je součástí genetického kódu)
	- porovnání symbiotické a standardní evoluce – u standardní rychle klesá diverzita (měří se pomocí Hammingovské vzdálenosti)
	- příklad: cartpole
- vynucené subpopulace / enforced sub-populations (ESP)
	- neurony jsou rozdělené na druhy – vyvíjejí se v rámci druhů
	- jeden skrytý neuron odpovídá jedné subpopulaci
	- možnost vyvíjet i rekurentní sítě
	- úspěšné při řešení těžkých úloh – např. balancování dvou tyčí
	- velký prohledávaný prostor tak vlastně rozdělíme na podúlohy
- kooperativní synaptická neuroevoluce (CoSyNE)
	- máme subpopulace pro váhy
	- váhy pro $i$-tou synapsi jsou v subpopulaci $P_i$
		- $i$-tý řádek matice
	- sloupec $x_j$ jsou hodnoty vah pro všechny synapse v síti
		- sítě $x_1,\dots,x_m$ se vyhodnotí a dostanou fitness
		- nejhorší sloupce se nahradí novými potomky
	- kooperativní koevoluce pro každou subpopulaci odděleně
		- několik prvků z populace se vybere a zamíchá (takže se vymění hodnoty dané váhy napříč sloupci/sítěmi)
		- víc se permutují prvky s nižší fitness
	- také se někdy používá CMA-ES
		- covariance matrix adaptation evolution strategy
		- vyvíjejí se jednotlivé celé sítě
		- při mutacích se zohledňují korelace mezi váhami
- NEAT
	- začíná se s malou sítí, sítě můžou růst
	- smysluplné křížení sítí s různou topologií
	- ochrana inovací pomocí druhů
	- uzly a váhy v síti mají tzv. historické značky
		- podle nich se párují při křížení
		- potomci dědí historické značky svých rodičů
	- přidání spoje je mutace
	- musíme si hlídat, aby měl konkrétní spoj v celé generaci jenom jednu historickou značku
		- u neuronů to asi nehlídáme
		- je to taková heuristika, kterou se trochu bráníme proti permutačnímu problému
	- křížení
		- zarovnají se geny hran se stejnými značkami
		- potomek dostane náhodně jeden z genů se stejnými značkami (tzv. odpovídající si geny)
		- disjunktní geny z obou se zkopírují
		- přesahující geny se zkopírují jenom od rodiče s vyšší fitness
			- to jsou ty geny, jejichž časové značky jsou větší než všechny časové značky ve druhém rodiči
	- ochrana inovací
		- dělíme jedince do druhů (k tomu musíme mít nějakou metriku – vzdálenost mezi jedinci)
			- $\delta=\frac{c_1E}N+\frac{c_2D}N+c_3\bar W$
			- $E$ … počet přesahujících genů
			- $D$ … počet disjunktních genů
			- $N$ … počet genů ve větším jedinci
			- $\bar W$ … průměrný rozdíl vah odpovídajících si genů
			- $c_1,c_2,c_3$ … konstanty určující váhy kritérií
		- nový druh je po několik generací chráněný – jedinci soutěží jenom mezi sebou
		- jedinci sdílejí zdroje s ostatními jedinci svého druhu – mají upravenou fitness
			- také si hlídáme, aby jeden druh nepokryl celou populaci
		- rozdělení do druhů můžeme ovládat nastavováním vzdálenostních konstant v každé generaci
		- používáme elitismus
	- při vyhodnocení na cartpolu fungoval NEAT podobně jako ESP
		- na těžší úloze byl lepší
- cellular encoding
	- Gruau, Whitley, Pyeatt, 1996
	- viz Gruauova simulace šestinohého robota
	- pravidla růstu – gramatika
	- nepřímé kódování – genom je komprimovaný

## Od simulace k realitě

- Karl Sims – kvádroví roboti
	- fenotyp robota – strom
		- vrcholy reprezentují kvádry, hrany reprezentují spoje
		- každý vrchol grafu navíc obsahuje neuronovou síť, rozměry kvádru atd.
	- genotyp je graf, ne nutně strom
		- hrany můžou tvořit cykly
		- je tam jeden speciální kořenový uzel
	- přepis genotypu na fenotyp
		- rekurzivním procházením grafu po hranách
		- začíná se v kořeni
		- navštívené hrany a uzly se kopírují do fenotypu
		- opakované návštěvy vloží kopie
			- jsou tam rekurzivní limity – maximální povolené počty opakování – aby se předešlo nekonečným cyklům
		- hrana může být označená jako reflexivní podle osy x/y/z, pak je podstrom zkopírovaný symetricky
- Hornby – L-systém
	- řízení robota se vyvíjí spolu s jeho morfologií (tzv. vtělená umělá inteligence)
	- generativní kódování – aby se pomocí jednoduchého genotypu dal popsat složitý robot
	- Tinkerbot
		- morfologie popsaná L-systémem
		- genotyp je bezkontextový 0L-systém vyvíjený genetickým algoritmem
		- podle L-systému se vygeneruje popis těla robota ve speciálním konstrukčním jazyku (podobný jazyku Logo)
	- L-systém – jako bezkontextová gramatika, akorát v každém kroku musím přepsat všechny neterminály najednou
- Lipson, Pollack – GOLEM
	- Genetically Organized Lifelike ElectroMechanics
	- robot skládající se z tyčích spojených kulovými klouby
	- vyvíjený v simulaci
	- řízení
		- neuronová síť bez omezení spojů
		- neuron může být připojený na tyč a ta se stane svalem – její délka se mění podle výstupu neuronu
	- cíl evoluce: co nejrychlejší pohyb po rovině
	- výsledný robot vytištěný na 3D tiskárně, potom se do tyček vložily motory
- projekt ERO
	- studentský softwarový projekt
	- genotyp analogický tomu Simsovému
	- hierarchický NEAT
- soft robots
	- příroda používá tvrdé i měkkné materiály!
	- přímé kódování nefunguje dobře
	- nepřímé kódování vyvíjené algoritmem HyperNEAT funguje líp
		- generující síť CPPN (compositional pattern producing network) dostává na vstupu 3D souřadnice a vzdálenost od středu a vrací materiál voxelu (+ informaci, zda má být vůbec přítomný)
- growing soft-bodied creatures
	- růst (morfologický vývoj) je odpovědí na stimuly z prostředí
		- kořeny rostlin sledují, kde jsou v půdě živiny
		- lidské kosti a tkáně přizpůsobují svoje vlastnosti v reakci na mechanickou zátěž
	- vlastnosti materiálu těla organismu ovlivňují evoluci i adaptivní chování
		- hypotéza: tvrdost/měkkost stavebního materiálu dovoluje vyvinout inteligentní chování
		- hypotéza: při správné kombinaci geometrie, vlastností materiálu a procesu růstu může robot využívat tzv. morfologické počítání
	- dva generátory CPPN – jeden určuje, zda je voxel plný nebo prázdný, druhý určuje, zda se smršťuje nebo roztahuje
- evolved electrophysiological soft robots
	- každý voxel má elektrický potenciál – rozdíl napětí uvnitř a vně buňky
		- když vnější napětí překročí práh, tak se buňka depolarizuje a prudce zvýší napětí
		- pak se napětí zase sníží (buňka se repolarizuje) a klesne do záporu
		- pak se buňka zotavuje (tzv. refrakční doba) a nedokáže přijmout impuls zvenku
	- organismus má centrální stimulátor, který pravidelně vysílá impulsy
	- CPPN je vyvíjený algoritmem HyperNEAT
	- excitovaná buňka může vybudit až 26 sousedních buněk
	- čas potřebný k excitaci sousední buňky je poloviční oproti době depolarizace, vzruchy se šíří jako vlny
	- refrakce trvá 5× déle než repolarizace
	- typy buněk
		- prázdná
		- vodivý sval
		- nevodivý sval
		- vodivá pasivní tkáň
		- nevodivá pasivní tkáň
		- stimulátor – přibližně uprostřed prostoru 10×10×10
	- fitness funkce odráží vzdálenost, kterou robot ušel (maximalizuje se), a také počet vodivých buněk (ten se minimalizuje? asi aby robot nebyl celý vodivý, ale měl pouze „nervy“)

## Robotické roje

- znaky robotických rojů, technologické motivace
	- velké množství jedinců, ti jsou homogenní a poměrně jednoduší
	- interakce mezi jedinci jsou založeny na jednoduchých pravidlech, která používají pouze lokální informace
	- celkové chování je výsledkem samoorganizace
	- robustnost, škálovatelnost, všestrannost/flexibilita, nízká cena?
	- superlineárnost – roboti mají dohromady větší schopnosti než prostý součet jejich jednotlivých schopností
- koordinovaný průzkum
	- tři přístupy: monitorování prostředí, feromonová robotika, řetězení
	- monitorování
		- robotický roj se snaží lokalizovat zdroj vůně/zápachu
		- jednoduché chování založené na detekci zápachu a větru
		- komunikace může zlepšit efektivitu
		- algoritmus
			- když nedetekuješ zápach → pohybuj se po rozšiřující se spirále
			- když detekuješ zápach → pohybuj se proti větru
	- feromonová robotika
		- viz dále
	- řetězení
		- omezený dosah senzorů
		- signalizace barvami
- feromonová robotika
	- roj se skládá z autonomních robotů bez centrálního řízení
	- agent pracuje jenom s lokálními informacemi
		- nemá mapu prostředí (mapa prostředí se v dynamickém prostředí špatně udržuje)
		- používá feromonovou stopu (dá se detekovat jen lokálně, odpařuje se a šíří se do okolí, agent může feromon vylučovat)
	- rozptýlení robotů
		- roboti, kteří se vidí, ale jsou daleko od sebe, se přitahují
		- roboti, kteří se vidí, ale jsou příliš blízko sebe, se odpuzují
	- robot, který najde cíl, začne vydávat (virtuální) feromon
	- virtuální feromon – zprávy posílané mezi roboty v dosahu
		- zpráva obsahuje typ feromonu a počet přeskočení (přes kolik robotů už prošla)
		- každý agent dostane více zpráv se stejným typem, tak vybere tu, která má nejnižší počet přeskočení, zvýší ho o jedna a pošle ji sousedům
		- nejkratší cestu k cíli robot najde tak, že se vydá směrem, odkud přišla zpráva s nejnižším počtem přeskočení
	- pokrytí grafu
		- navštívit každý uzel / projít každou hranu
		- klasický přístup: zmapovat graf, navrhnout plán na průchod grafem 
			- vyžaduje to mít složitý hardware, který to zvládne spočítat, také bychom museli při změně grafu počítat nový pán
		- plánování v reálném čase
			- používáme jenom lokální informace (značky na uzlech/hranách)
			- jednoduché algoritmy
			- při změně grafu se algoritmus nemění
		- algoritmus (na začátku jsou počítadla nulová)
			- zvyš počítadlo aktuálního uzlu o jedna
			- přesuň se na sousední uzel s nejmenším počítadlem
	- varianty algoritmu pokrytí uzlů
		- na začátku kroku jsme na pozici $s$, pak se přesouváme na pozici $s'$ (sousední uzel s nejnižší hodnotou počítadla)
		- změna hodnoty počítadla na pozici $s$ (tedy změna $u(s)$) se ale dá implementovat různě
		- Koenigovo pravidlo: $u(s)\leftarrow u(s)+1$ (tzn. základní verze)
			- exponenciální čas $O(n^{\sqrt n})$
			- funguje i pro skupinu $k$ mravenců
			- věta: souvislý graf bude vždy pokrytý nezávisle na počtu mravenců
				- důkaz sporem: uvažujme část grafu, která je opakovaně navštěvovaná
				- takže existuje podmnožina $V$ vrcholů grafu, která je navštěvovaná cyklicky, tedy $u$-hodnoty vrcholů tam rostou neomezeně a překročí hodnoty ve všech uzlech, do nichž se dá z nějakého uzlu z $V$ dostat
				- při návštěvě uzlu z $V$, který má souseda mimo $V$, musí být navštíven uzel mimo $V$ → spor
			- důkaz funguje i pro Korfovo pravidlo
			- robustnost: po zastavení se může pokračovat z libovolného uzlu; náhodné přemístění (ne moc časté) také nevadí
		- Korfovo pravidlo … $u(s)\leftarrow u(s')+1$
			- polynomiální $O(n^2)$
			- learning real-time A\*
			- $u(s)$ aproximuje součet minimální $u$-hodnoty souseda a ceny, za kterou se dá do souseda dostat
			- dokud nebyly navštíveny uzly, tak platí…
				- $u(s)=0$ znamená, že uzel nebyl navštíven
				- $u(s)$ je odhadem vzdálenosti uzlu od nejbližšího nenavštíveného uzlu
			- → „běž do souseda s nejnižší $u$-hodnotou, abys mohl navštívit nejbližší dosud nenavštívený uzel“
			- v průběhu algoritmu jsou přípustné $u$-hodnoty $0\leq u(s)\leq gd(s)$
				- $gd(s)$ … nejkratší vzdálenost do cílového uzlu (nejbližšího nenavštíveného?)
			- $u$-hodnota nikdy neklesá
				- lze nahlédnout z toho, že se agent vždycky volí nejnižšího souseda
			- podle pravidla … $u_{t+1}(s_t)=u_t(s_{t+1})+1$
			- věta: mravenec potřebuje maximálně $2\sum_s gd(s)\leq 2\sum_{i=1}^n i=n^2-n$ k tomu, aby došel na cílový uzel
				- důkaz pomocí potenciálu
			- potenciál grafu v čase $t$ … $2\sum_s u_t(s)-u_t(s_t)$
			- dokážeme, že potenciál v čase $t+1$ je vyšší než v čase $t$
			- $(2\sum_s u_{t+1}(s)-u_{t+1}(s_{t+1}))-(2\sum_s u_t(s)-u_t(s_t))=$
			- $=(2u_{t+1}(s_t)-u_{t+1}(s_{t+1}))-(2u_t(s_t)-u_t(s_t))=$
			- $=2u_{t+1}(s_t)-u_t(s_{t+1})-u_t(s_t)=$
			- $=2u_{t+1}(s_t)-(u_{t+1}(s_t)-1)-u_t(s_t)=$
			- $=u_{t+1}(s_t)-u_t(s_t)+1\geq 1$
		- další polynomiální pravidla
			- Wagnerovo pravidlo … if $u(s)\leq u(s')$, then $u(s)\leftarrow u(s)+1$
			- Thrunovo pravidlo … $u(s)\leftarrow \max(u(s)+1,\ u(s')+1)$
		- využití: robotický vysavač
	- úloha: projít všechny hrany grafu
		- EAW (edge ant-walk)
		- každý uzel má směrovku (ukazuje na hranu nebo spíše na uzel odpovídající hraně)
		- při projití směrovku otočíme, aby směřovala do další hrany (po řadě)
		- idea: mravenec se vydává cestou, kterou nejdéle nikdo nešel
		- zaručuje pokrytí hran v čase $O(n^3)$
- přemisťování a shlukování
	- koordinované přemisťování objektu
		- vyžaduje spolupráci
		- bez explicitní komunikace
		- přistup založený na chováních
		- zotavení ze stagnacie inspirované od mravenců
	- slepé hrnutí (bulldozing)
		- radlice s detekcí síly odporu
		- při srážce s jiným robotem nebo při detekci odporu na radlici počkáme a pak zase hrneme
	- shlukování
		- důležité mechanismy: komunikace, pozitivní a negativní zpětná vazba
		- příklad pravidla
			- pravděpodobnost uchopení objektu je nepřímo úměrná počtu vnímaných objektů
			- pravděpodobnost odložení objektu je přímo úměrná počtu vnímaných objektů
	- kooperativní manipulace
		- pouštní mravenci spolupracují při vytahování dlouhých objektů z písku
		- lze napodobit s roboty
		- jak dlouho čekat na kamaráda?
		- superlineární výkon
			- optimální výkon, když má skupina cca 6 členů
- rekonfigurovatelní roboti
	- modulární roboti skládající se s několika identických částí, které se můžou přeorganizovat, aby vytvořili vhodný tvar pro řešení úlohy
	- inspirace buňkami (celulární automaty) a jednotlivci (roje)
	- různé tvary robotů: řetězce, mřížky, mobilní rekonfigurovatelní, …
	- příklad robota řetězcového typu: CONRO
		- spojené zásuvky se západkami
		- infračervené navádění
		- dobrá mobilita
		- řízení se dokáže vyrovnat s náhlými změnami morfologie robota
	- další řetězcový robot: PolyBot
		- modul s jedním stupněm volnosti
	- robot mřížkového typu: A-TRON
		- dvě polokoule
		- 4 samčí a 4 samičí konektory
		- semo-spojování jednoduché, samo-rekonfigurace složitější
	- hybridní robot: M-TRAN
		- dvě propojené polokulaté krychle
		- hybridní mřížkový a řetězcový typ
		- magnety nebo mechanické háčky
		- pravidla pro celulární automaty
	- mobilní rekonfigurovatelní roboti
		- skládají se do spojených objektů
		- příklad: záchrana člověka
- stimergie
	- komunikace prostřednictvím změn prostředí
	- výsledek činnosti jedince zanechá trvalou značku, která ovlivňuje následující akce i jiných jedinců
	- cyklus stimul–reakce
	- příklad: budování vosího hnízda
		- pravidlo: přidej buňku do kouta, když tam jsou 2 nebo 3 stěny
		- může být deterministické nebo stochastické
- distribuované budování
	- každý robot dostane binární bitmapu finálního útvaru
	- sledování hranice – robot se pohybuje v pevné vzdálenosti od středu nejbližšího stacionárního robota
	- gradient – každý robot si nastaví gradient o jedna vyšší než nejnižší gradient souseda (počáteční robot má fixní gradient 0)
	- lokalizace – robot určuje svoji polohu pomocí komunikace s už lokalizovanými roboty (těmi v počátku, kteří určují globální souřadnice)
	- na začátku budování se jako první dávají do pohybu roboti, kteří jsou nejdál od počátku (mají nejvyšší gradient)
	- kolektivní budování inspirované termity: TERMES
		- umí se hýbat dopředu/dozadu, otáčet se na místě, chodit do schodů, přemisťovat kvádry

## Pokročilé evoluční NS

- NEAT
	- neuroevolution of augmenting topologies
	- principy
		- začíná se s malou sítí, sítě můžou růst
		- dochází ke (smysluplnému) křížení sítí s různou topologií
		- ochrana inovací pomocí druhů
	- topologie se vyvíjí zároveň s váhami sítě
	- každý uzel a každá váha mají svou historickou značku, ta se dědí
	- kříží se uzly se stejnými značkami
- nepřímé kódování
	- komprimovaný genom
	- možné přístupy: kódování založené na L-systémech, cellular encoding (pravidla růstu jsou popsány pomocí gramatiky), analogové genetické kódování
	- analogové genetické kódování (AGE)
		- implicitní kódování synapsí a vah v síti
		- genom je sekvence znaků z nějaké konečné abecedy
		- kód neuronu
			- začíná „device tokenem“ (pevná krátká sekvence)
			- pak kód vstupního konce (ukončený koncovým tokenem)
			- pak kód výstupního konce (také ukončený)
		- váhy spojů mezi neurony se spočítají nějakou funkcí $I$, která dostane vždycky výstupní kód jednoho neuronu a vstupní kód druhého neuronu
		- když device token není následovaný dvěma úseky zakončenými koncovými tokeny, tak je kód neuronu neplatný
			- úseky mezi kódy neuronů se nevyužívají
		- vstupní a výstupní neurony mají odlišné device tokeny
		- genetické operátory
			- přidání/smazání/nahrazení znaku
			- smazání/posunutí/zdvojení náhodného úseku genomu
			- přidání zařízení (neuronu)
			- homologické křížení
			- zdvojení celého genomu
		- generování počáteční populace: každý genom jako náhodná sekvence, do které je vložený zadaný počet neuronů s náhodnými terminálními sekvencemi
		- testováno na úloze balancování dvou tyčí bez znalosti rychlostí
			- lepší než NEAT
- HyperNEAT
	- ke generování sítě, která řeší úlohu, se použije generátor CPPN
		- funkce $f_1$ ze souřadnic neuronu určí jeho přenosovou (aktivační) funkci
		- funkce $f_2$ ze souřadnic dvou neuronů určí váhu spoje mezi nimi
	- CPPN se vyvíjí algoritmem NEAT
	- vhodné na úlohy, které vykazují symetrie
	- experimentátor rozhoduje, kde na substrátě budou umístěné neurony a kolik jich bude
	- článek: *adding the connection cost technique to HyperNEAT produces neural networks that are more modular, regular, and higher performing*
	- alternativa: ES-HyperNEAT (ES = evolving substrate)
		- algoritmus sám určuje hustotu a pozici neuronů na substrátě
- deceptive tasks (zavádějící úlohy)
	- žádná kombinace malých stavebních bloků nevede na optimální řešení
	- úloha je tím těžší, čím je složitější fitness krajina
		- klamavá fitness – ukazuje nesprávný směr k řešení
	- řešení
		- sdílení zdrojů (fitness sharing) spolu se zavedením druhů → podobná řešení se dělí o fitness, čímž se vynucuje hledání nových druhů
		- hierarchical fair competition
			- subpopulace podle úroveň fitness
			- každá subpopulace má vstupní úroveň a exportní úroveň fitness
				- jedinec překročí vstupní úroveň → je přijat do subpopulace
				- jedinec překročí exportní úroveň → přechází do vyšší subpopulace
			- v nejnižší úrovni je generátor náhodných jedinců
			- úrovně buď pevné, nebo adaptivní
		- fitness uniform selection scheme
			- místo hodnoty fitness se hodnotí jedinečnost fitness
			- náhodně zvol hodnotu fitness, vyber jedince s nejbližší fitness
		- reorganizace genomu
			- pořadí genů se mění tak, aby byly korelované geny blízko sebe a křížení je tak často nerozdělovalo
		- více fitness funkcí
			- různé fitness funkce zachycují různé vlastnosti jedinců
			- buď se dynamicky vybírá jedna fitness, nebo se dělá multikriteriální optimalizace
		- další přístupy: koevoluce, novelty search, kreativní přístup, …
- novelty search (hledání novinek)
	- fitness funkce se nahradí mírou novosti (novelty metric) – měří novost chování
	- archiv novinek – uchovává staré jedince, kteří přišli s novým chováním
	- příklad míry: průměrná vzdálenost ke $k$ nejbližším chováním
		- jedince porovnáváme vůči aktuální populaci a archivu novinek
	- když je míra dost velká, tak je jedinec zařazený do archivu (je to podobné síni slávy u koevoluce)
	- také kontrolujeme, jestli už jsme nenašli vyhovující řešení
	- funguje u zavádějících úloh, pokud můžeme intuitivně charakterizovat chování a pokud je počet možných chování omezen
	- dá se dobře kombinovat s NEAT
	- příklad: navigace v bludišti
		- tři varianty: fitness funkce (podle vzdálenosti od cíle na konci), novelty search (vzdálenost od ostatních robotů na konci), náhodná fitness
		- všechny tři varianty používaly NEAT
		- novelty search byl úspěšnější
		- problém: metrika pro chování je silně redukovaná (uvažuje se jenom koncová poloha)
		- taky by se místo přesné polohy dala použít jenom poloha v mřížce (to by byla ještě silnější redukce)
	- příklad: dvojnohý kráčející robot
	- není hledání novinek prostě prohledávání prostoru hrubou silou?
		- experiment: prohledávání bludiště (porovnáme novelty search s náhodně generovanými roboty a s tradiční evolucí)
		- testujeme, co se stane, když nejlepšího jedince přesuneme do nového bludiště
		- postup
			- 50 běhů NEAT s hledáním novinek (novelty search) v bludišti
			- první jedinec, který v daném běhu najde cíl, je přenesen do druhého bludiště a změří se jeho výkon
				- pokrytá plocha, uražená vzdálenost
			- evoluce pokračuje v druhém bludišti (50 generací)
				- použijí se různá cílová místa
		- kontrolní algoritmy
			- naivní hledání – náhodně generovaní jedinci s jediným skrytým neuronem
			- NCC (network complexity control) – náhodně generované sítě, $i$-tá síť má stejný počet neuronů jako nejlepší síť $i$-tého běhu novelty searche
			- random search – evoluce, ale s náhodnou hodnotou fitness funkce
	- závěr: novelty search produkuje specialisty
- curiosity search (zvědavé prohledávání)
	- novelty search produkuje specialisty – jedinec je porovnávaný s celou populací a stačí, když umí něco nového
	- curiosity search hledá jedince, kteří se chtějí každý naučit co nejvíc schopností – jedinec je porovnávaný jen sám se sebou
	- příklad: dlaždice a dveře
		- zavřené dveře je potřeba aktivně otevřít (pak zůstanou otevřené)
		- robot má 6 senzorů: vzdálenost od překážky, počet nenavštívených dlaždic, vzdálenost od zavřených dveří × 4 (červená, zelená, modrá, žlutá)
		- výstupy sítě: ovládání motorů, otevírání dveří dané barvy (tzn. celkem 6 výstupů)
		- porovnávané algoritmy
			- curiosity search – odměna za to, že jedinec navštíví všechna místa
			- novelty search – vzdálenost mezi dráhami $NS_T$ (nebo aspoň koncovými body drah $NS_E$)
			- curiosity + novelty (tzv. NSGA-II, non-dominated sorting genetic algorithm II)
				- dvě složky fitness funkce
				- definujeme si, kdy řešení *dominuje* jiné řešení (když není v žádné složce horší a je aspoň v jedné složce lepší)
				- populaci rozdělíme na fronty
					- fronta 1: řešení, která nejsou dominovaná žádným jiným řešením
					- fronta $i$: řešení, která nejsou dominovaná jiným řešením kromě řešení v nižších frontách
				- elitismus, explicitně zachovává diverzitu (crowding distance), vrací nedominovaná řešení
				- selekce pomocí operátoru *crowded tournament selection*
					- vítězí řešení, které dominuje to druhé
					- pokud jsou řešení ze stejné fronty, tak vítězí to s větší crowding distance
						- tzn. v dané frontě jsou ostatní řešení dost daleko
			- základní algoritmus (koncové body / target endpoints)
				- minimalizuje se vzdálenost koncové polohy od libovolného z koncových bodů
				- nenutí robota prozkoumávat celé bludiště
		- výsledky
			- novelty search prohledá všechno, ale ne jedním jedincem
				- porovnání celých drah vede na jedince, kteří sami prohledají větší část bludiště
			- kombinace curiosity + novelty toho prohledá víc
				- je skoro jedno, jestli používáme $NS_T$ nebo $NS_E$
			- curiosity search překonává target endpoints a novelty search
				- ale nejlíp funguje curiosity + novelty
			- celá populace u všech metod dohromady prozkoumá celé bludiště, samotný jedinec ale nikdy nezvládne prozkoumat celé bludiště (takového jedince se nám nepodařilo najít)
- kreativní myšlení
	- novelty search má problém, když mutace nedokáže vytvořit dost odlišné chování
		- tzv. novelty plateau
	- kreativní myšlení = *curiosity search* na vnitřních stavech (skrytých neuronech)
		- curiosity search se zabývá jenom výstupními neurony (chováním)
	- experiment: zavádějící bludiště
		- úloha nebyla dost těžká, tak na tom nebylo moc poznat
	- pro těžší úlohu (přemisťování míčků do osvětlené části) byl výsledek jasnější
		- kreativní myšlení bylo jasně lepší