Detail předmětu

Heuristika v logistických problémech

FSI-SHE-AAk. rok: 2024/2025

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ů

Garant předmětu

doc. Ing. Jan Roupec, Ph.D.

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

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#).

Základní literatura

Arun, J. A., Kavitha, S., Muruganantham, P.: Object Oriented Programming in C++. Notion Press, 2022. ISBN: 979-8886290639. (EN)
Kumar, A., Pant, S., Ram, M.: Meta-heuristic Optimization Techniques. De Gruyter, Berlin, 2022. ISBN 3110716178. (EN)
Lee, K. Y., El-Sharkawi M., A.: Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems.   ‎ Wiley-IEEE Press, 2008. ISBN ‎ 0471457116 (EN)

Doporučená literatura

J. A., Kavitha, S., Muruganantham, P.: Object Oriented Programming in C++. Notion Press, 2022. EAN 9798886290639. (EN)
A., Pant, S., Ram, M.: Meta-heuristic Optimization Techniques. De Gruyter, Berlin, 2022. ISBN 3110716178. (EN)
Reeves, C. R.: Modern Heuristic Techniques for Combinatorial Problems. Wiley, 1993,. ISBN 978-0470220795. (EN)

Zařazení předmětu ve studijních plánech

  • Program N-LAN-A magisterský navazující 1 ročník, zimní semestr, povinný

  • Program C-AKR-P celoživotní vzdělávání v akr. stud. programu

    specializace CZS , 1 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

13 hod., nepovinná

Vyučující / Lektor

doc. Ing. Jan Roupec, Ph.D.

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á

Vyučující / Lektor

doc. Ing. Jan Roupec, Ph.D.

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#.