Popis predmeta

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.

Independent assignments

Students are assigned 2 homework 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
Homeworks 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
Audio Technologies and Electroacoustics (profile)
Free Elective Courses (1. semester) (3. semester)
Communication and Space Technologies (profile)
Free Elective Courses (1. semester) (3. semester)
Computational Modelling in Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Science (profile)
Free Elective Courses (1. semester) (3. semester)
Control Systems and Robotics (profile)
Free Elective Courses (1. semester) (3. semester)
Data Science (profile)
Free Elective Courses (1. semester) (3. semester)
Electrical Power Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (1. semester) (3. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electronics (profile)
Free Elective Courses (1. semester) (3. semester)
Information and Communication Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Network Science (profile)
Elective Courses of the Profile (1. semester) (3. semester)
Software Engineering and Information Systems (profile)
Elective Course of the profile (3. semester) Elective Course of the Profile (1. 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,

For students

General

ID 222531
  Winter semester
5 ECTS
L3 English Level
L1 e-Learning
30 Lectures
5 Seminar

Grading System

85 Excellent
75 Very Good
65 Good
55 Acceptable

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.

Independent assignments

Students are assigned 2 homework 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
Homeworks 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
Audio Technologies and Electroacoustics (profile)
Free Elective Courses (1. semester) (3. semester)
Communication and Space Technologies (profile)
Free Elective Courses (1. semester) (3. semester)
Computational Modelling in Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Computer Science (profile)
Free Elective Courses (1. semester) (3. semester)
Control Systems and Robotics (profile)
Free Elective Courses (1. semester) (3. semester)
Data Science (profile)
Free Elective Courses (1. semester) (3. semester)
Electrical Power Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (1. semester) (3. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Electronics (profile)
Free Elective Courses (1. semester) (3. semester)
Information and Communication Engineering (profile)
Free Elective Courses (1. semester) (3. semester)
Network Science (profile)
Elective Courses of the Profile (1. semester) (3. semester)
Software Engineering and Information Systems (profile)
Elective Course of the profile (3. semester) Elective Course of the Profile (1. 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,

For students

General

ID 222531
  Winter semester
5 ECTS
L3 English Level
L1 e-Learning
30 Lectures
5 Seminar

Grading System

85 Excellent
75 Very Good
65 Good
55 Acceptable