\section{Klasické genetické algoritmy}

\emph{Genetický algoritmus},
dále jen
\emph{GA},
je jednou z pokročilých optimalizačních technik, které jsou
insipirovány principy genetiky a dříve popsaným mechanismem
přírodního výběru.

Tento algoritmus je řazen mezi globální iterativní
\emph{heuristiky},
tedy metody pro řízené prohledávání stavového prostoru určité třídy
problémů. Jejich účelem je co nejrychlejší nalezení použitelného
řešení nebo naopak nalezení řešení, které se bude co nejvíce blížit
řešení optimálnímu, bez ohledu na čas strávený jeho hledáním
\cite{WIKI_HEUR}.

Základním principem funkce GA je udržování konstatně veliké
populace řešení daného problému a její evoluce v diskrétním čase za
použití principů přírodního výběru (viz obr.
\ref{fig:theory-ga_scheme})
\cite{HAUPT04}.
Diskrétním časem se zde myslí tok času odměřovaný v pevně
stanovených intervalech a vyjádřený ve formě posloupnosti generací
uvažované populace.

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.55\textwidth]{figs/ga_scheme.png}
\caption{Obecné schéma genetického algoritmu}
\label{fig:theory-ga_scheme}
\end{center}
\end{figure}

Tímto způsobem napodobuje algoritmus vzorce chování, které můžeme
pozorovat v přírodě a ve své podstatě modeluje proces adaptace
populace řešení daného problému na prostředí, které je popsáno
omezující podmínkou a optimalizačním kritériem tohoto problému.

Omezující podmínku zde uvádím výslovně pro to, že z určitého úhlu
pohledu ji můžeme považovat za doplnění optimalizačního kritéria.
O jedincích, kteří jí nevyhovují a nejsou tak platným řešením,
můžeme totiž prohlásit, že jejich kvalita je z hlediska
optimalizačního kritéria nulová nebo dokonce záporná. I přes tento
fakt můžeme takové jedince v populaci ponechat a nevyřazovat je tak
zcela ze soutěže o přežití. V některých případech je pak takový
postup dokonce výhodný a má pozitivní vliv na vývoj celé populace.

Jako první zformuloval základní myšlenky genetického algoritmu
v sedmdesátých letech minulého století americký vědec John
H.\ Holland. Tuto myšlenku pak mnozí, včetně Hollanda samotného
a některých jeho studentů
\cite{HAUPT04},
dále rozvíjeli a takto vzniklé implementace genetického algoritmu
pak aplikovali s různou měrou úspěšnosti na širokou škálu
optimalizačních problémů.

Klíčové charakteristiky genetického algoritmu zahrnují
\cite{HAUPT04}:

\begin{itemize}
\item{
Pro GA není důležité, zda pracuje s vnitřními proměnnými diskrétního
nebo spojitého charakteru, a jeho výkonnost tedy není přímo závislá
na typu proměnných použitých při formulaci řešeného problému.

Z toho vyplývá, že GA lze použít téměř na libovolný problém, jehož
množiny charakteristických proměnných mají konečnou mohutnost.
}

\item{
GA není příliš citlivý na počet konfiguračních proměnných řešeného
problému, a tudíž ani na dimenzi odpovídajícího stavového prostoru.

S rostoucím počtem konfiguračních proměnných ovšem koreluje dimenze
stavového prostoru a jeho velikost se zvětšuje zpravidla
exponenciálně. Tento fakt je nutné vzít v úvahu při volbě velikosti
počáteční populace a minimálního počtu generací, po který bude
probíhat evoluce.
}

\item{
Pro GA je také typické, že současně prohledává více rozsáhlých
oblastí stavového prostoru. Konkrétní tvar, velikost a počet těchto
oblastí je na začátku algoritmu určen volbou počáteční sady řešení
a v průběhu samotného výpočtu algoritmu se pak dále vyvíjí.

Díky této charakteristice jsou tyto algoritmy vhodné k paralelizaci,
což je v dnešní době, kdy se stále více využívají paralelní
výpočetní systémy, velice žádoucí vlastnost.
}

\item{
S předchozím bodem také souvisí jedna důležitá vlastnost, a tou je
možnost výstupu několika optimálních, příp. suboptimálních řešení
daného problému na konci algoritmu.

Tato vlastnost nám může být užitečná například v situacích, kdy na
výsledné řešení máme i jiné požadavky, než jsme do algoritmu vložili
ve formě optimalizačního kritéria.

Taková situace může nastat v případě, když v době formulace problému
nejsou plně známy všechny požadavky na kvalitu výsledného řešení
nebo jsou-li takové požadavky do optimalizačního kritéria jen velice
obtížně zapracovatelné.
}

\item{
S ohledem na výše popsaný způsob prohledávání stavového prostoru
je zřejmé, že GA je zcela imunní vůči případným nespojitostem
optimalizačního kritéria řešeného problému a navadí mu ani extrémně
složitá plocha stavového prostoru.
}

\item{
Poslední z vlastností GA, kterou v tomto výčtu uvedu, je možnost
transformace konfiguračních proměnných řešeného problému.

Pokud nám typ těchto proměnných nebo podmínky, kterými jsou svázány,
z nějakého důvodu nevyhovují, můžeme proměnné nahradit za takové, se
kterými se nám bude snáze pracovat.

Říkáme pak, že jsme konfigurační proměnné zakódovali pomocí kódu,
který přiřazuje vnitřním proměnným algoritmu sémantický význam
v rámci kontextu řešeného problému právě ve formě konfiguračních
proměnných.
}
\end{itemize}

Je důležité si uvědomit, že ačkoliv dávají výše uvedené vlastnosti
genetickým algoritmům při řešení řady problémů výhodu před jinými
typy heuristik, mohou také za určitých podmínek hledání optimálního
řešení znatelně zkomplikovat.

Jedním z příkladů takového chování je situace, kdy má plocha
stavového prostoru velice jednoduchý, např. konkávní tvar (ve formě
prohlubně). V takovém případě zpravidla optimální řešení naleznou
dříve heuristiky založené např. na sledování gradientu než genetické
algoritmy a jim podobné.

Tento jev je důsledkem způsobu, jakým GA pracuje s populací. Tu je
totiž nutné s každou novou generací znovu a znovu vyhodnotit,
jedince po jedinci, řešení po řešení. Časová náročnost tohoto kroku
pak obecně záleží na složitosti vyhodnocení optimalizačního
kritéria.

Může se tak stát, že zatímco GA stále ještě vyhodnocuje některou
z počátečních generací řešení uvažovaného problému, nalezne
optimální řešení výše zmíněná heuristika.

Proto je vždy nutné dobře posoudit, jestli je na daný problém
vhodnější nasadit GA nebo nějakou jinou heuristiku lokálnějšího
charakteru, popř. zvolit kombinaci obou výše jmenovaných.

\subsection{Binární genetický algoritmus}

V této části kapitoly se zaměříme na jednu konkrétní variantu GA,
a to na
\emph{binární genetický algoritmus},
který je ve své podstatě mimořádně vhodný k implementaci na
počítači.

Tato varianta, mimochodem úplně první varianta GA, která kdy
vznikla, pracuje s čistě
\emph{binárně kódovaným chromosomem},
tj. s chromosomem složeným z pouze jedniček a nul. Je zřejmé, že
takto definovaný chromosom lze snadno reprezentovat posloupností
bitů v binárním kódu, se kterým interně pracují prakticky všechny
běžně používané výpočetní systémy.

Navíc budeme v dalším textu uvažovat čistě obecný algoritmus, na
kterém budeme zkoumat jeho základní stavbu, aniž bychom se přitom
soustředili na konkrétní problém, který tento algoritmus řeší. To
mimo jiné znamená, že budeme uvažovat
\emph{populaci složenou z obecných jedinců}
obsahujících binární choromosom, namísto z řešení konrétního
problému.

\subsection{Výběr množiny kódovaných parametrů}

Při výběru
\emph{parametrů pro reprezentaci informace uložené v jedinci}
se snažíme najít takové parametry řešeného problému, které by jej
plně popsaly na zvolené úrovni abstrakce. Obecně platí, že bychom
měli vybrat co nejmenší počet parametrů tak, abychom je mohli předat
optimalizačnímu kritériu jako vstupní hodnoty. Pokud máme navíc
k dispozici formální zadání problému, pak je samozřejmě
nejjednodušší vyjít přímo z množiny konfiguračních proměnných
obsažených v takovém zadání.

Tím se dostáváme k volbě
\emph{optimalizačního kritéria},
které nám při evoluci slouží jako měřítko kvality zkoumaných
jedinců. Toto kritérium by mělo plně využívat informaci obsaženou
v jedinci, tj. použít při výpočtu všechny parametry v něm
zakódované. Z opačného úhlu pohledu nám pak může optimalizační
kritérium posloužit při výběru nezbytné množiny parametrů, a tedy
i stanovení příslušné úrovně abstrakce:
\begin{itemize}
\item{
V řadě případů představuje optimalizační kritérium
\emph{matematická funkce}
s omezeným definičním oborem. Každé takové omezení pak ve svém
důsledku prodražuje výpočet její funkční hodnoty. V některých
případech je však možné funkci omezení alespoň částečně zbavit
pomocí transformace a někdy je dokonce možné část parametrů zcela
zanedbat jako nevýznamné a funkci tak dále zjednodušit.
}

\item{
Další možností stanovení optimalizačního kritéria je
\emph{využití naměřených experimentálních hodnot}.
Tím je myšleno porovnání informace obsažené v jedinci s výsledky
předešlých experimentů, které v takovém případě doplňují zadání
řešeného problému.

Typickým příkladem takové situace je pokus o sestavení
klasifikátoru, kde nás zajímá, zda chování jedincem specifikovaného
klasifikátoru odpovídá chování zjištěnému experimantálně. Jinými
slovy se jedná o to, zda klasifikátor dává v konkrétních situacích
výsledky, které odpovídají skutečným hodnotám pro tyto situace
změřeným.
}

\item{
Poslední způsob, úzce související s předcházejícím příkladem,
představuje
\emph{nahrazení matematické funkce experimentem}.

Tento způsob je z hlediska času potřebného k vyhodnocení jedince
zdaleka nejnáročnější, ale pokud nejsme s to přesně formulovat
podmínky optimality jedince, tak pro nás představuje jedno z možných
východisek z takové situace.
}
\end{itemize}

\subsection{Kódování a dekódování chromosomu}

\emph{Kódování},
resp. k němu inverzní
\emph{dekódování},
je operace spočívající v převodu parametrů vybraných způsobem
popsaným v předchozí kapitole do interního kódu, v našem případě
do kódu binárního.

Způsob kódování parametrů závisí na jejich typu:
\begin{itemize}
\item{
Pokud kódujeme
\emph{parametry ze spojité domény},
musíme jejich skutečné hodnoty vhodným způsobem aproximovat ve
zvoleném kódu. Tato činnost se obvykle nazývá
\emph{amplitudová kvantizace}
a je myslím natolik známá, že ji zde není nutné dále rozvádět.
}

\item{
V případě
\emph{parametrů z diskrétní domény}
stačí obvykle najít způsob přepisu hodnot do zvoleného kódu. To
znamená, že buď jejich hodnotu v tomto kódu přímo vyjádříme nebo
vytvoříme slovník s pomocí kterého hodnoty převádíme. Slovníkem se
zde myslí vyjádření bijektivního zobrazení z množiny hodnot
parametru do množiny kódových slov zvoleného kódu.
}
\end{itemize}

Takto zakódované parametry, tvořené
\emph{bloky bitů},
pak odpovídají genům, ze kterých je celý chromosom sestaven (viz
obr.
\ref{fig:theory-chromosome}).
Při další práci s takovým chromosomem je zpravidla výhodné dbát na
hranice genů v rámci chromosomu, a pracovat tak s geny jako s celky.

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figs/chromosome.png}
\caption{Struktura chromosomu}
\label{fig:theory-chromosome}
\end{center}
\end{figure}

\vfill\pagebreak

\subsection{Vytváření počáteční populace}
\label{chap:theory-new_population}

\emph{Populace}
je množina jedinců s konečnou mohutností, která je vybavena
operacemi definovanými nad jedinci. Tyto operace slouží k manipulaci
jedinců, a umožňují tak vývoj populace v čase.

Existuje několik jednoduchých způsobů jak takovou populaci vytvořit:
\begin{itemize}
\item{
Prvním z nich je
\emph{náhodné generování chromosomu každého jedince v populaci},
a to buď ve smyslu řetězce genů nebo přímo řetězce bitů.

Tento způsob je zdaleka nejjednodušší a umožňuje prohledat největší
část stavového prostoru. Díky těmto vlastnostem je také
nejpoužívanější.
}

\item{
Další způsob spočívá ve
\emph{vložení předem vytvořené skupiny jedinců do populace}
a doplnění zbytku populace metodou popsanou v předchozím bodě.

Tímto způsobem se lze zaměřit na určité oblasti stavového prostoru,
o kterých už dopředu tušíme, že budou s největší pravděpodobností
obsahovat velice kvalitní jedince.

Existuje také modifikace výše popsaného přístupu, kdy skupina
vkládaných jedinců není definována exaktně, ale je namísto toho
charakterizována pomocí
\emph{specifické vlastnosti},
kterou musí jedinci tvořící tuto skupinu splňovat. Jako příklad nám
může posloužit poměr jedniček a nul v binárním řetězci
reprezentujícím chromosom.
}

\item{
Poslední možností je
\emph{naplnit populaci zcela deterministicky vytvořenými jedinci}.

Tato možnost přichází v úvahu zpravidla v situacích, kdy už jsme
nějakým způsobem, např. příbuznou evoluční technikou, jedince
získali a potřebovali bychom evolucí dále zlepšit jejich vlastnosti.
}
\end{itemize}

\subsection{Selekce jedinců}
\label{chap:theory-selection}

\emph{Selekce jedinců}
je proces inspirovaný přírodním výběrem a ve své podstatě slouží
k určení pravděpodobnosti, s jakou se pak jednotliví jedinci
v populaci účastní páření.

Selekce pracuje ve dvou fázích, z nichž v první dochází k samotné
selekci a v druhé pak páření takto vybraných jedinců:
\begin{enumerate}
\item{
V první fázi pracuje selekce s
\emph{celou populací}
a v závislosti na konkrétní implementaci může nabývat těchto podob:

\begin{itemize}
\item{
Z populace je vyčleněna
\emph{skupina nejkvalitnějších jedinců},
kterým bude dovoleno spářit se. Mohutnost této skupiny je zpravidla
předem stanovena ve formě konstanty.

Nevýhoda tohoto postupu spočívá v nutnosti celou populaci předem
seřadit podle kvality jedinců, což je zpravidla velice náročné na
čas.
}

\item{
Z populace jsou vybráni všichni
\emph{jedinci, jejichž kvalita překračuje předem stanovenou mez}.
Tato se může v průběhu samotné evoluce dynamicky měnit podle
aktuální potřeby.

To znamená, že pokud nám v důsledku rostoucí průměrné kvality
populace projdou sítem téměř všichni jedinci, je načase mez selekce
odpovídajícím způsobem upravit. V opačném případě musíme naopak
takto zdecimovanou populaci doplnit čerstvými jedinci.

Tento způsob selekce se asi nejvíce blíží pravidlům přírodního
výběru tak, jak je popsal Charles Darwin.
}

\item{
Do další fáze přejde
\emph{celá populace}
bez ohledu na kvalitu jednotlivých jedinců, tj. tento krok populaci
nijak nezmění a ponechá ji v původním stavu.

To jednak výrazně zjednoduší udržování konstantní velikosti populace
a navíc tak z celého procesu úplně nevyřadíme slabší jedince. Ti pak
mohou díky náhodě získat možnost spářit se, což má v některých
případech za následek oživení jinak zdegenerované populace, ve které
převládá elita propojená četnými příbuzenskými vztahy.
}
\end{itemize}

Na tomto místě je třeba podotknout, že výše uvedené varianty prvního
kroku selekce se liší ještě v jedné důležité vlastnosti, a tou je
způsob vytváření nové generace populace.

První dvě varianty, které ze stávající populace vybírají k páření
pouze určitou skupinu jedinců, vytvářejí novou generaci tak, že do
ní nejdříve umístí tuto skupinu. Zbytek nové generace pak doplní
potomky vzešlými ze vzájemného páření jedinců z této skupiny tak,
jak je to popsáno v následujícím, druhém kroku selekce.

Poslední varianta se od obou předchozích liší v tom, že novou
generaci bezezbytku vyplní právě až v druhém kroku selekce.
Existuje však jedna vyjímka z tohoto pravidla, té se ale dotkneme
až v kapitole
\ref{chap:theory-elitism}
o elitismu.
}

\item{
Druhou fází selekce je
\emph{páření skupiny jedinců}
vybraných z populace v předchozí fázi s tím, že se jedinci páří vždy
ve dvojici.

Tyto dvojice lze sestavit několika různými způsoby:
\begin{itemize}
\item{
\emph{Párování do dvojic}
postupuje systematicky od jednoho konce skupiny ke druhému, a takto
vytvořené dvojice se vždy skládají z jedince z lichým pořadovým
číslem v rámci skupiny a z jedince s pořadovým číslem sudým.

Tento přístup je z hlediska implementace velice jednoduchý, ale
příliš neodpovídá chování přírodních procesů, které selekci sloužily
modelem.
}

\item{
\emph{Náhodné párování} má oproti párování do dvojic tu výhodu,
že se při vytváření dvojic z pseudonáhodně vybraných jedinců skupina
promíchá a tím máme větší šanci na spáření dvou výrazně se lišících
jedinců. To nám pak umožní prozkoumat i dosud neobjevené oblasti
stavového prostoru.

V této variantě párování mají všichni jedinci ve skupině zajištěnou
stejnou pravděpodobnost páření, ale v předchozímu kroku selekce se
do skupiny dostali z populace pouze silnější jedinci. Tím de facto
dojde k protěžování silnějších jedinců přesně tak, jak je tomu
v přírodě.
}

\item{
\emph{Vážené náhodné párování} se od párování čistě náhodného liší
tím, že jedinci ve skupině už nemají stejnou pravděpodobnost páření,
ale tato je naopak přímo odvislá od jejich kvality.

Jinými slovy jsme zúžili výběr jedinců k páření pouze na tu
kvalitnější část populace a při samotném páření jedinců z této
skupiny navíc preferujeme jedince s vyšší kvalitou na úkor těch méně
kvalitních. Touto cestou tak dále zesilujeme
\emph{selekční tlak},
tj. míru protěžování těch nejkvalitnějších jedinců ve skupině.

Vážení samotné je možné realizovat:
\begin{itemize}
\item{
stanovením
\emph{kvalitativní třídy jedince}
ve skupině.

Jedinci jsou ve skupině sestupně seřazeni podle kvality a následně
vzestupně očíslováni od nejlepšího po nejhoršího. Číslo, které jim
bylo takto přiřazeno, nazveme kvalitativní třída. Podle této třídy
je pak stanovena
\emph{pravděpodobnost výběru jedince}

\begin{equation}
P_n = \frac{N_k - C_n + 1}{\sum_{i = 1}^{N_k} C_i},
\end{equation}

kde $C_n$ je třída uvažovaného jedince a $N_k$ je mohutnost seřazené
skupiny jedinců, a tedy i celkový počet tříd
\cite{HAUPT04}.

\emph{Kumulativní pravděpodobnost výběru jedince}
pak stanovíme tak, že sečteme kumulativní pravděpodobosti jedinců
předcházejících v seřazené skupině jedinci uvažovanému
a pravděpodobnost výběru jedince samotného. Kumulativní
pravděpodobnost výběru prvního jedince v takové skupině je přitom
rovna přímo pravděpodobnosti jeho výběru.
}

\item{
výpočtem
\emph{normalizované kvality jedince}
v rámci skupiny, kterou spočítáme tak, že od kvality každého jedince
ve skupině odečteme nejvyšší kvalitu jedince, který neprošel prvním
 kolem selekce.

Pravděpodobnost výběru jedince je pak
\begin{equation}
P_n = \left|\frac{Q_n}{\sum_{i = 1}^{N_k} Q_i}\right|,
\end{equation}

kde $Q_n$ je normalizovaná kvalita uvažovaného jedince a $N_k$ je
mohutnost skupiny jedinců
\cite{HAUPT04}.

Kumulativní pravděpodobnost výběru jedince pak stanovíme obdobně
jako při výpočtu kvalitativní třídy jedince.
}
\end{itemize}

Výběr jedince do dvojice pak provedeme tak, že vygenerujeme
pseudonáhodné číslo z intervalu $(0, 1\rangle$ a hledáme ve skupině
jedinců takového jedince, jehož kumulativní pravděpodobnost výběru
je zdola nejblíže vygenerovanému číslu.
}

\item{
\emph{Turnajový výběr}
asi nejvěrněji kopíruje princip přírodního výběru a je také jednou
z nejčastěji používaných metod výběru páru.

Funguje tak, že každý jedinec ve výsledné dvojici vzejde
z miniaturního turnaje či
\emph{klání}
několika, zpravidla dvou nebo tří jedinců. Vítěz takového klání je
samozřejmě ten nejkvalitnější z jeho účastníků.
}
\end{itemize}

Každá takto získaná dvojice jedinců je posléze spářena za použití
níže popsaných operací křížení a mutace. Takto získaní potomci
jsou pak začleněni do nové generace populace. Způsob, jakým se
to běžně realizuje bude rozveden v kapitole
\ref{chap:theory-new_population}
o vytváření nové populace.

Nezbývá než podotknout, že pokud je dvojice tvořena buď shodnými
jedinci nebo jedincem dvakrát po sobě vybraným, můžeme takovou
dvojici považovat za platnou, anebo ji vytvořit znovu. V takovém
případě je vhodné upravit mechanismus výběru tak, aby k takové
situaci pokud možno nedocházelo vůbec, nebo alespoň zřídkakdy. Jedno
z možných řešení je provádět výběr jedinců bez náhrady.
}
\end{enumerate}

\subsection{Křížení jedinců}
\label{chap:theory-crossover}

Operace
\emph{křížení jedinců}
je velice přibližný model procesu ke kterému dochází v přírodě při
pohlavním rozmnožování buňek haploidních organismů. Při tomto
procesu dochází mezi rodičovskými jedinci k výměně genetické
informace uložené v chromosomu tak, že si oba rodiče část svého
chromosomu prohodí (viz obr.
\ref{fig:theory-crossover}).

\begin{figure}[htp]
\begin{center}
\includegraphics[width=\textwidth]{figs/crossover.png}
\caption{Základní typy křížení}
\label{fig:theory-crossover}
\end{center}
\end{figure}

Nejčastěji se používá několik typů křížení:
\begin{itemize}
\item{
U
\emph{jednobodového křížení}
se v chromosomu náhodně zvolí
\emph{bod křížení}
(tzv. kinetochora). Tento bod je v chromosomech obou rodičů shodný
a zpravidla se volí na rozhraní dvou genů tak, abychom neporušili
jejich strukturu. Oba rodiče si pak vzájemně prohodí část chromosomu
od tohoto bodu do konce chromosomu.
}

\item{
\emph{Vícebodové křížení},
často dvoubodové, funguje obdobným způsobem. Zvolíme příslušný počet
bodů křížení, což nám chromosom rozdělí do několika segmentů. Rodiče
si pak vždy prohodí sudé segmenty chromosomu.
}

\item{
\emph{Uniformní křížení},
narozdíl od předchozích dvou typů křížení, nedělí chromosom
v jednotlivých bodech, ale prochází oba chromosomy současně
a s předem zvolenou pravděpodobností prohazuje jejich odpovídající
části, ať už se jedná o celé geny nebo přímo o samotné bity.
}
\end{itemize}

Tímto způsobem je zajištěna výměna genetické informace mezi oběma
rodiči, která je motivována skutečností, že alespoň jeden takto
získaný potomek může s poměrně vysokou pravděpodobností zdědit
nejlepší vlastnosti rodičů a dosáhnout vyšší kvality než kterýkoliv
z jeho rodičů.

Účinnost této operace závisí na určité, předem stanovené
pravděpodobnosti, se kterou ke křížení dochází. To znamená, že někdy
ke spáření obou rodičů nemusí vůbec dojít.

\subsection{Mutace jedinců}

Výše popsaná operace křížení je jedním ze dvou hlavních způsobů jak
se může GA pohybovat stavovým prostorem a prozkoumávat tak jeho
povrch. Druhou možnost představuje operace
\emph{mutace}.

Mutace spočívá v náhodné změně hodnoty několika málo bodů
v chromosomu a zpravidla pracuje přímo na úrovni základních
stavebních prvků chromosomu, v našem případě tedy na úrovni bitů
(viz obr.
\ref{fig:theory-mutation}).

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figs/mutation.png}
\caption{Princip mutace}
\label{fig:theory-mutation}
\end{center}
\end{figure}

Touto formou je při prohledávání stavového prostoru posílen vliv
náhody, což má za následek širší pokrytí jeho povrchu a menší
pravděpodobnost degenerace celé populace. Dají se tak náhodně
objevit nové vlastnosti perspektivní v daném prostředí a současně
zabránit přílišnému sbližování genomů jedinců v populaci, které
má za následek ztrátu její variability.

I tato operace je, stejně jako je tomu v případě operace křížení,
účinná jen s určitou, pevně danou pravděpodobností.

\subsection{Elitismus}
\label{chap:theory-elitism}

\emph{Elitismus}
je důležitá vlastnost populace, která urychluje její konvergenci
k oblastem nejkvalitnějších jedinců. To umožňuje variantám GA, které
tuto vlastnost implementují, dosahovat vyšší efektivity ve srovnání
s klasickým přístupem, který tuto vlastnost nezahrnuje.

Princip elitismu spočívá v tom, že z populace vybereme v každé
generaci pevně stanovený počet nejkvalitnějších jedinců, tzv.
\emph{elitu},
a vytvoříme z ní jádro generace nové. Zbytek nové generace pak
doplníme přesně tak, jak jsme si to uvedli v kapitole
\ref{chap:theory-selection}
o selekci.

Elitním jedincům je přitom dovoleno dále se pářit, takže do nové
generace přejdou společně se svými potomky, zatímco ostatní jedinci
budou ve většině případů svými potomky nahrazeni. Tímto způsobem
jednoduše zajistíme, abychom neštastnou náhodou nepřišli
o nejkvalitnější jedince v důsledku křížení a mutací.

Průměrná kvalita skupiny elitních jedinců se tak může pouze zvyšovat
a pokud vůbec existuje z hlediska kvality optimální jedinec, bude
zaručeně členem této skupiny.

Elitní jedinci zpravidla přežívají po mnoho generací, a mají tak
výrazně větší počet příležitostí k páření. Díky tomu mají
nezanedbatelný vliv na vývoj celé populace, který je tím větší, čím
větší je jejich počet. Tento je pak v průběhu evoluce zpravidla
konstantní.

\subsection{Vytváření nové generace}

V kapitole
\ref{chap:theory-selection}
o selekci jsme narazili na
\emph{způsob vytváření nové generace}. Nyní, když už máme vybudovaný
potřebný aparát k výběru perspektivích jedinců a jejich páření,
můžeme tuto část textu uzavřít popisem možných způsobů, jakými se dá
z jedné generace populace vytvořit generace nová.

Rozeznáváme dva základní přístupy, které mají společný ten fakt, že
v obou nejprve přejde do nové generace případná elita. Zbytek
generace se pak doplní jedním ze dvou následujících způsobů (viz
obr.
\ref{fig:theory-new_generation}):

\begin{figure}[htp]
\begin{center}
\includegraphics[width=\textwidth]{figs/new_generation}
\caption{Způsoby vytváření nové generace}
\label{fig:theory-new_generation}
\end{center}
\end{figure}

\begin{itemize}
\item{
Metodou, kterou jsme si uvedli v kapitole o selekci, nejprve
vybereme z populace skupinu perspektivních jedinců, a tu pak po
dvojicích spáříme.

Dostaneme tak dvě přibližně stejně mohutné skupiny jedinců,
skupinu rodičů a skupinu potomků. Obě skupiny nemají stejnou
mohutnost, protože někteří rodiče nemuseli mít vůbec žádné potomky.
V každém případě má každá z obou skupin menší mohutnost než je
velikost populace, a tedy i velikost nové generace této populace.

Vzhledem k faktu, že nově vytvářená generace už může obsahovat
elitu, je velice pravděpodobné, že se nám do této generace nepovede
bezezbytku umístit jak skupinu rodičů, tak skupinu potomků.

Tuto situaci lze vyřešit tak, že do nové generace umístíme tolik
potomků, kolik to jen bude možné a pokud nám v této generaci stále
jestě zbyde volné místo, obsadíme ho rodiči. Přitom postupujme tak,
že přednost při umisťování do nové generace mají kvalitnější rodiče.
Méně kvalitní rodiče tedy uvolní místo některým jedincům ze skupiny
potomků.
}

\item{
Druhou možností je vyvořit novou generaci pouze z elity a potomků,
kteří v této generaci obsadí místo svých rodičů. Z toho je zřejmé,
že rodič, který není členem elity, se může do nové generace dostat
pouze v případě, že nemá žádného potomka.
}
\end{itemize}

\subsection{Stanovení některých parametrů evoluce}
\label{chap:theory-parameters}

Aplikace genetických algoritmů není v žádném případě exaktní věda
a blíží se spíše umění, kde výsledky do značné míry závisejí na
autorově citu pro danou problematiku. Mohu tak závěrem nabídnout
několik doporučení, která se z větší části zakládají na mé vlastní
zkušenosti.

Rád bych se zmínil o několika dosti podstatných aspektech GA, a to
o volbě velikosti populace, pravděpodobnosti úspěchu operací
křížení a mutace a v neposlední řadě i určení délky samotné evoluce.

Velikost populace nám udává rozlohu současně prozkoumávané oblasti
stavového prostoru. Naším cílem je vždy zvolit takovou velikost
populace, která by představovala rozumný kompromis z hlediska poměru
velikosti takto určené oblasti stavového prostoru a času, který
algoritmus potřebuje k vyhodnocení všech jedinců vyskytujících se
v této oblasti. Podle mých zkušeností se příliš nevyplatí zvyšovat
velikost populace nad několik málo stovek jedinců.

Pravděpodobnost úspěchu operací křížení a mutace, tedy
pravděpodobnost, s jakou se během páření skutečně provedou, by
neměla překračovat cca.\ 70\% v případě křížení a jednotky procent
v případě mutace. Čím vyšší hodnoty bychom volili, tím více bychom
se přibližovali náhodnému prohledávání stavového prostoru a evoluce
by tak ztrácela smysl.

Délka procesu evoluce je vyjádřena počtem generací, které algoritmu
povolíme vytvořit. Tento počet můžeme na začátku evoluce pevně
stanovit, nebo jej přímo za běhu dynamicky upravovat v závislosti na
vývoji stavu populace. Pokud například ani po pěti stech generacích
nedokáže algoritmus vyvinout lepšího jedince než nejlepšího dosud
známého, je načase evoluci ukončit. Jiná taková situace může nastat
v případě, že se kvalita nejlepšího známého jedince dostatečně
přiblížila našim požadavkům, a nemá tedy už cenu v evoluci dále
pokračovat.

Tím jsme prošli všechny fáze tvorby GA, od sestavení chromosomu
jedince, přes generování počáteční populace jedinců, až po vytváření
nových generací této populace za pomoci operací křížení a mutace.
Takto popsaný GA je pak více či méně přesným modelem procesu
přírodního výběru a můžeme jej, po přizpůsobení stavby jedince
konkrétní třídě problémů, použít k řešení různých optimalizačních
problémů.

