Genetické programování

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. října 2018; kontroly vyžadují 8 úprav .

Ve strojovém učení je genetické programování (GP) automatické vytváření nebo modifikace programů pomocí genetických algoritmů . Pomocí této metodiky se „pěstují“ programy, které stále lépe (v souladu s určitou fitness funkcí pro chromozomy) řeší zadaný výpočetní problém.

Historie

Kódovací algoritmus

Volba způsobu kódování programu v genetickém algoritmu je jedním z hlavních problémů genetického programování. Program by měl být nakódován tak, aby bylo snadné automaticky provádět náhodné změny (mutační operátor) a kombinovat dva algoritmy do jednoho (operátor crossover).

Metody kódování lze rozdělit do dvou tříd:

Neuronové sítě

Stromovité

V kódování stromu obsahuje každý uzel stromu funkci a každý list operand. Výraz reprezentovaný jako strom lze snadno rekurzivně vyhodnotit. Tradiční GPU se snáze používají k růstu programů napsaných v jazycích, které přirozeně ztělesňují stromovou strukturu: Lisp , Haskell , F# a další funkční programovací jazyky.

Byly také navrženy a úspěšně implementovány nestromové reprezentace programů, jako je lineární genetické programování vhodné pro tradiční imperativní jazyky.

Crossover operátor

Ve stromové reprezentaci je operátor křížení implementován výměnou mezi dvěma stromy libovolnými uzly spolu s jejich potomky (podstromy).

Příklad:

individuální . Děti [ randomChildIndex ] = ostatní Jednotlivec . Děti [ randomChildIndex ] ; Operátor mutace

Na rozdíl od crossover operátora operátor mutace ovlivňuje pouze jeden chromozom. Ve stromovém zobrazení jej lze implementovat změnou informací v uzlu nebo přidáním/odebráním uzlu nebo celého podstromu. V tomto případě je nutné hlídat správnost výsledků operátora.

Příklad:

individuální . Informace = náhodnéInformace ();

nebo

jednotlivec = vygenerovatNovehoIndividua ();

Metagenetické programování

Metagenetické programování je GP, ve kterém se mění a tedy „pěstuje“ nejen daný počítačový program, ale také samotné aplikované operátory křížení a mutací.

Odkazy

Literatura

  • Banzhaf, W., Nordin, P., Keller, RE, Francone, FD (1997), Genetické programování: Úvod: O automatické evoluci počítačových programů a jeho aplikacích , Morgan Kaufmann
  • Cramer, Nichael Lynn (1985), " Arepresentation for the Adaptive Generation of Simple Sequential Programs " ve sborníku z mezinárodní konference o genetických algoritmech a aplikacích , Grefenstette, John J. (ed.), CMU
  • Koza, JR (1990), Genetické programování: Paradigma pro genetické rozmnožování populací počítačových programů k řešení problémů , Technická zpráva katedry informatiky Stanfordské univerzity STAN-CS-90-1314 . Důkladná zpráva, možná použitá jako koncept jeho knihy z roku 1992.
  • Koza, JR (1992), Genetické programování: O programování počítačů prostřednictvím přirozeného výběru , MIT Press
  • Koza, JR (1994), Genetické programování II: Automatické zjišťování opakovaně použitelných programů , MIT Press
  • Koza, JR, Bennett, FH, Andre, D. a Keane, MA (1999), Genetické programování III: Darwinovské vynálezy a řešení problémů , Morgan Kaufmann
  • Koza, JR, Keane, MA, Streeter, MJ, Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Rutine Human-Competitive Machine Intelligence , Kluwer Academic Publishers
  • Langdon, WB, Poli, R. (2002), Základy genetického programování , Springer-Verlag
  • Poli, R., Langdon, WB, McPhee, NF (2008), A Field Guide to Genetic Programming , Lulu.com, volně dostupné z internetu ISBN 978-1-4092-0073-4
  • Smith, SF (1980), A Learning System Based on Genetic Adaptive Algorithms , PhD disertační práce ( University of Pittsburgh )
  • Sopov E.A. (2004), Evoluční algoritmy pro modelování a optimalizaci složitých systémů, disertační práce pro titul kandidáta technických věd, Krasnojarsk

.