Parallele Metaheuristiken für kombinatorische Optimierungsprobleme

Lecturers:Kókai, G.; Klemm, M.
Coverage:2 SWS (2,5 ECTS)
Comment:Anmeldung über per Mail an klemm@informatik.uni-erlangen.de
Dates & location:
  • single date on November 4, 2006, 15:00 - 18:00, 05.150
  • single date on December 9, 2006, 15:00 - 18:00, 05.150
  • single date on January 13, 2007, 15:00 - 18:00, 05.150
Audience:WF INF-DG (at 3. Semester)
Topics:

Heuristik ist ein griechisches Wort und bedeutet Problemlösung, Entdeckung und Erfindung. Metaheuristiken sind allgemeine algorithmische Verfahren zur Leitung der Suche, um auf möglichst effiziente Art und Weise sehr gute Lösungen für die jeweilige Problemstellung zu finden.

Das Ziel der Metaheuristiken ist die Entwicklung von Verfahren, die unabhängig von dem Objekt des Verfahrens sind und auf verschiedene Aufgaben anwendbar sind. Der wichtigste Vorteil der metaheuristischen Verfahren ist, dass sie auf eine relative breite Klasse der in der Informatik vorkommenden Probleme anwendbar ist, sie benutzen kein Hintergrundwissen, so dass sie auch funktionieren, wenn die Struktur der Aufgabe weniger bekannt ist.

Andererseits geben diese Verfahren keine Garantie, dass eine optimale Lösung gefunden wird. Sie finden aber immer eine relative gute Lösung, so dass sie auch dann verwendet werden können, wenn keine optimale Lösung existiert. Die bekanntesten Verfahren sind: Simulated Annealing, Tabu-Suche, verschiedene Hill-Climbing-Verfahren, evolutionäre Algorithmen.

Auch wenn Metaheuristiken während der Suche eine drastische Reduktion des Suchraumes vornehmen, bieten sich bei diesen Verfahren Strategien zur Parallelisierung an, um die Berechnungszeit zu verkürzen. Hierzu ist zu unterscheiden, welche Architektur ein Parallelrechner besitzt, um zu entscheiden, welche Parallelisierung am geeignetsten ist.

Für das Seminar sollen grundlegende parallele Metaheuristiken an Beispielen erarbeitet werden und im Rahmen eines 30minütigen Vortrags (wahlweise deutsch oder englisch) den anderen Seminarteilnehmern vorgetragen werden. Der Vortrag soll in einer 5seitigen Ausarbeitung zusammengefasst werden.

Vorläufige Liste von Vortragsthemen:

  • Metaheuristiken (G. Kókai)
  • Parallelität (M. Klemm)
  • Graph Coloring
  • Graph Partitioning
  • Steiner Tree Problem
  • Set Partitioning & Covering
  • Satisfiability Problems
  • Quadratic Assignment
  • Location Problem
  • Traveling Sales Person Problem
  • Vehicle Routing
  • Network Design
  • Bioinformatics
watermark seal