Genetický algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Genetický algoritmus (GA) je heuristický postup, který se snaží aplikací principů evoluční biologie nalézt řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus. Genetické algoritmy, resp. všechny postupy patřící mezi tzv. evoluční algoritmy používají techniky napodobující evoluční procesy známé z biologiedědičnost, mutace, přirozený výběr a křížení – pro „šlechtění“ řešení zadané úlohy.

Princip práce genetického algoritmu je postupná tvorba generací různých řešení daného problému. Při řešení se uchovává tzv. populace, jejíž každý jedinec představuje jedno řešení daného problému. Jak populace probíhá evolucí, řešení se zlepšují. Tradičně je řešení reprezentováno binárními čísly, řetězci nul a jedniček, nicméně používají se i jiné reprezentace (strom, pole, matice, …). Typicky je na začátku simulace (v první generaci) populace složena z naprosto náhodných členů. V přechodu do nové generace je pro každého jedince spočtena tzv. fitness funkce, která vyjadřuje kvalitu řešení reprezentovaného tímto jedincem. Podle této kvality jsou stochasticky vybráni jedinci, kteří jsou modifikováni (pomocí mutací a křížení), čímž vznikne nová populace. Tento postup se iterativně opakuje, čímž se kvalita řešení v populaci postupně vylepšuje. Algoritmus se obvykle zastaví při dosažení postačující kvality řešení, případně po předem dané době.

Obecné schéma genetického algoritmu[editovat | editovat zdroj]

Algoritmus lze slovy zapsat takto:

  1. (Inicializace) Vytvoř nultou populaci (obvykle složenou z náhodně vygenerovaných jedinců)
  2. (Začátek cyklu) Pomocí určité výběrové metody (zpravidla zčásti náhodné) vyber z populace několik jedinců s vysokou zdatností
  3. 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
  4. Vypočti zdatnost těchto nových jedinců
  5. (Konec cyklu) Pokud není splněna zastavovací podmínka, tak pokračuj od bodu 2
  6. (Konec algoritmu) Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje nejlepší nalezené řešení.

Pojmy[editovat | editovat zdroj]

Pro jedince se používá označení fenotyp a pro jeho reprezentaci se používá termín genotyp, genom nebo chromozom.[1]

Chromozom se dělí na jednotlivé geny, které jsou lineárně uspořádány. To znamená, že i-tý gen chromozomů stejného typu reprezentuje stejnou charakteristiku. Gen nabývá různých hodnot, kterým se říká alely.[2]

Individua mohou být zakódována (geneticky popsána) různým způsobem. To, jakým způsobem jsou popsána, může být důležité pro úspěch či neúspěch řešení konkrétní úlohy. Jedním z jednoduchých způsobů může být například binární řetězec dané délky.[3]

Příklad genetického algoritmu[editovat | editovat zdroj]

Vytvoření počáteční generace[editovat | editovat zdroj]

Předpokládejme, že je počáteční generace tvořena množinou náhodně vygenerovaných řetězců dané délky. Například množinu čtyř individuí reprezentovaných chromozomem délky 8.

(1,0,1,0,1,1,0,0)
(0,1,1,1,1,1,0,1)
(0,0,0,1,0,0,0,1)
(1,1,0,0,1,1,0,0)

Ohodnocení individuí[editovat | editovat zdroj]

Definice ohodnocující (fitness) funkce je dána konkrétním problémem, protože cílem je najít takové individuum nebo individua, která mají z hlediska příslušného problému optimální vlastnosti. Předpokládejme, že v našem příkladu je ohodnocující funkce dána počtem jedničkových bitů v chromozomu.

číslo chromozom ohodnocení podíl celkového kumulativně
#1 (1,0,1,0,1,1,0,0) 4 0,250 0,250
#2 (0,1,1,1,1,1,0,1) 6 0,375 0,625
#3 (0,0,0,1,0,0,0,1) 2 0,125 0,750
#4 (1,1,0,0,1,1,0,0) 4 0,250 1,000

Tvorba potomků[editovat | editovat zdroj]

K vytvoření potomků jsou používány dva základní genetické operátory – mutace a křížení.

U křížení vzniká v nové generaci potomek (či několik potomků současně) na základě dvou vybraných rodičů z generace předchozí. Nejprve se zvolí dvojice individuí, na kterou se poté aplikuje operátor křížení, čímž vznikne potomek či potomci.

Výběr dvojic individuí[editovat | editovat zdroj]

Výběr „rodičů“ by měl respektovat pravidla přirozeného výběru dle Darwinovy teorie o původu druhů. To znamená, že zdatnější jedinci mají větší šanci se prosadit v konkurenci jiných, lépe překonávat překážky a žít déle. Jedinci s vyšším ohodnocením mají větší pravděpodobnost výběru partnera. Výběr se dá přirovnat k ruletě, kde je obvod rulety rozdělen do oblastí různých velikostí podle hodnocení jedince. Náhodné číslo má pak vyšší pravděpodobnost, že dopadne zrovna do části, která patří jedinci s vyšší fitness, nežli do oblasti jedince s nižší fitness, protože jeho oblast na obvodu rulety je menší.

V tomto příkladu je pravděpodobnost výběru i-tého partnera dána vztahem p_i=\frac{f_i}{\sum_{j=1}^N f_j}. Byla vygenerována čtyři pseudonáhodná čísla r \in \langle 0, 1 \rangle a tímto vybrána čtyři individua pro reprodukci.

r individuum chromozom
1. pár 0,340 #2 (0,1,1,1,1,1,0,1)
0,975 #4 (1,1,0,0,1,1,0,0)
2. pár 0,705 #3 (0,0,0,1,0,0,0,1)
0,409 #2 (0,1,1,1,1,1,0,1)

Křížení[editovat | editovat zdroj]

Existuje řada technik křížení, ale vždy dochází k výměně částí chromozomů.

V tomto příkladu použijeme nejjednodušší jednobodové křížení. Náhodně zvolíme místo v chromozomu, od kterého počínaje vyměníme zbylé části chromozomu mezi oběma rodiči. Tím vzniknou dva noví jedinci, z nichž každý má část genetické výbavy po obou rodičích. V některých případech může být užitečné zachovat kopie rodičů pro příští generace beze změny.

individuum původní chromozom nový chromozom
1. pár #2 (0,1 | 1,1,1,1,0,1) (0,1 | 0,0,1,1,0,0)
#4 (1,1 | 0,0,1,1,0,0) (1,1 | 1,1,1,1,0,1)
2. pár #3 (0,0,0,1 | 0,0,0,1) (0,0,0,1 | 1,1,0,1)
#2 (0,1,1,1 | 1,1,0,1) (0,1,1,1 | 0,0,0,1)

Mutace[editovat | editovat zdroj]

Na výsledné potomstvo se aplikuje ještě další genetický operátor – mutace. Ta s malou pravděpodobností jednoduchým způsobem náhodně mění hodnotu jednotlivých genů. V náhodně vybraných chromozomech tedy změníme hodnotu genu:

(0,1,0,0,1,1,0,0)  ⇒  (0,1,0,1,1,1,0,0)        
(1,1,1,1,1,1,0,1)  ⇒  (1,1,1,1,1,1,0,1)
(0,0,0,1,1,1,0,1)  ⇒  (0,0,0,1,1,1,0,1)
(0,1,1,1,0,0,0,1)  ⇒  (0,0,0,1,1,1,0,0)

Zatímco křížení nastává s pravděpodobností obvykle 0,75–0,95[4] a do značné míry ovlivňuje efektivnost genetického algoritmu, mutace nastávají s pravděpodobností 0,001–0,05 a brání příliš rychlému zjednotvárnění vlastností v populaci, ztrátě potencionálně užitečného genetického materiálu a předčasné konvergenci populace.[2]

Opakování cyklu[editovat | editovat zdroj]

Právě vytvořené potomstvo se stává novou generací a starou generaci již nebereme v úvahu. Jedná se o nejjednodušší generační strategii, při které původní populace zcela vymře. Tím byl dokončen přechod od jedné populaci k druhé a celý cyklus se bude opakovat dokud nebude splněna ukončovací podmínka.

Ukončení algoritmu[editovat | editovat zdroj]

Podmínkou pro ukončení algoritmu může být například maximální počet generací, po který je populaci umožněn její vývoj, nalezení uspokojivého řešení, nedostatečná změna nejlepšího dosud nalezeného řešení v posledních k generacích atd.

Optimalizační úloha[editovat | editovat zdroj]

Genetické algoritmy jsou často v praxi využívány k řešení rozmanitých optimalizačních úloh. Přestože uvedený postup řešení genetického algoritmu je čistě ilustrativní, lze tento postup aplikovat s drobnými úpravami např. na řešení extremálních úloh.

Předpokládejme funkci dvou proměnných f(x,y). Hledáme maximum funkce na množině D=(x,y)|x,y \in \langle-100,100\rangle. Předpokládáme, že požadovaná přesnost je 4 místa za desetinnou čárkou. Potom je nezbytné rozdělit interval alespoň na: (100-(-100))\times 10\,000=2\,000\,000 stejných dílů. To znamená použít binární vektor délky 42 bitů (21 bitů pro proměnnou x, a stejný počet pro proměnnou y). Tímto byla vyřešena otázka zakódování jedinců, kterého je možné kdykoliv převést na hodnoty proměnných x a y.

Jako ohodnocující funkce je možné použít vlastní funkci f(x,y), která je nezáporná a má dostatečnou rozlišovací schopnost. Protože cílem je najít její maximum, není nutné ji ani nijak modifikovat (jinak by bylo nutné provést její transformaci). K ohodnocení individuí je nutné pouze dekódovat hodnoty proměnných x a y a pro každé individuum spočítat hodnoty funkce f(x,y).

Dále už může algoritmus pokračovat základními genetickými operátory křížení a mutace uvedenými výše. Je samozřejmě také nutné zvolit velikost počáteční populace (např. N=100) a pravděpodobnosti křížení (např. 0,9) a mutací (např. 0,01).

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. Mitchell, M.: An Introduction to Genetic Algorithms. Cambidge, MA: MIT Press 1996
  2. a b Hynek, Josef: Genetické algoritmy a genetické programování. Grada: Praha 2008
  3. Holland, J. H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan, 1975
  4. Schaffer, J. D., Caruana, R. A. Eschelman, L. J., Das, R.: A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization.

Externí odkazy[editovat | editovat zdroj]