NAIL119 Přírodou inpsirované algoritmy

Materiály

• Pilátovy skripta

• Materiály k Kaččiným cvikám

Poznámky

• Poznámky Kuby Smolíka - ručně psané

Zadání domácích úkolů 2022

1. Batoh

Za domácí úkol budete mít vyřešit pomocí evolučního algoritmu problém batohu. Ten spočívá v tom, že máme batoh kapacity K a N předmětů, každý s cenou $c_i$ a objemem $v_i$ a chceme vybrat takové věci, abychom maximalizovali zisk a zároveň abychom nepřekročili kapacitu batohu.

Vstupní data máte ve složce domaci_ukol_data. Obsahuje čtyři soubory s daty a dva s výsledky. Na první řádce souboru s daty je vždy počet předmětů a kapacita batohu oddělené mezerou, každý další následující řádek obsahuje cenu a objem předmětu taktéž oddělené mezerou. První dva soubory slouží pro snažší odladění evolučního algoritmu a obsahují i k sobě extra soubory s optimálním řešením. Na dalších dvou máte za úkol algoritmus pustit a výsledky na nich naměřené mi poslat.

Napište tedy nějaký svůj evoluční algoritmus, který bude řešit problém batohu a pusťte ho na vstupních datech. Svůj kód, popis evolučního algoritmu (zvolené evoluční operátory, kódování jedince, atd.) a rozbor výsledků, včetně nejlepšího dosaženého skóre i s jejich odůvodněním mi pošlete emailem do stanoveného deadline.

2. Klasifikace

Za domácí úkol budete mít vytvořit si vlastní libovolný dataset na image classfication task, abyste si vyzkoušeli, že vyrábět data není úplně snadné. Dataset by měl mít aspoň 5 různých tříd ke klasifikaci a ke každé nějaké rozumné desítky obrázků.

Až budete mít data, tak si na nich zkuste image classification task. Jak už jsem zmínila výše, trénovat celou konvoluční síť od začátku by bylo početně náročné, proto budete mít za úkol si vybrat 3 z už predtrénovaných modelů například odsud a přetrénovat je tak, aby uměly klasifikovat vámi vytvořená data.

Můžete si na vašich datech i zkusit natrénovat podobnou (klidně i stejnou) jednoduchou konvoluční síť, kterou jsme používali před na MNISTu výše a schválně se podívat, jak moc bude špatná oproti těm už předtrénovaným.

Své řešení mi pošlete emailem do stanoveného deadline. Řešení by mělo obsahovat:

1. slovní popis vašich dat (jaké máte labely, kolik každý obsahuje obrázků, velikost obrázků, zdůvodnění volby datasetu)

2. váš kód

3. slovní popis výsledků a porovnání modelů (jaké jste použili, jak byl který úspěšný (accuraccy všech modelů na testovací množině, sepsaná třeba v nějaké pěkné tabulce) a který byl nejlepší)

4. vámi vytvořený předzpracovaný dataset (obrázky by měly být malé, takže by neměl být problém s posláním)

Pár tipů:

• bylo by dobré mít u všech tříd stejný počet obrázků

• obrázky bude potřeba převést do nějakého jednotného rozumně malého rozměru (například 128 x 128 pixelů)

• když budete používat předtrénované sítě, tak ty vaše obrázky by měly být stejně velké jako ty, na kterých byla trénovaná ta síť původně

• zároveň bude potřeba je rozdělit na dvě disjunktní množiny -- trénovací a testovací (trénovací na přetrénovaní modelů a testovací na jejich vyhodnocení)

• model se dá přetrénovat například tak, že si nahradíte poslední nebo několik posledních vrstev vlastními, které budete přetrénovávat podle vašich dat

• pokud se vám model nedaří přetrénovat, aby dosahoval nějakých rozumných výsledků, zkuste použít nějakou augmentaci dat a trénovat na větších datech

VRP

Za domácí úkol budete mít vyřešit pomocí optimalizace mravenčí kolonií Vehicle Routing Problem, což je vlastně jen zobecněný problém obchodního cestujícího na princip optimalizace rozvozu zásilek doručovací společnosti. Jedná se o to, že máme depa, každé má svá vlastní vozidla s danou kapacitou a nějakou množinu zásilek, které je potřeba rozvézt k jejich majitelům. Cílem je najít množinu doručovacích tras tak, aby byly všechny zásilky dodány majitelům a aby byly minimalizované celkové náklady, tedy aby byl použit co nejmenší počet vozidel a aby byly trasy co nejkratší.

V našem případě použijeme zjednodušenou verzi tohoto problému s jedním depem, které má neomezený počet vozidel jednoho typu. Vstupní data najdete ve složce domaci_ukol_data, jsou ve formátu xml a obsahují 3 soubory -- 2 malé a jeden větší, které zároveň obsahují:

• Seznam uzlů se souřadnicemi x a y, kdy uzel s typem 0 je depo, a ty ostatní s typem 1 jsou lokace zákazníků.

• Seznam vozidel, v tomto případě máme jeden typ vozidla, které musí začínat a končit v depu a má nějakou maximální kapacitu předmětů, které uveze.

• Seznam požadavků, neboli do jakého uzlu se toho má co dovézt.

Svůj kód, popis řešení, výsledky a jejich rozbor mi pošlete emailem do stanoveného deadline.