Nesystematické prohledávání stavového prostoru
Úloha 1: Robotické skladiště V.
V této části se z plánování trasy pro roboty přesuneme na plánování rozložení zboží. Pro první prodejnu obtimalizujeme pouze 7 regálů na středu.
- Z předchozího prodeje máte pro malý i velký sklad seznam výrobků s pravděpodomnosmi, že si je zákazníci vyberou (a robot pro ně bude muset zajet). Pomocí algoritmu hill-climbingu optimalizujte rozložení výrobků ve skladu (pro zjednodušení bude každý výrobek zabírat plochu regálu o velikosti jednoho zastavení robota z jedné strany regálu).
- Vyberte náhodně 100 výrobků podle daných pravděpodobností (výběr s opakováním) a porovnejte ujetou vzdálenost před optimalizací a po optimalizaci.
Úloha 2: MAX-SAT
MAX-SAT je problém nalezení takového ohodnocení proměnných, aby celkový počet splněných klauzulí v Booleovské formuli v konjunktivní normální formě (CNF) byl co největší.
- Použijte tabu prohledávání prostoru ohodnocení proměnných a získejte co nejlepší řešení. Při testování svého algoritmu můžete použít veřejné datasety (stáhněte si variantu complete-unweighted).
- Jak byste do problému MAX-SAT převedli např. problém vytvoření rozvrhu, kdy o úterní cvičení od 14:30 do 16:00 v místnosti 349 stojí předměty A, B, C? Jak byste přidali další předměty, místnosti?
Úloha 3: Doručení balíčku V.
Dostali jste úkol naplánovat trasu pro dodávku plnou balíků, která má objet 6 měst (Praha, Brno, Ostrava, Plzeň, Liberec, České Budějovice) a vrátit se do Prahy, odkud také vyjede. Vzdálenosti mezi městy máte uvedené v datovém souboru.
- Vymyslete vhodné kódování problému
- Použijte simulované žíhání k optimalizaci délky trasy.
- Vytvořte graf závislosti klesající teploty na celkové délce trasy.
Úloha 4: Hra 2048 V.
Věčným snem (a noční můrou) programátorů je automatizace programování. Dnes se tomu s příchodem LLM (anglická zkratka pro velké jazykové modely) možná blížíme trochu víc, ale zde si zkusíme postup o něco starší (cca z roku 1990) – genetické programování.
- Pomocí algoritmu genetického programování vyšlechtěte řídící funkci pro hru 2048, která bude pro každé rozložení čísel vracet celé číslo 0 až 3 (směr tahu).
- Vyberte operátory pro tuto funkci (např. ternární, less_than apod.).
- Vyberte operátory křížení a mutace (např. prohození podstromu u křížení, nahrazení podstromu u mutace)
- Implementujte algoritmus a fitness funkci (inspirujte se např. počítáním skóre v základní hře 2048)
Úloha 5: CNC vrtačka V.
- Pomocí genetického algoritmu hledejte co nejlepší řešení Hamiltonovské cesty
- Jako prvotní řešení volte náhodnou permutaci.
- Jak spojit dvě řešení při křížení?
- Jak upravit řešení při mutaci?
- Vytvořte graf vývoje nejlepšího řešení v závislosti na číslu generace
- Jak ovlivňuje velikost populace kvalitu řešení?