Metaheuristics, 2021/2022

Index

• Course description
• Syllabus
• Bibliography
• Grading
• Tips for the class project

Course description

Metaheuristics are a class of algorithms that are suitable to find solutions to problems when little information is available beforehand to help guide the search for those solutions, and when a brute-force approach is not adequate.

In this course you will learn the working principles of these algorithms, how to implement and apply them to a particular domain. You will also develop writing and presentation skills.

Syllabus

1. Foundations
• Combinatorial problems
• Computational complexity
• Search paradigms
2. Single-State Methods
• Random search, Hillclimbing
• Variable neighbourhood descent, iterated local search
• Simulated annealing, late acceptance hillclimbing, tabu search
3. Empirical Analysis
• Design of experiments
• Performance assessment
4. Search Space Structure and Performance
• Search landscapes and local minima
• Ruggedness, plateaus, barriers and basins
5. Population Methods
• Genetic algorithms
• Evolution strategies
• Differential evolution and Particle swarm optimization
• Model-based evolutionary algorithms
6. Theory of Randomized Search Heuristics
• Run time analysis
• No free lunch theorem
7. Other topics (if time permits)
• Constraint handling
• Multimodal and multi-objective optimization
• Parallelization

Bibliography

• Stochastic Local Search: Foundations and Applications
  by H. Hoos and T. Stützle. Morgan Kaufmann, 2004.
  -- You can find some slides done by Thomas Stützle based on the book's material at his Heuristic Optimization course
  
  
• Essentials of Metaheuristics (available for free)
  by Sean Luke, 2010.
  
  
• Introduction to Evolutionary Computing
  by A. E. Eiben and J. E. Smith, Springer, 2003.
  
  

Grading

The grading of this course is based on a project and a final exam. The project is done individually and consists of applying metaheuristics to an application domain of the student's choice. For the project component, you will have to:

• write a technical report (10 A4 pages maximum) using the ACM conference style (see templates for Word for Windows, Word for Mac, and Latex) describing your EC application. (60%)
• make a 20-minute oral presentation of your work. (20%)
• submit all the code that you did to obtain the results shown in your technical report. (20%)

Your project will be graded based on the quality of your writing, the proper design, application, and testing of the algorithms used, the quality of your code, the clarity of your oral presentation.

The final grade will be computed as follows:

• project: 50%
• final exam: 50%

Tips for your project

You may want to have a look at the following list to get ideas for you class project.

• Wikipedia list of NP-complete problems.

As a final note, you may want to check David Goldberg's Technical Writing for Fun & Profit for tips on writing technical reports.