EVO: cvičení 3 - Genetické programování
- GP = evoluce spustitelných struktur, tomu je uzpůsoben i výběr operátorů.
- V rámci vyhodnocení fitness hodnoty je proveden kód kandidátního programu.
- GP má ze všech evolučních technik asi největší schopnost nás překvapit.
- chromozom - strom
- implementován jako binární strom v poli, potomci uzlu i jsou na indexech 2*i a 2*i+1
- některé (= většina) uzly jsou nevyužité
- inicializace
- Grow - strom roste náhodně, při dosažení maximální hloubky je ukončen (ale náhodně může skončit dřív).
- Full - strom má vždy maximální hloubku.
-
- křížení
- mutace
- nahraď uzel náhodně vygenerovaným podstromem
- fitness
Chráněné varianty funkcí -- Funkce musí vždy vrátit nějakou bezpečnou hodnotu.
- je dělení nulou chráněné na datovém typu Int?
- je dělení nulou chráněné na datovém typu Double? Je NaN bezpečná hodnota?
Symbolická regrese
několik pojmů na zmatení nepřítele:
Aproximace -
metoda nejmenších čtverců:
O výsledku musíme něco předpokládat, pak jen dopočítáme parametry.
|
|
Interpolace (křivka prochází danými body) - př. interpolace polynomem
|
|
Extrapolace:
odhad průběhu mimo rozsah zadaných bodů
|
|
Regrese =
odhad hodnoty závisle proměnné na základě znalosti nezávisle proměnné
|
Hledáme takovou funkci y = f(x), aby co nejlépe odpovídala známým bodům (x, f[x]).
Známé body (x, f[x]) můžeme zadat tabulkou, ale protože se nám nechce tu tabulku pořád přepisovat, necháme ji vygenerovat ze zadané funkce (ale evoluce tuto funkci samozřejmě nevidí, ta dostane jen tabulku!).
- stáhněte si archív s úlohou
- cv3.zip
- program na stderr vypisuje průběžné údaje (nejlepší jedinec v generaci, velikost a hloubka jeho stromu), nakonec na stdout vypíše příkazy pro gnuplot (vstupní body a nalezenou funkci).
- Jaký vliv mají křížení, mutace; různé typy inicializace (Grow × Full); druh fitness (suma odchylek × počet hitů)?
- Experimentujte, nalezněte vhodné parametry evoluce a funkci se zajímavým průběhem, kterou ale GP snadno vyevoluje.
- Dokáže naše GP nacházet funkce posunuté o konstantu (např. x**2 vs x**2+5)?
Neurčitý integrál
Primitivní funkce k funkci f(x) je taková funkce F(x), že F'(x) = f(x).
Mějme funkci F(x), jejíž derivace je funkce
f(x). F je tedy primitivní k f. Pokud by funkce F byla posunutá nahoru nebo dolů, její derivace bude pořád stejná. K funkci f tedy existuje nekonečně mnoho
primitivních funkcí, které se liší pouze o reálnou konstantu. Tato množina primitivních funkcí se často nazývá neurčitý integrál a píšeme
∫ f(x) dx = F(x) + C.
Pod pojmem určitý integrál
∫ab f(x) dx
rozumíme obsah plochy ve dvojrozměrné rovině, který je omezen grafem funkce f, osou x a svislými přímkami x = a a x = b.
Platí, že ∫ab f(x) dx = F(b) - F(a).
Dokážeme analyticky spočítat derivaci čehokoliv (až na výjimky). Opačný postup (integrace) neumíme.
Dokážeme numericky zintegrovat skoro cokoli (určitý integrál).
Můžeme evolučně najít neurčitý integrál?
Zkusíme trik, prakticky podvod: numericky spočítáme určitý integrál a ten předáme jako data GP symbolické regresi, ať najde funkci.
- Co konstanta? Až to najdeme, ručně dopíšeme "+C".
- Ale nebude nám vadit posun nahoru nebo dolu, naše GP je/není dobré při nacházení posunutých funkcí? Ano, posun nám bude vadit, chtěli bychom ho ignorovat.
- A co počáteční podmínky při integraci? Opět je to jen posun a ten už ignorujeme.
Odlišnosti od symbolické regrese z předešlé úlohy:
- Jiná vstupní data -- několik vzorků z určitého integrálu získané numerickou integrací.
- Jiná fitness -- musí hlídat správný tvar funkce, ale ignorovat posun (rozdíly každé dvojice vstupních vzorků a dvojice funkčních hodnot musí být stejné (s tolerancí, nemáme přesný vstup)).
- Podle návodu výše v zadání a pokynů cvičícího přenestavte program tak, aby místo symbolické regrese prováděl výpočet neurčitého integrálu.
- Ověřte funkčnost integrace na tabulkových integrálech typu
- ∫ x**2 dx = x**3/3 + c,
- ∫ sin(x) dx = -cos(x) + c,
- ∫ 1/(x**2+1) dx apod.
- Experimentujte, nalezněte vhodné parametry evoluce a zajímavou funkci, kterou evoluce snadno vyřeší.
PS: místo šizení z určitým integrálem bychom možná mohli každou kandidátní funkci zderivovat a porovnat se zadáním. Kdybyste to někdo zprovoznil a opublikoval, vzpomeňte si na mě v Poděkování.