Detail předmětu
Heuristika v logistických problémech
FSI-SHE-A Ak. rok: 2024/2025 Zimní semestr
Kurz je zaměřen na heuristické optimalizační metody jakožto nástroje pro řešení složitých problémů v situacích, kdy nelze použít klasické exaktní metody. Důraz je kladen nejen na pochopení rozdílů mezi exaktními algoritmy, aproximačními metodami a heuristickými algoritmy, ale také na způsob konkrétní programové realizace heuristických algoritmů. Zde je pozornost věnována nejen procedurální stránce, ale také návrhu vhodných datových struktur.
Jazyk výuky
angličtina
Počet kreditů
4
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Kurs předpokládá základní znalost algoritmizace a počítačovou gramotnost.
Pravidla hodnocení a ukončení předmětu
Zápočet: Účast na cvičeních + zpracování zadaných programů v C++ (celkem 2 programy). Zkouška: ústní, diskuse nad zpracovanými projekty s možnými doplňujícími otázkami. Klasifikace je plně v kompetenci vyučujícího podle platných směrnic VUT v Brně.
Přítomnost na přednáškách je doporučená, na cvičeních povinná. Výuka probíhá podle rozvrhu. Stanovení formy náhrady zameškaných cvičení je v kompetenci vyučujícícho.
Učební cíle
Hlavním cílem kursu je pochopení principu a filozofie heuristických algoritmů a jejich aplikace v řešení logistických problémů. Kromě toho je důraz věnován schpnosti efektivní objektové implementace heuristických algoritmů v objektově orientovaných programovacích jazycích, jako je C++ nebo C#.
Po absolvování kurzu budou studenti chápat rozdíly mezi exaktními, aproximačními a heuristickými algoritmy a budou schopni posoudit možnost jejich použití v konkrétních situacích. Budou znát základní klasifikaci metaheristik a typické algoritmy reprezentující jednotlivé kategorie. Absolventi budou schopni praktické implementace heuristických algoritmů v objektově orientovaných jazycích (C++, C#).
Použití předmětu ve studijních plánech
Program N-LAN-A: Logistics Analytics, magisterský navazující, povinný
Program C-AKR-P: Akreditované předměty v CŽV, celoživotní vzdělávání v akr. stud. programu
specializace CZS: Předměty zimního semestru, volitelný
Typ (způsob) výuky
Přednáška
13 hod., nepovinná
Osnova
1. Úvod, exaktní algorimy, aproximační algoritmy, heuristické algoritmy. Heuristika, metaheuristika.
2. Složitost úloh, časová náročnost hledání řešení.
3. Globální a lokální optimum.
4. Klasifikace metaheuristik – deterministické/stochastické, založené na jednom řešení/založené na populaci řešení, iterativní/hladové, ...
5. Prohledávání stavového prostoru – náhodné prohledávání, neinformované a informované metody
6. Aplikace heuristik pro kombinatorické problémy
7., 8. Heuristiky založené na lokálním prohledávání (simulované žíhání, tabu search)
9., 10. Heuristiky založené na populaci řešení (genetické algoritmy, scatter search)
11. Mravenčí kolonie, hejnové algoritmy
12., 13.: Efektivní implementace heuristických algoritmů
Cvičení
26 hod., povinná
Osnova
1. – 13.: Demonstrace látky z přednášek na reálných příkladech, implementace vybraných algoritmů pomocí OOP v jazycích C++ a/nebo C#.