Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023

Heuristické algoritmy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
18HEUR KZ 4 2+2 česky
Přednášející:
Jaromír Kukal, Matej Mojzeš
Cvičící:
Jaromír Kukal, Matej Mojzeš
Předmět zajišťuje:
katedra softwarového inženýrství
Anotace:

Heuristické optimalizační algoritmy pracují na diskrétním nebo spojitém definičním oboru. Jsou zahrnuty heuristiky založené na hrubé síle, náhodě, chamtivosti či fyzikální, biologické nebo sociologické motivaci. Jsou využity ke hledání optima a jsou vzájemně porovnány.

Požadavky:

Základní znalosti algebry, analýzy a programovacích technik.

Osnova přednášek:

1. Smysl, výhody a nevýhody heuristického přístupu

2. Složitost úloh a časová náročnost hledání řešení

3. Heuristiky pro minimalizaci účelové funkce

4. Globální a lokální optimum v diskrétním a spojitém případě

5. Suboptimální řešení a oblast přitažlivosti

6. Použití hrubé síly: systematické prohledávání a náhodná střelba

7. Naivní přístupy: chamtivá strategie a opakované lokální hledání

8. Simulované žíhání s Gaussovým a Cauchyovým šumem

9. Tabu přístup s prostorovým nebo funkčním omezením

10. Genetický model optimalizace

11. Metody evolučního hledání

12. Diferenciální evoluce

13. PSO - optimalizace modelováním hejna částic

14. Efektivita a porovnávání heuristik

Osnova cvičení:

1. Smysl, výhody a nevýhody heuristického přístupu

2. Složitost úloh a časová náročnost hledání řešení

3. Heuristiky pro minimalizaci účelové funkce

4. Globální a lokální optimum v diskrétním a spojitém případě

5. Suboptimální řešení a oblast přitažlivosti

6. Použití hrubé síly: systematické prohledávání a náhodná střelba

7. Naivní přístupy: chamtivá strategie a opakované lokální hledání

8. Simulované žíhání s Gaussovým a Cauchyovým šumem

9. Tabu přístup s prostorovým nebo funkčním omezením

10. Genetický model optimalizace

11. Metody evolučního hledání

12. Diferenciální evoluce

13. PSO - optimalizace modelováním hejna částic

14. Efektivita a porovnávání heuristik

Cíle studia:

Znalosti:

Demonstrovat principy, vlastnosti, výhody a nevýhody různých heuristických přístupů k řešení reálných a obtížných optimalizačních úloh. Efektivita heuristik na dané úloze může být měřena, což je korektní metodika pro nastavování parametrů heuristik a jejich porovnávání.

Schopnosti:

Orientace v dané problematice a schopnost řešení reálných úloh.

Studijní materiály:

Povinná literatura:

[1] Martí, R., Pardalos, P. M., Resende, M. G. C. Handbook of Heuristics. Cham (Switzerland): Springer, 2018.

[2] Locatelli, M., Schoen, F. Global Optimization: Theory, Algorithms, and Applications. Philadelphia: Society for

Industrial and Applied Mathematics, 2013.

Doporučená literatura:

[3] Kvasnička V., Pospíchal J., Tiňo P. Evolučné algoritmy. Bratislava: STU, 2000.

[4] Edelkamp, S., Schroedl, S. Heuristic Search: Theory and Applications. Waltham: Morgan Kaufmann, 2011.

[5] Yang, X-S. Nature-Inspired Metaheuristic Algorithms. 2nd edition. Cambridge: Luniver Press, 2010.

[6] Lee K. Y., Sharkawi M. A. Modern Heuristic Optimization Techniques, New York: Wiley, 2008.

[7] Horst R., Pardalos P. M. Handbook of Global Optimization., Springer, 1994.

Poznámka:
Rozvrh na zimní semestr 2022/2023:
Rozvrh není připraven
Rozvrh na letní semestr 2022/2023:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 2. 2. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet24706505.html