Gramatická evoluce - Grammatical evolution
Gramatická evoluce (GE) je evoluční výpočet a konkrétněji technika (nebo přístup) genetického programování (GP) propagovaná Conorem Ryanem, JJ Collinsem a Michaelem O'Neillem v roce 1998 ve skupině BDS na univerzitě v Limericku , ačkoli existují další související práce, které byly publikovány ještě dříve, jako např.
Stejně jako v jakémkoli jiném přístupu GP je cílem najít spustitelný program, fragment programu nebo funkci, které dosáhnou dobré fitness hodnoty pro danou objektivní funkci . Ve většině publikovaných prací o GP je výraz ve stromové struktuře ve stylu LISP přímo manipulován, zatímco GE aplikuje genetické operátory na celočíselný řetězec, následně mapovaný na program (nebo podobný) pomocí gramatiky, která je obvykle vyjádřena v Forma Backus – Naur . Jednou z výhod GE je, že toto mapování zjednodušuje použití vyhledávání v různých programovacích jazycích a dalších strukturách.
Problém vyřešen
V konvenčním GP typu Koza ve stylu bez typu musí sada funkcí splňovat požadavek uzavření: všechny funkce musí být schopné přijmout jako své argumenty výstup všech ostatních funkcí v sadě funkcí. Obvykle se to implementuje jednáním s jedním datovým typem, jako je plovoucí desetinná čárka s dvojitou přesností. Zatímco moderní rámce genetického programování podporují psaní, takovéto typové systémy mají omezení, kterými Gramatická evoluce netrpí.
Řešení GE
Společnost GE nabízí řešení tohoto problému vývojem řešení podle uživatelem určené gramatiky (obvykle gramatiky ve formě Backus-Naur ). Proto lze omezit vyhledávací prostor a začlenit znalosti domény o problému. Inspirace pro tento přístup pochází z touhy oddělit „genotyp“ od „fenotypu“: v GP jsou objekty, na nichž vyhledávací algoritmus pracuje, a co interpretuje funkce hodnocení kondice, jedno a totéž. Naproti tomu „genotypy“ společnosti GE jsou uspořádané seznamy celých čísel, která kódují výběr pravidel z poskytnuté bezkontextové gramatiky. Fenotyp je však stejný jako v Kozově stylu GP: stromová struktura, která je hodnocena rekurzivně. Tento model je více v souladu s tím, jak genetika funguje v přírodě, kde existuje oddělení mezi genotypem organismu a konečnou expresí fenotypu v proteinech atd.
Oddělení genotypu a fenotypu umožňuje modulární přístup. Zejména vyhledávací část paradigmatu GE nemusí být prováděna žádným konkrétním algoritmem nebo metodou. Všimněte si, že objekty, na kterých GE provádí vyhledávání, jsou stejné jako objekty používané v genetických algoritmech . To v zásadě znamená, že k vyhledávání lze použít jakýkoli existující balíček genetických algoritmů, jako je populární GAlib , a vývojář implementující systém GE si musí dělat starosti s mapováním ze seznamu celých čísel na strom programu . V zásadě je také možné provádět vyhledávání pomocí jiné metody, jako je optimalizace částicového roje (viz poznámka níže); modulární povaha GE vytváří mnoho příležitostí pro hybridy, jak velí problém zájmu, který má být vyřešen.
Brabazon a O'Neill úspěšně aplikovali společnost GE na předpovídání bankrotu podniků, předpovídání akciových indexů, hodnocení úvěrových dluhopisů a dalších finančních aplikací. GE byl také použit s klasickým modelem dravec-kořist k prozkoumání dopadu parametrů, jako je účinnost predátora, počet mezer a náhodné mutace na ekologickou stabilitu .
Je možné strukturovat gramatiku GE, která je pro danou funkci/koncovou sadu ekvivalentní s genetickým programováním.
Kritika
Navzdory svým úspěchům byla společnost GE předmětem určité kritiky. Jedním problémem je, že v důsledku své mapovací operace nedosahují genetičtí operátoři GE vysoké lokality, což je v evolučních algoritmech vysoce ceněná vlastnost genetických operátorů.
Varianty
Přestože je GE poměrně nová, existují již vylepšené verze a varianty, které byly rozpracovány. Výzkumníci GE experimentovali s použitím optimalizace částicového roje k provádění vyhledávání místo genetických algoritmů s výsledky srovnatelnými s normálními GE; toto se označuje jako „gramatický roj“; pomocí pouze základního modelu PSO bylo zjištěno, že PSO je pravděpodobně stejně schopný provádět proces hledání v GE, jako jsou jednoduché genetické algoritmy. (Přestože je PSO obvykle paradigmatem hledání s pohyblivou řádovou čárkou, lze jej diskretizovat, např. Jednoduchým zaokrouhlením každého vektoru na nejbližší celé číslo, pro použití s GE.)
Ještě další možná variace, se kterou se experimentovalo v literatuře, se pokouší kódovat sémantické informace do gramatiky, aby se dále zkreslil proces hledání.
Viz také
Poznámky
- ^ "Gramatická evoluce: Vyvíjející se programy pro libovolný jazyk" .
- ^ https://www.researchgate.net/profile/PA_Whigham/publication/2450222_Grammatically-based_Genetic_Programming/links/55c3c89908aebc967df1b765.pdf
- ^ Alfonseca, Manuel; Soler Gil, Francisco José (2. ledna 2015). „Vyvíjející se ekosystém predátor-kořist matematických výrazů s gramatickou evolucí“. Složitost . 20 (3): 66–83. Bibcode : 2015Cmplx..20c..66A . doi : 10,1002/cplx.21507 . hdl : 10486/663611 .
- ^ a b DOI.org
- ^ "Publikace: Poziční efekt crossoveru a mutace v gramatické evoluci - School of Computing - University of Kent" .
Zdroje
- Kurz gramatické evoluce .
- Gramatická evoluce v Javě .
- jGE - Java Grammatical Evolution .
- Skupina Biocomputing and Developmental Systems (BDS) na University of Limerick .
- Stránka gramatické evoluce Michaela O'Neilla , včetně bibliografie.
- DRP , Directed Ruby Programming, je experimentální systém navržený tak, aby uživatelé mohli vytvářet hybridní systémy GE/GP. Je implementován v čistém Ruby.
- GERET , Gramatical Evolution Ruby Exploratory Toolkit.
- gramEvol , Gramatická evoluce pro R .