Optimalizace velkých problémů: metaheuristiky - NOPT061

• Anglický název: Large-scale optimization: Metaheuristics
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Další informace: https://jbulin.github.io/teaching/spring/nopt061/
• Garant: RNDr. Jakub Bulín, Ph.D.; RNDr. Jiří Fink, Ph.D.; Mgr. Marika Ivanová, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika, Optimalizace

Anotace

čeština

Přednáška heuristických optimalizačních algoritmů založených na kombinaci kombinatorické optimalizace a umělé inteligence s aplikacemi na praktické problémy.

Poslední úprava: Hric Jan, RNDr. (12.05.2022)

angličtina

Lecture on heuristic optimization algorithms based on Convex Optimization and Artificial Intelligence for solving real-life problems.

Poslední úprava: Hric Jan, RNDr. (12.05.2022)

Cíl předmětu

čeština

Cílem předmětu je porozumění principům různých heuristických optimalizačních metod založených na kombinaci kombinatorické optimalizace a umělé inteligence, použitelných na velké instance pocházejících z praxe. (Předmět je vhodný pro studenty 3. ročníku bakalářského studia, a pro magisterské studenty.)

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (06.05.2024)

angličtina

Understand the main principles of various heuristic optimization methods based on convex optimization and artificial intelligence, with emphasis on large-scale instances. Learn how to apply these methods in practice. (The course is suitable for 3rd-year bachelor's students and for master's students.)

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (06.05.2024)

Podmínky zakončení předmětu

čeština

Studenti musí implementovat praktické domácí úkoly a splnit teoretickou zkoušku. Povaha domácích úkolů vylučujeme možnost opakování zápočtu.

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (13.05.2022)

angličtina

Students are expected to implement practical homework assignments and pass theoretical examination. The nature of homework assignments excludes the possibility of repeated attempts to get credit.

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (13.05.2022)

Literatura

čeština

Wolsey, Laurence A. Integer programming. Vol. 42. New York: Wiley, 1998.

Kochenderfer, Mykel J., and Tim A. Wheeler. Algorithms for optimization. MIT Press, 2019.

Blum, Christian, and Günther R. Raidl. Hybrid Metaheuristics: Powerful Tools for Optimization. Springer, 2016.

Desaulniers, Guy, Jacques Desrosiers, and Marius M. Solomon, eds. Column generation. Vol. 5. Springer Science & Business Media, 2006.

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (13.05.2022)

Sylabus

čeština

• Lokální prohledávání, Hill climbing, simulované žíhání

• Populační metody, např. Genetické algoritmy

• Řešení úloh pomocí redukce velikosti instance

• Hybridní metody: Lamarckian vs. Baldwinian, příklady

• Náhradní modely

• Aplikace, např. v oblastech logistiky a plánování

Výuka tohoto předmětu probíhá jednou za dva roky a střídá se s předmětem Optimalizace velkých problémů: přesné metody (NOPT059).

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (13.05.2022)

angličtina

• Local search, Hill climbing, Simulated annealing

• Population methods, e.g. Genetic algorithms

• Problem instance reduction, Large neighborhood search

• Hybrid methods: Lamarckian vs. Baldwinian learning, examples

• Surrogate models

• Applications, e.g. Minimum Common String Partition, Minimum Weight Dominating Set Problem, Arc Routing Problems, Public Transportation

The course is taught bi-yearly, alternating with the course Large-scale optimization: Exact methods (NOPT059).

Poslední úprava: Bulín Jakub, RNDr., Ph.D. (13.05.2022)