19/04/2018
The exercise sheet for the second implementation exercise is now online.

04/04/2018
The preliminary schedule for the oral exams is as follows: June 18 students of Applied Sciences faculty, ULB, on June 19 students of Sciences faculty, ULB, and on June 22, students from VUB. Please contact Dr. Stützle if this clashes with one of your exams (due to same day).

07/02/2018
Attention: The first lecture will be held only on February 28, 2018 at 08:00 in S.C.5.130, ULB Solbosch campus. This is the seminar room of the IRIDIA laboratory, which is in the fifth floor of building C.

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.

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 2017) but may include some updates and extensions.

Chapter 0	(.pdf)	Motivation, organizational matters
Intro	(.pdf)	Introduction to HO/SLS
Construction, iterative improvement	(.pdf)	Basic SLS techniques
SLS Methods	(.pdf)	Simple SLS methods
SLS Methods	(.pdf)	Simple and Hybrid SLS methods
SLS Methods	(.pdf)	Hybrid and population-based SLS Methods
GLSMs	(.pdf)	Generalized local search machines
Empirical Analysis (i)	(.pdf)	Empirical analysis, RTDs
Empirical Analysis (ii)	(.pdf)	Empirical analysis, RTDs
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
Various topics	(.pdf)	Dynamic and stochastich optimization, SLS engineering

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	(.tar.gz)	Test instances, best known solutions
Implementation exercise 1	(.tar.gz)	Basic code MKP
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 20, 2018)
Implementation exercise 2, Articles	(.pdf)	Articles (April 20, 2018)
Exercise sheet 4	(.pdf)	GLSMs, empirical analysis
Exercise sheet 5	(.pdf)	automatic configuration, search space analysis, multi-objective, other

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.

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.

• Stochastic Local Search (web resources)
  

• IRIDIA

Dr. Thomas Stützle