Homepage Sitemap Contact




Home « Studies « Teaching Materials
Sorry, only available in german.


Heuristische Optimierungsverfahren

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.



 Entnehmen Sie Angaben bezügl. Ort und Zeit bitte der LV-Liste der Universität Bremen



[Folien (ausser Übungsblätter) nur aus dem Campusnetz erreichbar]


Programmieraufgaben



generiert am 09.11.11
Uebungsblatt 1 Folien



generiert am 07.11.11
Uebungsblatt 10



generiert am 31.01.12
Uebungsblatt 2



generiert am 09.11.11
Uebungsblatt 3



generiert am 16.11.11
Uebungsblatt 4



generiert am 28.11.11
Uebungsblatt 5



generiert am 04.12.11
Uebungsblatt 6



generiert am 07.12.11
Uebungsblatt 7



generiert am 19.12.11
Uebungsblatt 8



generiert am 11.01.12


  Zur Liste der Lehrveranstaltungen der Universität Bremen




zurück





Deutsch








Sitemap Kontakt

ISMVL2014 DUHDE