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 biologie – dě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ě.

Obsah

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

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]

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]

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

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 4 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]

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 ohodnocující funkce je dána počtem jedničkových bitů v chromozomu.

číslo      chromozom               ohodnocení      % z celkového ohodnocení        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

Výběr dvojic individuí [editovat]

Tento výběr 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 ruletě, kde obvod rulety je 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ši.

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 4 pseudonáhodná čísla r \in <0,1> a tímto vybrána 4 individua pro reprodukci.

1. pár     2       (0,1,1,1,1,1,0,1)
                4       (1,1,0,0,1,1,0,0)
2. pár          3       (0,0,0,1,0,0,0,1)
                2       (0,1,1,1,1,1,0,1)

Křížení [editovat]

K vytvoření potomků jsou používány 2 základní genetické operátory - mutace a křížení. Existuje řada technik křížení, ale vždy dochází k výměně částí chromozomů.

Použijeme jednobodové křížení. Náhodně zvolíme gen v chromozomu a od tohoto genu 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.


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]

Aplikujeme další genetický operátor – mutaci. Mutace jednoduchým způsobem a s malou pravděpodobností mění náhodně hodnotu jednotlivých genů. Změníme tedy v některých chromozomech 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]

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]

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]

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]

Reference [editovat]

  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]

Citováno z „http://cs.wikipedia.org/w/index.php?title=Genetický_algoritmus&oldid=9841999“