5. Simulation

Ein Computer ist ein deterministisches Gerät: Jede Berechnung ist eindeutig durch Eingabe und Programm bestimmt und beliebig reproduzierbar. Eine echte Zufallsfolge dürfte aber keinerlei Gesetzmäßigkeit haben und wäre nicht reproduzierbar.

Deshalb erzeugt der Rechner nur pseudozufällige Folgen – Zahlen, die statistisch wie zufällig aussehen (bestehen z.B. Tests auf Gleichverteilung und Korrelation), tatsächlich aber vollständig durch Startwert (Seed) und Vorschrift bestimmt sind. Vorteil: Reproduzierbarkeit (nützlich für Debugging). Nachteil: endliche Periode und die Folge kann bei schlechten Parametern Muster zeigen.

Formel: \( r_{n+1} = (a \cdot r_n) \bmod m = (3 \cdot r_n) \bmod 32 \).

1. \(r_1 = (3 \cdot 9) \bmod 32 = 27 \bmod 32 = \mathbf{27}\)
2. \(r_2 = (3 \cdot 27) \bmod 32 = 81 \bmod 32 = \mathbf{17}\) (denn \(81 = 2 \cdot 32 + 17\))
3. \(r_3 = (3 \cdot 17) \bmod 32 = 51 \bmod 32 = \mathbf{19}\) (denn \(51 = 32 + 19\))
4. \(r_4 = (3 \cdot 19) \bmod 32 = 57 \bmod 32 = \mathbf{25}\) (denn \(57 = 32 + 25\))
5. \(r_5 = (3 \cdot 25) \bmod 32 = 75 \bmod 32 = \mathbf{11}\) (denn \(75 = 2 \cdot 32 + 11\))

Folge: 9, 27, 17, 19, 25, 11, …

Gleichverteilung: Man teilt den möglichen Wertebereich in \(k\) gleich große Klassen und zählt, wie viele der \(N\) erzeugten Zahlen in jede Klasse fallen. Bei perfekter Gleichverteilung erwartet man \(N/k\) Werte pro Klasse. Abweichungen werden z.B. mit dem \(\chi^2\)-Test statistisch bewertet.

Korrelation: Man bildet Paare aufeinanderfolgender Zahlen \((r_n, r_{n+1})\) und trägt sie in ein Streudiagramm ein. Bei einer guten Folge entsteht eine gleichmäßige Punktwolke; bei schlechter Folge sichtbare Streifen, Diagonalen oder Cluster. Alternativ: Korrelationskoeffizient berechnen – sollte nahe null liegen.

Merke: Beide Tests sind nötig – eine Folge kann gleichverteilt und trotzdem stark korreliert sein (z.B. wenn sie das Intervall zyklisch durchläuft).

Ist \(r_n = 0\), so folgt \(r_{n+1} = (a \cdot 0) \bmod m = 0\) – und ab dann bleibt die Folge dauerhaft bei null. Der Generator "stirbt".

Daher wählt man bei der multiplikativen Kongruenz stets einen Startwert \(r_0 \neq 0\). Zusätzlich müssen \(a\) und \(m\) so gewählt werden, dass 0 im Zyklus nicht auftritt (ein Grund, warum \(m\) oft als Primzahl bzw. Mersenne-Zahl wie \(2^{32}-1\) gewählt wird).

Ziel: \(F = \int_a^b f(x)\, dx\) schätzen. Man legt ein Rechteck über den Graphen mit Breite \(b-a\) und Höhe \(O_s\), sodass die Kurve komplett darunter passt. Dann würfelt man \(N\) zufällige Punkte gleichmäßig in dieses Rechteck: \(x \in [a,b]\), \(y \in [0, O_s]\).

Ein Punkt ist "Treffer", wenn \(y \leq f(x)\), also unter der Kurve liegt. Bei \(T\) Treffern gilt näherungsweise:

Rolle von \(O_s\): Es muss \(O_s \geq \max f(x)\) auf \([a,b]\) gelten – sonst schneidet man Teile der Kurve ab und unterschätzt \(F\). Ist \(O_s\) zu groß gewählt, landen unnötig viele Punkte oberhalb der Kurve, was die Konvergenz langsamer macht. Optimal: \(O_s\) so klein wie möglich, aber noch obere Schranke.

Ein Gradientenverfahren (bzw. reines Bergabsteigen) folgt in jedem Schritt der Richtung mit der stärksten Verbesserung. Trifft es auf ein lokales Minimum, sind alle Nachbarn schlechter – und der Algorithmus bleibt stecken, obwohl das globale Minimum vielleicht "hinter einem Berg" liegt.

Simulated Annealing akzeptiert dagegen mit einer gewissen Wahrscheinlichkeit auch Verschlechterungen. So kann es aus einem lokalen Minimum wieder herauskommen ("über den Berg klettern") und weiter unten ein besseres Minimum finden. Zu Beginn ist die Akzeptanzrate hoch (viel Exploration), am Ende gering (Konvergenz). Dadurch findet SA in der Praxis deutlich bessere Lösungen, insbesondere in Landschaften mit vielen lokalen Minima.

Sei \(\Delta z = z_{\text{neu}} - z_{\text{alt}}\) (Minimierungsproblem). Dann:

Fall 1: Verbesserung (\(\Delta z \leq 0\)). Wird immer akzeptiert (\(p = 1\)).

Fall 2: Verschlechterung (\(\Delta z > 0\)). Wird mit Wahrscheinlichkeit \(e^{-\beta \Delta z}\) akzeptiert. Je größer die Verschlechterung, desto kleiner \(p\). Je größer \(\beta\), desto kleiner \(p\). Für \(\beta \to \infty\) geht \(p \to 0\) (kaum noch Verschlechterungen).

Verhalten für drei \(\beta\)-Werte (bei fester Änderung \(\Delta z\)):

• \(\beta\) klein (heiß): flacher Abfall, viele Verschlechterungen werden akzeptiert.
• \(\beta\) mittel: mittlerer Abfall.
• \(\beta\) groß (kalt): sehr steiler Abfall – schon kleine Verschlechterungen werden fast nie akzeptiert.

Am Anfang soll der Algorithmus den Lösungsraum breit erkunden (Exploration), damit er nicht sofort in einem beliebigen lokalen Minimum landet. Dafür braucht es hohe Akzeptanz auch schlechter Züge → kleines \(\beta\).

Zum Ende hin soll der Algorithmus die gefundene gute Region ausnutzen und dort tief einlaufen (Exploitation). Verschlechterungen wären jetzt kontraproduktiv → großes \(\beta\).

Bliebe \(\beta\) klein, würde der Algorithmus ewig umherspringen und nie konvergieren. Bliebe \(\beta\) groß, wäre SA praktisch dasselbe wie ein Gradientenverfahren und würde in lokalen Minima steckenbleiben. Die langsame Abkühlung ist genau der Trick, der beides verbindet.

Lösung: Eine konkrete Rundreise, also eine geordnete Liste von Städten, z.B. \(1 \to 5 \to 2 \to 4 \to 3 \to 1\). Der Zielfunktionswert ist die Summe der Kantenlängen (Gesamtdistanz).

Veränderung (Nachbarschaftsoperation): Klassisch der 2-opt-Swap. Man wählt zwei Kanten der aktuellen Tour aus, entfernt sie und verbindet die entstehenden Endpunkte auf die andere Weise. Das dreht ein Teilstück der Tour um. Ergebnis: eine leicht veränderte Rundreise, deren Gesamtdistanz sich meist nur wenig unterscheidet.

Akzeptanz: Ist die neue Tour kürzer → immer übernehmen. Ist sie länger um \(\Delta z\) → mit Wahrscheinlichkeit \(e^{-\beta \Delta z}\) übernehmen, sonst verwerfen.

Computerexperiment: Das reale System wird durch deterministische Gleichungen modelliert (z.B. Differentialgleichungen der Strömung, Bewegungsgleichungen im Fahrsimulator). Zwei Läufe mit identischer Eingabe liefern identische Ergebnisse. Zufall spielt keine Rolle.

Monte-Carlo-Simulation: Das System ist selbst stochastisch oder wird gezielt mit Zufallszahlen "gefüttert". Beispiele: Warteschlangen (zufällige Ankunftszeiten), Risikoanalyse (zufällige Marktbewegungen), Integration schwieriger Funktionen. Zwei Läufe liefern unterschiedliche Ergebnisse; man analysiert Mittelwerte und Streuung.

Faustregel: Sobald Zufallszahlen im Modell auftauchen, spricht man von Monte-Carlo-Simulation.

Jeder Pseudo-Zufallsgenerator wiederholt sich nach seiner Periode. Ist die Periode kurz (z.B. nur 1000 Zahlen), passiert bei längeren Simulationen Folgendes:

• Nach 1000 Ziehungen erscheint dieselbe Folge wieder – der Rest der Simulation ist keine unabhängige Stichprobe mehr.
• Statistische Auswertungen (Mittelwerte, Konfidenzintervalle) werden verzerrt, weil dieselben Werte immer wieder auftauchen.
• Bei Monte-Carlo-Integration konvergiert der Schätzer nicht weiter – man addiert nur dieselben Punkte doppelt.

Deshalb wählt man Parameter wie \(m = 2^{32}-1\), \(a = 3^{19}\) mit Perioden im Bereich von \(10^5\) bis \(10^9\) und darüber.

Wenn \(O_s < \max_{x\in[a,b]} f(x)\), dann gibt es Bereiche, in denen \(f(x)\) über die obere Kante des Rechtecks hinausragt. Zufallspunkte werden aber nur bis \(y = O_s\) gezogen. Alle \(x\)-Werte, bei denen \(f(x) > O_s\), werden fälschlicherweise als "Treffer" behandelt, während der Anteil der Kurve oberhalb \(O_s\) komplett ignoriert wird.

Konsequenz: Die geschätzte Fläche wird systematisch unterschätzt – der Schätzer ist verzerrt (Bias), nicht nur ungenau. Mehr Iterationen helfen nicht, weil das Problem nicht statistischer, sondern konstruktiver Natur ist.

Merke: \(O_s\) muss echte obere Schranke sein. Ist die Kurve nicht bekannt, kann man z.B. eine grobe Skizze anfertigen, das Maximum abschätzen und einen Sicherheitszuschlag draufgeben.

Ein exaktes Verfahren (z.B. Simplex, Branch-and-Bound) garantiert bei endlicher Laufzeit die Optimallösung – oder erkennt zumindest, dass sie erreicht ist. Bei kombinatorischen Problemen wie TSP wachsen exakte Verfahren aber exponentiell mit der Problemgröße und sind für große Instanzen praktisch unbrauchbar.

Eine Metaheuristik wie SA ist ein allgemeines Suchschema, das gute Lösungen effizient findet, aber keinerlei Optimalitätsgarantie liefert. SA kann durchaus im lokalen Minimum enden – die Wahrscheinlichkeit dafür sinkt zwar mit langsamer Abkühlung, ist aber positiv. Vorteil: Für viele Probleme findet SA in vernünftiger Zeit eine sehr gute Lösung, mit der man in der Praxis leben kann.