Warning
This page is located in archive. Go to the latest version of this course pages.

Lokální prohledávání 2

Cílem tohoto cvičení je implementace algoritmu lokálního prohledávání pro vektory reálných čísel. 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. Pokud úkoly nestihnete na cvičení, dokončete je za domácí úkol!

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

Z minulého cvičení bychom měli mít implementované funkce $f_{Sphere}$ a $f_{Rosenbrock}$. Dnes je zkusíme optimalizovat s využitím přirozené reprezentace, vektorů reálných čísel. Implementujte i následující reálné funkce.

Opět 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).

Linear

Linear 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.) Napoví vám, jak se váš algoritmus bude chovat, pokud jej špatně inicializujete a populace nebude pokrývat optimum.

Minimalizujte $f_{Linear}(\mathbf{x}) = a_0 + \sum_{i=1}^D a_ix_i$.

Tuto funkci můžete používat bez omezení, pak ale nemá konečné optimum (což pro účely porovnání algoritmů nevadí). Pokud byste chtěli, aby tato funkce měla konečné optimum, je třeba omezit prostor přípustných řešení. Některé algoritmy se mohou chovat jinak, pokud zvolíte omezení v okolí počátku souřadnic, např. $\langle -1,1 \rangle$, nebo pokud zvolíte obor přípustých řešení mimo počátek souřadnic, např. $\langle 99, 101 \rangle$. Znaménka u koeficientů $a_i$ určují, ve kterém rohu funkce leží optimum. Pro první nástřel je možné volit $a_i=1$. Následně znaménka koeficientů volte náhodně.

Step

Step funkce je podobná funkci linear, ale má schodovitý charakter. Gradient v bodech, kde je definován, vám proto neposkytne žádnou informaci, kde hledat optimum.

Minimalizujte $f_{Step}(\mathbf{x}) = a_0 + \sum_{i=1}^{D} \lfloor a_ix_i \rfloor$.

Omezení a umístění optima - viz funkce linear s tím rozdílem, že množina globálních optim je tvořena celým jedním schůdkem.

Rastrigin

Rastrigin funkce je separovatelná a multimodální funkce (má více lokálních optim). Vypadá jako prohnuté plato na vajíčka.

Minimalizujte $f_{Rastrigin}(\mathbf{x}) = 10D + \sum_{i=1}^{D} \left[x_i^2 - 10\cos(2\pi x_i) \right]$.

K funkci je možné přistupovat jako k neomezené, inicializační rozsah se obvykle volí jako $\langle -5.12, 5.12 \rangle^D$. Můžete ale zkusit algoritmus inicializovat i v mnohem širším rozsahu, např. $\langle -100, 100\rangle^D$, a posoudit, zda to algoritmu spíše pomuže nebo spíše uškodí, a zkusit najit zdůvodnění.

Griewank

Griewank funkce je také multimodální funkce, podobně jako Rastrigin, ale má jich více a není separovatelná.

Minimalizujte $f_{Griewank}(\mathbf{x}) = 1 + \frac1{4000}\sum_{i=1}^{D} x_i^2 - \prod_{i=1}^D \cos\left(\frac{x_i}{\sqrt{i}}\right)$.

K funkci je možné přistupovat jako k neomezené, inicializační rozsah se obvykle volí jako $\langle -600, 600 \rangle^D$.

Schwefel

Schwefelova funkce je opět multimodální, avšak její lokální optima jsou tím blíže u sebe, čím dál jste od globálního optima. Má tedy jisté klamné rysy.

Minimalizujte $f_{Schwefel}(\mathbf{x}) = -\sum_{i=1}^{D} x_i\sin(\sqrt{\|x_i\|})$.

Funkce se obvykle optimalizuje v rozsahu $\langle -512.03, 511.97 \rangle^D$ a její minimální hodnota je cca -418.9829.

Perturbace, mutace

S normálním rozdělením

Implementujte operaci perturbace/mutace pro vektory reálných čísel. Operátor by měl vektor reálných čísel pozměněnit přičtením stejně velkého vektoru reálných čísel pocházejícího z normálního rozdělení $N(0, \sigma)$.

Parametr $\sigma$, směrodatná odchylka použitého normálního rozdělení.
Vstup Vektor reálných čísel.
Výstup Pozměněný vektor.

Podobně jako u binární reprezentace promyslete, zda budete přímo měnit datovou strukturu, která je vstupem operátoru, nebo zda budete vracet její pozměněnou kopii.

Libovolná jiná

Implementujte ještě alespoň jeden další operátor mutace pro vektory reálných čísel. Např.

  • využijte jiné rozdělení než normální:
    • rovnoměrné na hyperintervalu se středem v mutovaném bodě, parametrem bude rozměr hyperintervalu, nebo
    • Cauchyho rozdělení v každé souřadnici s parametrem $\gamma$, nebo
  • využijte vzor bodů v okolí mutovaného bodu, např.
    • výsledkem mutace může být vždy náhodně vybraný bod z $2D$ bodů ve vzdálenosti $\pm d$ od mutovaného bodu v každé z $D$ souřadnic, apod.

Lokální prohledávání

Aplikujte algoritmus lokálního prohledávání, který jste implementovali minulou hodinu, na výše uvedené funkce. Pokud jste algoritmus implementovali vhodným způsobem, nemělo by být nutné ho měnit, mělo by stačit vyměnit účelovou funkci, inicializační proceduru a operátor perturbace.

Lokální prohledávání a pravidlo 1/5

Patrně jste si již uvědomili, že lokální prohledávání s 'first-improving' strategií je vlastně (1+1)-ES. Vytvořte adaptivní verzi algoritmu lokálního prohledávání, která bude používat pravidlo 1/5 k adaptaci rozměrového parametru u operátoru mutace. Pravidlo 1/5 je popsáno v přednášce o reálných EA (slide 23-24).

Vizualizace

Pokuste se spustit simulace, nasbírat data a vytvořit grafy podobné těm ze slidu 22 přednášky o reálných EA, a to pro různé účelové funkce.

Na zvolené vizualizační knihovně nezáleží. Máte-li nějakou oblíbenou, použijte ji. Pokud vámi vybraný jazyk žádnou nedisponuje nebo ji neovládáte, doporučuji uložit data do souboru a ta vizualizovat v MATLABu, v Pythonu s využitím matplotlibu, nebo přinejhorším v Excelu/Google sheets.

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