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).

Tento článek potřebuje úpravy.

---

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.

Některé pojmy použité v dalším popisu:

• 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:

1. (Inicializace) Vytvoří se nultá populace (obvykle složená z náhodně vygenerovaných jedinců).
2. (Začátek cyklu) Pomocí určité výběrové metody (zpravidla zčásti náhodné) se vybere z populace několik jedinců s vysokou zdatností.
3. Z vybraných jedinců se vygenerují noví použitím následujících metod (operátorů), čímž vznikne další generace:
   • křížení – „prohození“ části několika jedinců mezi sebou;
   • mutace – náhodně se změní část jedince;
   • reprodukce – kopírování jedince beze změny.
4. Vypočte se zdatnost těchto nových jedinců.
5. (Konec cyklu) Pokud není splněna zastavovací podmínka, pokračuje se od bodu 2.
6. (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.^[1]

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.