\chapter{Realizace řešení}

V této kapitole si stručně rozebereme hlavní části implementace
binárního genetického algoritmu (GA) navrženého v předchozí
kapitole. Vzhledem k tomu, že se nejedná o práci vyloženě
implementačního charakteru, omezíme se jen na slovní popis
nejdůležitějších aspektů té které části implementace.

Závěrem této kapitoly naznačíme princip implementace plně
randomizovaného přístupu, který budeme v rámci testování výsledné
implementace GA používat k získání představy o použitelnosti GA pro
řešení zadaného problému.

\section{Základní koncepce programu}

Výsledný program implementující navržený GA pracuje buď v dávkovém
módu, nebo v módu interaktivním, kdy s uživatelem komunikuje
prostřednictvím jednoduchého uživatelského rozhraní typu CLI přes
terminál.

V dávkovém módu program očekává všechny vstupní údaje specifikované
formou hodnot příslušných parametrů. Pokud však nějaký údaj schází,
program se na něj uživatele přímo dotáže a základním způsobem přitom
kontroluje typ zadávané informace.

Při práci v interaktivním módu program funguje následovně:

\begin{enumerate}
\item{
Po svém spuštění si program od uživatele vyžádá cestu k souborům
obsahujícím předgenerovanou tabulku vektorů a popis struktury
testovaného obvodu ve formátu ISCAS-89.

Uživatel je také požádán o cestu k souboru, kam má uložit
statistická data získaná v průběhu měření. Ta se skládají
z průměrných hodnot kvality populace, kvality nejlepšího jedince
v rámci populace, diversity populace a konečně pak skutečného podílu
elity v populaci pro každou odsimulovanou generaci.
}

\item{
Program se uživatele dále dotáže na parametry procesu evoluce CA,
mezi které patří například typ jedince, velikost populace, podíl
elity a extrémních jedinců v populaci, typ selekce a křížení atd.
}

\item{
Následuje samotný proces evoluce CA podle zadaných parametrů a po
jeho skončení pak stejně dlouhý běh části programu implementující
plně randomizovaný přístup, který slouží jako měřítko výkonnosti
procesu evoluce CA (viz kap.
\ref{chap:implementation-random}
).

Tento krok je pak prováděn po předem stanovený počet opakování,
a takto získané výsledky jsou po zprůměrování uloženy do souboru
zadaného uživatelem v kroku 2. Na terminál je navíc vytištěn stručný
přehled dosažených výsledků.
}
\end{enumerate}

\section{Implementace struktury jedince}

V rámci předběžné přípravy jsme implementovali obě varianty
struktury jedince zmíněné v kapitole
\ref{chap:analysis-individual}
a prakticky tak ověřili, že implementace první varianty má výrazně
vyšší operační složitost. Z tohoto důvodu jsme se v další práci
rozhodli soustředit na variantu druhou, založenou na reprezentaci
celulárního automatu (CA) výčtem pravidel popisujících chování jeho
buňek doplněným o seed. Taková reprezentace automatu přímo vybízí
k implementaci chromosomu na této reprezentaci založeného ve formě
jednorozměrného pole pevné délky.

Každý prvek takového pole pak odpovídá jednomu páru nukleotidů
reálného chromosomu a několik prvků dohromady tvoří samotný gen.
Pro všechny prvky také platí, že mohou nabývat pouze dvou hodnot:
nuly a jedničky.

\vfill\pagebreak

Takto definované pole je možné logicky rozdělit na dvě samostatné,
na sebe navazující části (viz obr.
\ref{fig:implementation-individual}
):

\begin{enumerate}
\item{
\emph{oblast genů}
skládajících se z několika prvků pole,
\emph{jejímž fenotypem je samotná struktura CA}.

Každý gen z této oblasti kóduje číslo pravidla, kterým se řídí jemu
odpovídající buňka CA, v tabulce všech dostupných pravidel. Toto
číslo je pak reprezentováno v binárním kódu posloupností prvků
tvořících uvažovaný gen.

V našem případě jsme použili celkem čtyři různá pravidla: 60, 90,
150 a 240 (viz tab.
\ref{tab:theory-ca_rules}).
Díky tomu jsou tyto geny tvořeny pouze dvěma prvky, které plně
postačují na zakódování čísla pravidla.
}

\item{
\emph{oblast genů kódujících seed CA}.

Geny z této oblasti jsou tvořeny pouze jedním prvkem pole a hodnota
těchto genů přímo určuje počáteční stav jim odpovídajících buňek CA.
}
\end{enumerate}

\begin{figure}[hbp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figs/individual.png}
\caption{Implementace struktury jedince}
\label{fig:implementation-individual}
\end{center}
\end{figure}

Výše popsaná implementace chromosomu je, společně s operacemi nad
takovým chromosomem definovanými, základem samotné implementace
výsledného jedince.

\section{Vyhodnocení kvality jedince}

Námi implementovaný GA používá pro výpočet kvality jedinců jak
diagnostické pokrytí testovaného obvodu, tak pokrytí předgenerované
tabulky vektorů jimi specifikovanými CA:

\begin{itemize}
\item{
\emph{Diagnostické pokrytí testovaného obvodu}
určíme za pomoci externího simulátoru poruch
\emph{fsim},
který dokáže simulovat poruchy kombinačních logických obvodů.

V první fázi nejdříve vygenerujeme stanovený počet testovacích
vektorů vyhodnocovaným CA a ty uložíme do souboru. Ten pak ve druhé
fázi předáme simulátoru a počkáme si na výsledek.
}

\item{
\emph{Předgenerovaná tabulka vektorů}
se zpravidla skládá pouze z vektorů testujících těžko detekovatelné
poruchy testovaného obvodu (viz kap.
\ref{chap:analysis-fitness}).
Pokrytí této tabulky implementujeme tak, že z vyhodnocovaného CA
odebíráme postupně jeden testovací vektor za druhým a zkoušíme jimi
postupně pokrývat dosud nepokryté vektory v tabulce.

Samotné pokrytí vektoru je ve své podstatě ekvivalentní operaci
porovnání dvou řetězců při kterém uvažujeme tzv.
\emph{don't-care znaky}
s tím rozdílem, že v případě shody obou vektorů si tuto informaci
uložíme ve formě příznaku bezprostředně připojeného k vektorům
v tabulce (viz obr.
\ref{fig:implementation-vector_cmp}).

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figs/vector_cmp}
\caption{Příklad pokrytí vektoru v tabulce}
\label{fig:implementation-vector_cmp}
\end{center}
\end{figure}

Jakmile tímto způsobem zpracujeme všechny vektory odebrané
z automatu, spočítame si jako výsledek percentuální podíl počtu
pokrytých vektorů ku celkovému počtu vektorů v tabulce.
}
\end{itemize}

\section{Vytváření počáteční populace}

Během generování chromosomu jedinců počáteční populace rozlišujeme
mezi normálními jedinci a jedinci extrémními. Rozdíl spočívá
v pravděpodobnosti s jakou se v jejich chromosomech vyskytují
jedničky. U normálních jedinců je tato pravděpodobnost stejná jak
pro výskyt jedničky, tak pro výskyt nuly, a je rovna 50\%.
U extrémních jedinců je pravděpodobnost výskytu jedničky
specifikována uživatelem při spouštění programu.

Při samotném vytváření počáteční populace pak postupujeme tak, že do
prázdné populace nejprve vložíme uživatelem specifikovaný počet
extrémních jedinců na náhodně zvolená místa v populaci. Zbývající
prázdné místo v populaci pak vyplníme náhodně vygenerovanými
normálními jedinci.

\section{Implementace křížení a mutace}

Jak jsme již v předchozí kapitole naznačili, implementovali jsme
celkem tři varianty křížení: jednobodové, dvoubodové a uniformní
(viz obr.
\ref{fig:implementation-crossover}).
Všechny tři se pak chovají přesně tak, jak bylo popsáno
v kapitole
\ref{chap:theory-crossover}.
Vzhledem k námi použité implementaci chromosomu jsme navíc do těchto
operací zabudovali mechanismus, který zajišťuje, aby bod dělení
nerozbil gen skládájící se z více prvků. Takové geny obsahuje oblast
chromosomu, která kóduje strukturu CA.

Tento mechanismus pak pracuje tak, že náhodně zvolený bod dělení
představuje index prvku v poli implementujícím chromosom. Tomuto
indexu se pak vynuluje počet nejméně významných bitů, který je roven
horní celé části dvojkového logaritmu počtu dostupných pravidel. Tak
získáme index prvního prvku genu určeného bodem dělění a můžeme
s genem dále pracovat jako s celkem.

\begin{figure}[htp]
\begin{center}
\includegraphics[width=\textwidth]{figs/crossover-2}
\caption{Příklad implementace křížení}
\label{fig:implementation-crossover}
\end{center}
\end{figure}

Jednobodovou mutaci jsme implementovali tak, že pracuje přímo na
úrovni základních stavebních bloků genu, tj. prvků pole
implementujícího chromosom, kterým pak invertuje hodnotu podle
obrázku
\ref{fig:implementation-mutation}.

\begin{figure}[htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figs/mutation-2}
\caption{Příklad implementace mutace}
\label{fig:implementation-mutation}
\end{center}
\end{figure}

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

Novou generaci vytváříme ve dvou fázích, při kterých používáme
pomocnou populaci:

\begin{enumerate}
\item{
Vytvoříme prázdnou pomocnou populaci a okopírujeme do ní ze
stávající populace elitu, kterou pro jednoduchost její další
manipulace umisťujeme vždy na začátek pomocné populace. Zbytek této
populace doplníme ze stávající populace uživatelsky zvolenou metodou
selekce a přitom předpokládáme, že náhodný výběr jedinců v rámci
selekce nám zajistí dostatečné promíchání pomocné populace.

Samotný výběr jedinců ze stávající populace je během selekce
prováděn bez náhrady. To znamená, že jedinec už jednou vybraný za
kandidáta k páření nemůže být až do odvolání znovu vybrán a zůstává
tak nadále pasivní. Populace pak implementuje funkci, která umožní
všechny jedince znovu naráz aktivovat.

Takové chování selekce nám umožňuje implementovat turnajový výběr,
který se skládá z jednotlivých
\emph{turnajových kol}.

V rámci jednoho kola turnaje vybíráme ze stávající populace jedince
ke klání tak dlouho, až už nemáme k dispozici žádné aktivní
jedince nebo je pomocná populace zcela zaplněná. V prvním případě
pak za použití aktivační funkce zmíněné v předchozím odstavci
provedeme reaktivaci celé populace a zahájíme nové kolo turnaje.

Důležitým důsledkem takto definovaného způsobu selekce je fakt, že
velikost klání, tj. počet jedinců do něj vstupujících, může nepřímo
ovlivnit selekční tlak na propagaci těch nejkvalitnějších jedinců
v populaci do její další generace.

Čím více jedincům totiž povolíme vstup do každého klání, tím méně
klání se může v rámci jednoho kola turnaje uskutečnit. Výsledkem
bude pochopitelně menší počet vítězů na jedno kolo, a počet kol
nutných k doplnění pomocné populace tak stoupne. Protože se každý
jedinec může v rámci jednoho kola zúčastnit nejvýše jednoho klání,
je toto zvýšení počtu kol výhodné především pro elitní jedince,
jejichž pravděpodobnost výběru do klání a nakonec i postupu do
pomocné populace je velice vysoká.

Získáme tak další prostředek, kterým můžeme řídit vliv elity na
populaci a zabránit tomu, aby elita v populaci převládla společně
se svými potomky.
}

\item{
Z pomocné populace, kterou jsem naplnili v předešlé fázi, přeneseme
do nové populace celou elitu. V pomocné populaci nám tak zůstane
přesně tolik rodičů, kolik potomků je potřeba pro doplnění nové
populace. Nyní pomocí genetických operací postupně, po dvojicích
sousedů, spáříme zbylé jedince z pomocné populace a vložením jejich
potomků do nové populace získáme další generaci stávající populace.

Páření po dvojicích sousedů jsme zvolili pro nižší operační
složitost jeho implementace a předpokládáme přitom, jak už bylo
zmíněno v předchozím bodě, že pomocná populace je už dostatečně
promíchána z první fáze, a tento způsob páření by tedy neměl mít
žádné negativní dopady na vývoj populace jako takové.

Jeden z možných pohledů na tuto fázi je takový, že namísto abychom
přímo spářili vítěze dvou po sobě jdoucích klání, případně náhodně
vybraného jedince a jeho partnera vzešlého z vítězného klání,
uložíme si oba takové jedince pro pozdější zpracování do pomocné
populace. Takový přístup nám potom snadno umožní implementovat
výše zmíněný vícekolový turnaj a důsledné oddělení fáze selekce
od fáze páření nám dává větší volnost při volbě konkrétní
implementace obou fází.
}
\end{enumerate}

\section{Určování diversity populace}

Funkce pro určování diversity populace slouží ke dvěma účelům.
Jednak zjišťuje samotnou diversitu populace a jednak počítá skutečný
podíl elity v populaci.

\emph{Diversitu populace}
zjišťujeme tak, že si nejdříve vytvoříme seznam všech jedinců
v populaci. Tento seznam pak od začátku postupně probíráme, jedince
po jedinci, přičemž každého vybraného jedince započítáme a pak ho
ze seznamu odstraníme spolu se všemi jeho kopiemi. Po zpracování
celého seznamu nám tak zůstane počet unikátních jedinců v rámci celé
populace, na jehož základě pak stanovíme diversitu populace jako
percentuální podíl počtu unikátních jedinců ku počtu všech jedinců
populace.

Za kopii jedince považujeme každého jedince, který má s uvažovaným
jedincem zcela shodný chromosom. Tyto kopie nejčastěji vznikají
pokud při páření dvou elitních jedinců nedojde ke křížení ani
k mutaci. Takto vytvořené kopie pak přejdou do další generace po
boku svých rodičů.

Určení
\emph{skutečného podílu elity v populaci}
probíhá v podstatě stejným způsobem jako v případě zjišťování
diversity populace, ale při vyřazování jedinců ze seznamu počítáme
pouze elitní jedince, a to včetně všech jejich kopií. Podíl elity
v populaci pak počítáme obdobně jako diversitu populace.

\section{Plně randomizovaný přístup}
\label{chap:implementation-random}

Jako měřítko chování naší implementace GA nám slouží algoritmus
řešící identický problém náhodným prohledáváním svého stavového
prostoru.

Jinými slovy, necháme náhodně generovat jedince po dobu, kterou
trvala evoluce a udržujeme si přitom dosud nejlepšího takto
nalezeného jedince. Jím specifikovaný CA pak po vypršení časového
limitu prohlásíme za řešení problému.

\section{Zvolený jazyk implementace}

K implementaci jsme zvolili ANSI/ISO C++ z důvodů dobré
výkonnosti, relativně snadné přenositelnosti a možnosti případné
další paralelizace v rámci systému MPI
\cite{MPI}.

