Heuristische Optimierungsverfahren und ihre Anwendung

Lecturers:Kókai, G.
Coverage:2 SWS (4 ECTS)
Dates & location:
  • Thursday, 08:30 - 10:00, 05.150
Audience:WPF INF-DH-PS (5.-7. Semester)
Literature:
  • Mathias Gröbner: Ein Modell zur Beschreibung und Lösung von Zeitplanungsproblemen, Dissertation 2003.
  • Michalewicz, Fogel: How to solve it: Modern Heuristics, Springer, 2000
  • Dr. Peter Merz: Moderne heuristische Optimierungsverfahren
  • Dr. Marko Hofmann: Moderne Heuristiken (http://emma.informatik.unibw-muenchen.de/inst5/lehre/Vorlesung-Moderne-Heuristiken.pdf)
  • D. Corne, M. Dorigo and F. Glover: New Ideas in Optimization, McGraw Hill, 1999.
  • C. Reeves: Modern Heuristic Techniques for Combinatorial Problems, McGraw Hill, 1995.
Topics:

Viele Optimierungsprobleme können in der Praxis nicht mit exakten mathematischen Verfahren gelöst werden. Um dennoch Lösungen für diese Probleme bereitstellen zu können, verwendet man heuristische Optimierungsverfahren. Strategien, die auf Hypothesen und Vermutungen aufbauen und die mit gewisser Wahrscheinlichkeit (jedoch ohne Garantie) das Auffinden einer Lösung beschleunigen sollen, heißen Heuristiken. Typische Heuristiken sind das Ausnutzen bekannter Eigenschaften von Lösungen oder die Nachbildung menschlicher Problemlösungsprozesse, oder Verwendung biologischer Vorbilder. Den Schwerpunkt der Vorlesung bilden neben klassischen Heuristiken, wie lokale Suche, Simulated Annealing und Tabu Search, die neuen (Meta-)Heuristiken, die auf der Simulation natürlicher bzw. biologischer Prozesse beruhen. Es werden u.a. Ameisenkolonien, Partikel-Schwärme, und memetische Algorithmen behandelt. Die verschiedenen Methoden werden am Beispiel des Traveling Salesman Problems demonstriert, und an Hand anderer Probleme aus der Bioinformatik und embedded Systeme diskutiert.

Themenbereiche
Die folgenden Themenbereiche werden in dieser Vorlesung behandelt: Optimierungsprobleme

  • Einführung in die Anwendungsgebieten
  • Exakte versus heuristische Verfahren
  • Lokale Suche
  • Simulated Annealing und Tabu Search
  • Evolutionäre Algorithmen
  • Künstliche neuronale Netze
  • Ameisenkolonien
  • Memetische Algorithmen und Partikel-Schwärme

Audience

Hauptdiplomstudenten Informatik

Exam/certificate

  • unbenoter Schein: 50% der Hausaufgaben
  • benoteter Schein: 50% der Hausaufgaben +Kolloquium
  • Hauptdiplomprüfung
watermark seal