Homepage
Sitemap
Kontakt




Universität Bremen Universität Bremen Fachbereich 3 Informatik
Home « Lehre « Lehrmaterial


Heuristische Optimierungsverfahren ME-701.04

Veranstalter: Dr. Nicole Drechsler, Beate Kapturek

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.


 Ort & Zeit:
V 2 SWS Di von 08:00 - 10:00 MZH 1450
Ü 2 SWS Mi von 08:00 - 10:00 MZH 1450


[Folien (außer Übungsblätter) nur aus dem Campusnetz erreichbar]


Programmieraufgaben

PDF


generiert am 09.11.11
Uebungsblatt 1 Folien

PDF


generiert am 07.11.11
Uebungsblatt 10

PDF


generiert am 31.01.12
Uebungsblatt 2

PDF


generiert am 09.11.11
Uebungsblatt 3

PDF


generiert am 16.11.11
Uebungsblatt 4

PDF


generiert am 28.11.11
Uebungsblatt 5

PDF


generiert am 04.12.11
Uebungsblatt 6

PDF


generiert am 07.12.11
Uebungsblatt 7

PDF


generiert am 19.12.11
Uebungsblatt 8

PDF


generiert am 11.01.12




zurück





English









Zum Seitenanfang Zur Homepage
Zur Sitemap
Kontakt