Heuristické algoritmy
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
18HA | ZK | 4 | 2P+2C | česky |
- Garant předmětu:
- Jaromír Kukal
- Přednášející:
- Jaromír Kukal
- Cvičící:
- Jaromír Kukal
- 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 2024/2025:
- Rozvrh není připraven
- Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Aplikované matematicko-stochastické metody (povinný předmět programu)
- Aplikace informatiky v přírodních vědách (povinný předmět programu)
- Matematické inženýrství (volitelný předmět)