Genetické programování

Genetické programování (GP) využívá metod podobných biologické evoluci při vytváření počítačových programů, které co nejlépe řeší danou úlohu. Jedná se o metodu strojového učení, která používá evoluční algoritmy, které postupně zlepšují populaci počítačových programů. Za nejdůležitějšího z otců této metodologie se považuje John R. Koza (kniha Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press, 1992), i když první experimenty v tomto směru prováděli již Stephen F. Smith (1980) a Nichael L. Cramer (1985).

Algoritmus genetického programování 
Dnes již existuje celá škála různých variant genetického programování. Proto zde nelze podat vyčerpávající popis všech variant. Ani následující schéma klasického algoritmu tohoto druhu nelze vztáhnout na všechny aplikace, ale může sloužit pochopení principu metody.

V dalším popisu použijeme tyto termíny:
 Jedincem se rozumí vhodně zakódovaný počítačový program. Během výpočtů se takových programů vygeneruje v řadě po sobě následujících generací velké množství a na závěr se vybere nejlepší z nich.
 Zdatnost čili fitness je výsledek funkce zdatnosti (fitness function), která každému jedinci přiřadí číslo vyjadřující jeho schopnost řešit původně zadanou úlohu. Čím vyšší zdatnost, tím je jedinec kvalitnější. Hledaný nejlepší jedinec se pozná právě podle toho, že dosáhl nejvyšší zdatnosti. Funkce zdatnosti tak vyjadřuje cíl celého počínání, tj. program kvalitně řešící zadanou úlohu.
 Populace je soubor (obvykle stovek nebo tisíců) jedinců, které počítač zpracovává v jednom cyklu („vlně“) výpočtu.

Algoritmus lze slovy zapsat takto:
 (Inicializace) Vytvoř nultou populaci (obvykle složenou z náhodně vygenerovaných jedinců).
 (Začátek cyklu) Pomocí určité výběrové metody (zpravidla zčásti náhodné) vyber z populace několik jedinců s vysokou zdatností.
 Z vybraných jedinců vygeneruj nové použitím následujících metod (operátorů), čímž vznikne další generace:
 křížení – „prohoď“ části několika jedinců mezi sebou;
 mutace – náhodně změň část jedince;
 reprodukce – kopíruj jedince beze změny.
 Vypočti zdatnost těchto nových jedinců.
 (Konec cyklu) Pokud není splněna zastavovací podmínka, tak pokračuj od bodu 2.
 (Konec algoritmu) Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje nejlepší nalezené řešení.

V algoritmu nemusí být použity všechny tři uvedené operátory – záleží na konkrétní implementaci. V případě, že zvolená výběrová metoda může během evoluce odstranit nejlepšího jedince z populace, je vhodnější hledat nejlepšího jedince v každé generaci během celé evoluce.

Počítačová implementace 
Počítačové programy pro genetické programování mohou být napsány v nejrůznějších programovacích jazycích. V nejstarších implementacích byly instrukce programu a datové hodnoty organizovány ve stromových strukturách, což upřednostňovalo jazyky, které přirozeně zahrnují tyto struktury (příkladem je Kozou propagovaný Lisp). Později byly navrženy a úspěšně realizovány také jiné typy implementace, jako např. s lineární reprezentací jedinců, která více vyhovuje klasickým imperativním jazykům [Banzhaf a kol. (1997)]. Např. komerční software Discipulus používá právě lineární genetické programování kombinované s použitím strojového kódu pro vyšší rychlost.

Metodami genetického programování bylo ke konci roku 2003 již ve 36 různých složitých úlohách dosaženo výsledků přinejmenším srovnatelných s lidskými.

Mezi nejnovější úspěchy na poli teorie GP patří vytvoření přesného pravděpodobnostního modelu, který dokázal, že genetické algoritmy jsou podmnožinou genetického programování.

Zhodnocení metody 
Genetické programování je metodou, která umožňuje najít řešení klasických problémů a někdy také najde uspokojivé řešení některých velmi komplikovaných, nelineárních nebo kombinatorických úloh, například v oblasti data miningu nebo předpovídání počasí. GP může být u některých typů úloh náročnější na výpočetní výkon ve srovnání se specializovanějšími algoritmy a metodami.

Reference

Literatura 
 Mařík V., Štěpánková O., Lažanský J. a kol: Umělá inteligence 4, Academia, Praha, 2003, .
 Banzhaf, W., Nordin, P., Keller, R. E., Francone, F. D. (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
 Cramer, Nichael Lynn (1985), „A representation for the Adaptive Generation of Simple Sequential Programs“ in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
 Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
 Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
 Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
 Koza, J.R., Bennett, F. H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
 Koza, J.R., Keane, M. A., Streeter, M. J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
 Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
 Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, freely available from the internet 
 Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)

Související články 
 Biologická zdatnost

Externí odkazy 
 Genetic Programming FAQ
 The Hitch-Hiker's Guide to Evolutionary Computation
 John Koza's Genetic Programming Site
 Juergen Schmidhuber's GP Site, s články o GP napsanými před Kozovým článkem z roku 1987
 Bill Langdon's GP bibliography
 Meta-Genetic Programming Site
 Markus Brameier: On linear genetic programming, PDF, 1/2005
 ADT - nový způsob reprezentace jedince v populaci 

Umělá inteligence
Programování

de:Evolutionärer Algorithmus#Genetische Programmierung