Simulationsbasierte Optimierung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Idee der simulationsbasierten Optimierung (SBO) besteht darin, mit Simulationsmodellen eine Optimierungskomponente zu verbinden, die bestimmte Variablen eines Simulationsmodells zur Minimierung oder Maximierung einer Zielfunktion variiert.

Simulationsmodelle dienen zur Prognose komplexer, realer Systeme, die zufälligen Einflüssen unterliegen. Typischerweise nutzt man Simulationsmodelle, um die Auswirkungen einzelner Handlungsalternativen zu untersuchen, ohne diese tatsächlich umsetzen und mögliche negative Effekte auf das reale System zu verursachen. Man beschränkt sich i. d. R. auf eine relativ kleine Zahl von Handlungsalternativen, spielt diese mit Hilfe von Simulationssoftware durch, und wählt anschließend die nach einer bestimmten Zielsetzung beste Handlungsalternative aus. Die klassische Methode zur Auswahl einer Handlungsalternative besteht darin, die Simulationen mit entsprechende Software durchzuführen, die Auswahl dann jedoch weitgehend manuell zu treffen. Die simulationsbasierte Optimierung bezweckt hingegen, diese Auswahl der „besten“ Handlungsalternative automatisiert durch einen Algorithmus vorzunehmen, der ein zugrunde liegendes Simulationsmodell verwendet. Die Grundidee der SBO besteht darin, Handlungsalternativen durch Variablen eines Simulationsmodells zu beschreiben. Ein SBO-Algorithmus variiert diese Variablen, bewertet wiederholt die aus der Wahl von Variablenwerten resultierende Lösung durch Simulationsläufe und liefert dann die beste gefundene Lösung zurück.

In Analogie zur „klassischen“ Optimierung entsprechen also bei der SBO das Simulationsergebnis, welches z.B. ein Kostenwert sein kann, der Zielfunktion eines Optimierungsproblems, und die Variablen eines Simulationsmodells den Variablen eines Optimierungsmodells. Ein wesentlicher Unterschied zu „üblichen“ Optimierunsproblemen besteht jedoch darin, dass die „Zielfunktion“ bei der SBO stochastisch ist, d.h. sie unterliegt zufälligen Schwankungen, je nachdem welches eintretende Szenario in einem Simulationslauf betrachtet wird.

[Bearbeiten] Anwendungsbeispiele

Mögliche Zielsetzungen, aus denen konkrete SBO-Probleme abgeleitet werden können, sind das Finden

der besten Integration von Produktion und Logistik eines Unternehmens,
der besten Layouts, Verbindungen und Kapazitäten von Logistiknetzwerken,
der höchsten Auslastung verfügbarer Personalressourcen,
der besten Standorte für die Distribution von Gütern,
des besten Plans für den Betrieb eines Kernkraftwerks,
der besten Allokation von Ärzten und Pflegekräften eines Krankenhauses,
sowie der besten Einstellung von Toleranzen in Produktionsprozessen.

[Bearbeiten] Software

Auf dem Markt für Simulationssoftware existiert eine kaum überblickbare Vielfalt von Produkten. Diverse Simulationssoftwarepakete wurden inzwischen um Komponenten zur SBO erweitert:

CAOne ist eine Software für jede Art von Optimierung, Abläufe und Kopplung an Simulationsprogramme erfolgt einfach über eine grafische Benutzeroberfläche. Es ist jedes GUI-less Simulationsprogramm anbindbar, es wird Cross-Platform-Computing und Cluster-Computing unterstützt, stellt Künstliche Neuronale Netze zur Vorhersage aussichtsreicher Parameterkonstellationen sowie Fuzzy Logic basierte Zielfunktionen zur Verfügung.
Plant Simulation verfügt sowohl über eine eigene SBO Komponente, als auch über integrierte Neuronale Netze.
Die verbreitetste SBO-Komponente OptQuest ist inzwischen an 22 Produkte anderer Softwarehersteller angebunden, so z.B. Arena, Crystal Ball, ProModel, Enterprise Dynamics und SIMUL8. Außerdem ist OptQuest durch ein API (die OptQuest Engine Callable Library) in beliebige andere Anwendungen einbindbar.
ISSOP (Intelligentes System zur Simulation und Optimierung) besitzt Anbindungen u.a. an Arena, Enterprise Dynamics, eM-Plant, AutoMod, MATLAB, SAP-R3 und MS Excel.
RISKOptimizer erweitert die Monte-Carlo-Simulationssoftware @RISK für MS Excel um eine Optimierungskomponente.
Witness Optimizer ist in die Simulationssoftware Witness integriert.
Für ProModel kann neben OptQuest auch die SBO-Komponente SimRunner gewählt werden.
Das Produkt Extend verfügt über eine SBO-Komponente namens Extend Optimizer.
Die MATLAB Optimization Toolbox vereint verschiedene Methoden numerischer Optimierung aus dem Bereich linearer und nichtlinearer Optimierung
Simulink Response Optimization bzw. Simulink Parameter Estimation verändern die Parameter eines Modells dahingehend, dass dessen dynamisches Verhalten an einem Ausgang einem vorgegebenen Signalverlauf bzw. einem Korridor folgt.

[Bearbeiten] Algorithmen

Es lässt sich folgenden Einteilung der SBO-Algorithmen in Klassen vornehmen, die sich an den SBO-Forschungsrichtungen orientiert:

Algorithmen für endliche Lösungsräume: Ranking & Selection, Multiple Comparisons und Ordinal Optimization
Stochastic Approximation-Algorithmen (SA) wie FDSA und SPSA
Response Surface Methodology-Algorithmen (RSM) wie Sequential RSM mit linearer Regression oder neuronalen Netzen
Sample Path Optimization (SPO)
Metaheuristiken wie simulierte Abkühlung (SA), Genetische Algorithmen (GA), Tabu-Suche (TS), Scatter Search (SCS) und Particle Swarm Optimization (PSO)
Direct Search-Algorithmen (DS) wie Pattern Search (PS) und der Nelder-Mead-Simplex-Algorithmus, siehe Downhill-Simplex-Verfahren
Random Search