Simulation Flashcards
1
Q
Motivation Simulation
A
- Optimale Lösungen durch rekursive Berechnung der Werte
- Höhere Problemkomplexität erschwert Berechnung
- Komplexitäten:
- Zustandsraum (Berechnung der Werte für jeden Zustand)
- Erwartungswert (Berücksichtigung aller Transitionen)
- Entscheidungsraum (Berücksichtigung aller Entscheidungen)
- Idee: Abschätzung der Wertefunktion
- Wie kann die Wertefunktion angenähert werden?
- Simulationsverfahren: Simulation ermöglicht implizite Abbildung der Transitionen und Wahrscheinlichkeiten
Simulation im Markov-Entscheidungsprozess:
- Eine simulierte Realisierung ordnet jedem Nach-Entscheidungs-Zustand genau einen neuen Zustand zu
- Politik+Realisierung ergibt genau einen Pfad durch den Prozess
2
Q
Definition Simulation
A
- Definition: Simulation is the imitation of the operation of a real-world process or system over time. (Banks et al. 1996)
- Verwendung zur:
- Beschreibung und Analyse des Verhaltens eines Systems
- Beantwortung von what-if Fragen des realweltlichen Systems
- Unterstützung beim Gestalten von realweltlichen Systemen
- System wird für die Simulation durch ein Simulationsmodell dargestellt
- In Simulationen wird das Modell numerisch evaluiert
- Unterscheidung zwischen diskreten und kontinuierlichen Modellen
- Diskret: Zustandsvariable ändert sich nur zu bestimmten diskreten Zeitpunkten
- Häufig im betriebswirtschaftlichen Kontext
- Beispiel: Kundenanfragen
- Kontinuierlich: Zustandsvariablen ändern sich kontinuierlich über die Zeit
- Häufig in der Physik und Biologie
- Differentialgleichungen
- Beispiel: Wettersimulation
3
Q
Discrete-Event-Simulation
A
- umfasst die Modellierung eines Systems, welches sich über die Zeit entwickelt
- Entwicklung wird durch die Veränderung der Zustandsvariablen zu bestimmten Zeitpunkten dargestellt
- Zeitpunkt hier ist der Eintritt eines Ereignisses, z.B. Ankunft einer neuen Kundennachfrage
- Update des Zustands des Systems bei jedem Ereignis
4
Q
Simulation Vorteile und Nachteile
A
- Vorteile:
- numerische Lösung komplexer realweltlicher Systeme
- besseres Verständnis des Systems
- neue Politiken, Entscheidungsregeln, Informationsflüsse usw. können analysiert/getestet werden ohne das realweltliche System zu unterbrechen
- Eintritt bestimmter Phänomene kann genauer betrachtet werden
- Dehnung oder Raffung der Zeit möglich
- Nachteile:
- Stochastische Simulation ermöglicht nur Schätzungen
- Durchführung und Analyse zeitaufwendig und kostenintensiv
- Interpretation der Ergebnisse kann schwierig sein
5
Q
Online Simulation im Markov Entscheidungsprozess
A
- Idee: Nutzen von Simulation zur Abschätzung der Wertefunktion und zur Evaluierung von Entscheidungen
- Simulation spiegelt Transitionen und Entscheidungen im Markov Entscheidungsprozess wider
- Eine Realisierung ordnet jedem Nach-Entscheidungs-Zustand genau einen neuen Zustand zu
Simulation zur Abschätzung der Wertefunktion:
- Online: Ausgehend von einem spezifischen Zustand
- Simuliere Zukunft in vollem Detail
- Entscheide innerhalb der Simulation mit Basispolitik
- Erhalte realisierte Werte
- Nutze die Werte als Abschätzung der Wertefunktion
- „Forward Programming“
Reduzierung der Komplexität:
- Komplexitäten („Curses of Dimensionality“):
- Zustandsraum (Berechnung der Werte für jeden Zustand)
- Erwartungswert (Berücksichtigung aller Transitionen)
- Entscheidungsraum (Berücksichtigung aller Entscheidungen)
- Reduktion durch Online Simulation:
- Zustandsraum: Wert wird allein für den aktuellen Zustand berechnet
- Erwartungswert: Menge an 𝐿Realisierungen 𝜔1,…,𝜔𝐿
- Entscheidungsraum: Basispolitik 𝜋𝑏
6
Q
Rollout Algorithmus
A
- Gegeben sei Zustand 𝑆𝑘 und eine Menge an potentiellen Entscheidungen 𝑋(𝑆𝑘)
- Generiere Nach-Entscheidungszustände 𝑆𝑘𝑥1,𝑆𝑘𝑥2,𝑆𝑘𝑥3,…
- Für jeden Nachentscheidungszustand 𝑆𝑘𝑥:
- Simuliere 𝐿Pfade (Realisierung+Politik)
- Entscheidungen innerhalb der Simulation: Basispolitik 𝜋𝑏
- Erhalte 𝐿Ergebnisse
- Setze Wert 𝑉(𝑆𝑘𝑥)als Mittelwert der Ergebnisse
- Wähle Entscheidung 𝑥, die 𝑅 𝑆𝑘,𝑥 + 𝑉(𝑆𝑘𝑥)maximiert
7
Q
Reduktion des Entscheidungsraumes
A
- Zu-/Absage: 2 Entscheidungen
- Routing: noch 𝑛Kunden in der Tour, 1 Anfrage: Bis zu (𝑛+
- 1)!Möglichkeiten
- Reduktion:
- Explizite Entscheidung über Zu- und Absage
- Routing-Heuristik: Beibehaltung der aktuellen Tour und Einfügen an günstigster Stelle
Zu-/Absagen und Wertefunktionen:
- Die Annahme eines Auftrages reduziert die zur Verfügung stehenden Ressourcen zukünftige Aufträge zu bedienen. (Wert sinkt)
- Frage: Ist es wert einen Auftrag anzunehmen?
- Sinnvoll,
- Wenn Ressourcenreduktion gering
- Wenn durch Ressourceninvestition zukünftige Aufträge effizienter zu bedienen sind (Abdeckung)
2 Entscheidungspolitiken:
- Myopic (Kurzsichtig):
- Wertefunktion wird auf 0 gesetzt
- Maximierung des sofortigen Nutzen
- Kunden wird stets zugesagt, solange sie bedient werden können
- Online Simulation: Rollout Algorithmus
- Für jeden der zwei Nachentscheidungszustände
- Simuliere den Rest des Tages
- Nutze die myopic Politik als Basispolitik
- Anzahl der Simulationsläufe 𝐿=16
8
Q
Nachteile der Online-Simulation
A
- Stark limitierte Laufzeit
- Keine verlässliche Simulation:
- Wenige, gesampelte Realisierungen
- „Suboptimale“ Entscheidungen in der Simulation
- Fehler vergrößert sich über den Simulationsverlauf durch suboptimale Entscheidungen und angenommene Realisierungen
9
Q
Simulationshorizont
A
- Idee: Abschneiden der Simulation nach einer bestimmten Anzahl 𝐻 Entscheidungspunkten
- Erwartet: Tradeoff zwischen Antizipation und Verlässlichkeit
- Je länger der Simulationshorizont, desto mehr wird antizipert
- Je kürzer der Simulationshorizont, desto verlässlicher ist die Simulation
- Anpassung der Bellman-Gleichung
- Simulation von höchstens 𝐻 Entscheidungspunkten
- 𝐻 =0: myopic, 𝐻 =∞: Komplette Simulation bis zum Ende
10
Q
Zusammenfassung Simulation
A
- Markov Entscheidungsprozesse sind oft zu komplex, um sie exakt zu lösen
- Idee: Nutzung von Online Simulation zur Abschätzung der Wertefunktion
- Simulation basiert auf Realisierungen und einer Basispolitik
- Nachteile der Simulation
- Laufzeit ist limitiert
- Basispolitik führt zu suboptimalen Entscheidungen in der Simulation
