Semestrální práce

Vaším úkolem v této semestrální práci bude vybrat si či navrhnout vlastní optimalizační algoritmus pro black-box minimalizaci reálných funkcí. Odevzdávat budete

1. implementaci třídy vašeho optimalizátoru v Javě schopného pracovat v testovacím frameworku a
2. krátký report ve formě vědeckého článku, v němž popíšete, jak váš optimalizátor funguje.

Za tuto úlohu lze získat až 30 bodů:

• 15 b. za kvalitu odevzdaného reportu a
• 15 b. za efektivitu odevzdaného optimalizátoru danou umístěním v turnaji všech vašich optimalizátorů.

Šablony používají 2-sloupcový formát a poměrně malá písma, na celý report by vám měly stačit 1-2 strany. Na reportu budu hodnotit následující:

• (2 b.) Abstrakt. Měla by to být v podstatě reklama na váš report, proč by si čtenář měl váš report přečíst, čím ho váš report obohatí.
• (1 b.) Úvod do problematiky numerické black-box optimalizace, čím je důležitá, čím se vyznačuje. Jaké jiné metody, kromě té vaší se používají. Může být poměrně stručný.
• (4 b.) Popis principu vašeho algoritmu. Stručný, ale úplný popis principu vašeho algoritmu. Kritérium pro hodnocení bude především reprodukovatelnost, tj. čtenář by měl být schopný podle tohoto popisu sám váš algoritmus implementovat.
• (2 b.) Výsledky. Ukázka výsledků, porovnání s jinými algoritmy. Dosahuje-li váš algoritmus výjimečně dobrých (nebo naopak překvapivě špatných) výsledků na nějakém problému, ukažte to a diskutujte možné příčiny.
• (3 b.) Zhodnocení a závěr. Pokuste se objektivně zhodnotit výhody a nevýhody vašeho algoritmu (úspěšnost, rychlost, vhodnost pro jistý typ funkcí, atd.)
• Další body lze získat za použití LaTeXu (1 b.), za vypracování v angličtině (1 b.), za použití literatury, tj. za korektní citace v textech a uvedení v seznamu literatury na konci reportu (1 b.)

V archivu najdete 2 adresáře:

• AUIProject - zdrojové kódy testovacího frameworku v Javě a
• matlab - sada MATLABských skriptů a funkcí pro vizualizaci a porovnání běhů jednotlivých optimalizátorů na testovacích problémech.

K vypracování reportu použijte jednu z šablon (pro Word a LaTeX).

V archivu najdete kompletní projekt v Netbeans. Tento projekt obsahuje jedinou třídu s metodou main - třídu TestRunner. Tato třída v zásadě definuje, jaké optimalizátory a jaké testovací problémy se mají použít, vytváří instance jednotlivých optimalizátorů a aplikuje je postupně na všechny testovací problémy. Pro každou kombinaci algoritmus-problém vytvoří jeden soubor se statistikami (přípona .sts), které se dále zpracovávají v MATLABu.

Po dokončení běhu testovacího frameworku si můžete výsledky prohlédnout. Zkopírujte všechny .sts soubory z adresáře projektu Netbeans do adresáře se soubory MATLABu a spusťte skript scrCompareAlgorithms.m. Tento skript uspořádá turnaj všech algoritmů způsobem každý s každým. Jinými slovy, pro každou dvojici algoritmů spočítá na kolika problémech byl lepší první algoritmus a na kolika druhý. Vytvoří tzv. performance matrix, PM, takovou, že prvek PM(i,j) udává, na kolika problémech byl i-tý algoritmus lepší než j-tý. K rozhodnutí, zda jsou výsledky jednoho algoritmu lepší než druhého, se používá neparametrický Wilcoxon-Mann-Whitneyho U test, jak je implementován ve funkci ranksum v MATLABu.

Z hodnot v PM se vypočte celkové skóre algoritmu jako počet problémů, na nichž jiné algoritmy porazil, mínus počet problémů, na nichž byl jinými algoritmy poražen (tj. řádkový součet PM mínus sloupcový součet PM). Na základě tohoto skóre se vypočte pořadí algoritmů.

Skript následně spustí GUI tzv. ResultBrowseru, v němž můžete jednotlivé dvojice algoritmů na jednotlivých problémech vizuálně porovnávat.

Vaším úkolem je naimplementovat (a následně odevzdat) třídu, která bude dědit od abstraktní třídy auiproject.AbstractOptAlgInstance. Minimálně musíte definovat její 3 metody:

• initialize() - slouží k inicializaci struktur vašeho optimalizátoru,
• finish() - úklid (pokud je třeba) po skončení jednoho optimalizačního běhu, a
• step() - hlavní tělo optimalizátoru. Tato metoda bude volána testovacím frameworkem opakovaně během 1 běhu vašeho algoritmu. Jedná se o jeden krok algoritmu, metoda by neměla obsahovat iterační (generační) smyčku, opakované volání této metody za vás obstará testovací framework!

Svou třídu (např. MySuperTrooperSolver) umístěte do balíku auiproject.alg. Aby o ní testovací framework věděl, musíte její plně kvalifikované jméno (auiproject.alg.MySuperTrooperSolver) přidat v metodě main() třídy TestRunner do seznamu solvers.

Další detaily o implementaci frameworku najdete přímo ve zdrojových kódech jako javadoc.