Noch mehr Fraktale

Seit meinem ersten Eintrag über meinen Fraktal-tweetenden Bot @AFractalADay, habe ich selbigen noch um ein paar Fraktale erweitert, die ich hier kurz festhalten möchte. Der ganze Code ist auf Github.

Chaotic Maps

Eine Quadratic Map ist eine Rekursionsgleichung mit einem quadratischen Term, also beispielsweise

$$x_{i+1} = a_0 x^2 + a_1 x + a_2.$$

Das berühmteste Mitglied dieser Familie ist die Logistic-Map mit \(a_0=1, a_1=r, a_2=0\), die chaotisches Verhalten für \(3.56995 < r < 4\) zeigt. Aber leider ist sie nur eindimensional und ihr Attraktor deshalb nicht besonders hübsch.

Um visuell ansprechende Fraktale daraus zu erzeugen, brauchen wir also ein System aus zwei Rekursionsgleichungen, die wir als \(x\)- und \(y\)-Koordinaten betrachten können:

\begin{align*} x_{i+1} &= a_{0} + a_{1} x + a_{2} x^2 + a_{3} x y + a_{4} y + a_{5} y^2\\ y_{i+1} &= a_{6} + a_{7} x + a_{8} x^2 + a_{9} x y + a_{10} y + a_{11} y^2. \end{align*}

Jetzt haben wir 12 freie Parameter, die einen riesigen Parameterraum aufspannen, in dem etwa 1.6% aller Möglichkeiten chaotisches Verhalten mit einem seltsamen Attraktor zeigen.

Quadratic Map

Chaotische Differentialgleichungssysteme

Ein echter Klassiker ist das Differentialgleichungssystem, das die Chaostheorie begründet hat und nach dem der Schmetterlingseffekt benannt ist [1, 2]. Für bestimmte Paramtersätze verlaufen die Bahnkurven entlang eines seltsamen Attraktors, dessen fraktale Dimension \(\approx 2.06\) ist. Da der vollständige Attraktor somit in einer zweidimensionalen Projektion etwas langweilig aussieht, habe ich hier nur eine Trajektorie über kurze Zeit dargestellt.

Lorenz-Attraktor

Und es gibt eine ganze Menge weitere Differntialgleichungssysteme (und chaotic maps), die chaotische Attraktoren aufweisen. Deshalb zeige ich hier noch einen Rössler-Attraktor, der eine vereinfachte Version des Lorenz-Systems ist:

\begin{align*} \frac{\mathrm{d}x}{\mathrm{d}t} &= -(y+z)\\ \frac{\mathrm{d}y}{\mathrm{d}t} &= x + ay\\ \frac{\mathrm{d}z}{\mathrm{d}t} &= b + xz - cz \end{align*}

Und hier haben wir das Glück, dass auch seine Projektion sehr ansehnlich ist.

Rössler-Attraktor

Ich persönlich frage mich, nun wie der Attraktor für das Doppelpendel aussieht. Es ist anscheinend kein Fraktal, aber es sieht dennoch ganz interessant aus:

Doppelpendel

Ising model

Das Ising Modell für Ferromagnetismus wird auch als Drosophila der statistischen Physik bezeichnet: Es ist ein einfaches Modell, dass einen Phasenübergang aufweist — Eisen verliert seine magnetischen Eigenschaften oberhalb der Curie-Temperatur.

Es besteht aus magnetischen Momenten, Spins, die gerne in die gleiche Richtung zeigen wie ihre Nachbarn, aber durch hohe Temperatur gestört werden. Oder etwas formaler: Die innere Energie \(U\) wird durch den Hamiltonian \(\mathcal{H} = - \sum_{<ij>} s_i s_j\) bestimmt, wobei \(s_i = \pm 1\), je nachdem ob der Spin up oder down ist und die Summe über benachbarte Spins läuft. Das System wird immer einen Zustand anstreben, der die freie Energie \(F=U-TS\) minimiert. Das kann entweder passieren, indem \(U\) möglichst klein ist oder die Entropie \(S\) möglichst hoch. Bei großen Werten der Temperatur \(T\) bekommt der Entropie-Term ein höheres Gewicht, sodass Zustände mit hoher Entropie, also zufälligen Spinausrichtungen, bevorzugt sind, bei niedrigen Temperaturen werden Konfigurationen mit niedriger innerer Energie bevorzugt, also solche in denen alle Spins in die selbe Richtung zeigen. Die Temperatur, bei der sich beide Terme die Waage halten, nennt man kritische Temperatur. Hier bilden sich Regionen von Spins, die in die gleiche Richtung zeigen, auf allen Größenskalen. Die fraktale Dimension dieser Regionen ist 187/96, was solche kritische Konfigurationen interessant anzusehen macht. Ich empfehle auf das folgende Bild zu klicken und etwas hineinzuzoomen.

Kritisches Ising System

Number of longest increasing subsequences

Meine liebsten Probleme sind solche, die einfach scheinen aber sehr tief sind. Natürlich gehört das Problem des Handlungsreisenden dazu: Es ist einfach zu verstehen, dass der Müllmann bei jeder Mülltonne vorbei muss und dabei möglichst wenig Strecke fahren will. Gerade deshalb ist es das Paradebeispiel für NP-schwere Probleme (technisch gesehen ist nur seine Entscheidungs-Version “Gibt es eine Tour, die kürzer ist als \(X\)NP-schwer und nicht die typische Optimierungsversion: “Welche ist die kürzeste Tour”).

Aber fast noch besser gefällt mir das Problem der längsten aufsteigenden Teilfolge, oder auf englisch, longest increasing subsequence (LIS): Gegeben eine Folge von Zahlen \(S_i\), welche Teilfolge ist am längsten unter der Bedingung, dass die Zahlen aufsteigen.

Eine längste aufsteigende Teilfolge ist in einer Folge markiert

Dieses Problem ist so einfach, dass es erstmals von Stanisław Ulam als Fingerübung beschrieben wurde und nach meinem Eindruck heutzutage als Übung für dynamische Programmierung in Universitäten verwendet wird. Wer weiß wie viele Bewerber vor einem Whiteboard ins Schwitzen geraten sind bei dem Versuch es aus dem Stegreif zu lösen.

The Surprising Mathematics of Longest Increasing Subsequences -- Dan Romik

Auf der anderen Seite ist es aber offenbar tief genug, dass man ganze Bücher darüber schreiben kann. Es zeigen sich überraschende Querverbindungen zu scheinbar unabhängigen Problemen. Denn die Länge \(L\) der LIS einer Permutation fluktuiert genauso wie der Abstand von der Mitte zum Rand eines Kaffeeflecks oder die größten Eigenwerte von Zufallsmatrizen.

Nun ist die Lösung dieses Problems nicht eindeutig: Es kann viele längste aufsteigende Teilfolgen geben. Tatsächlich wächst die Anzahl sogar exponentiell mit der Länge der ursprünglichen Sequenz.

Verschiedene längste aufsteigende Teilfolgen der gleichen Folge

Allerdings wurde bisher nie untersucht wie viele genau. Oftmals hört man, es sei nicht praktikabel alle durchzuzählen, da es exponentiell viele seien. Und wenn es darum ginge alle zu enumerieren, würde das stimmen. Aber wir wollen an dieser Stelle nur die Anzahl wissen, die wir mittels dynamischer Programmierung effizient bestimmen können. Die Idee ist, dass wir für jedes Element, das an Position \(x\) in einer LIS auftauchen kann, berechnen, wie viele aufsteigende Teilfolgen der Länge \(L-x\) mit diesem Element beginnen.

Besonders einfach geht das, wenn wir zuerst eine Datenstruktur aufbauen, die kodiert welche Elemente in einer LIS aufeinander folgen können. Dazu erweitern wir Patience Sort, und da dieser Algorithmus nach einem Kartenspiel benannt ist, werden wir es auch mit Karten visualisieren: Wir schreiben jedes Element unserer Sequenz auf eine Karte und legen die Karten auf einen Stapel, sodass das erste Element der Sequenz oben liegt. Dann nehmen wir Karten von oben ab und legen sie auf verschiedene Stapel. Die erste Karte legen wir auf den ersten, noch leeren Stapel. Die folgenden Karten legen wir auf den ersten Stapel, dessen oberstes Element größer ist als die aktuelle Karte und ansonsten machen wir einen neuen Stapel rechts davon auf. Jedes mal wenn wir eine Karte ablegen, lassen wir sie auf alle Karten, die aktuell auf dem Vorgängerstapel liegen und kleiner sind, zeigen — dies sind die Karten die in einer aufsteigenden längsten Teilfolge direkt vor ihr auftauchen können.

Animation von Patience Sort

Am Ende haben wir \(L\) Stapel, wobei \(L\) die Länge der LIS ist, und wir können vom Stapel ganz rechts starten und den Pfeilen folgen, um eine LIS zusammenzubauen. Wenn wir nur an der Länge interessiert wären, müssten wir uns über den Inhalt der Stapel keine Gedanken machen und der Algorithmus ließe sich sehr kompakt darstellen:

fn lis_len<T: Ord>(seq: &[T]) -> usize {
    let mut stacks = Vec::new();
    for i in seq {
        let pos = stacks.binary_search(&i)
            .err()
            .expect("Encountered non-unique element in sequence!");
        if pos == stacks.len() {
            stacks.push(i);
        } else {
            stacks[pos] = i;
        }
    }
    stacks.len()
}

Aber wir wollen mehr, deshalb notieren wir uns im nächsten Schritt bei allen Karten des rechtesten Stapels wie viele aufsteigende Teilfolgen der Länge \(x=1\) mit ihnen starten, was trivialerweise je eine ist. Dann notieren wir bei allen Karten des Stapels links davon wie viele aufsteigenden Teilfolgen der Länge 2 mit ihnen anfangen. Das können wir berechnen, indem wir den Pfeilen rückwärts folgen und die Annotationen jeweils aufaddieren. Nachdem wir dies für alle Stapel wiederholt haben und den linkesten Stapel beschriftet haben, können wir alle Annotationen des linkesten Stapels aufaddieren, um die gesamte Anzahl LIS zu erhalten: hier \(7\).

Beispiel der Datenstruktur zum Zählen der unterschiedlichen LIS

Wie sich das ganze für längere Sequenzen aus unterschiedlichen Zufallsensembles im Detail verhält haben wir in einem Artikel veröffentlicht.

Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes

In diesem Artikel wird ein Ensemble von Problemen des Handlungsreisenden (TSP) eingeführt, das abhängig von einem Parameter \(\sigma\) von einer trivial einfach zu lösenden Konfiguration, nämlich Städte, die äquidistant auf einem Kreis angeordnet sind, zum zufälligen euklidischen TSP in der Ebene interpoliert.

Einfach und schwierig zu lösende TSP Konfigurationen

Danach werden mittels linearer Programmierung einige Phasenübergänge festgestellt, ab welchen Werten von \(\sigma\) das Problem schwierig zu lösen wird. Zu zwei dieser Übergänge werden strukturelle Eigenschaften der optimalen Lösung gefunden, die sich an dieser Stelle ebenfalls charakteristisch ändern. Da die optimale Lösung nicht von der Lösungsmethode abhängt, sind diese Phasenübergänge also nicht nur von Bedeutung für das spezielle Lineare Programm bzw. den Algorithmus der zu dessen Lösung genutzt wurde, sondern fundamentale Eigenschaft dieses TSP Ensembles.

Im Detail haben wir die klassische Formulierung von Dantzig genutzt:

\begin{align*} \label{eq:objective} &\text{minimize} & \sum_i \sum_{j<i} c_{ij} x_{ij}\\ \label{eq:int} &\text{subject to} & x_{ij} &\in \{0,1\}\\ %\mathbb{Z}\\ \label{eq:inout} & & \sum_{j} x_{ij} &= 2& & \forall i \in V \\ \label{eq:sec} & & \sum_{i \in S, j \notin S} x_{ij} &\ge 2& & \forall S \varsubsetneq V, S \ne \varnothing \end{align*}

Hier ist \(c_{ij}\) die Distanzmatrix zwischen allen Paaren von Städten aus \(V\) und \(x_{ij}\) die gesuchte Adjazenzmatrix, also \(x_{ij} = 1\), wenn \(i\) und \(j\) aufeinanderfolgende Stationen der Tour sind und \(x_{ij} = 0\) sonst. Die erste Zeile minimiert also die Strecke der Tour. Um zu vermeiden, dass wir die triviale Lösung \(x_{ij}=0\), also “wenn wir zu Hause bleiben müssen wir am wenigsten Strecke zurücklegen” finden, zwingt die dritte Zeile unseren Handlungsreisenden seine Tour so zu planen, dass in Summe zwei Striche an jede Stadt gezeichnet werden — genug, um hinein und wieder hinaus zu reisen. Allerdings, ist unser Handlungsreisender clever und würde versuchen uns auszutricksen, indem er halbe Striche einzeichnen würde, wie in einem anderen Blogeintrag visualisiert. Deshalb ist die Bedingung in der zweiten Zeile nötig, die die Einträge in der Adjazenzmatrix auf ganze Zahlen beschränkt. Dann bleibt nur noch das Problem, dass mehrere Routen, die nicht verbunden sind erlaubt wären, sodass wir sie durch die letzte Zeile verbieten: die Subtour Elimination Constraints. Der aufmerksame Leser mag schon erkannt haben, dass es für jede Untermenge von Städten so eine Constraint definiert, also exponentiell viele in der Anzahl der Städte. Die Lösung zu dieses Problem liegt darin, dass nur sehr wenige wirklich gebraucht werden, sodass man das Problem ohne diese Constraint löst, testet ob eine verletzt ist, was mittels der Berechnung eines minimum cut sehr schnell geht und dann eine einzelne Constraint, die diese Konfiguration verbietet hinzufügt. Diese Methode iterativ Constraints hinzuzufügen wird meist als Cutting Planes bezeichnet.

Also haben wir einen schnellen Algorithmus für das Problem des Handlungsreisenden gefunden? Nein, leider können wir den Millenium Preis noch nicht beanspruchen. Es gibt keinen bekannten Algorithmus, der dieses Problem unter Erfüllung der zweiten Zeilen, also Beschränkung auf ganzzahlige Lösungen lösen kann. Aber sobald wir diese Bedingung fallen lassen, können wir klassische Verfahren der linearen Programmierung nutzen, um dieses Problem effizient zu lösen. Dies wird auch Relaxation genannt. Die Länge der Strecke ist immer eine untere Schranke für die tatsächliche Lösung. Und wenn unsere Lösung per Zufall ganzzahlig ist, können wir uns sicher sein, die Optimale Lösung gefunden zu haben.

Als Ordnungsparameter des Phasenübergangs zwischen leichten und schweren Konfigurationen dient uns also die Wahrscheinlichkeit, dass mittels eines Simplex-Solvers eine ganzzahlige, und damit optimale, Lösung gefunden wird. Ohne die Subtour Elimination Constraints, fällt der Phasenübergang auf den Punkt, an dem sich die optimale Lösung erstmals von der Reihenfolge der Städte des ursprünglichen Kreises unterscheidet. Mit den Subtour Elimination Constraints, fällt der Phasenübergang auf den Punkt, wo die optimale Tour anfängt von einem Zickzack-Kurs auf große Meander zu wechseln. Dies wird durch die geometrische Gewundenheit, die Tortuosität,

\begin{align*} \tau = \frac{n-1}{L} \sum_{i=1}^{n} \left( \frac{L_i}{S_i}-1 \right). \end{align*}

ermittelt, die an diesem Punkt maximal wird. Hier wird die Tour in \(N\) Teilstücke mit gleichem Vorzeichen der Krümmung unterteilt und für jedes Teilstück das Verhältnis von direkter Ende-zu-Ende-Distanz \(S_i\) zu der Länge entlang der Tour \(L-i\) summiert.

Wir haben also kontinuierliche Phasenübergänge in der Schwierigkeit dieses Problems mittels linearer Programmierung detektiert und sie mit strukturellen Änderungen des Verhaltens in Verbindung gebracht.