# Heuristic Optimization

## MSc Lecture - Summer 2015

## Description

Heuristic algorithms are widely applied in practice where time, money, and knowledge limit the development of problem-specific algorithms. They are very simple to apply as they typically consider the problem as a black box and only access it via a problem-dependent fitness function. Examples include nature-inspired algorithms like simulated annealing and swarm intelligence algorithms, as well as evolutionary and genetic algorithms. These algorithms take inspiration from optimization processes in nature and are applicable to basically any optimization problem. In this project seminar we will compare these heuristic optimization algorithms with classical optimization algorithms, such as LP- and SAT-solvers.

During course time we will introduce these different algorithms and example use cases; furthermore, we will formally analyze some of these algorithms from a performance perspective. The projects will try out these algorithms and test them experimentally. Finally, some theoretical homeworks and an algorithm engineering project will practice the analysis and implementation of heuristic optimization algorithms.

## Requirements

The ability to understand and develop formal proofs will be beneficial for this course. The seminar will be held in English.

## Examination

The students are expected to perform the following tasks, which will determine the final grading:

- Implementation of algorithms (three projects, each 20% of the total grade);
- Small theoretical homeworks (20% of the total grade);
- Algorithm engineering Project (20% of the total grade).

For the more formal details see the official course page.

## Dates

Tuesday, 13:30-15:00, room A-1.1

## News

**No lecture on 26 May.**(Next lecture takes place on 2 June).

## Materials

Slides:

- Lecture 1.
- Lecture 2-3 (slides lecture 2).
- Lecture 4.
- Lecture 5.
- Lecture 6.
- Lecture 7.
- Lecture 8.
- Lecture 9.

Homework:

- Homework 1 (due April 29) [solutions].
- Homework 2 (due May 6) [solutions].
- Homework 3 (due May 13) [solutions].
- Homework 4 (due May 20) [solutions].

Project home works:

- Project 1 (due May 3).
- Project 2 (due May 27).
- Project 3 (due June 14).
- Project 4 (due July 13) [source code].