Heuristic Algorithms

Course guarantor:

Jaromír Kukal

Lecturer:

Jaromír Kukal

Tutor:

Jaromír Kukal

Supervisor:

Department of Software Engineering

Synopsis:

Heuristic algorithms of optimization operates on discrete or continuous domains.

Brutal force, stochastic, greedy, physically, biologically and sociologically motivated heuristic are included, used for optimum finding and compared.

Requirements:

Basic knowledge of algebra, calculus and programming techniques.

Syllabus of lectures:

1 Sense, advantages and disadvantages of heuristic approach

2 Task complexity and time complexity of solution finding

3 Heuristics for objective function minimization

4 Global and local opima in discrete and continuous cases

5 Suboptimum solution and basin of attraction

6 Brutal force approaches: exhaustive search and random shooting

7 Naive approaches: greedy strategy and repeated local search

8 Simulated annealing with Gauss and Cauchy noise

9 Taboo approach with space or function constrains

10 Genetic model of optimization

11 Evolutionary search methods

12 Differential evolution

13 Particle Swarm Optimizarion

14 Efficiency and coparison of heuristics

Syllabus of tutorials:

1 Sense, advantages and disadvantages of heuristic approach

2 Task complexity and time complexity of solution finding

3 Heuristics for objective function minimization

4 Global and local opima in discrete and continuous cases

5 Suboptimum solution and basin of attraction

6 Brutal force approaches: exhaustive search and random shooting

7 Naive approaches: greedy strategy and repeated local search

8 Simulated annealing with Gauss and Cauchy noise

9 Taboo approach with space or function constrains

10 Genetic model of optimization

11 Evolutionary search methods

12 Differential evolution

13 Particle Swarm Optimizarion

14 Efficiency and coparison of heuristics

Study Objective:

Knowledge:

Demonstrate principles, properties, advantages and disadvantages of various heuristic approaches for the solving of real and difficult optimization tasks.

The efficiency of heuristics on given task can be measured, which is the right methodology for parameter tuning and comparison of heuristics.

Abilities:

Orientation in given subject and ability to solve real tasks.

Study materials:

Key references:

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

[2] Locatelli, M., Schoen, M. Global Optimization: Theory, Algorithms, and Applications, SIAM, Philadelphia, 2013.

Recommended references:

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

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

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

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

Note:

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Aplikované matematicko-stochastické metody (compulsory course in the program)
• Aplikace informatiky v přírodních vědách (compulsory course in the program)
• Matematické inženýrství (elective course)