Course teacher(s)
Thomas,T STUTZLE (Coordinator)ECTS credits
5
Language(s) of instruction
english
Course content
Computationally hard problems arise in many relevant application areas of computational intelligence such as computer science, operations research, bioinformatics, and engineering. For many such problems, heuristic search techniques have been established as the most successful methods. In this course I will introduce and discuss heuristic optimization techniques with a main focus on stochastic local search techniques, which are the most relevant heuristic techniques. The course will illustrate the application principles of these algorithms using a number of example applications ranging from rather simple problems of more academic interest to more complex problems from real applications. A significant focus in the course will be also on relevant techniques for the empirical evaluation of heuristic optimization algorithms and the issues that arise in their development. Hands-on experience with these algorithmic techniques will be gained in accompanying practical exercises.
Objectives (and/or specific learning outcomes)
The main objective is to give students theoretical and practical knowledge of how to tackle effectively difficult optimization problems with heuristic techniques, in particular, stochastic local search methods. In more detail, the goals are
- learn about heuristic optimization techniques
- learn how these can be used to tackle combinatorial optimization problems
- learn how to analyze heuristic algorithms empirically.
- obtain hands-on experience with the implementation and the application of heuristic techniques.
Teaching methods and learning activities
The course consists of lectures, exercise sessions, where students deepen some topics covered in the lectures, and implementation tasks.
Contribution to the teaching profile
-
Knowledge about the available heuristic search techniques for tackling difficult computational problems and experience in determining which techniques are applicable in which situation.
-
Knowledge of the principles that underlie heuristic search techniques.
-
Understanding of the possibilities offered by heuristic search techniques as well as their advantages and their limitations.
-
Knowledge of how to evaluate the performance of computational systems such as heuristic serch techniques and of how to perform correct empirical analysis.
-
Knowledge of new tendencies and advances in the domain of heuristic optimization; capabilities of evaluating new heuristic search techniques and of learning to use new techniques if necessary
References, bibliography, and recommended reading
The course is mainly based on the book
Holger Hoos and Thomas Stuetzle. Stochastic Local Search-Foundations and Applications, Morgan Kaufmann Publishers, San Francisco, California, 2004.
Other relevant literature for the lecture is:
Emile H. L. Aarts und Jan Karel Lenstra (editors), Local Search in Combinatorial Optimization. John Wiley and Sons, 1997.
Marco Dorigo und Thomas Stuetzle, Ant Colony Optimization. MIT Press, 2004.
Zbigniew Michalewicz and David Fogel, How to Solve it: Modern Heuristics. Springer Verlag, 2000.
Vittorio Maniezzo, Thomas Stützle, and Stefan Voß, Matheuristics-Hybridizing Metaheuristics and Mathematical Programming, Springer Verlag, New York, 2009.
El-Ghazali Talbi, Metaheuristics - From Design to Implementation. Wiley, Chichester, UK, 2009.
Michel Gendreau and Jean-Yves Potvin, Handbook of Metaheuristics, Springer Verlag, New York, 2nd edition, 2010.
M. Birattari, Z. Yuan, P. Balaprakash and T. Stützle F-Race and Iterated F-Race: An Overview Technical Report TR/IRIDIA/2009-018, 2009.
Other information
Contacts
Thomas Stützle
Evaluation
Method(s) of evaluation
- Other
Other
Oral examination.
The implementation exercises will be marked and taken into account for the final mark.
Mark calculation method (including weighting of intermediary marks)
Final mark composition: 60% oral examination; 40% implementation exercises
Language(s) of evaluation
- english