Sprachen

Proseminar Metaheuristische Optimierung - SS2016

Kurzinformation: 
Nummer Umfang Termin Leiter
041407 2S Proseminar Heinrich Müller, Dominic Siedhoff
Beschreibung: 
Metaheuristiken sind algorithmische Verfahren zur näherungsweisen Lösung von Optimierungsproblemen. Im Unterschied zu Heuristiken die spezifische Gegebenheiten einer Problemstellung ausnutzen, sind Metaheuristiken so angelegt, dass sie auf beliebige Problemstellungen oder zumindest große Problemklassen angewandt werden können. Sie definieren einen allgemeinen Rahmen, der auf das zu lösende konkrete Problem anzupassen ist.

Metaheuristiken werden zur Lösung von Problemen eingesetzt, an denen klassische Optimierungsalgorithmen scheitern. In der Regel ist nicht garantiert, dass eine Metaheuristik eine global optimale Lösung findet. Es gibt jedoch zahlreiche Einsatzgebiete, in denen mit Metaheuristiken gute Lösungen erzielt werden. In der Informatik können Metaheuristiken etwa zur Optimierung der Architektur von Hardware-Plattformen in Bezug auf die Minimierung des Energieverbrauchs für eine gegebene Anwendung eingesetzt werden. Ein aktuelles Projekt an den Lehrstühlen Informatik 7 und 12 befasst sich beispielsweise mit der Entwicklung eines mobilen Scanners zur Ermittlung biologischer Viren in Blut- oder Speichelproben, der die notwendige Rechenleistung bei möglichst geringem Energieverbrauch erbringen muss.

Einige Metaheuristiken sind naturinspiriert, d.h. sie folgen Vorbildern, welche die Natur zur Optimierung einsetzt. Beispiele sind das Evolutionsprinzip, das Prinzip des Auffindens von Wegen zu Futterstellen durch Ameisenschwärme oder der Ablauf von Abkühlungsvorgängen.

In den Vorträgen des Proseminars soll die algorithmische Funktionsweise einer Reihe bekannter Metaheuristiken präsentiert werden und an Einsatzbeispielen illustriert werden.

Materialien:

Materialien zum Proseminar Metaheuristische Optimierung
Teilnahmevoraussetzungen: 

Formale Teilnahmevoraussetzungen gibt es nicht. Hilfreiche Voraussetzungen für das Seminar sind jedoch die Module ”Datenstrukturen, Algorithmen und Programmierung 1, 2“.

Literatur:

Das Proseminar orientiert sich an dem Buch Essentials of Metaheuristics (Sean Luke, Second Edition, 2013, frei verfügbar) das durch Material aus anderen Büchern oder wissenschaftlichen Artikeln ergänzt wird.

Zu erbringende Studienleistungen:

  • Teilnahme am zentral angebotenen Präsentationskurs. Diese Studienleistung ist Voraussetzung für die Modulprüfung.
  • Modulprüfung: Es ist ein Vortrag mit 30 Minuten Länge auf Grundlage einer zu erstellenden Präsentation (z.B. Powerpoint) zu halten. Ferner ist eine schriftliche Ausarbeitung zu erstellen, deren Umfang durch den Inhalt des Vortrags bestimmt ist. Der mündliche Vortrag, die Gestaltung der Präsentation sowie die schriftliche Ausarbeitung gehen jeweils zu einem Drittel in die Note der Prüfungsleistung ein.

Ablauf des Proseminars:

  • Vorbesprechungstermin: In der Woche vom 08.02. bis 12.02.2016 (letzte Vorlesungswoche des Wintersemesters).
  • Vergabe der Vortragsthemen: Bis Ende Februar 2016
  • Vorträge: Voraussichtlich ab 09.05., zwei-Stunden-Block wöchentlich. Der Termin wird noch bekannt gegeben.
  • Abgabe der schriftlichen Ausarbeitung: Spätestens zwei Wochen nach dem Vortrag