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