Zpracování reportu a prezentace

V reportu a prezentaci bychom především chtěli vidět smysluplné porovnání algoritmů. Hlavní hledisko pro porovnání je posouzení schopnosti algoritmu generovat body ze stavového prostoru v takovém pořadí, aby nacházel co nejlepší řešení co nejdříve, tedy po co nejmenším počtu předtím ohodnocených kandidátských řešení.

Ačkoli obsah reportu a prezentace by měl být tematicky skoro stejný, lišit by se u nich měly především rozsah a váha, které jednotlivým částem přiřadíte. Report by měl být detailnější, zatímco v prezentaci by měly být uvedeny jen hlavní výsledky a hlavní myšlenky algoritmu.

• Zadání (stručně)
• Popis zvolené reprezentace
• Popis fitness funkce (společné, i vaší vlastní, pokud jste ji použili)
• Popis algoritmů
  • Popis operátorů
    • Perturbační operátor u lokálního prohledávání
    • Operátory křížení a mutace u EA
    • Způsob hybridizace EA a lokálního prohledávače u memetického algoritmu
  • Hodnoty parametrů
  • Pseudokód???
• Smysluplné porovnání algoritmů:
  • Report:
    • Porovnejte především své tři algoritmy (např. lokální optimalizátor, klasický EA a memetický alg).
    • Chcete-li do porovnání zahrnout i výsledky některého svého kolegy, můžete, ale nezapomeňte jej citovat!
    • Tabulky a grafy se statistickým zhodnocením provedených experimentů na zadaných testovacích datech.
    • Grafy s průběhem mediánu nejlepší fitness v závislosti na počtu ohodnocení.
    • Grafy s průběhem mediánu nejlepší hodnoty jednotné ohodnocovací funkce v závislosti na počtu ohodnocení.
  • Prezentace:
    • Každý student ve skupině dodá do porovnání svůj “nejlepší” algoritmus.
    • Způsob porovnání stejný jako v reportu.
• Diskuse výsledků a zhodnocení

Velmi pravděpodobně na prezentaci 1 úlohy budete mít méně než 15 minut!

• Společná část: skupina studentů, řešící stejnou úlohu, vypracuje společně úvodní slajdy představující úlohu a závěrečné slajdy s prezentací výsledků a vzájemným porovnáním přístupů jednotlivých studentů.
• Individuální část: slajdy stručně a srozumitelně popisující zvolenou reprezentaci, operátory a ohodnocovací funkci algoritmů studenta.

Vytvořte vše jako 1 společnou prezentaci, nebo alespoň jednotlivé prezentace nakopírujte na jeden stroj - bude velmi málo času a nechtěli bychom se zdržovat prohazováním notebooků během prezentace. Individuální část každý student odprezentuje sám. Každá skupina si zvolí mluvčího, který bude mít tu čest prezentovat společné části.

Při porovnání výsledků algoritmů je třeba dbát na to, aby algoritmy měly stejné (nebo aspoň hodně podobné) podmínky. Pro většinu úloh stačí porovnávat dosažená řešení

• na stejných instancích úlohy a
• po stejném počtu ohodnocení účelové funkce.

Výjimkou je úloha komprese obrázků, kde je třeba také pro každý obrázek zafixovat povolenou velikost “footprintu” zakódovaného obrázku. (Na velikosti se dohodněte sami.) Pokud např. obrázek aproximujete pomocí průhledných trojúhelníků, k uložení informací o 1 trojúhelníku potřebujete

(3 vrcholy x 2 souřadnice x R bytů na reálné číslo) + S bytů na barvu trojúhelníka + T bytů na průhlednost (nebo váhu).

Aproximujete-li např. pomocí kruhů, potřebujte na 1 kruh

(1 střed x 2 souřadnice + 1 poloměr) x R bytů na reálné číslo + S bytů na barvu kruhu + T bytů na průhlednost (nebo váhu).

Po zvolení povolené velikosti “footprintu” tak můžete vypočítat, kolik trojúhelníků, kruhů, atd., byste měli ve své reprezentací použít.

To, co je pro nás na optimalizačním algoritmu nejdůležitější, je nejlepší dosažené řešení po jistém počtu ohodnocení účelové funkce (neboli za nějaký “čas”), tzv. best-so-far (BSF) řešení. (Už nás tolik nezajímá třeba průměrná kvalita jedinců v populaci.) Abychom si hodnotou BSF po jistém počtu ohodnocení mohli být alespoň trochu jistí, musíme provést N běhů algoritmu (desítky) na stejném problému. Tak pro všechny počty ohodnocení (pro každý “časový” okamžik) získáme 1 BSF řešení z každého z N běhů algoritmu. Z této sady hodnot je možné pro každou hodnotu počtu ohodnocení (pro každý “časový” okamžik) vypočítat statistiku polohy (průměr nebo medián) a statistiku rozsahu (směrodatná odchylka, mezikvartilové rozpětí, minimum-maximum).

Výsledky prezentujte v tabulkách či grafech. Uvádíte-li kvalitu dosaženého řešení, ujistěte se, aby vždy bylo zřejmé

• po kolika ohodnoceních byla tato kvalita dosažena,
• zda je kvalitou průměr, medián nebo nějaká jiná statistika měřená na opakovaných bězích algoritmu, a
• kolik běhů algoritmu bylo provedeno.

Kromě průměru či mediánu uvádějte také míru rozptylu hodnot: používejte dvojice

• průměr a směrodatná odchylka nebo
• medián a mezikvartilové rozpětí (inter-quartile range) nebo
• medián a minimum a maximum.

Místo strohé tabulky je mnohdy lepší použít obrázek:

• o krabicových grafech (40 years of box plots)
• pro zachycení rozdílů v dosažených řešeních po jistém počtu ohodnocení se hodí
  • funkce boxplot ze Statistics toolboxu MATLABu, nebo
  • funkce notBoxPlot dostupná na MATLAB File Exchange, nebo
  • funkce boxplot z balíku matplotlib pro Python, nebo
  • candlesticks z gnuplot, nebo
  • funkce boxplot v R, atd.
• pro zachycení rozdílů v dosažených řešeních v průběhu celého procesu optimalizace se hodí
  • funkce errorbar z MATLABu, nebo
  • funkce errorbar z balíku matplotlib pro Python, nebo
  • errorbars z gnuplot, nebo
  • funkce errorBarGraph v R, atd.