Genetické programování - Genetic programming

V umělé inteligenci je genetické programování ( GP ) technikou vyvíjejících se programů, počínaje populací nevhodných (obvykle náhodných) programů, vhodných pro konkrétní úkol aplikací operací analogických přirozeným genetickým procesům na populaci programů. Je to v podstatě heuristická vyhledávací technika často popisovaná jako „horolezectví“, tj. Hledání optimálního nebo alespoň vhodného programu v prostoru všech programů.

Operace jsou: výběr nejvhodnějších programů pro reprodukci (crossover) a mutace podle předem definované míry zdatnosti, obvykle znalost požadovaného úkolu. Operace crossoveru zahrnuje výměnu náhodných částí vybraných párů (rodičů) za vzniku nových a různých potomků, kteří se stanou součástí nové generace programů. Mutace zahrnuje nahrazení nějaké náhodné části programu jinou náhodnou částí programu. Některé programy, které nebyly vybrány pro reprodukci, jsou zkopírovány z aktuální generace do nové generace. Poté se výběr a další operace rekurzivně aplikují na novou generaci programů.

Členové každé nové generace jsou obvykle v průměru vhodnější než členové předchozí generace a program nejlepší generace je často lepší než programy nejlepších generací předchozích generací. Ukončení rekurze je, když některý jednotlivý program dosáhne předdefinované úrovně znalostí nebo kondice.

Může a často se stává, že určitý běh algoritmu má za následek předčasnou konvergenci k nějakému místnímu maximu, což není globálně optimální nebo dokonce dobré řešení. K dosažení velmi dobrého výsledku je obvykle zapotřebí více běhů (desítky až stovky). Může být také nutné zvýšit počáteční velikost populace a variabilitu jednotlivců, aby se zabránilo patologiím.

Dějiny

První záznam o návrhu na vývoj programů je pravděpodobně o Alanu Turingovi v roce 1950. Mezi vydáním knihy „Adaptace v přírodních a umělých systémech“ Johna Hollanda, která položila teoretické a empirické základy vědy, byla mezera 25 let. V roce 1981 Richard Forsyth demonstroval úspěšný vývoj malých programů, reprezentovaných jako stromy, za účelem provedení klasifikace důkazů o místě činu pro britské ministerstvo vnitra.

Ačkoli myšlenka vyvíjejících se programů, původně v počítačovém jazyce Lisp , byla mezi studenty Johna Hollanda aktuální, teprve když uspořádali první konferenci Genetic Algorithms (GA) v Pittsburghu, Nichael Cramer publikoval vyvinuté programy ve dvou speciálně navržených jazycích, které zahrnoval první prohlášení o moderním „stromovém“ genetickém programování (tj. procedurální jazyky organizované ve stromových strukturách a provozované vhodně definovanými operátory GA). V roce 1988 si John Koza (také doktorand Johna Hollanda) nechal patentovat svůj vynález GA pro evoluci programu. Následovalo zveřejnění na mezinárodní společné konferenci o umělé inteligenci IJCAI-89.

Koza na to navázal 205 publikacemi o „genetickém programování“ (GP), jméno vytvořil David Goldberg, také doktorand Johna Hollanda. Je to však série 4 knih od Kozy, počínaje rokem 1992 s doprovodnými videi, která skutečně založila GP. Následně došlo k enormnímu rozšíření počtu publikací s Genetickou programovací bibliografií, která překonala 10 000 záznamů. V roce 2010 Koza uvedl 77 výsledků, kde bylo genetické programování konkurenceschopné pro člověka.

V roce 1996 zahájil Koza výroční konferenci Genetic Programming, na kterou v roce 1998 navázala výroční konference EuroGP a první kniha ze série GP, kterou upravil Koza. V roce 1998 byla také první učebnice GP. GP pokračovala v rozkvětu, což vedlo k prvnímu odbornému časopisu GP a o tři roky později (2003) založil Rick Riolo každoroční seminář Teorie a praxe genetické programování a praxe (GPTP). Dokumenty o genetickém programování jsou i nadále vydávány na různých konferencích a souvisejících časopisech. Dnes existuje devatenáct knih o GP, včetně několika pro studenty.

Základní práce v GP

Raná práce, která připravila půdu pro aktuální témata a aplikace výzkumu genetického programování, je různorodá a zahrnuje syntézu a opravy softwaru , prediktivní modelování, dolování dat, finanční modelování, měkké senzory, design a zpracování obrazu. Aplikace v některých oblastech, jako je design, často využívají přechodné reprezentace, jako je mobilní kódování Freda Gruau. Rozvoj průmyslu byl významný v několika oblastech, včetně financí, chemického průmyslu, bioinformatiky a ocelářského průmyslu.

Metody

Reprezentace programu

Funkce reprezentovaná jako stromová struktura

GP vyvíjí počítačové programy, tradičně zastoupené v paměti jako stromové struktury . Stromy lze snadno vyhodnotit rekurzivně. Každý uzel stromu má funkci operátora a každý koncový uzel má operand, což usnadňuje vývoj a vyhodnocování matematických výrazů. Tradičně tedy GP upřednostňuje použití programovacích jazyků, které přirozeně ztělesňují stromové struktury (například Lisp ; vhodné jsou také další funkční programovací jazyky ).

Byly navrženy a úspěšně implementovány nestromové reprezentace, jako je lineární genetické programování, které vyhovuje tradičnějším imperativním jazykům [viz například Banzhaf et al. (1998)]. Komerční GP software Discipulus využívá k dosažení lepšího výkonu automatickou indukci binárního strojového kódu („AIM“). µGP používá směrované více grafy ke generování programů, které plně využívají syntaxi daného jazyka sestavení . Mezi další reprezentace programu, na kterých byl proveden významný výzkum a vývoj, patří programy pro virtuální stroje založené na zásobníku a sekvence celých čísel, která jsou mapována do libovolných programovacích jazyků pomocí gramatik. Kartézské genetické programování je další formou GP, která ke kódování počítačových programů používá grafickou reprezentaci místo obvyklé stromové reprezentace.

Většina reprezentací má strukturálně neúčinný kód ( introny ). Takové nekódující geny se mohou zdát zbytečné, protože nemají žádný vliv na výkon žádného jednotlivce. Mění však pravděpodobnost generování různých potomků pod operátory variací, a tím mění variační vlastnosti jedince . Zdá se, že experimenty vykazují rychlejší konvergenci při použití programových reprezentací, které umožňují takové nekódující geny, ve srovnání s programovými reprezentacemi, které nemají žádné nekódující geny.

Výběr

Výběr je proces, při kterém jsou vybráni určití jednotlivci ze současné generace, kteří by sloužili jako rodiče pro další generaci. Jedinci jsou vybíráni pravděpodobnostně tak, aby lépe fungující jedinci měli vyšší šanci, že budou vybráni. Nejčastěji používanou metodou výběru v GP je turnajový výběr , i když bylo prokázáno , že jiné metody, jako je poměrný výběr podle kondice, výběr lexikázy a další, fungují lépe pro mnoho problémů s GP.

Elitářství, které zahrnuje nasazení další generace nejlepším jedincem (nebo nejlepšími n jedinci) ze současné generace, je technika, která se někdy používá k zabránění regrese.

Crossover

V genetickém programování jsou z populace vybráni dva vhodní jedinci jako rodiče jednoho nebo dvou dětí. V genetickém programování stromů jsou tito rodiče zastoupeni jako obrácené lisp jako stromy, s jejich kořenovými uzly nahoře. Při křížení podstromu v každém rodičovství je náhodně zvolen podstrom. (Na animaci je zvýrazněno žlutě.) V kořenovém dárcovském rodiči (v animaci vlevo) je vybraný podstrom odstraněn a nahrazen kopií náhodně zvoleného podstromu od druhého rodiče, aby byl vytvořen nový podřízený strom.

Někdy se používá křížení dvou dětí, v takovém případě odstraněný podstrom (v animaci vlevo) není jednoduše odstraněn, ale je zkopírován do kopie druhého rodiče (zde vpravo), která nahradí (v kopii) jeho náhodně zvolený podstrom. Tento typ křížení podstromu tedy bere dva vhodné stromy a generuje dva podřízené stromy. Crossover genetického programování podstromu

Mutace

V genetickém programování existuje mnoho typů mutací. Začínají od vhodného syntakticky správného rodiče a mají za cíl náhodně vytvořit syntakticky správné dítě. V animaci je náhodně vybrán podstrom (zvýrazněn žlutě). Je odstraněn a nahrazen náhodně generovaným podstromem.

Ostatní operátoři mutace vyberou list (externí uzel) stromu a nahradí jej náhodně vybraným listem. Další mutací je náhodný výběr funkce (interní uzel) a její nahrazení jinou funkcí se stejnou aritou (počet vstupů). Zvedací mutace náhodně vybere podstrom a nahradí jej podstromem v sobě. Je tedy zaručeno, že zvedací mutace zmenší dítě. Náhrada funkce listu a stejné arity zajišťuje, že dítě má stejnou velikost jako rodič. Zatímco mutace podstromu (v animaci) může mít v závislosti na funkci a koncových sadách zkreslení buď pro zvětšení nebo zmenšení velikosti stromu. Jiné mutace založené na podstromu se snaží pečlivě kontrolovat velikost náhradního podstromu a tím i velikost podřízeného stromu.

Animace vytváření dítěte s genetickým programováním mutací rodiče odstraněním podstromu a nahrazením náhodným kódem

Podobně existuje mnoho typů lineárních genetických programovacích mutací, z nichž každá se snaží zajistit, aby mutované dítě bylo stále syntakticky správné.

Aplikace

GP byl úspěšně použit jako nástroj pro automatické programování, nástroj pro strojové učení a nástroj pro automatické řešení problémů. GP je zvláště užitečný v doménách, kde není předem známa přesná forma řešení nebo je přijatelné přibližné řešení (možná proto, že najít přesné řešení je velmi obtížné). Některé z aplikací GP jsou přizpůsobení křivek, modelování dat, symbolická regrese , výběr funkcí , klasifikace atd. John R. Koza uvádí 76 instancí, kde genetické programování dokázalo vytvářet výsledky, které jsou konkurenceschopné s výsledky produkovanými lidmi (tzv. -konkurenční výsledky). Od roku 2004 každoroční konference Genetic and Evolutionary Computation Conference ( GECCO ) pořádá soutěž Human Competitive Awards (nazývaná Humies), kde se předávají peněžní ceny za výsledky konkurenceschopné vůči člověku vytvořené jakoukoli formou genetických a evolučních výpočtů. GP za ta léta získala mnoho ocenění v této soutěži.

Meta-genetické programování

Meta-genetické programování je navrhovaná metoda meta učení při vývoji systému genetického programování pomocí samotného genetického programování. Naznačuje to, že chromozomy, crossovery a mutace byly vyvinuty samy, a proto by stejně jako jejich protějšky ve skutečném životě mělo být umožněno, aby se změnily samy, nikoli aby je určoval lidský programátor. Meta-GP byla oficiálně navrhuje Jürgen Schmidhuber v roce 1987. Doug Lenat ‚s Eurisko je starší úsilí, které mohou být stejné techniky. Jedná se o rekurzivní, ale ukončující algoritmus, který mu umožňuje vyhnout se nekonečné rekurzi. V přístupu „autokonstruktivní evoluce“ k meta-genetickému programování jsou metody produkce a variace potomků zakódovány v samotných vyvíjejících se programech a programy jsou prováděny za účelem produkce nových programů, které mají být přidány do populace.

Kritici této myšlenky často říkají, že tento přístup je příliš široký. Mohlo by však být možné omezit kritérium způsobilosti na obecnou třídu výsledků, a tak získat rozvinutý GP, který by efektivněji vytvářel výsledky pro podtřídy. Může to mít formu meta evolučního GP pro vytváření algoritmů lidské chůze, který se pak používá k vývoji lidského běhu, skákání atd. Kritérium způsobilosti aplikované na meta GP by jednoduše znamenalo efektivitu.

Viz také

Reference

externí odkazy