News

Information

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.

This course will introduce and discuss heuristic optimization techniques with a main focus on stochastic local search techniques. The course will illustrate the application principles of these algorithms using a number of example applications ranging from rather simple problems to other more realistic ones related to applications. A significant focus in the course will be also on techniques for the empirical evaluation of heuristic optimization algorithms and on techniques that help in the design and development of heuristic optimization algorithms. Hands-on experience with these algorithmic techniques will be gained in accompanying exercises and implementation exercises.

The course is based in part on the book

Holger H. Hoos und Thomas Stützle, Stochastic Local Search, Morgan Kaufmann Publishers, 2005.

The exercises will deepen the knowledge gained in the lectures and case studies of applications of heuristic optimization techniques to computationally hard problems will be done. In addition, the practical knowledge will be strengthened in additional practical implementation exercises. In these tasks, basic heuristics and metaheuristics will be implemented and their performance be empirically evaluated. The implementation exercises will comprise two tasks, the second building on the first one.

Slides

The slides of the lectures will be made available here shortly after the lectures. They are based on the slides from the past year (see spring semester 2016) but may include some updates and extensions.

Chapter 0 (.pdf) Motivation, organizational matters
Intro (.pdf) Introduction to HO/SLS
Construction, iterative improvement, simple SLS methods (.pdf) Basic SLS techniques, simple SLS methods
SLS Methods (.pdf) Simple SLS methods, intro ILS
SLS Methods (.pdf) Hybrid and population-based SLS Methods
GLSMs (.pdf) Generalized local search machines
Empirical Analysis (.pdf) Empirical analysis, RTDs, instance sets
Automatic configuration (.pdf) Parameters, tuning, configuration, applications
Search Space Analysis (.pdf) Basic measures, fitness distance, ruggedness, advanced measures
Multi-objective Optimization (.pdf) main concepts, SAC and CWAC search model, performance analysis

Exercises

Exercise sheets will be made available here shortly before the exercises.

Exercise sheet 1 (.pdf) Introduction SLS, iterative improvement
Implementation exercise 1 (.pdf) Exercise sheet
Implementation exercise 1 (.pdf) Slides for introduction to implementation exercise
Implementation exercise 1 (.zip) Test instances
Implementation exercise 1 (.zip) Code PFSP
Exercise sheet 2 (.pdf) Complex neighborhoods, simple SLS methods
Exercise sheet 3 (.pdf) Simple, hybrid, population-based SLS methods
Implementation exercise 2 (.pdf) Exercise sheet (April 5, 2017)
Implementation exercise 2, Articles (.pdf) Articles (April 5, 2017)
Exercise sheet 4 (.pdf) GLSMs, empirical analysis
Exercise sheet 5 (.pdf) automatic configuration, search space analysis, multi-objective

Exam

An oral exam will be held at the end of the lectures. A precondition for the exam is the successful completion of the two implementation exercises.

Literature

  • Holger H. Hoos und Thomas Stützle, Stochastic Local Search, Morgan Kaufmann Publishers, 2005.

    Additional literature:

  • Emile H. L. Aarts und Jan Karel Lenstra (Hrsg.), Local Search in Combinatorial Optimization. John Wiley and Sons, 1997.

  • Marco Dorigo und Thomas Stützle, Ant Colony Optimization. MIT Press, 2004.

  • Zbigniew Michalewicz and David Fogel, How to Solve it: Modern Heuristics. Springer Verlag, 2000.

  • Christos H. Papadimitiou und Kenneth Steiglitz, Combinatorial Optimization. Dover Publications, 2nd edition, 1998.

  • 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.
    This report gives an overview of the Iterated F-race method for the automatic configuration of heuristic (and other) algorithms. For an implementation of the method, please check the irace software package.

  • Ravindra K. Ahuja, Özlem Ergun, James B. Orlin, and Abraham P. Punnen A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics 123(1-3): 75-102 (2002).

  • David S. Johnson and Lyle A. McGeoch. Experimental analysis of heuristics for the STSP. In G. Gutin and A. Punnen, editors, The Traveling Salesman Problem and its Variations, pages 369-443. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.
    This chapter gives an extensive discussion of the empirical performance of constructive heuristics, local search algorithms and iterated local search for the symmetric TSP.

    More literature on specific topics will be given during the lectures.
  • Links

    Contact