DM812: Metaheuristics (5 ECTS)

STADS: 15004701

Level
Master's level course

Teaching period
The course is offered in the autumn semester.
Offered according to needs.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal

Prerequisites:
None

Academic preconditions:
The content of the course DM811 Heuristics and Local Search Algorithms for Combinatorial Optimization must be known.

Course introduction
The course will introduce the students to a number of generic search algorithms, so-called metaheuristics, which have proved useful to obtain near-optimal solutions for different optimization problems which occur in practical applications. The methods help subprocedures, such as construction heuristics and local search, to exit from local optima and diversify the search in order to improve the quality of the solutions. The overall final algorithms yield the best approximation results for many NP-hard combinatorial optimization problems that arise in practical applications and that are infeasible for exact solution approaches. The methods are often inspired by nature, as in the case of evolutionary algorithms and ant colony optimization, or are based on search trajectory perturbations, as in the case of iterated local search or tabu search. During the course the methods will be applied to example problems such as traveling salesman, graph coloring, scheduling, routing, packing and cutting problems. Important issues in relation to metaheuristics are the configuration and the tuning of parameters. We will introduce and use racing methods to settle these issues. Finally, in large projects, the adoption of a software framework may facilitate the sharing and reusing of source code. We will therefore review some of the frameworks available in this field and introduce in details one of them.

The course addresses all students who wish to study techniques with high practical value rather than theory. Therefore, practical implementation and experimentation will be a significant part of the course.

Expected learning outcome
After the course, the student is expected to be able to:
- describe in a precise and suitable language, including with the help of pseudo-code, the general algorithmic methods (metaheuristics) that are part of the syllabus;
- apply the methods to new combinatorial problems that resemble in nature the ones seen in the course, and describe in a precise written language the resulting algorithms;
- design new algorithms based on those learned in the course (hybrid methods);
- implement the designed algorithms in a suitable programming language;
- undertake empirical studies of the applied methods and draw sound conclusions on qualitative and quantitative aspects of these methods;
- undertake a practical solution of the configuration and tuning problem related to the methods.
- discuss the results obtained in the two previous points.

Subject overview
Heuristic algorithms, Simulated Annealing, Tabu Search, Iterated Local Search, Evolutionary Algorithms, Ant Colony Optimization, Racing Algorithms, Software Frameworks.

Literature

Meddeles ved kursets start

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Project assignment, evaluated according to the danisk 7-marks scale and external censorship.
The project consists in implementing, configuring and tuning a certain number of metaheuristics and describing the work in a written report.

Terms for reexam according to the rules decided by the Study Board.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 20 timer
Laboratorieøvelser: 14 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.