Folie 7

Vergleich von Systemkonfigurationen

• Simulationen werden oft zur Entscheidungsfindung eingesetzt.
• Typische Fragen sind: Was ist die beste Systemkonfiguration? Welche von n Systemkonfigurationen sollte gewählt werden?
• Es gibt Unterschiede: Viele Konfigurationen, von denen nur ein Teil untersucht wird (Optimierung). Wenige Konfigurationen, die alle untersucht werden (Auswahl aus Ergebnissen).
• Im Folgenden werden das zweite Problem und mögliche Optimierungsansätze behandelt, welche in Kapitel 9 erläutert werden.

Probleme bei der Auswahl der "besten" Konfiguration

• Ergebnisse sind stochastisch, Verhaltensunterschiede müssen geschätzt und Zufallseinflüsse von signifikanten Unterschieden getrennt werden.
• Ein zugehöriges Problem in der Simulation ist Ranking and Selection, welches ein aktuelles Thema auf Winter Simulationskonferenzen ist.

Grundsätzliche Fragestellungen

• Welche von n Konfigurationen am besten ist.
• Welche Scheduling-Strategie (FIFO, PS, RR,..) gewählt werden sollte, um die Verweilzeit zu minimieren.
• Wie viele Server eingesetzt werden sollten, um eine mittlere Antwortzeit < 10 sec zu erreichen.

Statistische Problemstellungen

• Für zwei Konfigurationen: Teste H0: V1 = V2 oder H0: V1 > V2; Bestimme ein Konfidenzintervall für V1 - V2.
• Für K Konfigurationen: Teste H0: V1 = V2 =... = VK (ANOVA); Simultan Konfidenzintervalle für Vk - V1; Auswahl der m besten von k Konfigurationen (mit vorgegebener Wahrsch.)

Beispiel aus Law/Kelton

• Erwartungswert der Wartezeit der ersten 100 Kunden in einem M/M/1 versus M/M/2 System.
• λ=1, μ=0.9-1 für M/M/1 und λ=1, μ=1.8-1 für M/M/2.
• Ergebnis analytisch berechenbar: V₁ = 4.13, V₂ = 3.70, also ist Variante 2 besser.
• Simulation: Analysiere das Modell startend mit leerer Warteschlange und freien Bedienern und simuliere jeweils 100 Ankünfte und deren Bedienung.

Methoden sind notwendig, um

• Fehlerwahrscheinlichkeiten für Entscheidungen zu ermitteln.
• Experimente so zu steuern, dass Entscheidungen mit vorgegebener Wahrscheinlichkeit korrekt sind.
• Auch mit stationären (nicht terminierenden) Simulationen umgehen zu können.

Gliederung

• Vergleich von zwei Systemen
• Vergleich von mehreren Systemen
• Allgemeine Verfahren zur Rangbildung und Auswahl

Vergleich zweier Systeme

• Zwei Systemkonfigurationen, für die ein Leistungsmaß μ analysiert werden soll (μ₁ = E[V;] Leistungsmaß für Variante i∈ {1,2}).
• Ziel: Ermittlung von ζ = μ₁ – μ₂, d.h. Bestimmung eines Konfidenzintervalls für ζ.
• Annahme: Beobachtung von Replikationen: n; Replikationen für das i-te Leistungsmaß werden durchgeführt; Vij die j-te Beobachtung des i-ten Leistungsmaßes;
• Vij ist Realisierung einer ZV Vi mit E(V) = μ₁.
• Interpretation des Konfidenzintervalls ζ + Φα (Φα halbe Breite für Signifikanzwahrscheinlichkeit a): Falls ζ + Φα < 0 → System 2 besser, falls ζ - Φα > 0 → System 1 besser.

Beispiel: Sicherheitsüberprüfung von PKWs

• Überprüfung von Bremsen, Licht und Lenkung. PKWs kommen nach Poisson-Prozess mit Rate 9.5 PKW/Std. an.
• Mögliche Systemkonfigurationen (Ziel: Vergleich der Verweilzeiten): Variante 1: 3 Mechaniker, jeder führt alle Arbeiten durch; Dauer der Arbeitsschritte: Bremse 6.5 Min, Licht 6 Min., Lenkung 5.5 Min. jeweils normalverteilt mit Stdabw. 0.5 Min. Variante 2: 3 Mechaniker, führen jeweils spezifische Arbeiten durch; Dauer der Arbeitsschritte: Bremse 5.85 Min, Licht 5.4 Min., Lenkung 4.95 Min. jeweils normalverteilt mit Stdabw. 0.5 Min

Was kann man erreichen?

• Gibt es einen signifikanten Unterschied der Verweilzeiten der beiden Konfigurationen?
• Statistisch signifikanter Unterschied: Anzahl der Beobachtungen ist groß genug, so dass der Unterschied zwischen den Mittelwerten größer als die Variabilität der Beobachtungen ist.
• Praktisch signifikanter Unterschied: Unterschied in den Verweilzeiten ist so groß, dass er die Entscheidung für eine Variante herbeiführt (zumindest größer als der Modellierungsfehler).

Annahme:

• Beobachtungen der Verweilzeiten sind approximativ normalverteilt und unabhängig.
• Schätzer für Erwartungswert und Varianz: V = (1/n) * Summe(Vij) und S = 1/(n-1) * Summe((Vij - V)²)
• Falls Varianzen beider Konfigurationen gleich (oder zumindest ähnlich) sind, so können die so genannten t-Konfidenzintervalle berechnet werden: W ± da = mit Formel

Beobachtungen

• Exakte Resultate, falls Beobachtungen normalverteilt und Varianzen σ₁² und σ₂² identisch sind; Im Prinzip entspricht das Vorgehen der „normalen“ Berechnung von Konfidenzintervallen für ein System.

• Gute Approximation, falls Varianzen ähnlich sind (aus Beobachtungen ableiten) oder n₁ = n2 gilt

• In allen anderen Fällen ist das Konfidenzintervall sehr schlecht (d.h. Wahrscheinlichkeit kleiner als 1 - α)

• Ansonsten approximatives Vorgehen nach Welch (1938) verwenden.

• Formel für die Anzahl der Freiheitsgrade und

• Formel für die Berechnung nach Welch

Geapaarte Konfidenzintervalle:

• Falls die Stichproben gleich mächtig sind, so können Beobachtungen gepaart werden. Formel für W und S
• V1i und V2i können unabhängig oder abhängig sein, während Vij und vkl für j≠l unabhängig sein müssen.

Nutzung des „algorithmischen Zufalls“ der Simulation

• Unterschiede in Leistungsgrößen entstehen durch Unterschiede im Systemverhalten und Zufallseinflüsse, wobei nur ersteres benötigt wird.
• Bisheriges Vorgehen: Reduzierung von Zufallseinflüssen durch mehrfaches Beobachten. Alternative: Nutzung identischer Zufallseinflüsse in zu vergleichenden Modellen.

Annahme Nutzung identischer ZZs in beiden Modellen.

• Eine eindeutige Zuordnung von ZZs zu Prozessen im System muss möglich sein.
• Dies kann problematisch sein, da unterschiedliche Systemkonfigurationen verglichen werden und ZZs aus unterschiedlichen Verteilungen kommen können.
• Eingriffe in die Struktur des Simulators notwendig; Änderbarkeit und Übersichtlichkeit komplexer Modelle eingeschränkt Generatoren reproduzierbare ZZs erzeugen (heute i.d.R. gegeben).

Zwei Modellvarianten mit gemeinsamen ZZ

• Seien v₁ zwei beobachteten Stichproben und W₁ die Differenzen.
• Stichproben beschreiben Realisierungen von ZVs V1, V2 und W; V1, V2, S1 und 2 sind die Mittelwert- und Varianzschätzer.
• Ziel: Schätzung von E(W) unter Verwendung von σ²(W) = VAR(W).
• Wenn V₁ und V2 positiv korreliert sind, so gilt COV(V1,V2) > 0 wodurch die Varianz des Schätzers reduziert wird!

Bisheriger Schätzer für σ²(W) (bei unkorrelierten ZVs V₁ und V2)

• S12 = S + S2 mit Formel
• Nun Schätzung direkt aus Formel
• Die einzelnen Werte vij müssen gespeichert und offline ausgewertet werden!
• Vorgehen klingt logisch und einfach, aber gemeinsame ZZs führen nicht zwangsläufig zu positiver Korrelation. Es können auch negative Korrelationen auftreten und die Varianz vergrößert werden!

Positive Korrelation bei Verwendung von gemeinsamen ZZs

• Intuitive Erklärung: z.B. lange Bedienzeiten führen zu langen Wartezeiten.
• Nachweis der Verhaltensmonotonie: z. B. durch Analyse der Transformationen.
• Schätzung von S1, S2 und S12 in Pilotläufen.
• Verwendung gemeinsamer ZZs in modernen Simulationssystemen:
• Definition von ZZ-Strömen und Verwendung von identischen Strömen für korrespondieren Ereignissen; In den meisten Simulationssystemen wird die Definition von unabhängigen Teilströmen ermöglicht
• Vermeidung von Abgängigkeiten: Startpunkte der Ströme müssen möglichst weit auseinander liegen.
• Die Verwendung gleicher Saaten reicht i.d.R. nicht aus!

Ansatz

• Es ist auch interessant für die trace-getriebene Simulation!
• Beispiel Caching-Algorithmen für Web-Server

ZZ-Ströme in OMNET++

• Konfiguration in der Datei omnetpp.ini
• Deklaration von ZZ-Strömen in Modulen durch
• Abbildung der ZZ-Ströme auf ZZ-Ströme in einem Modul oder auf den voreingestellten Strom (RNG 0)
• Innerhalb der Module können durch Wahl der Ströme bestimmte Ereignisse aus einem Strom generiert werden

ZZ-Ströme in AnyLogic

• Ein eigener Generator kann als Unterklasse der Java Klasse Java.util.Random definiert werden.
• Aufruf von einer Verteilung mit Generator als Parameter nutzt ZZ aus dem Generator.

Replikationen des Beispielmodells

• Generierung der Ankunftsabstände mittels Exponentialverteilung mit Rate 9.5 pro Stunde.
• Generierung der Bedienzeiten B₁ = E(B₁) + 0.5.Z (Z ist eine N(0,1) verteilte ZZ, E(B₁) entspricht dem Erwartungswert des jeweiligen Arbeitsgangs).
• Für Variante 1 wird die Bedienzeit als Summe B₁ + B2 + B3 berechnet, in der zweiten Variante werden jeweils einzelne Bedienzeiten benutzt.
• Experimentaufbau: 10 Replikationen für Variante 1 (M1); 10 unabhängige Replikationen für Variante 2 (M2U); 10 Replikationen für Variante 2 identischen Zufallszahlen (M2A)

Vergleich von Systemkonfigurationen:

• Zwei Möglichkeiten identisch und unabängig zu sein: Replikationen vor stationärer Phase löschen; stationäre Phase je Lauf bestimmen
• Batch Means: Bildung von Batches, damit Mittelwerte unabhängig; Weglassen von Werten im ersten Batch; Batchgröße je Lauf festlegen

Ergebnisse der Replikationen

• Simulationsdauer 16 Modellstunden pro Replikation.
• Stat mit 2 PKWs in der Warteschlange und Bestimmung der mittleren Verweilzeit
• Varianzen der Verweilzeiten sind nicht identisch, -> Approximation.
• Formelergebnisse. Konfidenzintervalle mit gemeinsamen Zufallszahlen sind kleiner, als mit den anderen beiden Methoden

Probleme beim Vergleich nicht terminierender Simulationen

• Beobachtungen müssen identisch und unabhängig verteilt sein.
• Mögliche Lössung: Unabhängige Replikationen (jeweils Beobachtungen vor Erreichen der stationären Phase löschen); Batch Means (Bildung von Batches)

Vergleich von mehreren Systemen

• K unterschiedliche Systemkonfigurationen sollen miteinander verglichen werden. Vergleich durch Vergleich der Konfidenzintervalle.
• Mögliche Fragestellungen: Berechnung individueller Konfidenzintervalle, Vergleich der ersten Konfiguration mit den restlichen (k= 2,3, ..), Vergleich aller untereinander (k(k-1)/2), auswhl der besten

Vorgehensweise

• Ziel ist, Aussagen über a treffen zu können.
• Bestenfalls sind liegenden alle Werte mit Wahrscheinlichkeit 1-a in K ermittelten Konfidenzintervalle, umfassen diese den korrekten Unterschied zwischen der ersten und k-ten Konfiguration und wird die beste ausgewählt?

Betrachtung von unterschiedlichen (K) Konfidenzintervallen

• Falls unabhängig: 1 - α = Produkt(1 – αi); Ansonsten muss die Bonferroni-Ungleichung angewendet werden: 1 - α >= max{1 - Summe(αi),0}

Fragen 1-3 mit abhängigen Werten

• Definiere C als die Anzahl der ermittelten Werte und setze αi= α/C.
• Bestimme die individuellen Vertrauensintervalle mit der Signifikanzwahrscheinlichkeit αi.
• Die Signifikanzwahrscheinlichkeit α gilt dann mindestens für das gemeinsame Vertrauensintervall.

Nachteile dieses Vorgehens:

• Bei zu großem C muss α sehr klein sein, was zu breiten Vertrauensintervallen führt oder viele Messungen benötigt werden.

• Die Auswahl ist schwierig und es kann sich zu wenige oder zu viele Elemente im Test befinden.

• Andere Konfigurationen sind Variante 1 und Variante 2

• Parameter wie in Folie 8 beschrieben

Ergebnisse bei Verwendung gemeinsamer Variablen

• Tabelle mit Werten
• Signifikanzwahrscheinlichkeit = 0.05

Ziel: Vergleich der ersten Konfiguration mit allen übrigen Varianten

• Bestimmung der Differenzen mit α=0.05. Konfidenzintervalle ohne gemeinsame Zufallszahlen deutlich größer
• Der Vergleich jeder Konfiguration mit jeder anderen Konfiguration erfordert noch mehr Vergleiche wodurch α weiter gesenkt werden muss, was sehr großen negativen Einfluss auf die Vertrauensintervalle haben wird.

Allgemeine Verfahren zur Rangbildung und Auswahl

• Auswahl von m aus K Varianten, sodass mit einer Wahrscheinlichkeit von p* das beste System gefunden wird.

Notationen

• Erwartung der iten Variante von Mi
• Annahme es gilt Mk>=Mk-1>=..>= M1
• Vi1, Vi2, .. Beobachtungen d.h. Realisierung der ZVs Vij mir E(Vij)=Mi und Var(Vij)=sigmai^2
• Pi= Prob(Vij> max h!=i Vhj)
• Auswahl einer Menge I Teilmenge {1,2,..,K sodass die m besten Elemente mit der WS p* in dem Intervall sind (subset selection)
• Auswahl von I= {K-m,..,K} mit der WS p*, falls Mk-m-Mk-m-1 mind. 8 (Fall m=0 umfasst auch die Auswahl des besten Systems
• Dieser Bereich ist ein sehr aktuelles Forschungsthema, welches viele komplexe Aufgaben mit sich bringt.

Vorgehensweise beim Auswhlen einer Menge I, die mit der Wahrscheinlichkeit 1

• α das beste System enthält.
• Wähle 1 aus, sodass 1/k <1 ist
• Wahl von ni (i=1,..,K) und Durchführung weiterer unabhängiger Replizierungen für das system