Lineární genetické programování

Lineární genetické programování (anglicky linear genetic programming, zkráceně LGP)^[1] je odvětví evolučních algoritmů, konkrétně genetického programování, kde jedinci jsou reprezentanti různých počítačových programů. Tyto programy jsou reprezentovány sekvencí instrukcí v nějakém imperativním programovacím jazyce či přímo ve strojovém kódu.

Každý LGP program odpovídá sekvenci lineárně seřazených instrukcí a je sekvenčně spouštěn. Slovo lineární neznamená, že by program mohl modelovat jen lineární funkce, ale chápání programu jako posloupnosti kroků.

Existují dva hlavní rozdíly lineárního genetického programování od známějšího stromového (v angličtině tree-based) genetického programování, v němž je program reprezentován stromem, jehož větve reprezentují nějakou operaci (např.: +,-,max,sin) a v listech se nacházejí konstanty. V kořeni se poté nachází výstup daného programu.

Na LGP program se můžeme dívat jako na graf datových toků (graph data flow), jenž může hodnotu proměnné (registru) použít i vícenásobně. To vede k tomu, že GLP program může být kompaktnější než program vyjádřený stromem, který když v jiné části potřebuje stejnou hodnotu, musí ji znovu vypočítat.
Lineární programy můžou obsahovat neefektivní části kódu (anglicky introns), které nemají vliv na výstup. Neefektivní části nejsou zbytečné, protože po aplikování genetických operátorů křížení a mutace se můžou stát efektivními. K vyhodnocování fitness funkce se tyto části mohou vynechat, a tím zrychlit zpracování programu. Detekci neefektivního kódu lze provést tak, že z grafu datových toků vynecháme všechny vrcholy, které se nepodílejí na výstupu programu.

Příklady LGP programů

LGP programy jsou reprezentovány sekvencí instrukcí. Díky tomu se programy oproti stromové variantě genetického programování jednodušeji čtou a jednodušeji se na ně aplikují evoluční operátory. Následuje ukázka jednoduchého programu, který počítá pravdivostní funkci na třech vstupech (R1, R2 a R3) a generuje jeden výstup (R0).

R4 = R2 AND R3
R0 = R1 OR R4
R0 = R3 AND R0
R4 = R2 AND R4   # Tato instrukce je neefektivní (nepřispívá do výstupu)
R0 = R0 OR R2

R1, R2 a R3 jsou vstupní registry, a z těchto registrů se dá jednom číst (read-only), zatímco z registrů R0 a R4 se dá číst i do nich zapisovat (read-write). Program je velmi jednoduchý a má jen pět instrukcí, což se však po aplikaci genetických operátorů křížení a mutace může rychle změnit. Tyto operátory mohou měnit délku jedince oproti klasickým evolučním algoritmům, kde jednotliví jedinci mají pevně danou délku. Je proto vhodné ve fitness funkci penalizovat velikost jedince, aby při podobné kvalitě výstupu preferovala kratší programy oproti delším.

Možná křížení:

jednobodové křížení (one-point crossover): vybereme náhodný bod v jednom jedinci a druhý náhodný bod v druhém jedinci a všechny instrukce za těmito body mezi jedinci prohodíme. V klasické evoluci jednobodové křížení generuje jen jeden náhodný bod, protože v klasické evoluci máme typicky pevnou délku jedinců.
dvoubodové křížení, $n$ -bodové křížení
segmentové křížení (nebo též linear crossover)^[1]

Možné mutace:

nahrazení instrukce za jinou náhodně vybranou instrukci
vymazání instrukce
přidání instrukce
nahrazení registru za jiný náhodně vybraný registr

V příkladu je uvedena i jedna instrukce, která je neefektivní (nebol intron), protože tato instrukce nemá vliv na výstup programu (na hodnotu v registru R0).

Další příklad jednoduchého programu napsaný v jazyce Slash/A, který je navržen pro použití v LGP. Jednotlivé instrukce jsou oddělené pomocí lomítka.

input/   # uloží vstup od uživatele a uloží ho do registru F
0/       # nastaví registr I = 0
save/    # uloží hodnotu registru F do data vektoru D na index I (tedy D[0] := F)
input/   # uloží další vstup uživatele do registru F
add/     # přičte k registru F hodnotu D[I] (tedy F := F + D[0])
output/. # vypíše hodnotu registru F na výstup

V tomto jazyce se jednoduše provádí/implementují různé genetické operátory, protože žádná funkce nemá parametry a nemusí se tedy řešit počet a typ vstupů (signatura) funkce. Jazyk vychází vstříc lineárnímu genetickému programování také tím, že každá nevalidní instrukce je při běhu programu ignorována.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Linear genetic programming na anglické Wikipedii.

↑ ^a ^b BRAMEIER, Markus; BANZHAF, Wolfgang. Linear genetic programming. New York: Springer (Genetic and evolutionary computation series). ISBN 978-0-387-31029-9.

Související články

Genetické programování

Externí odkazy

Slash/A - programovací jazyk a C++ knihovna speciálně navržená pro LGP
genetic-programming.org

[:0-1] BRAMEIER, Markus; BANZHAF, Wolfgang. Linear genetic programming. New York: Springer (Genetic and evolutionary computation series). ISBN 978-0-387-31029-9.

[1]