Mathematik > Arbeitsgruppen > Arbeitsgruppe Stochastische Optimierung > Forschung > Stochastische heuristische Optimierung, Optimierung und Simulation

Stochastische heuristische Optimierung, Optimierung und Simulation

Heuristische Optimierung

Komplexe Probleme der kombinatorischen Optimierung wie z.B. die Ermittlung kürzester Liefer- oder Versorgungswege können heutzutage nicht mit vertretbarem Aufwand exakt gelöst werden, obwohl die Menge S der Lösungen endlich ist. Zur praktischen Bearbeitung derartiger Probleme werden daher sogenannte heuristische Optimierungsverfahren eingesetzt, die nach plausiblen Prinzipien versuchen, möglichst gute Lösungen zu finden.

Eine große Klasse dieser Verfahren kopiert Vorgänge aus der Natur und übertragt diese auf meist stochastische iterative Verbesserungsschritte vorhandener Lösungen. Vertreter dieser Richtung sind z.B. genetische Algorithmen, Ameisenalgorithmen oder Simulated Annealing. Ein Nachteil dabei ist, dass es nur wenige beweisbare Qualitätsaussagen für diese Verfahren gibt. In der Arbeitsgruppe versuchen wir, verschiedene Aspekte heuristischer Optimierungsverfahren mathematisch zu durchleuchten und auf spezielle Anwendungen anzupassen.

Sogenannte modellbasierte Verfahren wie z.B. Ameisenalgorithmen oder die Cross-Entropy-Methode bilden ein 'Modell' für die Erzeugung guter Lösungen etwa in Gestalt der Pheromonmatrix oder einer Verteilung auf der Menge der zulässigen Lösungen. Dieses Modell wird iterativ verbessert, indem es zur zufälligen Erzeugung von Lösungen benutzt wird und daraufhin so angepasst wird, dass die gefundenen guten Lösungen in Zukunft eine höhere Wahrscheinlichkeit bekommen. In seiner Dissertation hat Z. Wu vor allem das asymtotische Verhalten derartiger Verfahren untersucht und allgemeine Bedingungen für die (möglicherweise unerwünschte, frühzeitige) Konvergenz ermittelt.

In manchen Fragestellungen führt eine Lösung nicht zu einem festen Zielfunktionswert, sondern es sind dafür weitere zufällige Einflüsse etwa in Gestalt externer Störungen (Wetter, Materialfehler, Maschinenausfall, Wechselkurse,..) zu berücksichtigen. Eine kürzeste Rundreise eines Lieferanten kann etwa durch den Ausfall von Verbindungen oder den Ausfall von Nachfrage einzelner Abnehmer gestört werden. Können diese Einflüsse nicht analytisch vollständig erfasst werden (d.h. kann der Erwartungswert der tatsächlichen Zielfunktion nicht berechnet werden), so simuliert man eine Lösung mit einer Reihe von Zufallsszenarien, um den mittleren Zielfunktionswert zu schätzen. Durch den Schätzfehler kann dabei eine Lösung fälschlicherweise als besonders gut bewertet werden und z.B. die Anpassung des Modells in eine falsche Richtung lenken.

In seiner Dissertation hat B. Görder statistische 'Ranking and Selection'-Methoden untersucht und insbesondere neue Methoden zur sicheren Einhaltung von Fehlerschranken gefunden. Diese Arbeit wurde 2013 mit dem Preis der Freunde und Förderer der TU Clausthal ausgezeichnet.

Literatur

  • B. Görder, "Simulationsbasierte Optimierung mit statistischen Ranking- undSelektionsverfahren", Dissertation, Clausthal 2012.
  • B. Görder and M. Kolonko, "Ranking and Selection: A New Sequential Bayesian  Procedure for Use with Common Random Numbers" [pdf-file]
  • Wu, Z: "Model-based heuristics for combinatorial optimization: a mathematical study of their asymptotic behavior", Doctoral Thesis TU Clausthal, Clausthal 2015, [pdf-file]

 

 

 

Sitemap  Datenschutz  Kontakt  Impressum
© TU Clausthal 2017