Simulationsstatistik und Optimierung Flashcards
Wann verwendet man Zufallsvariablen?
- Zur Modellierung stochastischer Prozesse und deterministischer Prozesse, deren Determismen zu komplex für die Abbildung im Modell sind (Idealisierung).
- Zufallszahlen zur Realisierung von Zufallsvariablen
Wie werden Zufallszahlen erzeugt ohne physikalische Prozesse?
Durch künstlich (deterministisch) erzeugte Pseudo-Zufallszahlen als Alternative.
- näherungsweises Folgen der gewünschten Verteilung
- stochastische Unabhängigkeit
- Abwesenheit von Häufungspunkten
Wie ist die Formel der linearen Kongruenzmethode?
Vier Parameter: Modulus m, Multiplikator a,
additive Konstante c, Initialwert x 0
X n+1 = (a*Xn+c) mod m
Wie sollte man die Parameter bei der linearen Kongruenzmethode wählen?
-m bestimmt die maximale Periodenlänge, d.h. m sollte möglichst
groß gewählt werden, z.B. m = 2 32 -1 bei einer 32 Bit-
Zahlendarstellung
-c sollte relative Primzahl zu m sein, d.h. der größte gemeinsame
Teiler von m und c ist 1, während a-1 als ein Vielfaches jeder
Primzahl gewählt werden sollte, durch die m teilbar ist
Zufallszahlen erzeugen welch Methoden?
- Verteilungsfunktion
- Dichtefunktion
-> dann durch inverse Transformation Zufallszahlen gemäß der vorgegebenen Verteilung
Welche Methoden der Datenerfassung gibt es?
Primäre Erfassung:
- Interviews
- Fragebögen und Reports
- Beobachtung
Sekundäre Erfassung:
-Analyse von Dokumenten und Inventar
In welche Daten unterscheidet man?
Lastdaten:
- Aufträge
- Produkte
Organisatorische Daten:
- Arbeits- und Schichtpläne
- Verfügbare Ressourcen
- Steuerung der Produktion
Technische Daten:
- Räumliche Verteilung der Ressourcen
- Leistungsdaten der Produktion
- Ausfälle
Wie schätzt man die Verteilung von Zufallsvariablen?
- es gibt viele Zufallsprozesse im Simulationsmodell
- aus vorhandenen Datenmaterial dann geeignete statistische Verteilungen ableiten (theoretische Verteilungstypen bevorzugen, beschreibende Statistik zur Darstellung)
- Analyse der Realisation der Zufallsvariablen
Wie erfolgt die Analyse der Realisation der Zufallsvariablen?
Fall 1: Daten passen zu keinem bekannten Verteilungstyp
Fall 2: Unterstellung eines bestimmten Verteilungstyps
->Anpassungstest durchführen, unbekannte Wahrscheinlichkeitsverteilung einer Zufallsvariablen auf Folgen einer bestimmten Verteilung testen
Wie erfolgt der Anpassungtest Chi-Quadrat Test?
- Stichprobe der Größe n
- Sitchprobe in m Klassen K1..Km (m
Woran könnte eine Simulation “leiden”?
- Anfangszustand und Anlaufphase
- Stationäre Prozesse (Eigenschaften zeitinvariant, hängen nicht von t ab)
Wie sollte man bei einer Simulation mit dem Anfangszustand und Anlaufphase umgehen?
- transiente Anlaufphase sollte in statistischer Auswertung der Simulationsergebnisse nicht berücksichtigt werden (Problem: ab wann nicht berücksichtigen), wird häufig visuell abgeschätzt
- Anfangszustand möglichst “gut” wählen, Ziel ist kurze Anlaufphase
- Abschneiden 2 Möglichkeiten: Solange jeder Wert Extremum ist (Conway Regel) oder Zum n-ten Überqueren des Mittelwerts
Wie erfolgt eine Punkt- und Intervallschätzung?
->Stichproben-Mittelwert („Punktschätzung“) als Schätzer für den
Erwartungswert der Variablen
-Keine Aussage über Schätzgenauigkeit bzw. Schätzzuverlässigkeit;
Mittelwert allein also kaum aussagefähig
-Zusätzlich ist folglich eine Intervallschätzung erforderlich:
z.B. in Form eines Konfidenzintervalls
Wie berechnet man einen Konfidenzintervall?
- Konfidenzniveau 1-α gegeben
- Stichprobe mit N Realisationen x1…xN von X gegeben
- Erwartungswert und Standardabweichung berechnen
- dann Konfidenzintervall des Erwartungswert abschätzen
Was sind transiente Prozesse?
- Zustand zeitvariant
- typische Analysen beziehen sich nur auf die Zeitdauer bis ein (Makro-)Zustand erreicht wird oder wie lange das System in einem Zustand verweilt, z.B.
- Dauer von Boarding bei Flug
- Wann löst sich der Stau auf?
Was sind stationäre Prozesse?
- Zustand zeitinvariant
- Analyse des (Mikro-)Zustandes in der stationären Phase möglich, z.B.
- mittlere Warteschlangenlänge oder Wartezeiten
- Aufenthaltszeiten
- Durchsatz
Wie kann man Simulationen optimieren?
- Simulationen leisten per se keine Optimierung
- Auswahl guter Modellparameter im Rahmen von parametrischen Simulationsexperimenten, Erstellung von Versuchsplänen für systematische Simulationsexperimente, z.B. durch Faktor Design
Was ist das Ziel vom Faktor Design?
Einfluss unterschiedlicher Parameter unabhängig betrachten, einschließlich insbesondere gemeinsamer Wirkung (z.B. “Synergien”)
Wie funktioniert das Faktor Design?
-Auswahl von k Parametern, Wert kann unabhängig gwählt werden
-Zuweisung von 2 signifikant unterschiedlichen Werten
2^k Experimente nötig
Ist es sinnvoll mithilfe des Faktor Design zu optimieren?
Faktor-Design ist keine Optimierungsmethode:
Es bleibt (wie bei der Simulation allgemein) bei der Bewertung
vorher feststehender Parameterkombinationen,
es erfolgt keine „Suche“ mit Ermittlung möglichst optimaler
Parameterkombinationen
Wie lautet bei Simulation das informale Optimierungsproblem?
- optimale Parameterkonfiguration (Lösung) aus der Menge aller möglichen Parameterkonfigurationen (zulässigen Lösungen)bestimmen
- optimal, dass eine Zielfunktion für keine ander Parameterkonfiguration einen höheren Wert annimmt
Wie lautet bei Simulation das formale Optimierungsproblem?
-Modell Ψ
-Lösungsraum L, der die für das Modell Ψ zulässigen
Parameterkombinationen (“zulässigen Lösungen”) enthält
-Zielfunktion f : L -> R als Maß der Güte zulässiger Lösungen l ε L
Wie funktioniert Simulationsoptimierung?
- Kombination von Simulation und einem Optimierungsverfahren
- Systemverhalten über Zielfunktion bewerten
Wann setzt man Simulationsoptimierung ein?
-nicht-exaktes Lösungsverfahren, laufzeitintensiv
Sinn von bei den Bedingungen:
- Großer bzw. unendlicher Lösugsraum(Rechenaufwand für alle Lösungen zu groß)
- Identifikation des globalen Optimums nicht zwingend bzw. Kein Beweis der globalen Optimalität einer Lösung notwendig(hinreichende Lösung reicht)
- viele lokale Optima, unregelmäßige Struktur des Lösungsraums
Was sind die Auswahlkriterien einer Software zur Simulationsoptimierung?
- Optimierungsmethode auswählen (Möglichkeit der Modifikation, Nebenbedingungen, Abbruchregeln)
- Durchführung der Optimierung (Rechenlast, Speichermöglichkeit, Darstellung)
- Auswertung (Konfidenzintervalle berechnen, Alternativen darstellen)
Was sind genetische Algerithmen?
-Ansatz: Ein Pool von „Individuen“ (also zulässigen Lösungen) wird
einem der biologischen Evolution nachempfundenen Prozess
ausgesetzt …
-Anfagspopulation erzeugen und bewerten
-dann Nachkommen(Selektion und Rekombination)
-dann Mutation und Erzeugung neuer Population
-Wiederholung bis optimierte Lösung
-dann Ausgabe beste Individuen
Wie funktioniert die Selektion bei genetischen Algorithmen?
Fitnessproportional:
-Standardansatz: „Fitte“ Individuen werden
bevorzugt, aber weniger „fitte“ Individuen
haben eine gewisse Selektionschance
Rangselektion -Feste Wahrscheinlichkeiten für Selektion des nach Sortierung nach „Fitness“ besten, zweitbesten, drittbesten... Individuums
Turnierselektion:
-Selektiere das beste Individuum bzw. unter
den besten Individuen einer Subpopulation,
etwa mit zufälliger Auswahl oder nach
spezifischen Kriterien
Teilselektion:
-Weniger „fitte“ Individuen ausschließen
(schnellere Konvergenz auf Kosten von Vielfalt und
damit von Optimalität)
Wie funktioniert die Rekombination bei genetischen Algorithmen?
Diskretes Crossover:
-Übernahme des Genotyps teil von der Mutter, teils vom Vater
Kontinuierliches Crossover:
-Linie, intermediär
Modifikation:
-Kreisförmige Chromosomen
Wie funktioniert die Mutation bei genetischen Algorithmen?
-zufällige Veränderungen des Genotyps
-Ziel: Eigenschaften, die anfangs nicht
im Genpool vorhanden sind (bzw. nicht
aus der Anfangspopulation erzeugt werden können) sollen dennoch erzeugt werden
-Mutation erzeugt potentiell Lösungen, die nicht zulässig sind, wenn möglich “Reperatur” sonst Verwerfung
Wie kann man genetische Algorithmen noch erweitern und verallgemeinern?
- Vererbung und Erzeugung von Nachkommen (mehr als 2 Eltern, isolierte Populationen)
- genetische Operatoren selbst einer evolutionären Entwicklung aussetzen(z.B. Mutationswahrscheinlichkeit anpassen)
- genetische Programmierung, Struktur der Chromosomen wird einer Evolution unterworfen
Was sind typische Probleme beim Einsatz von genetischen Algorithmen?
- Wahl bzw. Parametrisierung der genetischen Operatoren
- tendenziell laufintensiv
- Rechenbedarf kann verringert werden, durch z.B. Fokus auf Evolution von “Hotspots” mit größtem Einfluss auf “Fitness”
Was sind die Vorteile und Nachteile genetischer Algorithmen?
Vorteile:
- für verschiedenste Anwedungsbereiche geeignet
- robust bzgl. Parametrisierung und Design der genetischen Operatoren
- findet strukturell-unterschiedliche Lösungen
Nachteile:
- Optimalität nicht garantiert
- rechenaufwändig
