Folie 8

Experimentieren mit Simulatoren

• Simulation ist eine Grundlage zur Entscheidungsunterstützung.

Problemstellung

• Systeme können unterschiedlich konfiguriert, organisiert und betrieben werden.
• Die Werte der kontrollierbaren Größen (x_c ∈ W_c) werden festgelegt.
• Das Verhalten wird durch die Werte nicht kontrollierbarer Größen (X_U ∈ W_U) beeinflusst.
• Das Verhalten wird anhand eines Leistungsmaßes y = g(y_p) = g(f(x_c, x_U)) bewertet.
• Ein Simulator ist ein numerisches Modell.
• Die Funktionen g und f sind nicht explizit darstellbar.
• Der Wert von y kann nur für bestimmte Situationen beobachtet werden.

Methodik des Vorgehens

• Situationen werden festgelegt, d.h. die kontrollierbaren Größen (x_c) werden gesetzt.
• Die Ergebnisse werden bei unterschiedlicher Realisierung von X_U beobachtet.
• Die Realisierung des Zufalls ist durch den Saatwert des Zufallszahlengenerators vorgegeben.
• Es wird Experimentieren mit dem Simulator betrieben.
• Ein Design von Experimenten (Versuchsplan) wird benötigt.
• Das Experimentieren ist ein übliches Vorgehen in den Naturwissenschaften.
• Ziele werden definiert.
• Zu untersuchende Konfigurationen werden festgelegt (Experimentplan/Versuchsplan).
• Die Experimente werden durchgeführt.
• Ggf. werden neue Experimente definiert.

Einbettung in das Arbeiten mit Simulationsmodellen

• Hypothese formulieren, die analysiert werden soll.
• Ein Modell bilden, um die Hypothese zu untersuchen.
• Experimente planen, um die Hypothese zu testen.
• Die Experimente durchführen.
• Die Ergebnisse analysieren, ggf. die Hypothese modifizieren und den Prozess wiederholen.

Schritte zur Planung von Experimenten

• Ziele der Experimente definieren.
• Abhängige und unabhängige Variablen klassifizieren.
• Ein zugrundeliegendes Metamodell wählen.
• Ein Experimentdesign (Versuchsplan) wählen.
• Die Eigenschaften des gewählten Designs validieren.

Beispielanwendungen

• Chemische Reaktion: Eingaben sind Druck, Temperatur, Katalysator; Ausgaben sind Menge, Qualität.
• Anbau von Tomaten: Eingaben sind Dünger, Wasser, Saatgut, pH-Wert des Bodens; Ausgaben sind Menge, Qualität.
• Simulation eines Fertigungssystems: Eingaben sind Anzahl Maschinen, Zuverlässigkeit der Maschinen, Auswahlstrategien der Teile, Puffergrößen; Ausgaben sind Durchsatz, Auslastung, Verweilzeiten.

Unterschiede Simulation – reale Experimente

• Beliebige Kontrollierbarkeit auch eigentlich unkontrollierbarer Größen
• Einfache Wiederholung von Experimenten
• Beobachtbarkeit aller Größen

Faktoren und Niveaus

• Beim Experimentieren werden bestimmte Komponenten aus Wc fest eingestellt.
• Andere Komponenten aus Wc werden systematisch verändert.
• Veränderliche Komponenten heißen Faktoren, deren analysierte Werte Niveaus.

Unterscheidung von Faktoren

• Qualitative Faktoren:
  • Können ein Niveau aus einer endlichen Menge von Niveaus annehmen.
  • Sind nicht zwingend geordnet (z.B. unterschiedliche Schedulingstrategien, Winter/Sommer).
• Quantitative Faktoren:
  • Können numerische Werte annehmen (z.B. Regenmenge, Geschwindigkeit, Pufferplätze).
• Größen mit endlichem diskreten Wertevorrat können als quantitative oder qualitative Größen behandelt werden.

Beispielsysteme und Faktoren

• Supermarkt: Faktoren sind Ankunftszeit, Bedienzeit, Anzahl Kassen, Expresskasse.
• Fertigungslinie: Faktoren sind Anzahl Maschinen, Abfertigungsdisziplin, Puffergröße, Maschinengruppe, Geschwindigkeit Förderband.
• Einkaufsstrategie: Faktoren sind Auftragsrate, Auftragsgröße, Lieferzeit, Bestellzeiten, Max. Lagerbestand.

Modell zum Experimentieren

• Das Modell zum Experimentieren ist: y = f(t*, x, s).
  • t*: Zeitpunkt der Resultatbetrachtung.
  • x: Vektor der Einflussgrößen.
  • s: Saatwert(e) des Zufallszahlengenerators.

Typische Fragestellungen

• Welche Situationen (x) sind zu untersuchen?
• Wie viele Replikationen sind für ein x zu beobachten?
• Was kann im Vergleich der Situationen x und x' ausgesagt werden?
• Wie muss man x verändern, um y zu optimieren

Methoden zur Beantwortung

• Die Fragen werden durch Methoden des Experimentdesigns (Versuchsplanung) und der Experimentanalyse beantwortet.

Experimente mit einem Faktor

• Situation: Ein Faktor soll für m verschiedene Werte (Niveaus) untersucht werden
• x_i ist das i-te Niveau des Faktors
• µ_i = f(x_i) ist der zu beobachtende Wert bei Niveau x_i
• Falls f(.) durch ein Simulationsmodell realisiert wird, ist µ_i nur mit statistischen Schwankungen zu beobachten
• Übliches Vorgehen: Beobachte n Replikationen
  • y_{ij} = f(x_i, s_j) für jedes Niveau, wobei die s_j so gewählt sind, dass unabhängige Ströme von Zufallszahlen entstehen
• Ziel: Unterscheidung der statistischen Schwankungen von "wahren" Unterschieden in den Resultaten, insbesondere gilt µ_1 = µ_2 = ... = µ_m?

Vergleich der Mittelwerte

• Für m=2: Methoden aus Kapitel 7 zum Vergleich der Systemkonfigurationen nutzen (d.h. Konfidenzintervall für W = µ_1 – µ_2 bestimmen)

Falls m>2

• Methoden aus 7.2 oder 7.3 verwenden
• Diese sind aber aufwändig, wenn kleine Konfidenzintervalle notwendig sind
• Alternative: Testverfahren
  • H_0: µ_1 = µ_2 = ... = µ_m und H_1: µ_k ≠ µ_l für mindestens ein Paar (k, l).
• Teststatistik:
  • Falls F_0 > F_{α,m-1,nm-m} kann H_0 zum Niveau α verworfen werden.
  • Bedeutet, dass die Niveaus des Faktors einen signifikanten Einfluss haben.
  • F-Test, Werte sind vertafelt.
  • mit µ_i = 1/m Σ_{i=1}^m (1/n Σ_{j=1}^n y_{ij}).
  • F_0 = m(n-1) Σ_{i=1}^m (µ_i - µ)^2 / ((m-1) Σ_{i=1}^m Σ_{j=1}^n (y_{ij} - µ_i)^2)
  • mit µ = 1/m Σ_{i=1}^m µ_i

Experimentdesigns mit wenigen Faktoren

• k (≥ 2) Faktoren mit jeweils m_i (i = 1,...,k) Niveaus, jeweils ein Ausgangsniveau und m_i - 1 weitere Niveaus
• Einfaches Design Simulieren, wobei alle Faktoren auf dem Ausgangsniveau sind
• Pro Experiment genau einen Faktor ändern
• N = 1 + Σ_{i=1,...,k} (m_i - 1) Experimente sind notwendig
• Aber Einfluss der Faktoren ist oft nicht unabhängig, z.B. schnellere CPU + größerer Hauptspeicher in einem PC.

Vollständiges Design

• Alle Kombinationen von Faktorniveaus werden untersucht
• N = Π_{i=1,...,k} m_i Experimente sind notwendig
• Alle Effekte berücksichtigt, aber viele Experimente notwendig

"Curse of dimensionality"

• Simulationslauf inkl. nötiger Replikationen dauert eine Minute
• Dauer eines vollständigen Designs:
  • k=1, m=2: 2 min
  • k=2, m=3: 9 min
  • k=3, m=5: 2 std
  • k=6, m=10: 2 Jahre
  • k=10, m=20: 19290 Jahre
• Intelligente Strategien sind notwendig

Reduktion der Zahl der Experimente

• Zahl der Niveaus reduzieren oft werden nur zwei Niveaus erfasst, die als -1 und +1 bezeichnet werden zum Beginn werden (nicht zu große) Intervalle für Faktorwerte geschätzt und das Minimum und Maximum als Niveaus verwendet
• In iterativen Experimenten können sich die Intervalle ändern (z.B. zur Optimierung)

Reduktion der Zahl der Faktoren

• Zuerst untersuchen, ob ein Faktor überhaupt einen Einfluss auf das Modellverhalten hat (nicht einfach, da Abhängigkeiten existieren)

Teilentwürfe verwenden

• Kompromiss zwischen einfachem und vollständigem Design

Faktordesigns für k Faktoren (Full Factorial Designs)

• Aufzählen aller Vektoren (-1,...,-1), (+1,-1,...,-1),...,(+1,...,+1)
• Änderung der ersten Stelle zuerst
• 2^k Experimente (von 1 bis 2^k nummeriert)
• R_i ist das Resultat des i-ten Experiments (man nutzt hier in der Literatur R_i statt y_i!)
• Experimente für den Fall k=3: Siehe Tabelle

Grafische Darstellung von Full Factorial Designs

• Siehe Abbildungen

Effekte

• e_i sei der Effekt von Faktor i
• Diese Effekte für i=1,2,3 werden auch als Haupteffekte bezeichnet

Haupteffekte

• Haupteffekte beschreiben durchschnittliche Änderung des Resultats, wenn Faktor i von -1 nach +1 wechselt und alle anderen Faktoren unverändert bleiben

• Neben den Haupteffekten (= Einfluss eines einzelnen Faktors) treten Nebeneffekte durch die Interaktion von zwei oder mehr Faktoren auf

Messung der Interaktion zwischen zwei Faktoren i und j

• Hälfte der Differenz zwischen dem mittleren Effekt von Faktor i, wenn Faktor j das Niveau +1 hat (alle anderen Faktoren konstant) und wenn Faktor j das Niveau -1 hat (alle anderen Faktoren konstant)

Interaktionen höherer Ordnung

• Interpretation von Interaktionen höherer Ordnung ist schwieriger, kann aber mathematisch analog definiert werden!

Interaktion zwischen drei Faktoren h, i und j

• Hälfte der Differenz zwischen der durchschnittlichen Interaktion zwischen h und i, wenn j Niveau +1 hat und der Interaktion zwischen h und i, wenn j Niveau -1 hat (wie vorher werden weitere Faktoren konstant gehalten)

Eigenschaften

• Konzept auf weitere Interaktionen erweiterbar
• Kompakte Darstellung der Interakti-onen in der Designmatrix

Betrachtung des Falls k=

• Siehe Designmatrix

Anzahl der Effekte bei k Faktoren

• k Haupteffekte
• (k über 2) Nebeneffekte der ersten Ordnung
• (k über 3) Nebeneffekte der zweiten Ordnung
• Insgesamt 2^k - 1 Effekte
• Jedes Experiment entspricht Simulationslauf
• Stochastische Schwankungen in den Ergebnissen sind zu erwarten

Verbleibende Fragen

1. Wie geht man mit stochastischen Schwankungen in den Resultaten um?
2. Haben alle Faktoren und Effekte wirklich einen Einfluss?
3. Wie behandelt man große Faktorzahlen?
4. Welche Faktoren sind besonders wichtig?

Verbleibende Fragen

• Punkte 3 und 4 werden in den Abschnitten 8.4 und 8.7 behandelt.
• Übliches Vorgehen bei stochastischen Schwankungen:
  • Mehrere Replikationen pro Faktorkombination
  • Resultate als Mittelwerte der Replikationen
  • Schätzung der Varianz zur Beurteilung der Qualität der Resultate

Vorgehen zur Berechnung von Konfidenzintervallen

• Es werden n Replikationen für jede Faktorkombination durchgeführt.
• R_i² das Resultat der i-ten Faktorkombination in der z-ten Replikation ist.
• e_j² der ermittelte Haupteffekt für Faktor j in der z-ten Replikation ist.
• Mit dem Konfidenzintervall ê_i ± t_{n-1,1-α/2} · √(S²(ê_i) / n).

wichtige Anmerkungen

• Die einzelnen Konfidenzintervalle sind nicht unabhängig!
• Bestimmung simultaner Konfidenzintervalle erfordert:
  • Nutzung von unabhängigen Replikationen pro Effekt (unrealistisch) oder besser.
  • Nutzung der Bonferroni-Ungleichung.

Beispiel

• Ankunftsstrom Poisson mit Rate 1.333.
• Bedienzeiten exponentiell verteilt mit Mittelwert 1.0.
• B Pufferplätze (Kosten pro Platz 0.15), Bediener s (Kosten pro Bediener 0.25)

Zielfunktion

• Zielfunktion f(b,s) = Durchsatz / (1 + 0.15b + 0.25s).
• Niveaus b ∈ {2,3} und s ∈{1,2}.
• Analyse per Simulation.
• Jeweils 5 unabhängige Replikationen.
• Länge einer Replikation 1100 Zeiteinheiten.

Ergebnisse

• Durch eine Analyse der Ergebnisse kann unter anderem die Abdeckung des simultanen Konfidenzintervalls bestimmt werden.

Behandlung großer Faktorzahlen

• Die Anzahl der auszuführenden Experimente wächst schnell mit wachsender Faktor- und Replikationszahl.
• Experimente sind kaum noch durchführbar (auch bei Nutzung paralleler Hardware).
• Unwichtige Faktoren aussortieren.
• Weniger als n 2^k Experimente bei k Faktoren durchführen.

Was bedeutet es, weniger Experimente durchzuführen?

• Anzahl Replikationen sollte nicht verringert werden
• Nicht alle möglichen Faktorkombinationen analysieren
• Entwicklung von 2k-p Designs d.h. die Anzahl der Experimente wird um den Faktor 1/2p reduziert Es werden gewisse Faktorkombinationen weggelassen

Beschreibung eines Designs

• Geschieht durch eine Designmatrix D
• Enthält pro Experiment eine Zeile
• Enthält pro Faktor eine Spalte Vollständiges 23 Design

Um die Berechnungen durchzuführen

• Möchte man ein orthogonales Design haben, d.h. die Spalten der Designmatrix sind paarweise orthogonal Weiterhin wird gefordert, dass die Summe der Elemente in jeder Spalte 0 ist

Konstruktionsvorschrift

• Generiere ein 2(k-p) Design
• Ordne die fehlenden Haupteffekte den Spalten des Designs zu damit lassen sich unterschiedliche Designs einfach realisieren die Spalten der Designmatrix bleiben paarweise orthogonal verschiedene Effekte werden identischen Spalten zugeordnet (dies ist beim vollständigen Design nicht der Fall!)

Beispiel eines 24-1 Designs

• Siehe Tabelle
• Der Effekt beschreibt also eigentlich e4+e123 Formeln für weitere Effekte:
• e1 = 234; e3 = 124; e12 = 34; e23 = 14
• e2 = e 134; e4 = 123; e13 = 24; 1 = 1234

Vermengung von Effekten

• Liegt vor wenn die Effekte nicht einzeln bestimmt werden können

• Berechnung der Vermengung von Effekten: Effekte werden mit Großbuchstaben bezeichnet und durch die Spalten der Matrix beschrieben

• AB sei die komponentenweise Multiplikation der Vektoren, d.h. AB wird durch dAB(x)= dA(x)·dB(x) beschrieben

• Die komponentenweise Multiplikation ist kommutativ Neutrales Element ist 1

Vermengung

• AB und CD sind vermengt, falls dadB=dcdp gilt Es gilt immer A² = 1 sowie A1=1A=A und damit auch AB²C = AC
• Ein Generator ist eine Menge von disjunkten Elementen, in vollständigem Design gibt es keinen Generator.
• Erzeugung von Generatoren auf Basis der identischen Spalten in Aus den Generatoren sind alle Vermengungen berechenbar

Auflösung eines Designs

• Die Auflösung gibt an, welche Effekte nicht vermengt werden.
• Es gilt p+q < 4, also sind in einem Design der Auflösung IV keine Effekte der Ordnung p und q mit p+q < 4 vermengt Haupteffekte (Ordnung 1) nicht untereinander und auch nicht mit Nebeneffekten der Ordnung 2 vermengt, Nebeneffekte der Ordnung 2 sind dagegen vermengt.
• Das Design hat Ordnung IV Wenn der k-te Faktor mit dem Nebeneffekt der Faktoren 1 bis k-1 vermengt ist, hat das Design Auflösung k

Anhaltspunkte zur Konstruktion von Designs

Der Einheitsvektor sollte mit Effekten höherer Ordnung vermengt werden Haupteffekte sollten nur mit Effekten höherer Ordnung vermengt werden

• In beiden Fällen ist Annahme, dass die Effekte höherer Ordnung vernachlässigbar sind
• Falls angenommen werden kann, dass bestimmte Nebeneffekte bedeutsam sind, so sollten diese nur mit Effekten höherer Ordnung vermengt werden
• Ein Design höherer Ordnung ist i.d.R. besser

Einige Designs

• siehe Tabelle

Weitere Experimentdesigns

• bisher vorgestellte Designs untersuchen jeweils Fakroren mit den Werten -1 und 1
• bei Parametern bedeutet dies, dass jeweil der kleinste und größte Wert des Intervalls gewählt wird
• es kann gezeigt werden, dass für die Anpassung von linearer Regressionsmodellen diese Auswahl optimal ist trotzdem haben diese Designs auch Nachteile mit kontinuierlichen Parametern gearbeitet wird, da Nivoes für Faktoren a priori definiert sein müssen

Zufälliges Design

• Intervallee für einzelne Faktoren werden auf normiert
• bei Faktoren und Experimenten werden Zufallszahlen aus [0,1]k gezogen

Verteilung

• unabängig und gleichverteilt in allen Dimensionen oder
• bzgl. vorgegebener Verteilungen (Parameterschätzung ist bekannt)

An jedem Designpunkt

• wird entweder eine feste Anzahl von Replikationen durchgeführt
• oder simulieren so lange, bis eine vorgegebene Varianz erreicht wird

Nachteil des zufällugen Designs

• bei hoher Dimension werden große Bereiche des Parameterraums nicht untersucht Alternative sind geschichtete Stichproben

Geschichtete Stickproben

• Unterteilung des [0,1]k in gleich große Unterräume [1;,u;]k
• Zufällige Auswahl je eines Punktes aus jedem Unterraum Verschiedene Varianten existieren
• Gleichverteilte unabhängige Auswahl in jeder Dimension, Auswahl bzgl. vorgegebener Verteilung, Unterschiedliche Anzahl der Designpunkte in den Unterräumen

Latin Hypercube Design

• Verteilung der Designpunkte im Raum soll erreicht werden
• Vorgehen am Beispiel von Dimensionen und n Experimenten:
• Unterteile jede Dimension in gleich große Intervalle
• Es entsteht ein Gitter mit Zellen
• Verteile die Buchstaben so auf die Zellen

Algorithmus

• Wähle einen Buchstaben
• Bestimme zufällig je einen Designpunkt in jeder zum Buchstaben gehörigen Zelle

Eigenschaften

• Die Anzahl der möglichen Designs ist immens
• Designs können von sehr unterschiedlicher Qualitäts ein
• Ziel das ist Designpunkte möglichst gleichmäßig in der Fläche verteilt sind
• Maß: ( Distanzmaß/Norm, xi Designpunkt) maximal sein

Verallgemeinerung auf Dimensionen

• Unterteile jede Dimension in Intervalle gleicher Größe Jede Zelle ist durch ganzzahlige Werte spezifiziert die Projektion einer Zelle
• Wähle für das Design Zellen, so dass für Dimension die Projektionen der ausgewählten Zellen die Werte liefert
• Wähle aus jedem Intervall zufällig einen Punkt Ist die ist Erzeugung eines space filling Designs exsitieren Datenbanken mit Designs

Metamodelle

• Ziel der Die Metamodellbildung ist die Herstellung eines einfachen Zusammenhangs zwischen den Faktorwerten und der abhängigen
• Anforderung an Metamodelle: Einfache Handhabung und Analyse und Genaue Approximation
• Oft lineare Regressionsmodelle oder Korrelationmodelle

Idee der Metamodellbildung

• Modell mit Faktoren
• Stochastisches Simulationsmodell ỹ = f(x)
• Eigentlich y = f(x, s) mit Saatwert s deterministisch
• ỹ ist Schätzwert des Resultats
• Metamodell h(x); h(x) ist einfacher

Lineares Regressionsmodell

• einfachste Funktion: y = βο + B1x1 + ... + Bkxk+ €
• ist die abhängige Variable (Antwort) x sind die Faktorwerte Β sind Reversionskeoeffizienten ist Fehler

Annahme Normalverteilung

• Modellgenerierung:
• Unterschiedliche Variable untersuchen
• Eine passende Reversionsgleichund finden

Modell

• Durchführung von Gleichungen
• Ziel: so wählen, dass minimal wird
• D.h. so wählen, dass partielle Ableitungen werden

Daraus ergibt isch diese vereinfachtung

• Lineare Algebra zur Hilfe nehmen
• Konfidenzintervalle für Paramter berechnen
• Testen, ob 0 in den Paramterintervallen liegen

Weitere Aspekte des Experimentdesigns

Anzahl der unterschiedlichen Designpunkte sollte größer als die Anzahl der Variablen sein

• Simulationsexperimenten sollten Resultate in der Regel Mittelwerte mehrerer Beobachtung
• der Nutzung statistischer Verfahren sollten Replikationen für Designpunkte aufgenommen werden
• Hinzunahme eines Punktes im kann sinnvoll sein

Grundannahme der Parameter Varianz ist

• Die Annahme ist aber falsch
• Also die Parameterschätzungen der Ausreisser verringern

Alternative Metamodelle : Kriging-Modell

Ursprünglich aus der Geophysik zum Aufspüren von Goldvorkommen

Exakte Resultate für analysierte Punkte (bei stochastischen Modellen des geschätzten Wertes!)

• für die
• Ausweitung
• Sequentielle Verbesserung /Experimentieren

8.7 Auswahl relevanter Faktoren und Faktorkombinationen

• Situation in vielen praktischen Experimenten Es gibt eine Vielzahl von Faktoren (oft mehr als hundert), deren Bedeutung unklar ist

• so dass nur ein Teil der Faktoren ausreichen würde, um die gewünschten Effekte zu beschreiben Wie können relevante Faktoren von nicht relevanten unterschieden werden