Genetické programování (GP) je v umělé inteligenci evoluční metodika založená na algoritmech inspirovaná biologickou evolucí k nalezení počítačových programů, které vykonávají uživatelem definovaný úkol. Je to specializace genetických algoritmů (GA), kde každý jednotlivec je počítačový program. Je to technika strojového učení používaná k optimalizaci populace počítačových programů podle fitness prostředí určeného schopností programu vykonávat daný výpočetní úkol.
V roce 1954 začal GP s evolučními algoritmy, které poprvé použil Nils Aall Barricelli, aplikovanými na evoluční simulace. V 60. a počátkem 70. let se evoluční algoritmy staly široce uznávanými metodami optimalizace. Ingo Rechenberg a jeho skupina byli schopni řešit složité inženýrské problémy pomocí evolučních strategií, jak je doloženo v jeho disertační práci z roku 1971 a výsledné knize z roku 1973. John Holland měl v 70. letech velký vliv.
V roce 1964 Lawrence J. Fogel, jeden z prvních praktiků metodologie GP, aplikoval evoluční algoritmy na problém objevování konečných automatů. Pozdější práce související s GP vyrostla z komunity učících se klasifikátorů systémů, která vyvinula sady řídkých pravidel popisujících optimální politiky pro Markovovy rozhodovací procesy. První prohlášení o moderním „stromovém“ genetickém programování (tedy procedurálních jazycích organizovaných ve stromových strukturách a provozovaných vhodně definovanými operátory GA) vydal Nichael L. Cramer (1985). Tato práce byla později značně rozšířena Johnem R. Kozou, hlavním zastáncem GP, který byl průkopníkem aplikace genetického programování v různých složitých optimalizačních a vyhledávacích problémech. Gianna Giavelli, Kozova studentka, byla později průkopníkem využití genetického programování jako techniky k modelování exprese DNA.
V 90. letech se GP používalo hlavně k řešení relativně jednoduchých problémů, protože je výpočetně velmi náročné. V poslední době přineslo GP mnoho neotřelých a vynikajících výsledků v oblastech, jako jsou kvantové výpočty, elektronický design, hraní her, třídění a vyhledávání, a to díky vylepšení technologie GP a exponenciálnímu růstu výkonu CPU. Tyto výsledky zahrnují replikaci nebo vývoj několika vynálezů z období po roce 2000. GP bylo také aplikováno na vyvíjející se hardware i počítačové programy.
Vývoj teorie pro GP byl velmi obtížný, a tak v 90. letech byla GP považována za jakéhosi vyvrhele mezi vyhledávacími technikami. Ale po sérii průlomů na počátku 21. století, měla teorie GP impozantní a rychlý vývoj. Natolik, že bylo možné sestavit přesné pravděpodobnostní modely GP (schematické teorie, Markovovy řetězové modely a meta-optimalizační algoritmy). [citace nutná][pochybné – viz diskusní stránka]
Funkce reprezentovaná jako stromová struktura.
GP vyvíjí počítačové programy, tradičně reprezentované v paměti jako stromové struktury. Stromy lze snadno vyhodnotit rekurzivním způsobem. Každý stromový uzel má operátorskou funkci a každý terminálový uzel má operand, takže matematické výrazy lze snadno vyvíjet a vyhodnocovat. GP tedy tradičně upřednostňuje použití programovacích jazyků, které přirozeně ztělesňují stromové struktury (například Lisp; další funkční programovací jazyky jsou také vhodné).
Byly navrženy a úspěšně implementovány reprezentace jiných než stromů, jako je lineární genetické programování, které vyhovuje tradičnějším imperativním jazykům [viz např. Banzhaf et al. (1998)]. Komerční GP software Discipulus používá automatickou indukci binárního strojového kódu („AIM“) pro dosažení lepšího výkonu. µGP používá řízené multigrafy pro generování programů, které plně využívají syntaxi daného assembleru.
Hlavní operátory používané v evolučních algoritmech, jako je GP, jsou crossover a mutace.
Crossover se aplikuje na jedince jednoduchým přepnutím jednoho z jeho uzlů s jiným uzlem od jiného jedince v populaci. U stromové reprezentace znamená nahrazení uzlu nahrazení celé větve. To zvyšuje efektivitu operátora crossoveru. Výrazy vyplývající z crossoveru jsou velmi odlišné od jejich původních rodičů.
Mutace ovlivňuje jedince v populaci. Může nahradit celý uzel ve vybraném jedinci, nebo může nahradit pouze informaci uzlu. Pro zachování integrity musí být operace zabezpečené proti selhání nebo musí být brán v potaz typ informace, kterou uzel obsahuje. Mutace si musí být například vědoma binárních operačních uzlů, nebo musí být operátor schopen zpracovat chybějící hodnoty.
Základní myšlenky genetického programování byly modifikovány a rozšiřovány různými způsoby:
Meta-Optimalizující sémantické evoluční vyhledávání (MOSES) je meta-programovací technika pro vývoj programů iterativně optimalizující genetické populace. Bylo prokázáno, že výrazně předčí genetické a evoluční systémy učení programů a byla úspěšně aplikována na mnoho reálných problémů, včetně výpočetní biologie, vyhodnocování sentimentu a kontroly agentů. Při aplikaci na sledované problémy klasifikace MOSES funguje stejně dobře jako, nebo lépe než podpůrné vektorové stroje (SVM), a zároveň nabízí větší vhled do struktury dat, protože výsledný program demonstruje závislosti a je srozumitelný způsobem, jakým velký vektor čísel není.
MOSES je schopen překonat standardní GP systémy ze dvou důležitých důvodů. Jedním z nich je, že používá odhad distribučních algoritmů (EDA) k určení Markovovy deky (tedy závislostí v bayesovské síti) mezi různými částmi programu. To rychle vylučuje nesmyslné mutace, které mění jednu část programu, aniž by provedly odpovídající změny v jiných, souvisejících částech programu. Druhým důvodem je, že provádí redukci, aby redukovala programy do normální podoby v každé iterační fázi, čímž činí programy menšími, kompaktnějšími, rychleji proveditelnými a čitelnějšími pro lidi. Kromě toho, že se vyhne špagetovému kódu, normalizace odstraňuje redundance v programech, čímž umožňuje menší populace méně složitých programů, urychluje konvergenci.
Meta-Genetické programování je navržená meta-učební technika vývoje genetického programovacího systému za použití samotného genetického programování. Naznačuje, že chromozomy, crossover a mutace byly samy o sobě vyvinuty, proto by se stejně jako jejich skutečné protějšky měly nechat změnit samy od sebe, spíše než aby byly určovány lidským programátorem. Meta-GP byla formálně navržena Jürgenem Schmidhuberem v roce 1987,. Eurisko Douga Lenata je dřívější úsilí, které může být stejnou technikou. Je to rekurzivní, ale ukončující algoritmus, umožňující vyhnout se nekonečné rekurzi.
Kritici této myšlenky často říkají, že tento přístup má příliš široký záběr. Mohlo by však být možné omezit kritérium zdatnosti na obecnou třídu výsledků, a tak získat vyvinutý praktický lékař, který by efektivněji produkoval výsledky pro podtřídy. To by mohlo mít podobu Meta vyvinutého praktického lékaře pro výrobu algoritmů lidské chůze, které se pak používají k vývoji lidského běhu, skákání atd. Kritérium zdatnosti aplikované na Meta praktického lékaře by bylo jednoduše kritériem účinnosti.
Pro obecné problémové třídy nemusí existovat způsob, jak prokázat, že Meta GP spolehlivě přinese výsledky efektivněji než vytvořený algoritmus jiný než vyčerpání. Totéž platí pro standardní GP a další vyhledávací algoritmy.