====== Lokální prohledávání 1 ======

Cílem tohoto cvičení je implementace jednoduchého algoritmu lokálního prohledávání, nejprve pro binární reprezentaci, později i pro jiné reprezentace. Tento algoritmus bude sloužit jako jeden z algoritmů v porovnáních, zároveň jeho části využitelné i v evolučních algoritmech.

<WRAP center round important 100%>
Rozhodli jsme se neomezovat vás v programovacím jazyku, který si zvolíte pro implementaci. Pokud ale budete chtít od učitelů pomoci, vězte, že Pošík a Kubalík jsou schopni pomoci v jazycích Python, Java, C, v ostatních si budete muset poradit převážně sami.
</WRAP>


<WRAP center round tip 100%>
**Níže uvedené úkoly jsou určeny k tomu, abyste jejich řešení sami implementovali.** Ačkoli v mnoha jazycích existují knihovny pro EA, z výukových důvodů zde požadujeme vaše vlastní řešení. Pročtěte si [[help:common:plagiaty_opisovani|Pravidla samostatné práce]].
</WRAP>


===== Fitness funkce =====
Implementujte následující fitness funkce.

==== Binární ====
Pro binární reprezentaci předpokládáme, že $x_i$ označuje $i$-tý bit chromozomu, $D$ je délka chromozomu (pokud není uvedeno jinak).

** OneMax **

//OneMax// je základní, snadno optimalizovatelná funkce, slouží spíše jako sanity check vašeho algoritmu. (Pokud váš algoritmus funguje špatně na této funkci, patrně nebude fungovat ani na jiných.)

$f_{OneMax}(\mathbf{x}) = \sum_{i=1}^D x_i$

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:onemax.txt |Testová data}}
</WRAP>



** LABS **

LABS (Low-Autocorrelation binary sequence) je naopak velmi obtížný binární problém. Předpokládejme sekvenci $S=(s_1,\dots,s_D)$, kde $s_i=\pm 1$. Autokorelace sekvence $S$ jsou definovány jako

$C_k(S) = \sum_{i=1}^{D-k}s_is_{i+k}$.

"Energie" sekvence $S$, kterou je třeba minimalizovat, je definována jako

$f_{LABS}(S) = E(S) = \sum_{k=1}^{D-1}C_k^2(S)$.

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:labs.txt |Testová data}}
</WRAP>

==== Pro vektory reálných čísel ====

Pro reálnou reprezentaci předpokládáme, že $x_i$ označuje $i$-tý prvek vektoru reálných čísel, $D$ je délka chromozomu (pokud není uvedeno jinak).

** Sphere **

//Sphere// je základní, snadno optimalizovatelná funkce reálných argumentů, slouží spíše jako sanity check vašeho algoritmu. (Pokud váš algoritmus funguje špatně na této funkci, patrně nebude fungovat ani na jiných.)

$f_{Sphere}(\mathbf{x}) = \sum_{i=1}^D (x_i-o_i)^2$,

kde $\mathbf{o}=(o_1,\dots,o_D)$ je vektor souřadnic minima funkce.

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:sphere.txt |Testová data}}
</WRAP>


** Rosenbrock **

//Rosebrockova// funkce je opět obtížnější:

$f_{Rosenbrock}(\mathbf{x}) = \sum_{i=1}^{D-1} \left[ 100(x_{i+1}-x_i^2)^2 + (1-x_i)^2 \right]$

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:rosenbrock.txt |Testová data}}
</WRAP>



===== Perturbace =====
Implementujte operaci perturbace pro binární reprezentaci. Operátor by se měl pro každý bit nezávisle rozhodovat, zda jej invertuje nebo ne. Je tedy možné, že dojde k inverzi více než 1 bitu při jediné operaci perturbace.
^ Parametr | Pravděpodobnost inverze bitu |
^ Vstup | Binární chromozom |
^ Výstup | Pozměněný binární chromozom |
Promyslete si a rozhodněte se, zda budete přímo měnit datovou strukturu, která je vstupem operátoru, nebo zda budete vracet její pozměněnou kopii.

===== Mapování bin->real =====
Implementujte funkci pro převod binárního řetězce na vektor reálných čísel.
^ Parametr | Dolní a horní mez všech souřadnic v reálném prostoru |
^ Vstup | Binární řetězec |
^ Výstup | Vektor reálných čísel |

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:bin2real.zip |Testová data}}
</WRAP>

===== Lokální prohledávání =====
Implementujte algoritmus lokálního prohledávání pro binární reprezentaci. 
^ Parametr | Účelová funkce, kterou chcete optimalizovat |
^ Parametr | Perturbační operátor, který chcete použít |
^ Parametr | Ukončovací podmínky |
^ Vstup | Počáteční řešení (bin. vektor) |
^ Výstup | Výsledek optimalizace (bin. vektor) |
^ Výstup | Statistiky o optimalizaci |

Pokuste se váš algoritmus aplikovat na všechny výše uvedené účelové funkce.