Folie 1

Modellierung, Simulation und Analyse

• Peter Buchholz ist der Dozent für Informatik IV.
• Die Vorlesung ist Teil des Studiengangs "Praktische Informatik – Modellierung und Simulation".

Einordnung und Historie

• Die Vorlesung ist ein Vertiefungsmodul zur Behandlung komplexer technischer Systeme (z. B. eingebettete und verteilte Systeme).
• Basiert auf der Wahlpflichtvorlesung Modellgestützte Analyse und Optimierung (MAO) im Bachelor.
• Ergänzt das Basismodul Modellierung und Analyse eingebetteter und verteilter Systeme (MAevS).
• Kenntnisse über Modelle, Simulation, Stochastik/Statistik und Programmierung sind erforderlich.

Inhalte der Veranstaltung

• Ereignisdiskrete Simulation: Grundlagen, Realisierung und Anwendung z.B. auf Computernetze mit OMNeT++.
• Modellierung mit verschiedenen Ansätzen (AnyLogic).
• Simulation kontinuierlicher und hybrider Systeme.
• Effizienzsteigerung für diskrete Simulationen, Parallelisierung und Behandlung seltener Ereignisse.
• Experimentieren mit Simulatoren und Optimierung mittels Simulationsmodellen (stochastisch/deterministisch).

Organisation

• Die Lehrveranstaltung umfasst Vorlesungen (3 SWS) und Übungen (1 SWS), was insgesamt 4+2 CP entspricht.
• Montags werden bei Bedarf zusätzliche, zweistündige Übungen angeboten.
• Die Übungen sind zum Teil praktisch und erfordern einen relativ hohen Aufwand (Softwareinstallation, Einarbeitung in Werkzeuge, Erstellung von Modellen).
• Es findet eine mündliche Prüfung statt, die über das Sekretariat ([email protected]) vereinbart wird.
• Die Termine werden online bekannt gegeben.

Weitere Informationen

• Die Inhalte der Vorlesung können mit weiteren Vorlesungen aus dem Forschungsbereich "Eingebettete und verteilte Systeme" kombiniert werden.
• Dient als Grundlage/Ergänzung für Projektgruppen und Masterarbeiten.
• Themen für Masterarbeiten sind immer verfügbar.

Literaturhinweise

• Vorlesungsbegleitende Folien sind online verfügbar.
• A.M. Law, Simulation Modeling and Analysis, McGraw Hill (2015).
• Bungartz et al., Modellbildung und Simulation, Springer (2013).
• Kleijnen, Design and Analysis of Simulation Experiments, Springer (2008).
• Myers, Montgomery, Response Surface Methodology, Wiley (2002).
• Santner et al., The Design and Analysis of Computer Experiments, Springer (2003).
• Borshchev, Big Book of Simulation Modeling – Multimethod Modeling with AnyLogic 6, AnyLogic (2013).
• Einführung in OMNET++ (www.omnetpp.org).
• Diverse Artikel (Angaben in den jeweiligen Kapiteln).

Gliederung (Themenübersicht)

• Einführung und Wiederholung (3 + 2 Ü).
• Simulation von Computernetzen (inkl. OMNeT++) (3 + 1 Ü).
• Hybride Modellbildung & hybride Simulation (inkl. AnyLogic) (4 + 2 Ü).
• Parallele Simulation (2).
• Simulation seltener Ereignisse (1 + 0.5 Ü).
• Vergleich von Systemkonfigurationen (2 + 0.5 Ü).
• Experimentieren mit Simulatoren (4 + 1 Ü).
• Optimierung von Simulationsmodellen (3).
• Resümee (1).

Geplante Übungstermine

• 15.10.2024: Analytische Berechnungen für einfache Modelle.
• 22.10.2024: Grundlagen der Simulation.
• 05.11.2024: OMNET++.
• 19.11.2024: AnyLogic System Dynamics.
• 26.11.2024: AnyLogic WS.
• 17.12.2024: Vergleich von Systemkonfigurationen.
• 14.01.2025: Experimentieren mit Simulatoren.

Formale Darstellung eines Systems

• Ein System hat kontrollierbare Eingaben (C), unkontrollierbare Eingaben (U) und beobachtbare Ausgaben (P).
• Das Verhalten des Systems wird durch eine Funktion f: Wc × WU → Wp oder eine Relation zwischen Eingaben und Ausgaben beschrieben.
• Die wesentlichen Ziele sind, f zu verstehen und den Einfluss von C und U auf P zu nutzen.

Analyse durch Modellierung

• Der Fokus liegt auf dem dynamischen Verhalten von Systemen (Verhalten im Zeitverlauf).
• Analyse durch direkte Beobachtung ist oft aufwendig, teuer oder unmöglich.
• Stattdessen wird ein Ersatzsystem, ein Modell, analysiert.

Definitionen

• Niemeyer: Modelle sind materielle oder immaterielle Systeme, die andere Systeme so darstellen, dass eine experimentelle Manipulation der abgebildeten Strukturen und Zustände möglich ist.
• Cellier: Ein Modell M für ein System S und ein Experiment E ist ein System S', auf das E angewendet werden kann und Aussagen über die Anwendung von E auf S erlaubt.

Struktur dynamischer Modelle

• Statische Struktur: Abbildung des Systemzustands auf Zustandsvariablen (diskret, kontinuierlich, ein-/mehrdimensional).
• Dynamische Struktur: Abbildung der Zustandsänderungen auf Berechnungsvorschriften (kontinuierlich, abrupt, deterministisch, stochastisch).
• Qualitative Beschreibung: Wirkungszusammenhänge zwischen Zustandsgrößen, Abstraktion von konkreten Zeitpunkten.
• Quantitative Beschreibung: Exakte numerische Darstellung der Dynamik über die Zeit.

Qualitative Darstellung von Abhängigkeiten

• Wirkungsgraphen: Abstrakte Spezifikation von Zusammenhängen in den ersten Phasen der Modellierung.
• Es werden nur qualitative Informationen dargestellt (A größer -> C größer), keine mathematischen Relationen.

Formale, quantitative Modelle

• Diese Modelle können auf einem Computer analysiert werden.
• Simulationsmodelle bilden den zeitlichen Ablauf im Computer nach.
• Analytische Modelle sind mathematische Modelle des Systems.
• Vorteile: Alles ist kontrollierbar, Experimente sind wiederholbar, der Detaillierungsgrad ist wählbar.
• Allerdings: Das Modell ist nicht die Realität, Modellierung ist oft mehr Kunst als Technik, Modellanalyse kann aufwendig sein.

Ansätze zur Modellbildung

• Black-Box-Sichtweise: Modellbildung auf Basis des beobachteten Verhaltens am Ausgang (in Abhängigkeit vom Eingang), induktives Vorgehen.
• White-Box-Sichtweise: Modellbildung auf Basis der Systemstruktur, deduktives Vorgehen.

Abstraktionslevel

• Die Anwendung bestimmt den Detaillierungsgrad: vom strategischen (hoher Abstraktionsgrad, wenige Details) zum operativen Level (maximaler Detailgrad).

Dynamische Modelle - wichtige Unterteilung

• Zeitdiskret: Zustandsvariablen ändern sich in festen Zeitabständen, atomare Änderung, deterministisch/stochastisch.
• Ereignisdiskret: Zustandsvariablen ändern sich durch Ereignisse, atomare Änderung, deterministisch/stochastisch bzgl. Nachfolgezustand und Verweilzeit.
• Kontinuierlich: Zustandsvariablen ändern sich kontinuierlich; Zustandsänderungen in Abhängigkeit vom aktuellen Zustand; meist deterministisch.

Deterministische Modelle

• Für feste Modellparameter ist der Ablauf festgelegt; ein Durchlauf liefert die Ergebnisse.
• Parameter werden durch Messungen oder Schätzungen festgelegt.
• Die Realität ist oft nicht deterministisch.
• Physikalische Phänomene (freier Fall), hardwarenahe Berechnungen können deterministisch sein.

Stochastische Modelle

• Auch für feste Modellparameter ist der Ablauf nicht festgelegt, es gibt unkontrollierbaren Zufall.
• Der Zufall wird im Rechner durch Pseudozufallszahlen realisiert (deterministisch bei bekannter Realisierung).
• Bewertung erfordert mehrfaches Beobachten, statistische Auswertung oder Analyse des stochastischen Verhaltens (aufwändig oder unmöglich).
• Detaillierte Analyse erfordert oft stochastische Modelle.

Modelltypen

• Für dynamische Systeme gibt es mathematische Modelle.
• Stochastisch: Markov-Prozesse, stochastische Prozesse (beide zustandsdiskret, Basis für diskrete Simulation)
• Deterministisch: Differenzengleichungen und (lineare/nichtlineare) Differentialgleichungen (Basis für kontinuierliche Simulation)
• Kombination: hybride Simulation.

Kontinuierliche Systeme

• Elektronische Schaltungen und System Dynamics können als Beispiel dienen.
• Modelliert durch gewöhnliche Differentialgleichungen (ODEs).
• Gewöhnliche Differentialgleichungen berücksichtigen Abhängigkeiten über die Zeit; partielle zusätzlich Abhängigkeiten in Zeit und Raum.
• Die Lösung ist in der Regel numerisch, oft durch angepasste Diskretisierung.
• Sie werden grafisch durch Spezifikationen von Wirkungszusammenhängen dargestellt

Ereignisdiskretes Modell (Bediensystem)

• Objekte: Kunden, Bedieneinrichtung, Warteschlange.
• Attribute: Ankunftszeiten, Bedienzeiten, Kundenzahl.
• Attributänderungen: bei Ankunft (Bediener belegen, Kundenzahl + 1), bei Bedienende (nächster Kunde, Kundenzahl - 1).

Diskrete Systeme (Modelltypen)

• Modelliert als Warteschlangennetze mit Clients, LAN, Router und externen Servern.
• Bedienwünsche/Routen werden durch Zufallsvariablen beschrieben.
• Bedienkapazität durch Schedulingstrategie definiert.
• Aufträge mit identischem Verhalten werden in Klassen zusammengefasst.

Modellierungsansätze

• Dazu gehören anwendungsnahe Spezifikationen und zugehörige Werkzeuge.

Sichtweisen der Vorlesung

• Es wird Modellierung und Analyse-Simulation betrachtet
• Der Fokus liegt auf Optimierung, Kopplung unterschiedlicher Systeme (diskrete und kontinuierliche Simulatoren) sowie Effizienzsteigerung von Simulationsläufen.

Vorgehensweise

• Der Prozess beinhaltet die Beobachtung von realen Phänomenen, Erstellung eines konzeptuellen Systemmodells, mathematischen Modells und formalen Modells.
• Experimente und der Einsatz von Simulatoren führt zu Modellergebnissen und zur Realisierung, Effizienzsteigerung und Optimierung.

Modellanalyse

• Die Analysemöglichkeiten werden durch Modelltypen bestimmt.
• Es gibt analytische- und Simulationsmodelle
• Es gibt determinatistiche und stochastische Modelle

Analytische Modelle

• Sie berechnet die Lösung in geschlossener Form, kann aber dennoch aufwändig sein (z.B. lineare Gleichungssysteme).
• Sie ermöglicht es, das zeitabhängige Verhalten nur in einfachen Fällen nachzubilden, aber auch stationäre Verhaltens/Zustände zu bestimmen (i.d.R. durch Lösung linearer Gleichungssysteme).

Warteschlangennetze

• Die Analyse verwendet Ankunftsraten (λ) und Bedienungsraten (μ).
• Operational wird das Ziel verfolgt, die mittlere Population, Auslastung, Verweilzeit der Aufträge zu bestimmen,

Einzelne Stationen

• Wichtige Größen zur Auslastung (ρ=λ/μ<1), Bedienzeit (E[S]=1/μ), Wartezeit (W), Verweilzeit (R=S+W), Durchsatz (E[X]=λ, falls λ<&mu) und Population (N).
• Das Gesetz von Little besagt: E[ɴ]=E[X]⋅E[R].
• Bei exponentiell verteilten Zwischenankunfts- und Bedienzeiten wird z.B. die Exponentialverteilung mit Parameter λ>0 verwendet.

Ankunfts- und Bedienzeiten

• Die Gedächtnislosigkeit der Exponentialverteilung ist wichtig.
• Das Minimum parallel laufender Exponentialverteilungen mit Raten μ und λ wird z.B. berechnet.

Darstellung des Ablaufs

• Der Ablauf wird dargestellt als Zustandsraum mit Kunden im System (M/M/I-System).
• Das System befindet sich im stationären Gleichgewicht.

Realitätsnähe Exponentialverteilung

• Exponentiell verteilte Ankunfts- und Bedienzeiten sind nicht immer realistisch, da sie Gedächtnislosigkeit bedingen.
• Gründe hierfür sind z.B. Mindestzeiten, Schwankungen um den Erwartungswert und alterungsabhängige Fehler.

Exponentielle Zwischenankunftszeiten

• Die exponentiell verteilten Zwischenankunftszeiten sind nicht immer selbstverständlich.
• Ankünfte jeder Minute, Bedienzeit 59 Sekunden (beides konstant)

###Exponentielle

• Die Modellierung wird durchgeführt durch Zwischenankunfts-, Bedienzeit-, Ausfall- und Reparaturzeiten auf Basis von Annahmen des zugehörigen ZVs .
• Direkte Nutzung von Daten ist durch einen trace-getrieben Simulation möglich.

Pseudozufallszahlen

• Die Nutzung von Pseudozufallszahlen erfolgt anhand eine Algorithmus dessen Ausgaben ohne Kenntnis des Algorithmus zufällig aussehen.
• Dieses ist leicht integrierbar, durch Änderung des Startwertes und reproduzierbar

Software

• Pseudozufallszahlenerzeugung erfolgt durch z.B. lineare Kongruenzgeneratoren
• Die Tests erfolgen anhand statistischer Verfahren

Die Simulation

• Eine kontinuirliche Simulation ist z.B. deterministisch
• Eine diskrete Simulation ist z.B. stochastisch und Konfidenzintervalle sind bestimmbar

Differentialgleichungen

• Das Basismodell lautet -> Differentialgleichungen
• z.B. Zustandsvektor, Eingabevektor, Zeit oder Zustandsänderungen

Simulationen

• Statische Struktur des Simulators erfolgt durch Zustandsvariablen
• Dynamische Struktur des Simulators erfolgt durch Ereignisroutinen

Statische Struktur

• AnzahlKundenimSystem
• Planung eines Ereignisses in der Zukunft
• mit Bedienzeit, AZ Zwischenankunftszeit

Zustand des Simulators

• Umfasst Werte aller Zustandsvariablen
• Alle bereits geplanten Ereignisse mit ihren Eintrittszeitpunkten

Simulationshauptroutine

• Führt Ereignisroutine aus
• Modifiziert S-Zusände
• Speichert Ressourcen

###Wahrscheinlichkeit

• Die Wahrscheinlichkeit, dass auch zufällige Prozesse in der Natur auftreten, ist gegeben
• Die Details müssen nicht bekannt sein/Komplexität vermieden werden