[ [[courses:a0m33eoa:en:labs:week_02|English version]] ]
====== 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 budou využitelné i v evolučních algoritmech.
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, Julia, Java, C, v ostatních si budete muset poradit převážně sami.
**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]].
===== 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$
{{ :courses:a0m33eoa:cviceni:onemax.txt |Testová data}}
** 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$ (takže budete muset před ohodnocením nahradit všechny 0 číslem -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)$.
{{ :courses:a0m33eoa:cviceni:labs.txt |Testová data}}
==== 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.
{{ :courses:a0m33eoa:cviceni:sphere.txt |Testová data}}
** 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]$
{{ :courses:a0m33eoa:cviceni:rosenbrock.txt |Testová data}}
===== 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 |
{{ :courses:a0m33eoa:cviceni:bin2real.zip |Testová data}}
===== 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.