\section{genpla}
\subsection*{duplicitní termy}
Zde jsem pouze doimplementoval funkci, která otestuje daný term vůči všem termům v daném spojovém seznamu proti duplicitě. Šlo vlastně o porovnání dvou textových řetězců. Funkce vrací 0 v případě rozdílnosti jinak vrátí 1 a nastaví validitu termu na 1. Smazání termu a generování dalšího již bylo v práci implementováno, poněvadž jsou ostatní testy implementovány podobně.
\subsection*{optimalizace kódu}
Z analýzy jsem určil, že největší přínos bude mít zoptimalizovat veškeré testy validity do jednoho průchodu. Proto jsem nejdříve všechny funkce, které prováděly test daného termu vůči ostatním převedl na funkce, které testují pouze dva termy vůči sobě. Poté jsem jejich kódy spojil do jedné funkce \verb|doPostChecks(...)|,která procházela spojový seznam všech doposud vygenerovaných termů a podle zadaní používala kusy kódu původních kontrol k otestování vůči termu přidávanému.

Dále bylo nepatrně pozměněno pár částí kódu při opravách chyb.

\section{genstate}

Z analýzy nám vyšlo, že budeme pro konstrukci přechodů stavového automatu používat termy v PLA tabulce, což nám umožňuje z velké části použít 1. generátor a doplnit ho pouze o třídu, která ponese informaci o stavovém automatu jako celku. To je především počet stavů, počet ekvivalentních tříd, dále pak o minimálním zapojení automatu po splnění kontrol spojitosti apod.

\subsection{Použité datové struktury}

Pro grafové algoritmy uvedené v analýze budeme používat celkem malé množství hran vedoucích z každého uzlu grafu. Je to způsobeno tím, že i když budeme generovat úplný determinsitický automat, tak si budeme vést pouze nutné stavy pro spojitost, dostupnost a konečnost automatu. Ostatní hrany budou generovány za běhu při generování termů. 

Byla proto zvolena jako nejvhodnější datová struktura reprezentující graf, metoda statického pole spojových seznamů příslušných hran o velikosti počtu uzlů. Výhodou je, že máme dostupné pohromadě všechny přechody, které vedou z jednoho uzlu.

\subsection{Průběh algoritmu }

Celý algoritmus generování probíhá zjednodušeně asi takto: Po načtení vstupních argumentů si program náhodně připraví třídy ekvivalence s počtem stavů v káždé z nich. Dále si vytvoří prázdný graf s počtem uzlů podle počtu tříd ekvivalence. Pokud jsou zapnuty příslušné kontroly, tak zajistí náhodnou spojitost grafu, pak doplní koncovost a dostupnost uzlů v grafu. Poté náhodně rozdělí zbylý počet termů mezi třídy ekvivalence. Zde přichází generátor termů z první části. Zavoláme ho postupně na všechny třídy ekvivalence a vygenerujeme tím veškeré přechody. Pak už zbývá jen vygenerovat ekvivalentní stavy z jejich tříd a podle zadání změnit některé termy a tím příslušné stavy na pseudo-ekvivalentní. Celý algoritmus je ještě zachycen na přiloženém obrázku a vybrané části podrobněji popsány dále. 

\begin{verbatim}
\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm]{alggenstate.eps}
\caption{Hrubé schéma algoritmu genstate}
\label{fig:logo}
\end{center}
\end{figure}
\end{verbatim}

\subsubsection*{Spojitost, koncovost, dostupnost}

Nakonec jsem minimální spojitost grafu řešil podle analýzy tak, že jsem si předpřipravil spojitý graf. Toho jsem docílil náhodným generováním $\sqrt{n}$ náhodně ohodnocených hran pro každé z $n$ uzlů. Aby byl takový graf spojitý, tak první hrana každého uzlu vede v 50-ti procentech na uzel s indexem o $1$ větší. Ve zbylých 50ti procentech vede na libovolný uzel s indexem vyšším, než pro který generujem hranu.
Po vygenerování takto zaplněného grafu na něj pustím Jarníkův algoritmus na minimální kostru. Výsledný graf již považuji za spojitý.
Pokud je zapnutá koncovost resp. dostupnost, doplním hrany tak, aby z každého uzlu vedla hrana resp. aby do každého uzlu vedla alespoň jedna hrana.

\subsubsection*{Generování přechodů}

Po náhodném doplnění počtu termů pro všechny třídy ekvivalence je postupně procházíme. Pro každou třídu přednastavíme parametry generátoru a necháme si vygenerovat správný počet termů, které již budou vygenerovány podle přednastavených kontrol. Pokud generujeme úplný deterministický automat, tak je tato fáze nahrazena pseudo generátorem, který vrátí všechny možné kombinace termů. V tomto bodě máme pro danou třídu ekvivalence předgenerované termy ve správném počtu. Zavoláme na ně tedy metodu \verb|DoplnStavy()|, která nám přímo do datové části každého termu vyplní aktuální a přechodový stav automatu. Začne vyplňovat přechody podle hran vygenerovaného grafu, zbytek přechodů doplní náhodně, s přihlédnutím na zapnutou kontrolu determinismu.

\subsubsection*{Ekvivalentní stavy}

Poslední částí je převést třídy ekvivalence na ekvivalentní stavy. Celý princip je založen na tom, že stavy zařazené do stejné třídy ekvivalence můžeme libovolně zaměňovat. Jsou totiž ekvivalentní. V tomto okamžiku máme ve všech termech nastaveny přechody, které označují jednotlivé třídy. Protože víme, které stavy patří do které třídy ekvivalence, tak se celý problém zjednodušil na pouhé nahrazování tříd v přechodech za náhodný stav z příslušné třídy. 
Toho docílíme tím, že každému stavu kopírujeme termy z příslušné třídy ekvivalence a přepisujeme indexy tříd na indexy stavů podle předem vygenerované tabulky.

Pseudo-ekvivalentní stavy jsou generovány jako procentuální množství termů, které nebudou mít definován určitý stav do kterého přechazejí. Procházejí se postupně všechny termy a se zadanou pravděpodobností se změní přechod na nedefinovaný. 

\chapter{Implementace gennetwork}

Tento generátor používal na generování obvodu úplně jiný přístup, než oba dva předchozí, proto bylo nutné navrhnout ho kompletně od začátku. Byl mnohem náročnější na implementaci, proto se zde o něm rozepíši trochu více. Především proberu algoritmus a datové struktury trochu více do hloubky.

\section{Datové struktury}

Z analýzy problému bylo jasné, že si budeme muset v paměti uchovávat celý obvod v jediné struktuře, kvůli použití genetického algoritmu. Dále bylo jasné, že si budeme muset vést celé zapojení jednoho obvodu v podobě grafu nad kterým budou definovány elementární metody na jeho úpravu. Tyto metody musí udržovat integritu dat zvolené formy grafu. 

\subsection{Graf zapojení obvodu}

Při implementaci grafu bylo asi ze všeho nejdůležitější rozhodnout, jestli budou spoje obvodu jako samostatné entity, nebo budou vedeny jen jako ukazatele mezi uzly grafu. S tím také úzce souviselo, jak bude reprezentováno větvení hran. Uvedu zde nástin pro a proti u obou případů.

{\bf spoj jako samostatná entita}\\
klady:
\bitem 
\item veškeré informace si nese sám. Jestli jde o globální vstup, do jakých hradel je zapojen, kolikrát je větven, počáteční a koncová úroveň v obvodu
\item máme přistup k seznamu všech hradel, takže operace nad všemi nebo nad různě vymezenou částí je jednodušší
\item spoj má implementované svoje elementární metody
\eitem
zápory:
\bitem 
\item zabírá více místa v paměti
\item podstatná část informací, kterou si spoj vede, je redundantní a tudíž je zde potencionální problém nekonzistence dat, včetně redundance metod spoje
\eitem

{\bf spoj jako ukazatel na následníka}\\
klady:
\bitem 
\item rychlejší procházení celým obvodem
\item nevedení si zbytečných redundantních informací
\item veškeré operace mohou být implementovány jako metody uzlu grafu --- méňě metod
\eitem
zápory:
\bitem 
\item pro obvod musí být vytvořen jeden velký uzel(hradlo) s globálními vtupy a výstupy 
\item všechny informace o spoji si musíme pokaždé dopočítat
\eitem

Nakonec jsem zvolil spoj jako samostatnou entitu kvůli přednosti, že si všechny informace nese sám spoj a nemusejí se dopočítávat. Tím jsem mohl řešit další problém a to jak implementovat větvení spojů. V úvahu připadali 3 možnosti:
\benum
\item na každý výstup hradla lze připojit více spojů --- budeme mít jen větvené spoje, větvení se pozná z parametrů hradla
\item vytvoříme nový typ hradla - větvení, informaci o větvení ponese toto hradlo a spoj, kterej do něj vede
\item každému spoji jde přiřadit více koncových hradel
\eenum

Všechny tři řešení měla svá pro a proti. Kvůli dodržení jednoduchosti spojů a uzlů v grafu jsem povolil vždy zapojovat na jejich přípojné body pouze jednu entitu. Proto jsem zvolil implementaci č.2. Ostatní implementace měli problémy například při větvení globálního vstupu nebo pokud jedna větev byla globálním výstupem. Zároveň jsem si však uvědomoval, že zmenšování či zvětšování větvení spoje bude v této implementaci mnohem složitější, než ve zbylých dvou.

Jelikož v obvodě nesmějí být zpětné vazby, zavedeme si vlastnost úroveň. Všechny hradla na jisté úrovni smějí být na výstupu spojeny jen s hradly na úrovni vyšší. Analogicky všechna hradla na jisté úrovni smějí být na vstupu spojeny pouze s hradly, které jsou na nižší úrovni. Zároveň jsem zvolil, že všechna hradla na větvení budou vždy jen o jednu úroveň výš než hradlo, ze kterého vede větvený spoj. Aby se nám nepletla obyčejná hradla s hradly na větvení, tak jsem určil, že obyčejná hradla budou umisťovaná pouze do lichých úrovní. Do sudých úrovní budeme umisťovat pouze hradla větvení. Tím jsme dosáhli toho, že můžeme hranu později větvit, i když vede mezi sousedními obyčejnými hradly.
Každé nově generované hradlo, přidávané do obvodu, budem generovat na nejvyšší neobsazené úrovni. Tím dosáheneme co největší rozmanitosti generovaných obvodů.

\subsection{Entity}

\verb|class Thradlo|

Tato třída představuje v celém programu jedno hradlo. Mezi její nejdůležitější vlastnosti patří: \verb|typ|, \verb|pocet_vstupu|, \verb|pocet_vystupu|, \verb|zapojene_vstupy|, \verb|zapojene_vystupy|, \verb|nazev|, \verb|uid|, \verb|uroven|, \verb|realna_uroven|, \verb|obvod|, \verb|next|, \verb|vstupy|, \verb|vystupy|. Většina vlastností je zřejmá podle jejich názvů. Vlastnost \verb|next| je ukazatel na další hradlo v obvodě a implementuje tak jednoduchý spojový seznam všech hradel. Vlastnost \verb|vstupy| resp. \verb|vystupy| je pole ukazatelů na připojené spoje na vstupu resp. výstupu.

Metody jsou zaměřeny především na připojování a odpojování spojů od vstupů a výstupů hradla. Metoda \verb|zmensi_hradlo()| a \verb|zvetsi_hradlo()| se už podle názvu orientují na změnu počtu vstupů/výstupů v hradle a používají se především u hradel na větvení spojů. Dále jsou implementovány metody na výpočet různých koeficientů a testovatelnosti. Některé metody rozeberu později podrobněji.\\[7mm]

\verb|class Tspoj|

Třída implementující spoj mezi hradly. Její důležité vlastnosti jsou: \verb|uid|, \verb|vstup|, \verb|vystup|, \verb|zac|, \verb|kon|, \verb|vetveni|, \verb|op|, \verb|fc|, \verb|obvod|, \verb|next|. Vlastnost \verb|vstup| a \verb|vystup| specifikuje, jestli jde o globální vstup nebo výstup v obvodě, \verb|zac| a \verb|kon| jsou ukazatele na připojená hradla. Jestli je spoj operační\footnote{Operační spoj jsem si zavedl pro spoj, který je globální vstup a nebo je připojen na výstup nějakého funkčního hradla} určuje vlastnost \verb|op| a \verb|fc| určuje jestli je funkční\footnote{Funkční spoj označuje spoj který je přiveden na vstup funkčního hradla nebo je to globální výstup}. Tyto vlastnosti pomáhají při kontrole větvení a pomáhají při kontrole konzistence dat. Vlastnost \verb|next| jako v případě hradla tvoří jednoduchý spojový seznam všech spojů v obvodě.

Implementované metody jsou převážně na připojení a odpojení ke vstupům hradel, případně převedení spoje na globální vstup/výstup, dále pak na počítání testovatelnosti a nakonec zajímavá metoda \verb|Rozvetvi()|, která obstarává celkem složité větvení spojů. O té se zmíním ještě později.\\[7mm]

\verb|class Tobvod|

Tato třída jak již název napovídá představuje jeden celý kombinační obvod. Jako vlastnosti má veškeré zadané parametry generovaného obvodu např. \verb|pocet_vstupu|, \verb|maximalni_vetveni|, \verb|pocet_hradel|. Dále obsahuje některé pomocné věci při generování triviálního obvodu. Pro představu \verb|cislovani_hradel|, \verb|akt_vstup|, \verb|max_uroven|. Další nedílnou součástí jsou parametry určující pravděpodobnost výskytu jednotlivých hradel, stejně jako jejich maximální fan-in a pravděpodobnosti na jejich vícevstupové modely. Nesmíme zapomenout na ukazatele na seznam spoju a hradel \verb|Hradla|, \verb|Spoje| a ještě na obousměrně zřetězený spojový seznam hradel seřazených podle úrovně --- \verb|seznam_zac|, \verb|seznam_kon|. Statistické informace o obvodu nese třída uložena v parametru \verb|info|. Mezi další důležité vlastnosti patří pole vah pro výpočet fitness funkce, stejně jako globální vlastnosti obvodu. Do toho počítaje pro příklad \verb|celkova_testabilita| nebo \verb|realne_urovne|.

Mezi duležité metody třídy patří napřiklad: \verb|vygeneruj_obvod|, \verb|vytvor_nove_hradlo(..)|, \verb|spocti_urovne()|, \verb|spocti_fitness()|, \verb|proved_mutaci(..)|. Dále pak třída deklaruje metody na uložení v různých formátech a jiné pomocné metody. O některých se budu zmiňovat ještě později.\\[7mm]

\verb|class Tinfo|

V této třídě jsou uchovány statistické hodnoty již vytvořeného obvodu. Používá se pro počítání fitness funkce při zapnuté kontrole počtu hradel v obvodě. Tyto informace se ještě použijí při výpisu informací do ukládaného formátu a na obrazovku.\\[7mm]

\verb|class Thlavni|

Tato třída je nadevšemi třídami a nese informace o celém algoritmu, především pak struktury pro správné použití genetického algoritmu. Je to především pole ukazatalů na obvody vystihující aktualní populaci jedinců --- \verb|generace|.

Třída má jen 2 metody a to jsou \verb|zaloz_generaci()| a \verb|nova_generace()|. První z nich generuje počáteční populaci pomocí metody \verb|Tobvod::vygeneruj_obvod| a druhá z nich implementuje genetický algoritmus. Ten popíšu později.

\section{Průběh algoritmu}

Celý průběh generování sítě logických hradel probíhá zhruba asi takto: Nejprve se načtou vstupní parametry z příkazové řádky, poté se předpřipraví datové struktury a přepočítají se pravděpodobnosti generování různých typů hradel. Pokud není zapnuté ani jedno optimalizační kritérium, tak se vygeneruje jeden triviální obvod, uloží se a program končí. V opačném případě se vytvoří první generace pomocí metody \verb|Thlavni::zaloz_generaci()|. Následovně se začne populace jedinců zušlechťovat pomocí metody \verb|Thalvni::nova_generace()|. Program poté zušlechťování iterativně opakuje, dokud se nesplní jedno ze dvou možných ukončujících kritérií :
\benum
\item počet prošlých generací se rovná zadanému maximálnímu počtu generací
\item počet generací při kterých nebyl změněn nejsilnější jedinec se rovná hodnotě zadané v příkazové řádce. Jinak se použije standratní hodnota rovna 50
\eenum
Po ukončení iterativní smyčky máme na počátku populace nejlepšího jedince, toho uložíme do zvolených formátů a program končí.

\section{Popis některých důležitých metod}

\subsection{Základní operace se spoji a hradly}

U všech těchto metod bylo velmi důležité striktně dodržet konzistenci dat. Zde se projevil výběr datových struktur. Bylo nepodstatně těžší tyto metody bezchybně naprogramovat, než kdybych zvolil struktury s méně redundantními daty.

Nejsložitější případy vznikali při rozvětvování ještě nevětveného spoje a naopak při zmenšování větvícího hradla. Pokud se totiž hradlo zmenšilo až na jeden výstup, tak se zároveň samo smazalo a vstupní s výstupním spojem se sloučili v jeden. Tím vznikal potencionální problém pokud jsme měli někde ukazatel na spoj, který se při tomto zmenšování smazal. Na to si bylo potřeba dávat velký pozor.

\subsection{Metoda na tvorbu nového hradla}

\verb|Tobvod::vytvor_nove_hradlo(..)|\\

Tato metoda má argument, kterým se vybírá jestli generujeme i hradlo NOT nebo ne. Při generování triviálního obvodu bylo totiž potřeba generovat pouze hradla s více vstupy, abychom mohli snížit v celém obvodě nezapojené výstupy hradel. Metoda generuje hradlo typu $i$ ze všech typů hradel $n$ s pravděpodobností $P(i)$, která se počítá ze zadaných celočíselných indexů výskytů všech typů hradel $p(j)$ a to podle tohoto vzorce $$P(i) = \frac{p(i)}{\sum_{j=1}^{n}{p(j)}}$$Indexy výskytů hradel se dají měnit z příkazové řádky programu, standartně jsou nastaveny na hodnotu $5$.

Podle podobného principu se počítá i pravděpodobnost generování vícevstupového hradla v rámci jednoho typu hradla. Standartně jsou všechna hradla nastavena na maximální fan-in. Toto se dá předefinovat z příkazového řádku.

Všechny zde uvedené proměnné jsou v rámci jednoho zvoleného typu hradla. Pokud si označíme $i$ jako počet vstupů generovaného hradla, $n$ maximální fan-in, tak index výskytu hradla $p(i)$ je počítán jako $$p(i) = \frac{n-1}{i-1}$$ Pravděpodobnost $P(i)$ generování hradla s fan-in rovno $i$ je potom $$P(i) = \frac{p(i)}{\sum_{j=1}^{n}{p(j)}}$$ Tato pravděpodobnost je v průběhu celého programu neměnná a nedá se nijak ovlivnit.

Metoda potom pomocí konstruktoru vytvoří hradlo s vypočítanými parametry.

\section{Generování triviálního obvodu}

\verb|Tobvod::vygeneruj_obvod()|

Podle analýzy problému jsme určili, že budeme generovat triviální obvod s pevně danými neměnnými parametry a toho jsem se při implementaci musel držet. Šlo především o počet vstupů, počet výstupů, počet hradel a maximální větvení. Dále jsme se měli držet pravděpodobnosti generování typů hradel. To už jsme vyřešili předchozí popisovanou metodou.

Metoda si vede 2 pomocné pole ve kterých si ukládá:
\bitem
\item spoje, které můžeme alespoň jednou rozvětvit a nepřesáhneme zvolené maximální větvení --- pole $SP$
\item nezapojené výstupy operačních hradel\footnote{Nazývám tak všechny typy hradel mimo hradla větvení.} --- pole $HR$
\eitem

Metoda potom vygeneruje hradlo a pokud existuje nezapojený globální vstup tak ho s 90-ti procentní pravděpodobností připojí na 1. vstup hradla. Ve zbylých 10-ti procentech zkouší buď větvit spoj z pole $SP$, nebo připojit na hradlo z pole $HR$. Zbylé vstupy se pokouší zapojit s těmito pravděpodobnostmi --- 60\% globální vstup, 30\% připojit na výstup náhodného hradla z $HR$, 30\% větvení náhodného spoje z $SP$. Pokud se nám z nějakého důvodu nepodaří zapojit nějaký vstup, zkusíme zmenšit počet vstupů hradla, nebo ho smažeme a zkusíme vygenerovat znovu.

Při každém nově vytvořeném spoji, a pokud není omezeno větvení na 1, tak spoj přidáme do pole $SP$. Při úspěšném zapojení celého hradla ho přidáme do pole $HR$. Zároveň musíme při větvení koukat, jestli nepřesáhneme maximální větvení, v tom případě musíme hranu z pole $SP$ odstranit.

Když máme zapojené všechny globální vstupy, tak si náhodně zvolíme počet globálních výstupů, které budou připojeny přímo na výstup z operačního hradla. Volíme mezi 70-ti a 90-ti procenty ze všech globálních výstupů.

Následně vygenerujeme nové hradlo a vypočítáme pro něj 2 hodnoty, které určují kolik jeho vstupů musíme minimálně a maximálně zapojit přímo na výstupy předešlých hradel z pole $HR$. Zároveň volíme pravděpodobnosti zapojení na hradlo z $HR$ nebo větvení nějakého pole z $SP$ tak, abychom v průměru měli jeden vstup zapojený na $HR$. Tím dosáhneme toho, že budeme počet hradel v poli $HR$ stále udržovat na přibližně podobné hodnotě, a s blížícím se koncem generovaných hradel do správného počtu se budeme blížit i zvolenému počtu přímo zapojených globálních výstupů. V této fázi dodržujeme stejná pravidla přidávání a odebírání hradel a spojů z pomocných polí $SP$ a $HR$.

Po dokončení této fáze nám stačí zapojit výstupy hradel z pole $HR$ na globální výstupy a zbylé nezapojené globální výstupy zapojit na nějaké větvení z pole $SP$.

Chci připomenout, že pokaždé při pokusu o rozvětvení spoje z pole $SP$, nejdříve kontrolujeme, jestli je možno připojit daný spoj na hradlo pomocí metody \verb|Thradlo::test_pripojeni_vstupu()|. Metoda kontroluje, aby na jedno hradlo nebyly připojeny 2 větve ze stejného spoje. Kdyby toto nastalo, logická fuknce hradla by se v mnoha případech degradovala.

Tím máme vygenerován triviální náhodný obvod, který splňuje požadované parametry.

Pokud se nějakým důvodem nepovede zapojit naponěkolikáté vygenerované hradlo, tak se celý obvod smaže a funkce vrátí hodnotu odlišnou od nuly. 

\section{Genetický algoritmus}

Ve zvolené implementaci obvodu není nutné nikterak kódovat jedince pro účely genetického algoritmu. Pro náš algortimus potřebujeme chromozóm s pevnou délkou, který by jistým způsobem popisoval celý obvod. Všechny generované obovdy mají stejný počet operačních hradel a každé je na svojí úrovni. Proto můžeme brát hradla jako geny a spojový seznam hradel jako chromozóm. Způsob jak se vypořádává algortimus se spoji je vysvětlen v části o křížení.
  
Na začátku genetického algoritmu, se připraví počáteční generace cyklickým voláním metody na vygenerování triviálního obvodu. 

\verb|Thlavni::nova_generace()|

Tato metoda implementuje všechny fáze genetického algoritmu mimo mutace.
Na začátku se vytvoří nová prázdná populace, a podle principu elitismu se do ní začnou kopírovat nejsilnější jedinci z generace předchozí. V našem případě je elitismus podle analýzy nastaven na $1$, tudíž se kopíruje $1$ jedinec. Dále jsou do nové populace vygenerováni noví trivialní jedinci, a to v počtu, který se rovná 8-mi procentům velikosti populace. Tu jsme zvolili jako turnaj z $n$. V našem případě je zvolena konstanta $2$. Větší konstantou bychom docílili většího selekčního tlaku genetického algoritmu, a tím bychom více směřovali k hledání maxim v okolí již známých řešení. Avšak v našem případě je stavový prostor problému velmi složitý a má jistě mnoho lokálních extrémů. Proto volíme spíše randomizovaný výběr. Je to vidět i na trošku volnější metodě křížení, která v sobě má také jistou náhodnost.

Když máme vybrané rodiče, tak dochází ke křížení. Poněvadž máme ve všech obvodech stejný počet hradel a každé hradlo je ve svoji úrovni obvodu, je velice vhodné křížit dva obvody jejich rozdělením za určitým hradlem. Problém může nastat jedině při dopojování spojů mezi hradly. Celý mechanizmus funguje asi takto:

Nejprve se náhodně vybere hraniční hradlo a to zhruba mezi 10-ti a 90-ti procenty obvodu --- aby bylo co napojovat. Nový obvod se vytvoří překopírováním 1. části hradel z 1. rodiče a zbylý počet hradel z 2. rodiče. Poté se zapojí hradla v první části podle 1. rodiče. Spoje které vedou do 2. části se nekopírují. Analogicky se to udělá s 2. částí obvodu. Zde se nebudou kopírovat spoje, které vedou z první části obvodu.

Nyní si algoritmus připraví 5 pomocných polí $hr1$ až $hr4$ a $sp\_pole$. Jejich význam je následující:
\benum
\item vede všechny volné výstupy operačních hradel v 1. části
\item vede všechny voné výstupy hradel větvení v 1. části
\item vede všechny volne vstupy operačních hradel v 2. části
\item vede všechny hradla větvení v 2. části, v poli je ma uloženy $n-1$ krát, kde $n$ je počet výstupů daného hradla
\item vede si všechny možné spoje k větvení v 1. části
\eenum

Algoritmus se teď pokouší dozapojit chybějící spoje pomocí těchto $4$ polí. Snaží se dosáhnout, aby byly všechny globální vstupy a výstupy zapojené, stejně jako aby zůstala pole $hr1$ a $hr3$ prázdná. Pokud algoritmu dojdou vstupy hradel v $hr3$ a globální výstupy, snaží se je nahradit zmenšením větvení v druhé části obvodu (pole $hr4$).
Pokud mu naopak dojdou v první části globální vstupy a výstupy hradel z pole $hr1$, snaží se tyto chybějící spoje zapojit již na původně obsazené výstupy větvících hradel z pole $hr2$. Dojdou-li i ty, snaží se větvit spoje z pole $sp\_pole$.
Pokud se mu podaří vyčerpat pole $hr1$ i $hr3$ máme všechno zapojené a stačí nám zmenšit všechna nezapojená větvení z pole $hr2$. V opačném případě mažeme celý obvod a přecházíme k tvorbě nového potomka rodičů.

Po úspěšném křížení je s 5-ti procentní pravděpodobností udělána mutace obvodu. Následně jsou potomkovi dopočítány všechny kvalitativní vlastnosti, včetně fitness funkce a je zařazen do nově vznikající populace. V tomto okamžiku je potomek připraven a dalším cyklem se tvoří další potomek s drobným rozdílem. Pokud rodiče byli vybrání v minulé iteraci, jsou vybráni znovu, ale opačně, takže dojde k opačnému křížení. Tvorba potomků pokračuje, dokud není zaplněna celá populace.

Nakonec se celá nová populace seřadí podle výsledku fitness funkce a stará populace se nahradí novou.\\[7mm]

\subsection{Mutace obvodu}

\label{impl.mutace}

\verb|Tobvod::proved_mutaci()|

Metoda je volána na správně zapojený obvod a provede náhodně jednu ze tří druhů mutací:
\bitem
\item zamění 1 hradlo za jiné generované podle platných pravděpodobností
\item vybere náhodný spoj, k němu najde náhodný vhodný jiný spoj a dojde k prohození zapojení konců mezi oběma spoji
\item náhodně vybere 1 větvení a přepojí jeho část spojů na jiné větvení 
\eitem.

Nejprve si pro všechny typy mutací připravíme 2 pomocná pole.
\bitem
\item pole všech spojů které se můžou větvit, seřazené podle úrovně počátku v obvodu. Pole $SP$
\item pole všech hradel větvení v obvodě. Pole $HR$
\eitem

Chci podotknout, že ve všech zde uvedených metodách kontroluji, při zapojování větvené spoje na libovolné hradlo, aby nedošlo k zapojení dvou různých větví stejného spoje.

{\bf Záměna hradla}

Algoritmus vybere jedno náhodné operační hradlo z celého obvodu, které bude měnit za jiné. Poté si pomocí pole $HR$ vypočítá, kolik musí mít nové hradlo minimálně a maximálně vstupů, aby šlo zapojit. Voláním metody \verb|obvod::vytvor_nove_hradlo()| se vytvoří hradlo, které splňuje podmínky na počet vstupů. Začnou se přepojovat spoje ze starého hradla na nové. S výtupem problém není, ten mají obě dvě hradla pouze jeden. U vstupů je situace jiná. Nejprve se přepojí všechny operační spoje\footnote{spoje co mají nastavenu vlastnost op. Neboli spoje co nevedou z větvení.}, pak i ostatní. V případě, že nové hradlo má ještě nějaké nezapojené vstupy, ty se vhodným větvením doplní. Pokud po úplném zapojení nového hradla zůstaly některé spoje na starém hradle, tak buď zmenšíme větvení ze kterého spoj vychází, nebo zmenšíme náhodné větvení na vyšší úrovni. Tím nám vznikne neobsazený vstup na hradle, kam již můžeme spoj ze starého hradla přepojit.

{\bf Překřížení dvou spojů}

Algoritmus vybere náhodně libovolný spoj z celého obvodu, poté náhodně vybírá jiný spoj se kterým by si vyměnil svůj koncový prvek. Postupně zkouší náhodný spoj a kontroluje (dle řady omezujících podmínek) jestli je možné si konce vyměnit:
\bitem
\item kontorla proti zpětné vazbě --- Začátky obou spojů musí být připojeny na nižší úroveň než menší úroveň obou konců
\item nesmí vzniknout spoj mezi hradly větvení, kontrolujeme vlastnosti op a fc spojů.
\item nesmí se přímo propojit globální vstup a výstup jedním spojem
\item pokud přepojujeme větvený spoj, tak ho nesmíme přepojit na hradlo, do kterého už vede jiná větev téhož spoje
\eitem

Pokud spoj všechny podmínky splní, tak si v pořádku mohou oba spoje vyměnit konce. V opačném případě se spoj vyřadí z výběru a zkusí se náhodně jiný. Kdyby nastala situace, že nenajdeme žádný vhodný spoj, tak výměna konců neproběhne.

{\bf Přesouvání některých větví}

Náhodně vybereme z pole $SP$ jedno větvení ze kterého budeme přesunovat větve jinam. Poté náhodně zvolíme počet větví, které budeme přepojovat. Na původním hradle nám musí zbýt alespoň jeden spoj. Začínáme s odpojováním zvolených spojů od větvení. Postupujeme postupně, spoj odpojíme od větvení, hradlo ihned zmenšíme, spoj odpojíme také od koncového hradla a smažeme ho. Zbývá nám zapojit nově vzniklý nezapojený vstup hradla rozvětvením vhodného Spoje, které máme seřazené v poli $SP$. Pokud se nám to nepodaří, vždy můžem zapojit zpátky na původní hradlo větvení. Takhle postupujeme se všemi zvolenými spoji k přesunu.

\subsection{Fitness funkce}
\label{imp:fitness}

Fitness funkce se počítá z několika složek, které zvolíme při startu algoritmu. Všechny složky jsou implmenentovány jako reálné číslo v intervalu $<0;1>$. Toto číslo reprezentuje jak moc obvod splňuje příslušné optimalizační kritérium a do výsledné fitness funkce je promítnuto přes svou váhu. Standartně jsou váhy pro aktivované složky nastaveny na $1.0$. Kritéria které jsme nevybrali, mají váhu nastavenou na $0$ a tím se do výsledku nepromítnou. Celý program umožňuje tyto váhy libovolně přenastavit a tím vlastně kvalitativně určit, která kritéria jsou pro nás jak moc důležitá. Program implementuje 5 různých kritérií optimalizace.
\benum
\item počet úrovní logicého obvodu. Tzn. počet hradel přes které vede nejdelší cesta z globálního vstupu na globální výstup.
\item správnost počtu všech typů generovaných hradel. Značí, že chceme co nejvíce dodržet zadané pravděpodobnosti generovaných hradel.
\item řiditelnost obvodu. Chceme optimalizovat obvod na požadovanou úroveň řiditelnosti
\item pozorovatelnost obvodu. Chceme optimalizovat obvod na požadovanou úroveň pozorovatelnosti
\item testovatelnost obvodu. Chceme optimalizovat obvod na požadovanou úroveň testovatelnosti
\eenum

Dále je do fitness funkce promítnuto malé zvýhodnění potomků, kteří přežili z dřívější populace. Je to z důvodu situace, kdy více generovaných různých potomků má stejné maximální ohodnocení použitých složek. Poněvadž používám k řazení potomků standartně implementovanou funkci \verb|qsort()|, která není stabilní\footnote{Nestabilní metoda řazení, nám nezaručí ve výsledku stejné pořadí prvků se shodným klíčem, jaké bylo před řazením}, tak by se s velkou pravděpodobností jedinci na začátku populace stále obměňovali. To nám vadí z důvodu, že konec genetického algoritmu je závislý na počtu generací, kdy je nejsilnější jedinec nezměněn.

Fitness funkce $fit$ konkrétního obvodu je tedy počítána podle vzorce, kde $n$ je počet složek, $f(i)$ je hodnota složky $i$, $w_i$ je váha složky $i$ a $s$ je stáří tohoto obvodu: $$fit = \sum_{i=1}^{n}{[w_i\times f(i)]} + 0.00001\times sig(s)$$

\paragraph{Výpočty jednotlivých složek}
\subparagraph{Úroveň --- }
Když $r$ je úroveň obvodu, $n$ je zadaná úroveň, tak složka fitness funkce $f$ se počítá:$$ f = \frac{1}{|n-u|+1}$$

\subparagraph{Počet hradel jednotlivých typů --- }
Složka fitness funkce $f$ je počítána podle vzorce, kde $N$ je počet typů hradel, $n_i$ je počet hradel v obvodě typu $i$, $P(i)$ je zadaná pravděpodobnost hradla typu $i$ v obvodu, $m$ je počet hradel v obvodě. $$ f = 1-\frac{4\times \sum_{i=1}^{N}[|m\times P(i)-n_i]}{2\times m} $$

\subparagraph{Testovatelnost --- }
Odpovídající část fitness funkce $f$, kde $t$ je vypočítaná testovatelnost z obvodu, $zt$ je zadaná testovatelnost. $$ f = 1 - |zt - t|$$

Obdobně se počítají i složky řiditelnosti a pozorovatelnosti.

\subsection{Ostatní parametry}

{\bf Velikost populace}

Další důležitý parametr genetického algoritmu, které jsme doposud nezmínili, je především velikost populace. Ta ovlivňuje rozmanitost a počet bodů ve stavovém prostoru ze kterých vycházíme. Vysokým nastavením této hodnoty zbytečně bez velkého přínosu zvýšíme časovou náročnost každé generace. Ovšem moc malé nastavení způsobí již zmiňovanou malou rozmanitost jedinců, tím zvyšujeme šanci na degeneraci populace a zvětšujeme šanci uvíznout v lokálních extrémech ohodnocující funkce. Ze zkušeností jsem počáteční hodnotu nastavil na $50$ jedinců. Avšak po přidání funkce nových náhodných jedinců v populaci a po experimentálním testování, jsem zvýšil standartní velikost populace na $80$. Toto testování je uvedene v další kapitole. Zároveň jsem doimplementoval možnost měnit velikost přímo z příkazové řádky.\\[7mm]

{\bf Pravděpodobnost mutace}

Podle \cite{PAA} je vhodné nastavit mutaci na pravděpodobnost někde kolem 5ti procent. To se mi i osvědčilo u jiných dříve řešených problémů. Přesto jsem udělal pár testů na malém počtu dat, kde se nepotvrdil nijak pozorovatelný vliv mutace na výsledcích algortimu. Pravděpodobně to bude tím, že již námi zvolený způsob křížení v sobě nese jistou náhodnou změnu obvodu.\\[7mm]

{\bf Ukončující kritérium}

V programu jsou implementována dvě odlišná ukončující kritéria. První je statické a program ukončí po projití pevně stanoveného počtu generací. Toto kritérium nemá standartní hodnotu a jestli jej chceme použít, musíme ji zvolit na příkazovém řádku.
Standartně je definováno druhé dynamické ukončující kritérium. To daný algoritmus a program ukončí, pokud se v posledních $n$ generacích nezměnil nejsilěnjší jedinec. Standartně je definováno na hodnotu 50.

\section{Testovatelnost}

Implementace výpočtu celkové testovatelnosti obvodu do generátoru byl klíčový. Kvůli tomuto požadavku jsme především zvolili celou metodu iterativních algoritmů pro generaci obvodu, abychom mohli zpětně ovlivňovat zapojení obvodu a tím testovatelnost přizpůsobovat požadavkům. 

Poněvadž je výpočet testovatelnosti v obvodu sám o sobě docela obtížný úkol, rozhodl jsem se použít již některou dříve vymyšlenou metodu bez úprav. Především byl problém ve zvolení správné testovatelnosti. Nároky byli zhruba tyto:
\bitem
\item schopnost počítat testovatelnost v krátkém čase s co nejmenší složitostí
\item postačuje nám kombinační testovatelnost
\item výsledek výpočtu testovatelnosti musíme být schopni rozumně převést na interval $<0;1>$
\eitem

Výběr z metod byl složitý. Nejvíce se mi líbila metoda SCOAP, avšak zde byl vážný problém s objektivním převodem celočíselných výsledků do intervalu $<0;1>$, což byla nutnost při námi navrženém způsobu výpočtu fitness funkce.  Přesto je tato metoda v kódu programu implementována, ale není používána.

Další zajímavá metoda byla metoda ing. Strnadela. Způsob jejího výpočtu byl založen na počítání všech cest v obvodu. Složitost jejího výpočtu je tedy závislá na velikosti obvodu a jeho větvení. Což neodpovídá našim požadavkům.

Proto jsem z metod vysvětlených v analýze, vybral podle požadavků metodu CAMELOT. Měl jsem však obavy, že metoda, která používá plošné koeficienty, nebude tak objektivní. Při větších obvodech nemusí podávat správné výsledky kvůli četnému větvení spojů, či redundaci celých částí obvodu. Tuto domněnku bylo potřeba v řádně otestovat.

Její implementace je v souladu s jejím popisem v kapitole~\ref{anal.CAMELOT}. Poněvadž jsou se u jednoduchých hradel podílejí všechny vstupy na zcitlivění cest stejným podílem, tak v implementaci jsou za funkce f(...) a g(...) zvoleny aritmetické průměry.

Algoritmus probíhá ve dvou průchodech. V prvním jdeme postupně od vstupů k výstupům přes hradla seřazená podle hloubky a počítáme řiditelnost. V druhém průchodu jdeme přes všechny hradla od výstupů a počítáme pozorovatelnost společně s testovatelností. Celková řiditelnost, pozorovatelnost a testovatelnost se pak výpočítají jako průměr ze všech spojů v obvodě.
