möchte­gern­geek

Simulated Annealing ist eine Optimierungsmethode, die von natürlichen Kristallisationsprozessen inspiriert ist. Man startet in der Schmelze bei hohen Temperaturen und lässt es dann abkühlen, sodass die Atome sich in einem Zustand minimaler Energie anordnen, dem Kristallgitter. Wenn man also für ein Optimierungsproblem die zu optimierende Größe als Energie ansieht, und man eine Lösung durch eine kleine Änderung in eine andere Lösung verwandeln kann, kann man mit dieser Methode eine Näherung für das Optimum finden.

Wenn wir also eine Sequenz $S$ von $N$ Zahlen sortieren wollen, können wir die Summe der Differenzen zwischen benachbarten Zahlen als Energie betrachten, denn die ist minimal in einer sortierten Liste.

Um eine Lösung in eine andere zu verwandeln, reicht es zwei Elemente der Sequenz zu tauschen.

Der Kern von Simulated Annealing ist der Metropolis Algorithmus.

1. Starte bei einer hohen Temperatur $T$.
2. Berechne die Energie $\mathcal{H}(S)$ der aktuellen Konfiguration $S$.
3. Erzeuge eine neue Konfiguration $R$ durch eine kleine Änderunge von $S$.
4. Akzeptiere $R$ mit der Wahscheinlichkeit
   $$p_{\mathrm{acc}}=min[1,\exp (-(\mathcal{H}(R)-\mathcal{H}(S))/T)],$$
   sodass eine „sortiertere“ Sequenz immer akzeptiert wird und eine „unsortiertere“ vor allem bei hohen Temperaturen. Wenn $R$ akzeptiert wird, gilt $S:=R$, ansonsten wir die alte Konfiguration $S$ weiter benutzt.
5. Reduziere die Temperatur (beispielsweise durch Multiplikation mit einer Zahl etwas kleiner als 1) und breche ab, wenn die Zieltemperatur erreicht ist. Ansonsten beginne wieder bei Punkt 2.

Genug der Theorie: In einem Gist auf GitHub präsentiere ich ein schnell terminierendes Sortierprogramm, das zwar nicht immer eine sortierte Liste findet, aber zumindest eine Näherung! Es ist also Bogosort in mehr als nur einer Hinsicht überlegen!

Wer braucht da noch $$ Sortier-Algorithmen?!

Programmiersprachen muss man üben, um sie zu lernen und um sie nicht wieder zu vergessen. Ich habe also meine Zeit damit vertrieben einen SHA-256 zu schreiben — eine kryptographische Hash Funktion. Die Spezifikation ist glücklicherweise sehr sehr verständlich. Und auch wenn es tausende andere Implementationen gibt, die schneller sind, alle Grenzfälle beachten (ich befürchte, dass mein Programm Probleme auf Big Endian Systemen bekommt), und sogar Schaltkreise, die hochoptimiert nur diese Operation beherrschen (Stichwort: Bitcoin ASIC), ist meiner dennoch sehenswert, da er SHA-256 in 256 Zeilen darstellt.

Der Code ist als Gist auf GitHub, da er in seinen 256 Zeilen ansonsten den Lesefluss stören würde.

In Python ist es übrigens etwas kürzer.

print(hashlib.sha256(b"Hallo Welt!").hexdigest())

Eines der bekanntesten Modelle der statistischen Physik ist das Ising-Modell. Es besteht aus (klassischen) Spins auf einem Gitter im Wärmebad und soll magnetische Eigenschaften von Festkörpern modellieren. Es zeigt nämlich in 2D und 3D (und 4D … ) einen Phasenübergang zweiter Ordnung von „magnetisch“ zu „nicht magnetisch“, so wie ferromagnetische Materialien, die oberhalb der Curie Temperatur nicht mehr ferromagnetisch sind.

In einfachen Worten: Die Spins des Ising-Modells richten sich so aus wie ihre Nachbarn und die Temperatur bringt sie wieder durcheinander.

Aber es wäre natürlich langweilig das Modell so zu benutzen, wie alle anderen auch. Deshalb stelle ich hier eine Anwendung aus Pattern Recgonition and Machine Learning vor, die nichts mehr mit Magneten zu tun hat: Rauschunterdrückung in Bildern.

Andererseits bin ich Physiker und darf deshalb nichts machen, was direkt nützlich wäre, also beschränke ich mich auf schwarz-weiße Bilder, die man direkt auf das „spin up“-„spin down“ des Ising-Modells abbilden kann.

Die Idee ist, das jeder Spin einem Pixel $$ entspricht. Dann koppelt man die Spins des Ising-Modells $$ an die Pixel $$ des verrauschten Bildes über einen zusätzlichen Energie-Term

Dabei bedeutet $$, dass man über alle Nachbarn von $$ summiert.

Von diesem Modell kann man dann per Simulated Annealing den Grundzustand suchen oder man macht es sich einfach equilibriert bei $$.

Das Schema dazu wurde bereits in diesem Post gezeigt. Graue Knoten entsprechen den Pixeln des verrauschten Bilds $$ und weiße Knoten den Ising-Spins $$, die am Ende als Pixel des entrauschten Bilds interpretiert werden.

Genug der Theorie. Es wird Zeit für pixelige Bilder. Leider hatte ich kein verrauschtes Bild, also habe ich ein beliebiges Bild gemalt und 10% aller Pixel invertiert.

Links das verrauschte Bild und rechts das entrauschte. Ja, nicht perfekt. Und in dem zitierten Buch wird auf der gleichen Seite noch eine sehr viel bessere Methode angesprochen. Aber die hatte nichts mit dem Ising-Modell zu tun. Und man sieht ja auch eine Verbesserung. Oder?

Nebenbei bemerkt, kann man das Ising-Modell auch als zellulären Automaten mit zufälligem Element betrachten, denn jeder Spin ist eine Zelle, die nur lokal von seinen Nachbarn und zufällig durch die Temperatur beeinflusst wird.

Der Code ist als Gist auf Github.