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

Logo Matematická biologie

Základní pojmy

Mezi základní pojmy GA patří jedinec, označme jej Ten je v GA v souladu s biologickou analogií popsán sadou svých „chromosomů“ a konkrétním obsahem jednotlivých genů. Konkrétní reprezentace jedince může být v GA představovánajediným (haploidní jedinec) řetězcem (polem) číselných hodnot, kde konkrétní pozice v tomto řetězci odpovídá konkrétnímu genu a hodnota v tomto poli pak zprostředkovaně určuje vlastnost daného jedince.Číselné hodnoty nejčastěji implementujeme z důvodu jednoduchosti práce s nimi jako binární, ale mohou obecně nabývat reálných hodnot s tím, že pak jsou prováděné výpočty významně komplikovanější. Jedince v GA můžeme tedy za použití binárních hodnot popsat jako řetězec

(1)

Populace je pak tvořena sadou jedinců

(2)

Účelová funkce  zobrazuje z prostoru binárního genotypu do prostoru reálných čísel. Každý jedinec se tedy projevuje prostřednictvím hodnoty své účelové funkce, která modeluje prostředí. Její hodnota je analogií fenotypu a provádí transformaci

(3)

Platí, že čím je hodnota účelové funkce nižší, tím je daný jedinec optimálnější v kontextu daného konkrétního řešeného problému. Jedinec s minimální hodnotou účelové funkce tedy představuje nejvhodnější aktuálně známé řešení daného problému. Účelová funkce je tedy kriteriem, které odhaduje blízkost daného jedince k řešení (jedinci) optimálnímu a které se snažíme minimalizovat. V NN je analogickým minimalizačním procesem hledání optimálních hodnot vah sítě v průběhu adaptační dynamiky – minimalizace chybové funkce sítě.

Každého jedince v populaci můžeme ohodnotit dle jeho vhodnosti k přežití vůči ostatním vzhledem k danému prostředí. K tomu to účelu slouží funkce Vhodnosti (fitness). Vhodnost jedince je zobrazení

(4)

Z praktických důvodů je vhodné zavést normalizaci tak, aby hodnota fitness byla pro všechny jedince v intervalu zavádíme tedy normalizovanou funkci vhodnosti, kde platí:

Nejjednodušším způsobem, jak vyčíslit fitness jedince je provést lineární interpolaci jednotlivých bodů fitness z účelové funkce

(7)

kde je hodnota blízká nule.

Řešení úlohy pomocí GA vypadá rámcově tak, že máme k dispozici, respektive vygenerujeme počáteční populaci jedinců, představující několik prvků z prostoru možných řešení.

Tyto jedince je možné vyhodnotit a určit u nich funkci vhodnosti. Tím bychom dle maxima funkce vhodnosti vybrali jednice nejvhodnějšího, ovšem pouze z velmi omezené počáteční populace představující jen omezenou oblast řešení. Velmi pravděpodobně by se nejednalo o nejoptimálnější globální řešení.

Abychom byli schopni prozkoumat pokud možno co nejširší oblast řešení, musíme mít k dispozici možnost vytvářet jedince nové.Stávající jedince v populaci  necháme„rozmnožit“ a vygenerujeme tak populaci novou představující další prvky z prostoru řešení.

Celý prostor možných řešení a tedy všechny možné jedince ale ve většině případů vzhledem k jeho velkým rozměrům a výpočetní náročnosti vygenerovat a vyhodnotit nelze. Proto nenecháme rozmnožovat všechny jedince aktuální populace, ale pouze jedince nejnadějnější z pohledu funkce vhodnosti. Ostatní jedinci s nižší hodnotou funkce vhodnosti se zpravidla nerozmnožují a „umírají“. Při rozmnožování je tak vytvořena populace nová, která je představována potomky z populace předcházející. Celková velikost populace zůstává zpravidla konstantní.

Řešení či skupina možných řešení úlohy pomocí GA jsou tedy představovány hledáním takových jedinců, kteří mají z pohledu daného problému optimální vlastnosti (hledáme minimum účelové funkce, jedince s maximální hodnotou funkce vhodnosti). Je zřejmé, že GA musí mít možnost generovat z populace nové jedince a vybírat z nich ty nejlepší. K tomu slouží operátory (křížení, mutace, selekce), které jsou blíže popsané v dalších podkapitolách.

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