Heuristische Optimierungsverfahren
H | 03-ME-701.04
Gelangen exakte Optimierungsmethoden aufgrund der betrachteten Problemkomplexität an ihre Grenzen,
werden heuristische Methoden zur Problemlösung eingesetzt. Diese sind zum einen konstruktive Heuristiken, die das betrachtete Problem analysieren und zielgerichtet vorgehen und zum anderen Metaheuristiken, die ansatzweise universell einsetzbar sind und bei "schwierigen" Optimierungs- und Suchproblemen eingesetzt werden.
Dazu gehören Evolutionäre Algorithmen, die einen Schwerpunkt der Vorlesung darstellen. Diese Optimierungsmethode orientiert sich an der aus der Biologie bekannten Evolutionstheorie: charakteristische Beschreibungen von Problemlösungen werden codiert und bilden sogenannte Individuen, die mit Hilfe einer Fitnessfunktion bewertet werden. Durch wiederholte Selektion, Rekombination und Eliminierung werden immer neue und verbesserte Individuen, also Lösungen erzeugt. Das Ziel ist es, diese im Laufe der Generationen bzgl. ihrer Fitness zu verbessern, d.h. zu optimieren. Evolutionäre Algorithmen sind oftmals in der Lage, bessere Lösungen zu finden als andere bewährte Optimierungsmethoden.
Die Vorlesung gibt eine detaillierte Einführung zu Konstruktionsheuristiken, Verbesserungsheuristiken, Evolutionären Algorithmen und anderen Metaheuristiken, wie beispielsweise Tabusuche oder Ameisenkolonien sowohl in Theorie als auch Praxis. Insbesondere werden folgende theoretisch/methodische Grundlagen im Zusammenhang dieser Inhalte behandelt:
- Darstellung des Suchraumes für Optimierungsprobleme
- Optimalitätskriterien für Optimierungsprobleme
- Qualitätsabschätzung einer Lösung bei unbekanntem Optimum
- Konstruktions- und Verbesserungsheuristiken zum Handlungsreisendenproblem und zur Graphpartitionierung
- Kodierungsfunktionen zur Repräsentation mittels Evolutionärer Algorithmen
- Theoretische Grenzen Evolutionärer Algorithmen
- Theoretische Grundlagen der Mehrzieloptimierung
- Tabusuche
- Ameisenkolonien
Zielsetzung der Veranstaltung sind der Erwerb von tiefgehenden Kenntnissen über heuristische Optimierung, sowohl in Theorie als auch Praxis. Dazu gehören algorithmische Beschreibungen, aber auch ein praktischer Teil, der Implementierungen der einzelner Methoden vorsieht. Ein weiterer Aspekt der Vorlesung ist die Mehrzieloptimierung, wodurch für die Praxis relevante Problemstellungen im Bereich der Optimierung betrachtet werden.
