Login |
 
 

Überblick

Leistung: SWS : 2, Credits 4

Teilnehmer: Min: 1 Max: 12 Erwartet: 6

Kurstyp : Seminar

Sprache: deutsch

Vorraussetzungen

Besuch der Data Mining Vorlesungen (ibs. Data Mining II) ist von Vorteil, aber nicht zwingend erforderlich

Leistungsnachweis

Vortrag und etwa 6 Seiten Zusammenfassung der Vortragsinhalte

Inhalt

Für viele klassische Optimierungsprobleme, wie z.B. Schulstundenplanung, Ligenplanung im Sportbereich oder auch das bekannte "Traveling Salesperson"-Problem, sind exakte Algorithmen ungeeignet, weil sie in endlicher Laufzeit keine befriedigende Lösung finden. Der Suchraum ist schlicht zu groß um ihn effizient systematisch zu durchsuchen. Oft ist man aber auch gar nicht an der optimalsten Lösung interessiert, sondern "nur" an einer guten Lösung, die dem Optimum nahe kommt. Genau hier kommen Heuristiken und im speziellen die Metaheuristiken ins Spiel. Im Gegensatz zu problemspezifischen Heuristiken, die jedesmal neu angepasst werden müssen, abstrahieren Metaheuristiken von der konkreten Probleminstanz und sind somit auf breiter Front einsetzbar. Interessanterweise hat der Großteil der gängigen Verfahren seinen Ursprung bei Mutter Natur: Genetische Algorithmen,  Ameisenkolonien oder die simulierte Abkühlung sind auf den Computer übertragene Vorgänge des täglichen Lebens. Und offenbar funktionieren diese Verfahren in der Praxis erstaunlich gut. In diesem Seminar wollen wir uns mit einer Reihe von Metaheuristiken beschäftigen. Im Einzelnen sind folgende Themen vorgesehen:

  • Genetische Algorithmen
  • Simulated Annealing
  • Ameisenkolonien
  • Tabu Search
  • Schwarmintelligenzen
  • Neuronale Netzwerke
  • Der Sintflutalgorithmus
  • Threshold Accepting
  • Iterated local search
  • Constraint programming
  • Scatter Search
  • Greedy Randomized Adaptive Search Procedure - GRASP
  • Distribution estimation algorithms
  • Variable Neighbourhood Search
  • Guided Local Search
  • Parallelisierte Metaheuristiken
  • Praktische Anwendung: Generierung von Tischtennispielplänen

Weitere Informationen

Link zum Eintrag im Vorlesungsverzeichnis