Slovník | Vyhledávání | Mapa webu
 
Analýza a hodnocení biologických datUmělá inteligence Úvod do genetických algoritmů (GA) Úlohy GA GA souhrn

Logo Matematická biologie

GA souhrn

Typické kroky GA lze shrnout následovně:

  1. Inicializace populace, kódování a nastavení parametrů jedinců. První generace.
  2. Ohodnocení populace, definice kritérií pro jedince. Výpočet fitness.
  3. Selekce jedinců k reprodukci.
  4. Křížení rodičovských jedinců, vytvoření potomků. Výběr potomků pro příští generaci.
  5. Mutace některých jedinců v nové populaci.
  6. Vyhodnocení jedinců nové populace, zda některý není řešením. Ano = konec.
  7. Pokud není, pak pokračuj bodem 2 pro novou populaci.

Genetické algoritmy jsou vhodné pro optimalizační úlohy, které jsou matematickými metodami řešitelné obtížně, nebo vůbec. Jejich implementace bývá relativně jednoduchá, nicméně často vyžadují mnoho strojového času a operační paměti. Velkou implementační výhodou GA je možnost jejich snadné paralelizace na více výpočetních jednotkách. GA vždy dosáhnou nějakého řešení, otázkou je, zda bude dostatečně kvalitní, záruka jeho optimálnosti neexistuje. Lze zde pozorovat jistý rozdíl od klasických algoritmů, které při hledání řešení postupují gradientními metodami, v zásadě v jednom pravděpodobně nejsprávnějším směru dle hodnoty gradientu kriteriální funkce. GA oproti tomu prozkoumávají širší oblast řešení, nevyžadují na rozdíl od gradientních metod spojitou kriteriální funkci a operátor mutace umožňuje prozkoumat i řešení zcela mimo aktuální lokální minimum. GA zpravidla rychle konvergují k nalezení konkrétního suboptimálního řešení, ale další zpřesňování k nalezení optimálního řešení v této prohledávané oblasti bývá pomalé. Proto se často používají tzv. hybridní algoritmy, kdy je nejprve použit GA a optimální řešení je pak prohledáváno lokálně gradientní metodou.

 

 
vytvořil Institut biostatistiky a analýz Masarykovy univerzity | | zpětné odkazy | validní XHTML 1.0 Strict