Heuristic Optimization Methods

Course Description

Complexity. Categorization of heuristics and bounds. Exact methods (exhaustive search, dynamic programming). Constructive heuristics (greedy algorithms). Improvement heuristics (hill climbing, local serach). Metaheuristics: Simmulated Annealing, Tabu Search, Evolutionary strategies, Ant Colony optimization, GRASP. Survey of additional heuristic techniques. Case studies on real world problems applying constructive, hybrid and meta heuristics.

General Competencies

Students are expected to gain understanding of the basic underlying theory of heuristic search as an optimization method to solve complex problems. Furthermore, they are expected to become familiar with the most commonly used heuristics (Greedy, Simmulated Annealing, Tabu Search, Evolutionary algorithms, Ant Colony optimization) and fully understand their methodology. They are expected to gain understanding of the advantages and disadvatanges of various heuristic approaches, and be able to evaluate the strength, limitations and quality of different methods. Most importantly, students are expected to become capable of applying their acquired knowledge to develop and implement appropriate and efficient heuristic approaches of their own for new complex problems.

Learning Outcomes

  1. explain the basic underlying principles of heuristic search as an optimization method to solve complex problems
  2. distinguish between problem complexity and algorithm complexity
  3. distinguish between exact methods and heuristic 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)
  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 in student groups.

Exams

Written exam.

Experiments

Examples of heuristic methods.

Consultations

Instructors are available for students during the weekly time slot announced on the web, as well as during regular office hours.

Other Forms of Group and Self Study

Student project

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Class participation 0 % 5 % 0 % 5 %
Seminar/Project 0 % 25 % 0 % 25 %
Mid Term Exam: Written 0 % 35 % 0 %
Final Exam: Written 0 % 35 %
Exam: Written 0 % 70 %

Week by Week Schedule

  1. Introduction to optimization; optimization models; combinatorial optimization
  2. Algorithm and problem complexity; categorization of optimization methods; Why and when to use heuristics
  3. Exact methods: integer programming, Branch and Bound
  4. Exact methods: Dynamic Programming
  5. Greedy algorithms
  6. Case Study: network planning
  7. Basic concepts of metaheuristics
  8. Midterm exam
  9. Local search
  10. Tabu Search
  11. Simulated annealing
  12. Evolutionary algorithms
  13. Ant colony optimization
  14. Student projects
  15. Final exam

Study Programmes

University graduate
Computer Engineering (profile)
Recommended elective courses (3. semester)
Computer Science (profile)
Recommended elective courses (3. semester)
Information Processing (profile)
Recommended elective courses (3. semester)
Software Engineering and Information Systems (profile)
Recommended elective courses (3. semester)
Telecommunication and Informatics (profile)
Recommended elective courses (3. semester)

Literature

Z. Michalewicz, D.B. Fogel (2004.), How to Solve it: Modern Heuristics, 2nd Edition, Springer-Verlag
V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, G. D. Smith (1996.), Modern Heuristic Search Methods, Wiley
J. Dréo, A. Pétrowski, P. Siarry, E. Taillard (2005.), Metaheuristics for Hard Optimization: Methods and Case Studies, Springer
El-Ghazali Talbi (2009.), Metaheuristics: From Design to Implementation, Wiley
Xin-She Yang; (2008.), Nature-Inspired Metaheuristic Algorithms, Luniver Press