MW17.8 Modern Heuristics

Inhalt und Einordnung

Betriebswirtschaftliche Planungs- und Entscheidungsprobleme sind in der Regel durch hohe Komplexität, unsichere und dynamische Umweltbedingungen sowie Subjektivität der Entscheidungsmaßstäbe gekennzeichnet. Daher ist es im Rahmen der Planung erforderlich, Vereinfachungen der in Modellen berücksichtigten Problembedingungen, des Planungsprozesses sowie vor allem der verwendeten Planungsverfahren vorzunehmen. Derartige Vorgehensweisen der Vereinfachung und Annäherung tatsächlicher Sachverhalte werden allgemein als Heuristiken bezeichnet.

Insbesondere bei der Lösung komplexer Optimierungsprobleme haben (Optimierungs-) Heuristiken eine hohe Bedeutung.

Art der Veranstaltung

Das Modul wird als Projektseminar durchgeführt und setzt sich aus einem Vorlesungsteil (ca. erste Hälfte der Vorlesungszeit) und einem Projektteil (zweite Hälfte) zusammen.

Im Vorlesungsteil werden Heuristiken allgemein definiert und es wird dargestellt, wie Heuristiken bewertet werden können. Anschließend werden die verschiedenen Klassen an Optimierungsheuristiken sowie heuristische Metastrategien ausführlich behandelt.

Im daran anschließenden Projektteil sollen die Studierenden Heuristiken in einem eigenen kleinen Forschungsprojekt erarbeiten. Dabei kann es sich um einen Literaturüberblick, um eine Heuristikentwicklung, den Test von Heuristiken und/oder das Entwerfen und "Durchrechnen" von Fallbeispielen handeln. Die jeweiligen Erkenntnisse/Ergebnisse werden im Rahmen einer Präsentation kurz vorgestellt sowie in einer schriftlichen Ausarbeitung knapp festgehalten.

Gliederung

1. Begriff der Heuristik

  • Heuristik als allgemeines Planungsprinzip
  • Beispiele für allgemeine Heuristiken

2. Bewertung von Heuristiken

  • Vorüberlegungen
  • Beurteilungskriterien und deren Messung
  • Evaluationsmethoden im Überblick
  • Worst Case-Analyse
  • Simulative Beurteilung von Heuristiken

3. Optimierungsheuristiken

  • Begriff der Optimierungsheuristik
  • Eröffnungs- bzw. Konstruktionsverfahren
  • Verbesserungsverfahren / Lokale Suche

4. Heuristische Metastrategien

  • Begriff der Metastrategie
  • Tabu Search (TS)
  • Simulated Annealing (SA)
  • Genetische Algorithmen (GA)
  • Multiagenten- und Ameisensysteme

Vorlesungsfolien, Übungsblätter & zusätzliche Materialien

Die Materialien zum Download werden bei MoodleExterner Link bereitgestellt.

Literatur

  • Domschke, W.; Klein, R.; Scholl, A. (1996): Taktische Tabus. Tabu Search: Durch Verbote schneller optimieren. c't - Magazin für Computer Technik, Heft 12/1996, S. 326-332.
  • Gendreau, M.; Potvin, J.-Y. (2005): Metaheuristics in combinatorial optimization. Annals of Operations Research 140, S. 189-213.
  • Glover, F.; Laguna, M. (2002): Tabu Search. 6. Aufl., Kluwer, Boston.
  • Michalewicz, Z.; Fogel, D.B. (2004): How to solve it: Modern heuristics. 2. Aufl., Springer, Berlin.
  • Müller-Merbach, H. (1981): Heuristics and their design: A survey. European Journal of Operational Research 8, S. 1-23.
  • Pfohl, H.-C.; Hebel, R. (1982): Bewertung heuristischer Methoden. Zeitschrift für Operations Research 26, S. B123-B139.
  • Reeves, C.R. (1993) (Hrsg.): Modern heuristic techniques for combinatorial problems. Blackwell, Oxford.
  • Scholl, A. (2001): Robuste Planung und Optimierung: Grundlagen - Konzepte und Methoden - Experimentelle Untersuchungen. Springer, Berlin.
  • Voß, S.; Martello, S.; Osman, I.H.; Roucairol, C. (1999) (Hrsg.): Meta-heuristics - Advances and trends in local search paradigms for optimization. Kluwer, Boston.

Weitere Literatur wird im Rahmen des Projektseminars bekanntgegeben.