Search
[ English version ]
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 Pravidla samostatné práce.
Implementujte následující fitness funkce.
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$
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)$.
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.
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]$
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.
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.
Implementujte funkci pro převod binárního řetězce na vektor reálných čísel.
Implementujte algoritmus lokálního prohledávání pro binární reprezentaci.
Pokuste se váš algoritmus aplikovat na všechny výše uvedené účelové funkce.