\chapter{Analýza a návrh řešení}

Záměrem této kapitoly je analýza jednotlivých částí zadaného
problému a návrh jejich optimálního řešení. Optimalita řešení bude
posuzována především z hlediska operační složitosti a chování
výsledného algoritmu řešícího zadaný problém.

Naším cílem je navrhnout takový binární genetický algoritmus (GA),
který by vyvíjel celulární automaty (CA) použitelné jako generátory
testovacích vektorů pro logické obvody. Pro jednoduchost se v našem
rozboru omezíme pouze na logické obvody kombinačního charakteru.

\section{Základní koncepce algoritmu}

Námi navrhovaný algoritmus se bude držet koncepce klasického GA,
a jeho struktura tedy bude vypadat následujícím způsobem:

\begin{enumerate}
\item{
Vytvoření počáteční populace jedinců obsahující extremisty (viz kap.
\ref{chap:analysis-extremists})
}

\item{
Volba páru jedinců z populace podle principů přírodního výběru
}

\item{Případné zkřížení obou vybraných jedinců}

\item{Případná mutace obou potomků vzešlých z předchozího kroku}

\item{
Vložení obou potomků upravených v předchozím kroce do nové populace
}

\item{Pokud není nová populace plná, skok na krok 2}

\item{Nahrazení stávající populace populací novou}

\item{
Pokud je dosaženo vytýčeného cíle, ukončení procesu, jinak skok na
krok 2
}
\end{enumerate}

Kontrolní mechanismus bude zajištěn formou algoritmu pro náhodnou
syntézu CA, jehož struktura je definována takto:

\begin{enumerate}
\item{
Nastavení nejlepšího známého jedince na jedince čerstvě
vygenerovaného
}

\item{Pokud vypršel povolený časový limit, ukončení procesu}

\item{Vygenerování nového jedince}

\item{
Pokud je nový jedinec lepší než nejlepší dosud známý jedinec, update
nejlepšího známého jedince
}

\item{Skok na krok 2}
\end{enumerate}

\section{Návrh struktury jedince}
\label{chap:analysis-individual}

Jedním z nejdůležitějších aspektů návrhu GA je způsob reprezentace
řešení uvažovaného problému, v našem případě pak popisu struktury
jednodimenzionálního CA, přesněji LHCA.

V zásadě je možné samotný CA reprezentovat dvěma způsoby:

\begin{itemize}
\item{
linearizovanou
\emph{charakteristickou maticí a k ní připojeným seedem}.

Tento způsob reprezentace vychází z naivní představy, že každé buňce
CA nejdříve charakteristickou maticí přesně určíme ty buňky, které
budou tvořit její okolí, a pak jí seedem přiřadíme nějaký počáteční
stav. Okolí každé z buňek je definováno jedním řádkem matice, jehož
délka odpovídá počtu všech buňek. Do tohoto okolí pak patří
všechny buňky, které odpovídají sloupcům obsazeným v takovém řádku
jedničkami.

Velice podstatnou nevýhodou této reprezentace je její příliš
vysoká paměťová složitost a s ní korelující operační složitost
výpočtu kvality jedince, který je postaven na bázi takové
reprezentace. Její asymptotická paměťová složitost totiž řádově
roste s druhou mocninou počtu buňek.
}

\item{
\emph{výčtem pravidel},
kterými se jednotlivé buňky řídí,
\emph{a k němu připojeným seedem}.

Rád bych na tomto místě připomněl, že pravidla slouží k popisu
chování buňek v rámci CA. Každá buňka má jednoznačně určené okolí,
tvořené jejím levým a pravým sousedem a dále pak buňkou samotnou.
Pokud navíc známe pravidlo, kterým se konkrétní buňka řídí, jsme
také schopni určit z tabulky pravidel nový stav této buňky na
základě znalosti tohoto pravidla a stavu buňek v jejím okolí.

Taková reprezentace má podstatně lepší vlastnosti, než je tomu
v předchozím případě. Její asymptotická paměťová složitost je
lineární funkcí celkového počtu buňek.
}
\end{itemize}

Libovolná z obou výše definovaných variant reprezentace CA může
sloužit jako základ struktury jedince, se kterým pak výsledný GA
dále pracuje. V rámci této práce jsme se rozhodli vyzkoušet
struktury obě. Jak přesně je budeme implementovat rozebereme až
v následující kapitole.

\section{Simulace celulárního automatu}

Abychom mohli CA použít pro generování posloupnosti testovacích
vektorů, musíme ho být nejdříve schopni vůbec odsimulovat. Způsoby,
jakými to můžeme provést, se liší podle použité reprezentace
automatu:

\begin{itemize}
\item{
Pokud použijeme
\emph{linearizovanou charakteristickou matici doplněnou seedem},
začneme tak, že všechny buňky uvažovaného CA inicializujeme podle
seedu. Poté budeme stav buňek transformovat po stanovený počet kroků
následujícím postupem:

Každé buňce CA určíme z charakteristické matice všechny buňky
tvořící její okolí a provedeme součet modulo 2 stavů těchto buňek.
Tak získáme nový stav každé buňky a současně i jeden testovací
vektor.
}

\item{
I v situaci, kdy uvažovaný CA reprezentujeme
\emph{výčtem pravidel doplněným o seed},
bude náš první krok stejný jako předchozím případě. Všechny buňky
automatu nastavíme seedem do jejich výchozího stavu, který dále
transformujeme po předepsaný počet kroků následujícím způsobem:

Okolí libovolné buňky CA určíme způsobem naznačeným např.
v kapitole
\ref{chap:analysis-individual}.
Na základě stavu buňek v takto definovaném okolí a pravidla, kterým
se uvažovaná buňka řídí, určíme z tabulky pravidel nový stav této
buňky. Tímto způsobem pak určíme nový stav každé buňce a zároveň
obdržíme i jeden testovací vektor.
}
\end{itemize}

\section{Vyhodnocení kvality jedince}
\label{chap:analysis-fitness}

Operace vyhodnocení kvality jedince je úhelným kamenem každého GA.
Od způsobu, jakým kvalitu jedince určujeme, se odvíjí operační
složitost celého algoritmu. Je proto nasnadě, že naším cílem je
nalezení co nejefektivnější implementaci této operace.

V našem případě pracujeme s jedinci reprezentujícími CA a takové
jedince lze tedy ohodnotit jen na základě vlastností jimi
specifikovaných automatů. Ty zjistíme tak, že každý takový automat
nejdříve necháme vygenerovat posloupnost testovacích vektorů určité
délky, většinou se jedná o několik málo tisíc vektorů, a takto
získanou posloupnost pak dále ohodnotíme jedním ze dvou
následujících způsobů:

\begin{itemize}
\item{
\emph{určením diagnostického pokrytí testovaného obvodu},
kdy simulací prostřednictvím simulátoru poruch
\emph{fsim}
\cite{FSIM}
ověříme diagnostické pokrytí testovaného obvodu námi uvažovanou
posloupností.

Takto lze získat nejpřesnější možnou informaci o vhodnosti
konkrétního CA pro zamýšlený účel, ale bohužel zato zaplatíme
vysokou časovou náročností celého procesu.
}

\item{
\emph{určením pokrytí předgenerované tabulky vektorů} námi
uvažovanou posloupností. Zmíněná tabulka vektorů, získaná za pomoci
ATPG nástroje
\emph{Atalanta}
\cite{ATALANTA}
způsobem popsaným v kapitole
\ref{chap:experiments-atpg_tables},
se zpravidla skládá pouze z vektorů testujících těžko detekovatelné
poruchy testovaného obvodu.

Tyto poruchy jsou detekovatelné pouze a jedině jedním nebo několika
málo testovacími vektory. Vzhledem k tak nízkému počtu použitelných
vektorů existuje obecně jen velice malá pravděpodobnost, že
posloupnost pseudonáhodných testovacích vektorů generovaná CA bude
obsahovat mimo jiné právě tyto vektory. Z tohoto důvodu si zvláště
ceníme automatů, které jsou schopny takové vektory generovat, a tyto
poruchy tak detekovat.

Tento způsob ohodnocení posloupnosti představuje zpravidla podstatně
rychlejší cestu k posouzení vlastností CA, než je poruchová
simulace. Vyžaduje však jistou dodatečnou práci spočívající ve
vygenerování zmíněné tabulky vektorů.
}
\end{itemize}

Rozhodli jsme se implementovat oba výše uvedené způsoby vyhodnocení
kvality jedince s tím, že během evoluce jako takové budeme z důvodů
menší časové náročnosti používat pokrývání předgenerované tabulky
vektorů. U jedinců získaných jako výsledek evoluce na závěr
dodatečně určíme diagnostické pokrytí testovaného obvodu pro jimi
specifikované CA, abychom si tak mohli udělat lepší představu
o reálných vlastnostech takových automatů.

\section{Vytváření počáteční populace}
\label{chap:analysis-extremists}

Při volbě způsobu vytváření počáteční populace jsme sáhli po
přístupu popsaném ve stejnojmenné kapitole
\ref{chap:theory-new_population}, a to vložení skupiny
\emph{extrémních jedinců}
do populace a jejím doplněním jedinci generovanými náhodně. Extrémní
jedinci jsou takoví jedinci, v jejichž chromosomu se nevyskytují
nuly a jedničky se stejnou pravděpodobností.

Takto definovaní extrémní jedinci jsou speciálním případem jevu
v literatuře někdy označovaného jako
\emph{polarizace chromosomu}
\cite{CORNO02}.
Kompletně polarizovaný chromosom má každý locus okupován se 100\%
pravděpodobností právě jedním genem a pravděpodobnost, že locus
obsadí některá z allel tohoto genu je nulová. Oproti tomu, ve zcela
nepolarizovaném chromosomu může každý locus obsadit libovolná
z přípustných allel se stejnou pravděpodobností. V našem případě
uvažujeme pouze dvě allely, nulu a jedničku, jejichž pravděpodobnost
obsazení určitého locusu je přes celý chromosom konstantní.

Na evoluci populace složené z jedinců obsahujících takové chromosomy
je možné nahlížet tak, že na začátku je populace polarizována kolem
určité sady více či méně kvalitních řešení, která se v optimálním
případě postupem času přemění na řešení ještě kvalitnější. Za
takových podmínek se nám celý proces evoluce optimálních, resp.
suboptimálních řešení může znatelně urychlit.

Jiný pohled na extrémní jedince je takový, že tito jedinci
specifikují CA s rozváženým seedem, které byly popsány v kapitole
\ref{chap:theory-unbalanced_ca}.
Posloupnosti testovacích vektorů generované takovými automaty
v některých případech dosahují výrazně lepšího diagnostického
pokrytí testovaných obvodů, než posloupnosti generované automaty,
jejichž seed je čistě náhodný
\cite{CORNO02, FISER_CM, FISER_PT}.

\section{Vhodný typ selekce}
\label{chap:analysis-selection}

Během specifikace problému jsme se rozhodli pro implementaci dvou
z nejpoužívanějších metod selekce, a to tzv.
\emph{ruletového výběru},
což je speciální případ váženého náhodného párování s výpočtem
normalizované kvality jedince (viz kap.
\ref{chap:theory-selection}),
a turnajového výběru. Ruletový výběr představuje ideální volbu
z hlediska snadnosti implementace a turnajový výběr je taktéž
vhodným kandidátem k implementaci, protože věrně kopíruje proces
přírodního výběru. %Z tohoto důvodu jej také budeme při měření
%standardně používat.

\section{Vhodný typ křížení a mutace}

Stejně tak jako jsme volili implementaci dvou různých metod selekce,
rozhodli jsme se implementovat celkem tři různé typy křížení:
jednobodové, dvoubodové a uniformní. Co se mutace týče,
k implementaci jsme vybrali mutaci jednobodovou.

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

Novou generaci stávající populace budeme vytvářet tak, že do nové,
prázdné populace nejprve převedem ze stávající populace elitu
a zbytek doplníme potomky vzešlými pářením jedinců vybraných ze
stávající populace jedním z typů selekce zmíněných v kapitole
\ref{chap:analysis-selection}.

