Heuristic Optimization Methods

Course Description

Introduction to optimization methods and heuristics. Algorithm and problem complexity. Categorization of heuristics and bounds. Exact methods (exhaustive search, dynamic programming). Constructive heuristics (greedy algorithms). Improvement heuristics (hill climbing, local search). Metaheuristics: 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 meta heuristics.

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

Study Programmes

University graduate
[FER3-HR] Audio Technologies and Electroacoustics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Communication and Space Technologies - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Computational Modelling in Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Computer Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Computer Science - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Control Systems and Robotics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Data Science - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electrical Power Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electric Machines, Drives and Automation - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electronic and Computer Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Electronics - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Information and Communication Engineering - profile
Elective Courses (1. semester) (3. semester)
[FER3-HR] Network Science - profile
Elective Courses (1. semester) (3. semester)
Elective Courses of the Profile (1. semester) (3. semester)
[FER3-HR] Software Engineering and Information Systems - profile
Elective Course of the profile (3. semester)
Elective Course of the Profile (1. semester)
Elective Courses (1. semester) (3. semester)
[FER2-HR] Computer Engineering - profile
Recommended elective courses (3. semester)
[FER2-HR] Computer Science - profile
Recommended elective courses (3. semester)
[FER2-HR] Information Processing - profile
Recommended elective courses (3. semester)
[FER2-HR] Software Engineering and Information Systems - profile
Recommended elective courses (3. semester)
[FER2-HR] Telecommunication and Informatics - profile
Recommended elective courses (3. semester)

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,

Laboratory exercises

For students

General

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

Grading System

85 Excellent
75 Very Good
65 Good
55 Sufficient