\chapter{Testování řešení}

V této kapitole se zabýváme experimentálním vyhodnocením
implementace námi navrženého binárního genetického algoritmu (GA),
použitého pro návrh celulárních automatů (CA) vhodných jako
generátory testovacích vektorů pro kombinační logické obvody.

Jako měřítko výkonnosti výsledné implementace GA nám pak slouží plně
randomizovaný přístup popsaný v kapitole
\ref{chap:implementation-random}.

\section{Metodika testování}

V rámci měření jsme pro řadu testovaných kombinačních obvodů
provedli srovnání obou metod z hlediska kvality jimi produkovaných
CA. Obě metody, tj. GA a randomizovaný přístup, jsme vždy nechali
pracovat stejně dlouho. Pro každý testovaný obvod jsme provedli
sérii měření vlivu několika vybraných parametrů na kvalitu
výsledných CA.

Postup měření pro jednu hodnotu měřeného parametru se dá shrnout
následujícím způsobem:

\begin{enumerate}
\item{
Volba hodnoty měřeného parametru
}

\item{
Nastavení hodnot ostatních parametrů na výchozí hodnoty (viz níže
uvedené kapitoly)
}

\item{
Běh evoluce; na závěr vyhodnocení získaného CA poruchovou simulací
}

\item{
Běh randomizovaného přístupu po stejnou dobu, jako trval běh
evoluce; na závěr vyhodnocení získaného CA poruchovou simulací
}

\item{
Kroky 3 a 4 opakovat celkem 5x; výsledky z kroků 3 a 4 průběžně
průměrovat a takto získané průměrné hodnoty výsledků na závěr uložit
do souboru
}
\end{enumerate}

Výše uvedeným způsobem jsme měřili tyto parametry (v závorce je
uveden seznam měřených hodnot, kurzívou jsou pak vyznačeny
\emph{výchozí hodnoty}):

\begin{itemize}
\item{
Podíl extremistů v populaci (\emph{50\%}, 60\%, 70\%, 80\%, 90\%)
}

\item{
Polarizace chromosomu extremistů (\emph{5\%}, 95\%)
}

\item{
Typ selekce (\emph{Turnajový výběr}, Ruletový výběr)
}

\item{
Typ křížení (Jednobodové křížení, Dvoubodové křížení,
\emph{Uniformní křížení})
}
\end{itemize}

Ostatní parametry jsme pak zafixovali na následujících hodnotách
(viz níže uvedené kapitoly):

\begin{itemize}
\item{
Velikost populace: 150
}

\item{
Podíl elity v populaci: 1\%
}

\item{
Počet jedinců vstupujících do klání: 2
}

\item{
Pravděpodobnost křížení: 70\%
}

\item{
Pravděpodobnost mutace: 10\%
}

\item{
Maximální počet generací: 1500
}
\end{itemize}

Testované obvody jsme vybírali jednak s ohledem na průměrný počet
pseudonáhodných testovacích vektorů, které jsou k jejich úplnému
otestování potřeba (viz.
\cite{FISER_PT}),
a jednak podle počtu jejich vstupů, který určuje velikost potřebného
CA, a tedy i časovou náročnost samotného měření. Pro obvody
s několika stovkami vstupů, jako je např. c2670, se časová náročnost
měření pohybuje v řádu týdnů procesorového času.

Při měření jsme použili testované obvody uvedené v tabulce
\ref{tab:implementation-cut}.
V případě sekvenčních obvodů jsme pak testovali jejich full-scan
verze. Generovanými vektory se v tabulce rozumí počet testovacích
vektorů generovaných CA při vyhodnocování kvality jim odpovídajících
jedinců.

\begin{table}[htp]
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
\bf{Testovaný obvod} & \bf{Počet vstupů} &
\bf{Potřebné vektory} & \bf{Generované vektory} \\
\hline
\hline
c3540 & 50 & 32 K & 2 K \\
\hline
c880 & 60 & 13 K & 500 \\
\hline
c2670 & 233 & 4.4 M & 2 K \\
\hline
s386 & 13 & 3600 & 300 \\
\hline
s420 & 34 & 1.4 M & 1 K \\
\hline
s953 & 45 & 46 K & 1 K \\
\hline
s713 & 54 & 1 M & 1 K \\
\hline
s838 & 67 & až 100 M & 2 K\\
\hline
b07 & 50 & 3 M & 500 \\
\hline
\end{tabular}
\end{center}
\caption{Tabulka testovaných obvodů}
\label{tab:implementation-cut}
\end{table}

\section{Generování tabulky vektorů}
\label{chap:experiments-atpg_tables}

Tabulku vektorů detekujících těžko detekovatelné poruchy (viz kap.
\ref{chap:analysis-fitness})
jsme pro každý testovaný obvod sestavili tak, že jsme tento obvod
nejdříve otestovali posloupností testovacích vektorů z náhodně
sestaveného LFSR za pomoci ATPG nástroje Atalanta
\cite{ATALANTA}.
Tímto nástrojem jsme pak určili poruchy nepokryté takovou
posloupností a pro tyto poruchy jsme, opět pomocí Atalanty,
vygenerovali příslušné testovací vektory.

%Následuje příklad obou kroků pro obvod s838 (tabulka je uložena
%v souboru \verb|s838.pat|):

%\begin{verbatim}
%atalanta-M.exe -S -l 110000000000000000000011 12111111111111111111111 75
%    -U s838.flt -v s838.bench

%atalanta-M.exe -W 1 -D 1 -t s838.pat -f s838.flt s838.bench -P s838.txt
%\end{verbatim}

Shora uvedeným postupem jsme tedy získali tabulku testovacích
vektorů, které detekují poruchy nepokryté posloupností testovacích
vektorů ze zcela náhodně vytvořeného LFSR. Výsledná velikost tabulky
pak přímo závisela na délce zmíněné posloupnosti. Na základě
výsledků v
\cite{FISER_TL}
bylo naším cílem získat tabulku o cca.\ 900 vektorech, které se však
ne vždy podařilo získat.

To se zpravidla stávalo v případech jednodušších obvodů,
např. u s386, u kterých byla délka úplných testů menší, než
požadovaná velikost tabulky. V takových případech jsme pak použili
největší možnou tabulku, jejíž velikost byla stále ještě menší než
délka úplného testu takového obvodu.

U obvodu b07 jsme pak zjišťovali vliv velikosti tabulky na kvalitu
získaných CA, takže jsme velikost volili v pokud možno pravidelných
rozestupech.

\section{Vhodný druh polarizace}
\label{chap:experiments-polarization}

Obecně platí, že pro vetšinu obvodů dávají dobré výsledky CA
s jednoduchou strukturou a seedem obsahujícím pouze několik málo
jedniček
\cite{CORNO02}.
Takové automaty tedy můžeme považovat za slibná počáteční řešení.
Na základě tohoto předpokladu jsme zvolili standardní hodnotu
pravděpodobnosti obsazení locusu jedničkou u extrémních jedinců
jako 5\% a pro úplnost také provedeme některá měření s touto
pravděpodobností rovnou 95\%.

Podíl extrémních jedinců v populaci se pak bude během měření
pohybovat od standardních 50\% až do 90\%, vždy v 10\% skocích,
abychom tak zjistili vliv velikosti tohoto podílu na průběh evoluce
samotné populace.

\section{Vhodné parametry selekce}

V případě turnajového výběru jsme se přiklonili k omezení
počtu účastníků klání na dva, abychom tak potlačili vliv elity,
která zpočátku představuje 1\% jedinců v populaci. Důvodem pro
takové rozhodnutí bylo zjištění v rámci předběžných měření, že elita
má při nárůstu jejího podílu v populaci nad 5\% velice silnou
tendenci celou populaci záhy ovládnout. Pokud bychom to dopustili,
přišli bychom tím takřka úplně o variabilitu populace, která by tak
rychle zkonvergovala k lokálním extrémům.

\section{Vhodné parametry křížení a mutace}

V průběhu měření budeme standardně používat křížení uniformní,
abychom tak co nejdéle zachovali počáteční variabilitu populace.
Pravděpodobnost, že ke zkřížení vybraných jedinců skutečně dojde
nastavíme na 70\%
\cite{AIJ_TUT, HAUPT04}.

Pravděpodobnost jednobodové mutace potomků vzešlých z křížení dvou
jedinců pak zafixujeme na 10\%. Tuto poměrně vysokou hodnotu jsme
se rozhodli zvolit z důvodu velice rychlé degenerace populace,
kterou jsme pozorovali v předběžných měřeních s nižšími hodnotami
tohoto parametru.

\section{Ostatní parametry evoluce}

Ostatními parametry evoluce rozumíme především velikost populace
a délku evoluce. Způsobu jakým co nejlépe stanovit jejich hodnotu
jsme se dotkli už v kapitole
\ref{chap:theory-parameters}.

V rámci předběžných měření jsme zjistili, že desetinásobné zvětšení
populace, konkrétně z 50 na 500 jedinců, nám typicky přineslo nárůst
diagnostického pokrytí benchmarku pro CA specifikované výslednými
jedinci pouze o necelé 1\%. Na základě tohoto poznatku jsme pak
velikost populace omezili na 150 jedinců.

To nám stále ještě umožňuje pracovat s dostatečně rozmanitou
populací, aniž bychom však genetický algoritmus (GA) přespříliš
zahltili nadměrným počtem jedinců, které je třeba s každou další
generací znovu a znovu vyhodnocovat.

Při stanovení délky evoluce jsme se rozhodli horní mez počtu
generací, po které evoluce probíhá, implementovat dynamicky tak, že
pokud nedokáže výsledný GA během 500 generací najít řešení lepší než
to nejlepší dosud známé, evoluce bude automaticky ukončena.

Tak zabráníme plýtvání časem v případě, že se populace stala
v podstatě nehybnou, ať už v důsledku degenerace nebo emergence
optimálního jedince, a zároveň neznemožníme čile se měnící populaci
další vývoj.

\section{Naměřené výsledky}

V níže uvedených tabulkách jsou shrnuty výsledky GA s různým
nastavením ve smyslu kvality nejlepších takto nalezených jedinců
(pro použité způsoby vyhodnocování viz legendu v kap.
\ref{chap:experiments-results}),
včetně doby potřebné k evoluci těchto jedinců. Pro srovnání jsou pak
v tabulkách uvedeny výsledky, kterých dosahoval za stejnou dobu plně
randomizovaný přístup.

Všechny výsledky jsou uváděny v procentech maximální kvality
jedince, tj. úplného pokrytí předgenerované tabulky vektorů pro daný
testovaný obvod, resp. úplného diagnostického pokrytí testovaného
obvodu získaného poruchovou simulací.

%
\vfill\pagebreak
%

\subsection{Tabulky naměřených výsledků pro testované obvody}
\label{chap:experiments-results}

Legenda k tabulkám naměřených výsledků:

\begin{description}
\item[Evoluce (tab.)] Evoluce s vyhodnocováním kvality jedinců
pokrýváním předgenerované tabulky vektorů
\item[Evoluce (sim.)] Evoluce s vyhodnocováním kvality jedinců
poruchovou simulací
\item[Rand. přístup (tab.)] Randomizovaný přístup s vyhodnocováním
kvality jedinců pokrýváním předgenerované tabulky vektorů
\item[Rand. přístup (sim.)] Randomizovaný přístup s vyhodnocováním
kvality jedinců poruchovou simulací
\item[Std.] Standardní nastavení GA
\item[Extr.] Podíl extremistů v populaci
\item[Polar.] Polarizace chromosomu extremistů
\item[Ruleta] Ruletový výběr
\item[1-B kříž.] Jednobodové křížení
\item[2-B kříž.] Dvoubodové křížení
\end{description}

%*************************

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
60.77 &
60.51 & 60.57 & 60.33 & 61.13 &
60.41 & 60.72 & 60.077 & 60.13 \\
\hline
\emph{Evoluce (sim.)} &
95.56 &
95.58 & 95.55 & 95.51 & 95.58 &
95.62 & 95.54 & 95.58 & 95.58 \\
\hline
\emph{Rand. přístup (tab.)} &
60.57 &
60.57 & 60.72 & 60.57 & 60.75 &
60.67 & 60.64 & 60.57 & 60.92 \\
\hline
\emph{Rand. přístup (sim.)} &
95.54 &
95.62 & 95.60 & 95.55 & 95.64 &
95.59 & 95.64 & 95.53 & 95.62 \\
\hline
\hline
\emph{Prům. čas [s]} &
3972 &
4084 & 4482 & 4516 & 4918 &
3630 & 4719 & 3474 & 3266 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku c3540 pro tabulku 779 vektorů}
\label{tab:c3540}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
37.84 &
39.30 & 39.30 & 39.30 & 38.64 &
36.43 & 36.78 & 37.84 & 37.39 \\
\hline
\emph{Evoluce (sim.)} &
97.58 &
97.43 & 97.71 & 97.67 & 97.64 &
97.71 & 97.83 & 97.58 & 97.83 \\
\hline
\emph{Rand. přístup (tab.)} &
36.48 &
36.28 & 35.98 & 36.080 & 36.58 &
35.58 & 36.080 & 36.48 & 36.13 \\
\hline
\emph{Rand. přístup (sim.)} &
97.18 &
97.35 & 97.30 & 97.37 & 97.43 &
97.47 & 97.58 & 97.18 & 97.72 \\
\hline
\hline
\emph{Prům. čas [s]} &
1220 &
1477 & 1536 & 1509 & 1431 &
1254 & 1508 & 991 & 960 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku c880 pro tabulku 398 vektorů}
\label{tab:c880}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
12.14 &
11.68 & 12.066 & 11.86 & 11.94 &
11.89 & 11.84 & 11.30 & 11.84 \\
\hline
\emph{Evoluce (sim.)} &
84.35 &
84.35 & 84.32 & 84.37 & 84.31 &
84.35 & 84.27 & 84.36 & 84.38 \\
\hline
\emph{Rand. přístup (tab.)} &
11.76 &
11.76 & 11.91 & 11.71 & 11.81 &
11.81 & 11.68 & 11.71 & 11.68 \\
\hline
\emph{Rand. přístup (sim.)} &
84.30 &
84.33 & 84.27 & 84.35 & 84.33 &
84.34 & 84.40 & 84.30 & 84.35 \\
\hline
\hline
\emph{Prům. čas [s]} &
19968 &
19485 & 15363 & 17204 & 18007 &
12468 & 26432 & 9768 & 15431 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku c2670 pro tabulku 784 vektorů}
\label{tab:c2670}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
87.25 &
86.10 & 85.63 & 85.83 & 85.49 &
87.12 & 87.73 & 84.68 & 85.56 \\
\hline
\emph{Evoluce (sim.)} &
94.010 &
92.92 & 92.40 & 92.87 & 91.77 &
93.91 & 93.54 & 92.14 & 92.97 \\
\hline
\emph{Rand. přístup (tab.)} &
87.12 &
86.98 & 86.51 & 86.92 & 86.85 &
87.32 & 86.92 & 87.39 & 86.92 \\
\hline
\emph{Rand. přístup (sim.)} &
93.49 &
93.59 & 93.54 & 93.59 & 93.65 &
93.70 & 93.80 & 93.80 & 93.70 \\
\hline
\hline
\emph{Prům. čas [s]} &
255 &
300 & 322 & 314 & 335 &
249 & 651 & 261 & 225 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku s386 pro tabulku 295 vektorů}
\label{tab:s386}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
85.051 &
85.32 & 85.12 & 85.32 & 85.59 &
79.66 & 80.74 & 84.65 & 84.92 \\
\hline
\emph{Evoluce (sim.)} &
97.21 &
97.35 & 97.26 & 96.84 & 97.49 &
93.91 & 94.56 & 96.79 & 97.21 \\
\hline
\emph{Rand. přístup (tab.)} &
80.067 &
79.87 & 80.00 & 80.34 & 80.067 &
80.00 & 79.93 & 80.74 & 80.067 \\
\hline
\emph{Rand. přístup (sim.)} &
94.093 &
94.047 & 93.81 & 95.26 & 93.77 &
93.77 & 92.98 & 94.23 & 93.58 \\
\hline
\hline
\emph{Prům. čas [s]} &
723 &
1024 & 1212 & 958 & 950 &
730 & 976 & 641 & 674 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku s420 pro tabulku 297 vektorů}
\label{tab:s420}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
78.44 &
78.64 & 79.25 & 79.026 & 78.025 &
77.64 & 79.72 & 77.41 & 77.97 \\
\hline
\emph{Evoluce (sim.)} &
93.62 &
94.050 & 94.12 & 94.14 & 93.75 &
94.68 & 94.24 & 94.087 & 94.27 \\
\hline
\emph{Rand. přístup (tab.)} &
78.78 &
78.89 & 78.92 & 78.80 & 78.72 &
78.92 & 78.75 & 78.44 & 78.58 \\
\hline
\emph{Rand. přístup (sim.)} &
93.62 &
94.31 & 94.61 & 94.35 & 93.77 &
94.25 & 94.42 & 93.75 & 93.72 \\
\hline
\hline
\emph{Prům. čas [s]} &
2465 &
2903 & 2644 & 2537 & 2603 &
2277 & 4323 & 2038 & 2255 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku s953 pro tabulku 719 vektorů}
\label{tab:s953}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
88.11 &
87.76 & 87.97 & 87.97 & 87.62 &
88.11 & 88.11 & 87.19 & 87.26 \\
\hline
\emph{Evoluce (sim.)} &
91.12 &
90.91 & 91.15 & 90.67 & 90.88 &
90.81 & 91.26 & 90.74 & 90.81 \\
\hline
\emph{Rand. přístup (tab.)} &
88.11 &
88.26 & 88.11 & 88.043 & 88.19 &
87.90 & 88.11 & 88.11 & 88.043 \\
\hline
\emph{Rand. přístup (sim.)} &
90.98 &
90.84 & 91.15 & 90.81 & 91.015 &
90.91 & 91.26 & 91.015 & 90.95 \\
\hline
\hline
\emph{Prům. čas [s]} &
608 &
848 & 820 & 868 & 628 &
592 & 1101 & 529 & 536 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku s713 pro tabulku 281 vektorů}
\label{tab:s713}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
79.85 &
82.91 & 83.062 & 85.27 & 84.92 &
74.15 & 77.75 & 83.41 & 84.34 \\
\hline
\emph{Evoluce (sim.)} &
93.56 &
95.45 & 95.80 & 97.90 & 97.50 &
86.95 & 91.23 & 96.48 & 97.11 \\
\hline
\emph{Rand. přístup (tab.)} &
74.42 &
74.38 & 74.38 & 74.23 & 74.11 &
74.26 & 74.42 & 74.30 & 74.19 \\
\hline
\emph{Rand. přístup (sim.)} &
87.70 &
88.098 & 88.098 & 87.56 & 87.42 &
87.40 & 87.40 & 87.96 & 87.35 \\
\hline
\hline
\emph{Prům. čas [s]} &
3330 &
5172 & 4952 & 3354 & 3192 &
4026 & 5305 & 3563 & 3977 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku s838 pro tabulku 516 vektorů}
\label{tab:s838}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
17.69 &
22.31 & 23.85 & 20.00 & 27.69 &
16.92 & 12.31 & 13.077 & 16.15 \\
\hline
\emph{Evoluce (sim.)} &
93.91 &
94.60 & 94.77 & 93.87 & 95.18 &
94.065 & 93.76 & 93.75 & 94.67 \\
\hline
\emph{Rand. přístup (tab.)} &
20.00 &
19.23 & 19.23 & 22.31 & 20.77 &
18.46 & 18.46 & 19.23 & 19.23 \\
\hline
\emph{Rand. přístup (sim.)} &
93.71 &
94.62 & 94.69 & 94.19 & 94.81 &
94.048 & 93.59 & 94.53 & 94.42 \\
\hline
\hline
\emph{Prům. čas [s]} &
147 &
173 & 166 & 184 & 159 &
124 & 126 & 111 & 112 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 26 vektorů}
\label{tab:b07_26}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
23.33 &
25.42 & 30.83 & 30.42 & 32.083 &
24.17 & 23.75 & 28.75 & 29.58 \\
\hline
\emph{Evoluce (sim.)} &
93.45 &
95.32 & 95.91 & 96.00 & 96.00 &
94.95 & 95.34 & 93.91 & 95.73 \\
\hline
\emph{Rand. přístup (tab.)} &
22.92 &
21.17 & 22.50 & 22.92 & 21.25 &
22.50 & 21.25 & 23.75 & 21.67 \\
\hline
\emph{Rand. přístup (sim.)} &
95.32 &
95.0042 & 94.95 & 94.97 & 94.77 &
94.99 & 94.69 & 94.81 & 95.0046 \\
\hline
\hline
\emph{Prům. čas [s]} &
193 &
266 & 251 & 252 & 236 &
213 & 200 & 229 & 159 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 48 vektorů}
\label{tab:b07_48}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
30.99 &
36.056 & 33.52 & 38.028 & 39.44 &
22.54 & 23.38 & 32.39 & 35.49 \\
\hline
\emph{Evoluce (sim.)} &
94.33 &
95.64 & 91.16 & 94.44 & 92.81 &
95.22 & 95.54 & 90.080 & 94.51 \\
\hline
\emph{Rand. přístup (tab.)} &
23.66 &
23.38 & 26.76 & 23.94 & 22.82 &
23.10 & 23.66 & 23.94 & 23.94 \\
\hline
\emph{Rand. přístup (sim.)} &
95.39 &
94.95 & 95.29 & 95.29 & 95.075 &
94.90 & 95.18 & 95.0044 & 95.093\\
\hline
\hline
\emph{Prům. čas [s]} &
258 &
246 & 333 & 308 & 302 &
271 & 388 & 252 & 239 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 71 vektorů}
\label{tab:b07_71}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
39.80 &
41.37 & 41.18 & 45.49 & 42.55 &
32.16 & 36.27 & 39.22 & 38.82 \\
\hline
\emph{Evoluce (sim.)} &
96.085 &
94.97 & 93.48 & 90.72 & 90.22 &
95.57 & 94.030 & 89.14 & 94.26 \\
\hline
\emph{Rand. přístup (tab.)} &
32.35 &
33.53 & 32.75 & 32.55 & 33.73 &
32.94 & 33.14 & 33.33 & 32.75 \\
\hline
\emph{Rand. přístup (sim.)} &
95.52 &
95.62 & 95.27 & 95.39 & 95.50 &
95.52 & 95.32 & 95.22 & 95.62 \\
\hline
\hline
\emph{Prům. čas [s]} &
352 &
429 & 401 & 381 & 401 &
346 & 394 & 274 & 265 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 102 vektorů}
\label{tab:b07_102}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
61.11 &
59.68 & 62.22 & 62.064 & 61.35 &
58.81 & 59.52 & 58.81 & 60.24 \\
\hline
\emph{Evoluce (sim.)} &
95.50 &
94.95 & 95.71 & 95.77 & 96.014 &
95.022 & 95.52 & 95.075 & 95.75 \\
\hline
\emph{Rand. přístup (tab.)} &
59.29 &
58.97 & 58.65 & 58.97 & 59.048 &
59.29 & 59.52 & 58.41 & 59.21 \\
\hline
\emph{Rand. přístup (sim.)} &
95.38 &
95.0044 & 95.25 & 94.79 & 95.70 &
94.92 & 95.70 & 95.38 & 95.29 \\
\hline
\hline
\emph{Prům. čas [s]} &
637 &
817 & 775 & 849 & 722 &
612 & 868 & 581 & 562 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 252 vektorů}
\label{tab:b07_252}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
63.99 &
64.71 & 67.00 & 66.77 & 66.88 &
63.76 & 64.83 & 65.44 & 64.75 \\
\hline
\emph{Evoluce (sim.)} &
93.69 &
95.43 & 95.75 & 95.55 & 95.48 &
94.63 & 95.15 & 94.95 & 95.093 \\
\hline
\emph{Rand. přístup (tab.)} &
64.60 &
64.30 & 64.15 & 64.60 & 63.76 &
63.34 & 64.26 & 63.76 & 64.49 \\
\hline
\emph{Rand. přístup (sim.)} &
94.97 &
94.90 & 94.44 & 95.38 & 94.95 &
95.32 & 94.85 & 95.25 & 95.11 \\
\hline
\hline
\emph{Prům. čas [s]} &
1257 &
1455 & 1484 & 1418 & 1358 &
1139 & 1769 & 1099 & 978 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 526 vektorů}
\label{tab:b07_526}
\end{table}

%*************************

\end{landscape}

\begin{landscape}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
72.86 &
73.73 & 70.89 & 74.57 & 73.90 &
70.08 & 70.44 & 71.99 & 72.65 \\
\hline
\emph{Evoluce (sim.)} &
95.13 &
95.41 & 94.83 & 95.47 & 95.50 &
94.53 & 94.93 & 94.83 & 94.92 \\
\hline
\emph{Rand. přístup (tab.)} &
70.61 &
70.49 & 70.79 & 70.49 & 70.64 &
70.20 & 70.54 & 70.87 & 70.38 \\
\hline
\emph{Rand. přístup (sim.)} &
95.25 &
95.32 & 94.81 & 94.93 & 95.15 &
95.38 & 90.51 & 94.42 & 94.62 \\
\hline
\hline
\emph{Prům. čas [s]} &
1606 &
1913 & 1817 & 1758 & 1749 &
1445 & 1688 & 1334 & 1273 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 784 vektorů}
\label{tab:b07_784}
\end{table}

%*************************

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
\bf{Měření} &
\bf{Std.} &
\bf{Extr. 60\%} & \bf{Extr. 70\%} & \bf{Extr. 80\%} &
  \bf{Extr. 90\%} &
\bf{Polar. 95\%} & \bf{Ruleta} & \bf{1-B kříž.} & \bf{2-B kříž.} \\
\hline
\hline
\emph{Evoluce (tab.)} &
73.65 &
74.75 & 74.91 & 75.77 & 76.039 &
72.11 & 72.67 & 73.58 & 73.95 \\
\hline
\emph{Evoluce (sim.)} &
95.61 &
95.29 & 95.77 & 95.78 & 95.94 &
94.79 & 94.95 & 95.54 & 94.95 \\
\hline
\emph{Rand. přístup (tab.)} &
72.42 &
72.62 & 72.69 & 72.83 & 72.50 &
72.28 & 72.65 & 72.65 & 72.48 \\
\hline
\emph{Rand. přístup (sim.)} &
94.048 &
94.62 & 94.92 & 94.72 & 95.15 &
94.58 & 94.99 & 95.057 & 94.56 \\
\hline
\hline
\emph{Prům. čas [s]} &
1982 &
1688 & 2439 & 2051 & 2140 &
1755 & 2228 & 1753 & 1931 \\
\hline
\end{tabular}
\end{center}
\caption{Výsledky měření benchmarku b07 pro tabulku 1021 vektorů}
\label{tab:b07_1021}
\end{table}

%*************************

\end{landscape}

%*************************

\subsection{Výsledky pro obvod c3540}

Při porovnávání s randomizovaným přístupem, dále jen
\emph{RS}
podle Random Search, budeme za výsledek GA považovat kvalitu
nejlepšího jedince v populaci po dosažení 550. generace této
populace. Při zkoumání vlivu hodnoty parametrů algoritmu na průběh
evoluce nás pak bude zajímat spíše průměrná kvalita jedinců
v populaci. Takto lépe podchytíme trend vývoje uvažované populace
v závislosti na hodnotě sledovaného parametru. Mez 550. generace
jsme pak zvolili proto, že v řadě srovnávaných případů došlo
v populaci k rychlé degeneraci a populace se ustálila natolik, že
nemělo smysl v měření dále pokračovat.

Příkladem testovaného obvodu, u kterého se neprojevil takřka žádný
rozdíl mezi výsledky dosahovanými GA a RS, je obvod c3540. Drobné
fluktuace ve výsledcích jsou s vysokou pravděpodobností dílem
náhody, a lze je tak považovat za statistické chyby měření.

Na výsledky dosahované GA pro obvod c3540 nemá podle grafů na
obrázcích
\ref{fig:experiments-c3540-xr-09} a
\ref{fig:experiments-c3540-or-095}
prakticky žádný vliv polarizace extrémních jedinců ani jejich podíl
v populaci. V obou případech jsou pak výsledky GA srovnatelné
s výsledky RS.

Polarizací jako takovou rozumíme v tomto kontextu míru polarizace ve
prospěch počtu jedniček v chromosomu extrémních jedinců.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/c3540-xr-09.png}
\caption{Vliv podílu extremistů pro obvod c3540}
\label{fig:experiments-c3540-xr-09}
\end{center}
\end{figure}

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/c3540-or-095.png}
\caption{Vliv polarizace extremistů pro obvod c3540}
\label{fig:experiments-c3540-or-095}
\end{center}
\end{figure}

Z grafu na obrázku
\ref{fig:experiments-c3540-st-1}
je navíc dobře patrné, že použitá implementace ruletového výběru
nedokáže zajistit zdravý vývoj populace. Rozdíl průměrných kvalit
takové populace a populace prořezávané turnajovým výběrem se blíží
5\%. I přes to však GA dosahuje za použití tohoto typu výběru
výsledků srovnatelných s RS.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/c3540-st-1.png}
\caption{Vliv typu selekce pro obvod c3540}
\label{fig:experiments-c3540-st-1}
\end{center}
\end{figure}

Za použití dvoubodového křížení pak populace sice dříve konverguje
ke kvalitním jedincům, ale z dlouhodobého hlediska má tento typ
křížení na průměrnou kvalitu populace stejný vliv, jako standardně
používané křížení uniformní (viz obr.
\ref{fig:experiments-c3540-ct-1}).
Výsledky obou metod, tedy GA a RS, jsou pak opět plně srovnatelné.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/c3540-ct-1.png}
\caption{Vliv typu křížení pro obvod c3540}
\label{fig:experiments-c3540-ct-1}
\end{center}
\end{figure}

%*************************

\subsection{Výsledky pro obvod s838}

Opačná situace nastala v případě obvodu s838. U tohoto obvodu
dosahoval GA ve srovnání s RS v některých případech až o 10\%
lepších výsledků (viz graf na obr.
\ref{fig:experiments-s838-xr-09}).

Na tomto grafu je dobře vidět vliv podílu extrémních jedinců
v populaci na její průměrnou kvalitu. Zvýšením tohoto podílu ze
standardních 50 na 90\% dosahuje průměrná kvalita populace hodnot
o necelých 5\% vyšších. Tento rozdíl navíc kolem 50. generace
dosahuje krátkodobě téměř 10\%. Oproti RS pak dosahuje GA v případě
90\% zastoupení extrémních jedinců v populaci přibližně o 10\%
lepších výsledků.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/s838-xr-09.png}
\caption{Vliv podílu extremistů pro obvod s838}
\label{fig:experiments-s838-xr-09}
\end{center}
\end{figure}

Graf na obrázku
\ref{fig:experiments-s838-or-095}
popisuje vývoj průměrné kvality populace v případě, že je populace
z 50\% tvořena extrémními jedinci, jejichž chromosom je z naprosté
většiny vyplněn samými jedničkami. Pro všechny loci chromosomu
takových jedinců platí, že pravděpodobnost jejich obsazení jedničkou
je v tomto případě rovna 95\%. Z grafu je pak vidět, že takový
způsob polarizace chromosomu extrémních jedinců je méně výhodný, než
standardně používaná 5\% polarizace. Rozdíl průměrné kvality
populací dosahované v obou případech překračuje 5\%. Pro uvažovanou
95\% polarizaci pak GA dosahuje srovnatelných výsledků s RS.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/s838-or-095.png}
\caption{Vliv polarizace extremistů pro obvod s838}
\label{fig:experiments-s838-or-095}
\end{center}
\end{figure}

Stejně jako tomu bylo u obvodu c3540, platí i v tomto případě, že
použitá implementace ruletového výběru není příliš efektivní
z hlediska konvergence populace ke kvalitnějším jedincům. Průměrná
kvalita populace zde stoupá jen velice pozvolna (viz obr.
\ref{fig:experiments-s838-st-1}).
Rozdíl oproti standardně používanému turnajovému výběru dosahuje
téměř 10\%. I přes výše zmíněné nedostatky však výsledky GA
s ruletovým výběrem převyšují výsledky RS o několik málo procent.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/s838-st-1.png}
\caption{Vliv typu selekce pro obvod s838}
\label{fig:experiments-s838-st-1}
\end{center}
\end{figure}

\vfill\pagebreak

Vliv typu křížení na průměrnou kvalitu populace zachycuje graf na
obrázku
\ref{fig:experiments-s838-ct-1}.
Je na něm patrná výhoda dvoubodového křížení oproti standardně
používanému křížení uniformnímu. Průměrně dosahovaná kvalita
populace je v případě prvně jmenovaného typu křížení o necelých 5\%
vyšší než u uniformního křížení. Výsledky GA používajícího
dvoubodové křížení jsou pak zhruba o 10\% lepší než výsledky RS.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/s838-ct-1.png}
\caption{Vliv typu křížení pro obvod s838}
\label{fig:experiments-s838-ct-1}
\end{center}
\end{figure}

%*************************

\subsection{Výsledky pro obvod b07}

Posledním z testovaných obvodů, u kterých si podrobněji popíšeme
výsledky měření, je obvod b07. Tento obvod je do značné míry
speciální tím, že jsme u něj zjišťovali vliv velikosti
předgenerované tabulky vektorů, používané při vyhodnocování kvality
jedinců, na vývoj populace jedinců v průběhu evoluce.

Nejzajímavějších výsledků jsme pak dosáhli pro poměrně malou
tabulku, čítající celkem 71 vektorů.

Rozdíl průměrné kvality populace obsahující standardních 50\%
extrémních jedinců a populace s 90\% takových jedinců se pohybuje
v rozmezí 5 a 10\% (viz obr.
\ref{fig:experiments-b07-71-xr-09}).
Podstatnější je však fakt, že GA pracující s takovouto populací
dosahuje téměř o 20\% lepších výsledků než RS, což představuje
oproti RS téměř dvojnásobné zlepšení.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/b07-71-xr-09.png}
\caption{Vliv podílu extremistů pro obvod b07}
\label{fig:experiments-b07-71-xr-09}
\end{center}
\end{figure}

Graf na obrázku
\ref{fig:experiments-b07-71-or-095}
popisuje mimo jiné i vývoj průměrné kvality populace, která obsahuje
jedince s 95\% polarizací chromosomu. Je z něj jasně patrný propad
této kvality ve srovnání s kvalitou dosahovanou v populaci, která
používá standardní 5\% polarizaci. Tento pokles dosahuje kolem
150. generace téměř 20\% a v další generacích se ustaluje zhruba na
10\%. Co se výsledků GA s takovou populací týče, ty jsou pak plně
srovnatelné s výsledky dosahovanými RS.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/b07-71-or-095.png}
\caption{Vliv polarizace extremistů pro obvod b07}
\label{fig:experiments-b07-71-or-095}
\end{center}
\end{figure}

V případě ruletového výběru se i u tohoto obvodu opakuje situace
popsaná u obou dříve zmíněných obvodů. Průměrná kvalita populace je
při použití tohoto typu selekce přibližně o 10\% nižší, než když
zvolíme turnajový výběr (viz obr.
\ref{fig:experiments-b07-71-st-1}).
Je zajímavé, že posledně jmenovaný typ selekce je z výše uvedeného
hlediska v prvních asi sto generacích výrazně horší a ruletový výběr
překonává teprve při překročení přibližně 125. generace. Jinak jsou
GA a RS opět srovnatelné z pohledu nejlepších jimi dosažených
výsledků.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/b07-71-st-1.png}
\caption{Vliv typu selekce pro obvod b07}
\label{fig:experiments-b07-71-st-1}
\end{center}
\end{figure}

Na obrázku
\ref{fig:experiments-b07-71-ct-1}
je uveden graf vlivu typu křížení na vývoj průměrné kvality
populace. I v tomto případě se dvoubodové křížení chová obdobným
způsobem jako u předchozích dvou testovaných obvodů. Hlavní rozdíl
spočívá v tom, že diference průměrné kvality populací u obou typů
křížení, tj. dvoubodového a standardně používaného uniformního, je
mnohem více patrná, především pak v počátcích samotné evoluce. Tato
diference lehce překračuje hranici 5\%. GA využívající tento typ
křížení pak dosahuje o více jak 10\% lepších výsledků než RS.

\begin{figure}[p]
\begin{center}
\includegraphics[width=0.85\textwidth]{figs/b07-71-ct-1.png}
\caption{Vliv typu křížení pro obvod b07}
\label{fig:experiments-b07-71-ct-1}
\end{center}
\end{figure}

\vfill\pagebreak

\subsection{Shrnutí naměřených výsledků}

I v tomto závěrečném shrnutí budeme pracovat se zmíněnými třemi
obvody, tj. s c3540, s838 a b07, protože výsledky pro ně změřené
představují poměrně dobrou reprezentaci výsledků naměřených pro
všechny testované obvody (pro jejich celkový přehled viz tab.
\ref{tab:final_1}).

\begin{table}[p]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\bf{Testovaný obvod} &
\bf{GA (tab.)} &
\bf{GA (sim.)} &
\bf{RS (tab.)} &
\bf{RS (sim.)} &
\bf{Prům. čas [s]} \\
\hline
\hline
c3540 & 61.13 & 95.58 & 60.75 & 95.14 & 4918 \\
\hline
c880 & 38.64 & 97.64 & 36.58 & 97.43 & 1431 \\
\hline
c2670 & 11.94 & 84.31 & 11.81 & 84.33 & 18007 \\
\hline
s386 & 85.49 & 91.77 & 86.85 & 93.65 & 335 \\
\hline
s420 & 85.59 & 97.49 & 80.067 & 93.77 & 950 \\
\hline
s953 & 78.025 & 93.75 & 78.72 & 93.77 & 2603 \\
\hline
s713 & 87.62 & 90.88 & 88.19 & 91.015 & 628 \\
\hline
s838 & 84.92 & 97.50 & 74.11 & 87.42 & 3192 \\
\hline
b07 (26 vek.) & 27.69 & 95.18 & 20.77 & 94.81 & 159 \\
\hline
b07 (48 vek.) & 32.083 & 96.00 & 21.25 & 94.77 & 236 \\
\hline
b07 (71 vek.) & 39.44 & 92.81 & 22.82 & 95.075 & 302 \\
\hline
b07 (102 vek.) & 42.55 & 90.22 & 33.73 & 95.50 & 401 \\
\hline
b07 (252 vek.) & 61.35 & 96.014 & 59.048 & 95.70 & 722 \\
\hline
b07 (526 vek.) & 66.88 & 95.48 & 63.76 & 94.95 & 1358 \\
\hline
b07 (784 vek.) & 73.90 & 95.50 & 70.64 & 95.15 & 1749 \\
\hline
b07 (1021 vek.) & 76.039 & 95.94 & 72.50 & 95.15 & 2140 \\
\hline
\end{tabular}
\end{center}
\caption{Přehled výsledků změřených pro 90\% podíl extremistů
v populaci}
\label{tab:final_1}
\end{table}

Výše popsané výsledky měření je možné shrnout ze dvou různých úhlů
pohledu. Prvním je vliv různých hodnot sledovaných parametrů GA na
jeho výkonnost jako takovou a druhým je pak skutečná použitelnost
takto nastaveného algoritmu pro řešení zadaného problému. Jako
měřítko nám přitom poslouží už tolikráte citovaný plně randomizovaný
přístup:

\begin{enumerate}
\item{
Začněme jedním velice zajímavým parametrem GA, kterým je
\emph{podíl extrémních jedinců v populaci}.

Ačkoliv se tento parametr u obvodu c3540 takřka vůbec neprojevil,
u zbývajících dvou obvodů se už situace značně lišila. Samotné
zvýšení hodnoty tohoto parametru z 50 na 90\% se projevilo nárůstem
průměrné kvality populace o 5\% v případě obvodu s838 a o 10\%
u obvodu b07.

Ještě více dramatický je rozdíl výsledků dosahovaných GA s takto
zvýšenou hodnotou parametru a RS, který dosahoval více než 10\%
pro obvod s838 a téměř 20\% v případě obvodu b07.
}

\item{
Druhým na řadě je možná ještě zajímavější parametr GA, kterým je
\emph{polarizace chromosomu extrémních jedinců}.

V kapitole
\ref{chap:theory-unbalanced_ca}
o CA s rozváženým seedem jsme se zmínili o důsledcích, jaké má
rozvážení seedu pro testování logických obvodů. Co jsme ale pouze
naznačili, byla optimální míra takového rozvážení. V řadě
experimentů byly zkoumány vlastnosti CA se seedem tvořeným téměř
výhradně samými nulami
\cite{CORNO02, FISER_CM, FISER_PT}.
To byl také důvod, proč jsme takové nastavení parametru použili jako
výchozí.

Možná by zde také bylo na místě jen letmo připomenout, že námi
používaní jedinci s polarizací chromosomu 5\% de facto reprezentují
výše zmíněné CA (viz kap.
\ref{chap:experiments-polarization}).

V případě obvodu c3540 se nastavení tohoto parametru opět takřka
nijak neprojevilo, zato u dalších dvou obvodů jsme mohli pozorovat
negativní vliv zvýšení polarizace ve prospěch počtu jedniček v
chromosomu extrémních jedinců. Zatímco u obvodu s838 se jednalo
o pokles průměrné kvality populace o 5\%, v případě obvodu b07 to
už představovalo téměř 10\%.

Ve všech třech případech se pak zvýšená polarizace promítla do
výsledných vlastností GA tak, že tento dosahoval takřka totožných
výsledků s RS.
}

\item{
Dalším sledovaným parametrem je
\emph{typ selekce}.

Zde se téměř jednoznačně ukázalo, že u všech zmiňovaných obvodů se
ruletový výběr projevil jako nevhodná varianta selekce. Ve všech
třech případech se pak průměrná kvalita populace zvyšovala v průběhu
evoluce pouze zanedbatelně. Rozdíl mezi ní a průměrnou kvalitou
populace dosahovanou za použití turnajového výběru se pohyboval
v rozmezí od 5 do 10\%, počínaje obvodem c3540 a konče obvodem b07.

Výsledky GA používajícího ruletový výběr se velice blížily výsledkům
dosahovaným RS, od kterých se nikdy nelišily více než o několik málo
procent v obou směrech. Jedním z důsledků použití tohoto typu
selekce byla takřka konstantní diversita populace v průběhu měření,
která se většinou pohybovala kolem 90\%. Tak vysoká diversita
populace mohla podle mého názoru přiblížit vlastnosti GA s tímto
nastavením a RS, a proto jsme pak u obou metod mohli pozorovat
obdobné chování.
}

\item{
Posledním z probíraných parametrů je
\emph{typ křížení}.

Na rozdíl od parametru popisovaného v předchozím bodě je u tohoto
parametru situace pro sledovanou hodnotu přesně opačná. U každého ze
zmiňovaných obvodů se projevila změna ze standardně používaného
uniformního křížení na křížení dvoubodové pozitivně a ve všech
případech se jednalo o cca.\ 5\% nárůst průměrné kvality populace.

Co se srovnání RS a GA využívajícího dvoubodové křížení týče, tak
v případě obvodů s838 a b07 dosahoval takový algoritmus zhruba
o 10\% lepších výsledků než RS a výsledky pak byly srovnatelné pouze
u obvodu c3540.
}
\end{enumerate}

Na základě výše uvedeného výčtu sledovaných parametrů je možné
formulovat následující doporučení: jako nejslibnější nastavení GA se
mi jeví použití populace tvořené z 90\% extrémními jedinci, jejichž
chromosomy obsahují mizivé procento jedniček, spolu s turnajovým
výběrem a dvoubodovým křížením.

Závěrem bych se rád zmínil o
\emph{vlivu velikosti předgenerované tabulky vektorů}
na chování GA, který se nejvýrazněji projevil právě u obvodu b07 pro
tabulku o 71 vektorech.

Z měření provedených pro tento obvod výplývá, že s klesající
velikostí tabulky se vlastnosti GA, konkrétně dosahované pokrytí
této tabulky, ve srovnání s RS zlepšovaly. Nejlépe to pak bylo
patrné právě pro již zmíněnou tabulku 71 vektorů. Při dalším poklesu
se začaly vlastnosti algoritmu opět pomalu zhoršovat.

To si vysvětluji tím, že v případě velkých tabulek obsahujících
i přes tisíc vektorů bude cílový CA vyvíjený pomocí GA
přespecifikovaný. Algoritmus pak bude přehlcen daty o takovém
automatu, takže pro něj bude těžší takový automat vyvinout.

Pokud však použijeme příliš malé tabulky, čítající pouze několik
málo desítek vektorů, poskytneme tak GA nedostatečné množství
informací o cílovém CA, a tím mu také zkomplikujeme hledání takového
automatu.

Z tohotu úhlu pohledu se pak jako ideální jeví tabulky, jejichž
velikost nepřekračuje 150 vektorů. Směrodatnost tohoto tvrzení je
ale třeba prokázat dalším měřením pro co nejširší škálu testovaných
obvodů.

