Heuristic Optimization Methods

Data is displayed for academic year: 2023./2024.

Laboratory exercises

Course Description

Introduction to optimization methods and heuristics. Algorithm and problem complexity. Categorization of heuristics and bounds. Exact methods. Constructive heuristics (greedy algorithms). Improvement heuristics (hill climbing, local search). Metaheuristics: Iterative Local Search, Variable Neighborhood Search, Large Neighborhood Search, Simulated Annealing, Tabu Search, Evolutionary strategies, Ant Colony optimization, GRASP, PSO. Survey of additional heuristic techniques. Case studies on real world problems applying constructive, hybrid and metaheuristics.

Study Programmes

University graduate
[FER3-EN] Control Systems and Robotics - profile
Elective course (3. semester)
Elective courses (1. semester)
[FER3-EN] Data Science - profile
Elective courses (1. semester)
Recommended elective courses (3. semester)
[FER3-EN] Electrical Power Engineering - profile
Elective courses (1. semester) (3. semester)

Learning Outcomes

  1. explain the basic underlying principles of heuristic search as an optimization method to solve complex problems
  2. calculate problem complexity and algorithm complexity
  3. distinguish between exact methods and heuristic methods, and when to apply which methods
  4. identify the need for heuristics
  5. explain the methodology of the most commonly used heuristics (Greedy, Simmulated Annealing, Tabu Search, Evolutionary algorithms, Ant Colony optimization, PSO)
  6. explain the advantages and disadvantages of various heuristic methods
  7. develop new (hybrid) heuristic methods by applying existing heuristic methods
  8. evaluate the quality of the solutions obtained with heuristic methods

Forms of Teaching

Lectures

Lectures are held in two cycles. The first cycle contains 7 weeks of lectures followed by the second cycle lasting 6 weeks, with a teaching load of 2 hours per week.

Laboratory

Students are assigned 2 laboratory assignments in which they will independently design, implement and test heuristic algorithms for solving given combinatorial optimization problems.

Other

Project: design, implementation and testing of heuristic algorithms for solving a given combinatorial optimization problem.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Laboratory Exercises 25 % 25 % 25 % 25 %
Seminar/Project 50 % 25 % 50 % 25 %
Mid Term Exam: Written 0 % 25 % 0 %
Final Exam: Written 0 % 25 %
Exam: Written 0 % 50 %

Week by Week Schedule

  1. Introduction to optimization; optimization models, combinatorial optimization.
  2. Complexity theory; categorization of optimization methods; why and when to use heuristics.
  3. Exact methods: integer programming, branch and bound, dynamic programming.
  4. Greedy algorithms. Basic concepts of metaheuristics.
  5. Local search. Greedy randomized adaptive search procedure (GRASP).
  6. Variable neighborhood search. Large neighborhood search.
  7. Tabu search.
  8. Midterm exam
  9. Simulated annealing.
  10. Ant colony optimization.
  11. Particle swarm optimization. Project assignment.
  12. Evolutionary algorithms.
  13. Case studies involving hybrid and meta heuristics.
  14. Project presentations.
  15. Final exam

Literature

(.), Handbook of Metaheuristics (International Series in Operations Research & Management Science, Band 272),
(.), Metaheuristics: From Design to Implementation,
(.), How to Solve it: Modern Heuristics, 2nd Edition,

For students

General

ID 222973
  Winter semester
5 ECTS
L3 English Level
L1 e-Learning
30 Lectures
5 Seminar
0 Exercises
12 Laboratory exercises
0 Project laboratory
0 Physical education excercises

Grading System

85 Excellent
75 Very Good
65 Good
55 Sufficient