Lukáš Marek - Vývoj aplikací (0:00 | 19.5.)   

Genetické programování (část 2)

V minulém díle seriálu jsme si probrali teoretický úvod, dnes se zkusíme podívat jak genetický algoritmus pracuje. Než začneme, tak poslední upozornění - autor není znalec přírodních věd, takže pokud je tedy mezi ctěnými čtenáři genetik, snad projeví jistou shovívavost.

Genetické algoritmy si kromě základní myšlenky vypůjčují od pana Mendela také názvosloví. Rozlišují tedy gen, jako základní stavební jednotku organismu. Organismus může být tvořen buď jednou, nebo dvěmi sadami genů. Sada genů se nazývá gameta. Organismy se mohou mezi sebou množit, mají tedy potomky a předky. V genetickém algoritmu potom organismus vyjadřuje vlastní řešení problému - pokud se vrátíme k problému z minulého dílu, použitý organismus bude tvořen několika geny, z nichž každý bude vyjadřovat pořadí navštívení daného města.

Posledním používaným pojmem je populace, což je jedna generace organismů.

No a protože jde o programování, tak gen může být tvořen (a to záleží i na konkrétní implementaci genetického programování) celým či desetinným číslem, znakem, booleovskou hodnotou a podobně.

Jednoduchý organismus s jednou sadou genů vypadá takto:

Organismus s dvěmi sadami genů - nazývaný též Mendelův organismus analogicky vypadá takto:

Jednoduché, ne?

Rozmnožování

Další analogii s přírodou najdeme v rozmnožování. Pokud "spáříme" dva organismy, vzniknou dva další. Chcete příklad?

V případě jednoduchých organismů tak, že první z potomků dostane náhodně gen buď z rodiče A nebo B, druhý z potomků dostane zbývající gen. Například takto:

U Mendelovských organismů je rozmnožování o trošku složitější, zato je ale podobné rozmožování u živých organismů:

Z každého organismu se totiž vezme jedna kompletní sada genů (gameta) a z těch se složí organismus nový. Potomci Mendelovského organismu jsou tedy více podobní svým rodičům.

V příštím díle se budeme věnovat mutacím - jako studijní materiál zatím doporučuji film Moucha ;-).