Warning
This page is located in archive.

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.

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.

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.

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$

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)$.

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.

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]$

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

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.

courses/a0m33eoa/cviceni/tyden_02.txt · Last modified: 2018/11/04 17:50 by xposik