Tree based genetic programming/cs

Genetické programování (genetic programming) je nejnovější z evolučních technik. Více také na Genetické programování (česká Wikipedie). Tree based genetic programming je jedna z forem genetického programování ve které je jedinec reprezentován stromem programu.

Contents

[edit] Jedinec v tree based GP

Reprezentován stromem programu o maximální hloubce max_depth. Strom musí být uzavřený.

  • uzavřenost - dodržení arity funkcí, tj. na konci větví musí být pouze terminály.
  • úplnost a postačitelnost - má-li robot chodit musí mít terminál MOVE jinak nenajdeme řešení
  • terminály - MOVE,TURN_LEFT,TURN_RIGHT,..
  • funkce - IF_FOOD_AHEAD, CODE_BLOCK, ...

[edit] Inicializace jedince

  • full - délka všech uzlů je max_depth
    • pokud jsme na úrovni max_depth, pak generujeme terminál, jinak funkci
  • grown - délka je náhodná, ale ne větší než max_depth
    • náhodně ze sjednocení terminálů a funkcí
  • half-and-half
    • přibližně rovnoměrné rozdělění hloubky stromů
      • P .. počet žádaných jedinců
      • rozdělíme P na max_depth-1 častí
      • každé části postupně přiřadíme hloubku 2,3,...,max_depth
      • vygenerujeme pro každou část 50% jedinců pomocí full a 50% pomocí grown s dodržením přižazených hloubek

[edit] Vhodnost jedince (Fitness)

  • hybná síla Darwinovského výběru v GP
  • v přírodě vhodnost určuje, zda se jedinec dožije věku ve kterém je schopen se rozmnožovat
  • ohodnocená např. počtem potomků
  • v GP kvalita (schopnost) řešit zadaný problém
  • Raw fitness, Standardized Fitness, Adjusted fitness
  • Normalized fitness
    • podíl fitness jedince a sumy fitness všech jedinců v populaci
    • rozsah 0 až 1, větší hodnota lepší, suma normalized fitness populace je rovna jedné

[edit] Operátory GP

Při vytváření nové generace jedinců máme prázdnou populaci, poté nádodně s respektováním pravděpodobností vybereme a použijeme některý operátor a to tak dlouho až má nová populace požadovaný počet jedinců

  • Způsoby výběru jedinců v prvním kroku následujících operací
    • Fitness proportionate selection - na základě hodnoty Normalized fitness
    • Tournament selection - náhodně je z populace vybraná množina jedinců a z nich nejlepší
    • Random selection - náhodný výběr

[edit] Primární operátory GP

[edit] Reprodukce

  • základní hnací motor Darw. teorie
  • 1.krok - výběr jednoho jedince
  • 2.krok - zkopírování jedince do další generace

[edit] Crossover (sexuální rekombinace)

  • 1.krok - výběr dvou jedninců
  • 2.krok - náhodný výběr uzlu stromu u obou rodičů, většinou mají vnitřní uzly větší pravděpodobnost výběru (větší funkční bloky, větší rozdíl mezi rodiči a potomky)
  • 3.krok - prohození vybraných podstromů mezi rodiči
  • 4.krok - potomci s hloubkou menší než max_depth jsou vloženi do populace, místo ostatních je vložen jeden z rodičů
  • POZN: Crossover v GP má stejnou funkci jako v GP, ale lépe bojuje proti předčasné konvergenci v populaci, protože ze dvou stejných rodičů mohou vzniknout odlišní jedinci.

[edit] Sekundární operátory GP

[edit] Mutace (někdy se řadí k primárním operátorům)

  • 1.krok - výběr jedince
  • 2.krok - výběr uzel, smaž jeho podstrom a vytvoř nový náhodný (respektuj max_depth)
  • 3.krok - vlož mutanta do populace

[edit] Permutace

  • 1.krok - výběr jedince
  • 2.krok - změna pořadí argumentů u funkcí
  • 3.krok - vlož mutanta do populace

[edit] Editace

  • 1.krok - výběr jedince
  • 2.krok - optimalizuj nesmyslné části NOT(NOT(X)) -> X
  • 3.krok - vlož mutanta do populace

[edit] Zapouzdření (enkapsulace)

  • označení vhodných podstromů k zamezení jejich modifikace

[edit] Decimace

  • většinou jen pro odstranění velkého množství nevhodných jedinců z první genereace (náhodně generovaná)
  • vybírá se jen asi 10% jedinců

[edit] Příprava pro aplikaci GP

  • vytvoření množiny terminálů
  • vytvoření množiny funkcí
  • určení způsobu výpočtu vhobnosti jedince (funkce fitness)
  • nastavení řídících paramatrů
  • nastavení kritéria pro zastavení GP a způsob výpisu výsledků

[edit] Literatura

[edit] Poznámky

  • Ano, niektore ulohy skutocne nejdu algoritmizovat. Dokazal to pan Ashby niekedy v 30.-40. rokoch minuleho storocia.
  • Potom je tu teorema o neuplnosti - Goedel.

[edit] J.Koza

  • kniha z roku 1999, okolo 1150 stránek
  • naprogramováno v Lispu (nebo Prologu?)
  • řešen problém Santa-Fe Ant a další
  • random tree depth: max 6
  • max tree depth: 17
  • init random type: half-and-half
  • P(vnitrni_uzel) = 0,9, P(vnejsi_uzel) = 0,1
  • ...
  • PS: nepoužíváme zapouzdření


Languages: 

English  • Česky

Retrieved from "http://pr.perl6.cz/parrot-lgp/wiki/Tree_based_genetic_programming/cs"
Personal tools
sister sites
Language