Eine Implementierung des Downhill Simplex Algorithmus in F#

 

Das ist der erste Post, in dem wir den sogenannten Downhill Simplex Algorithmus in F# implementieren werden. In diesem Post wird es hauptsächlich um meine Implementierung gehen, basierend auf dem Algorithmus wie er in Wikipedia beschrieben ist, und um die Dinge, die ich dabei gelernt gehabe.

Für eine grundlegende Einführung in den Downhill Simplex Algorithmus und wie er prinzipiell funktioniert, kann ich den Wikipedia-Artikel empfehlen. Ich werde den Algorithmus hier nicht weiter erläutern, daher würde ich diejenigen, die noch ein tieferes Verständnis des Algorithmus suchen, auf weiterführende Literatur verweisen. Für die Implementierung reicht ein grundlegendes Verständnis aber vollkommen aus.
Als nächstes werde ich erst mal ein paar Begriffe definieren, die wir gleich brauchen werden, sobald es an die Implementierung geht. Ich verwende dafür englische Begriffe, da sich diese später auch im Quellcode wiederfinden.

  • Point: Eine geordnete Menge an Parametern
  • Evaluated: Ein beliebiges bewertetes Datum, das einen Kostenwert zugeordnet hat
  • Unsorted: Beliebige unsortierte Daten
  • Sorted: Beliebige sortierte Daten

Die Begriffe und deren Bedeutung habe ich der Beschreibung des Algorithmus entnommen. Nun gilt, eine un-/sortierte Liste an Punkten, bewertet oder nicht bewertet, bildet unseren Simplex. Der Algorithmus transformiert verschiedene Arten von Simplexe in anderen Arten.
<h2Typendesign

In unserer Implementierung machen wir Gebrauch vom strikten F# Typsystem, um Fehler in unserer Implementierung so wie früh wie möglich zu erkennen.

Manche Eigenschaften lassen sich nicht so einfach im Typensystem abbilden, z.B. die Eigenschaft, dass eine Unsorted<Point list> eine Liste an Punkten beinhalten muss, deren Länge um genau eins größer ist, als die Länge jeder Liste an Parametern in jedem Punkt.
Oder anders ausgedrückt, wenn man die geschachtelten Listen als Matrix aufzeichnen würde, muss es eine (N+1) x N Matrix ergeben, wobei N die Anzahl der Parameter ist, in jedem Punkt.
Wir könnten diese Arten von Eigenschaften nur dann im Typensystem abbilden, wenn wir uns auf genau ein bestimmtes N festlegen. Wenn die Entscheidung, welchen Wert N hat, aber erst zur Laufzeit getroffen wird, können wir diese Eigenschaft auch nur Laufzeit überprüfen.
Als Konsequenz daraus werden die Funktionen, die diese Typen erzeugen, als Rückgabetyp eine Option<T> benutzen und None zurückliefern, wenn die Parameter der Funktion, die erwarteten Eigenschaften nicht erfüllen.
Im nächsten Schritt des typbasierten Designs werden wir noch die Funktionssignaturen festlegen, ausschließlich auf Grundlage der Beschreibung des Algorithmus.

Die meisten Signaturen sollten relativ einfach den Schritten aus dem Algorithmus zuordenbar sein. Schauen wir mal schnell drüber.

  • tryCreate: Erzeugt den initialen Simplex, falls die Eingabe alle erwarteten Eigenschaften erfüllt
  • evaluate: Gegeben eine Funktion, die einen Punkt bewertet, wenden wir diese auf die komplette unsortierte Liste an
  • sort: Wandelt eine unsortierte Liste in eine sortierte Liste
  • mean: Berechnet den Mittelpunkt aller Punkte, bis auf den schlechtesten
  • reflect, expand, contract, compress: Diese Funktionen werden benötigt, beim Erzeugen des nächsten Simplex
  • step: Führt die nächste Iteration des Algorithmus durch

Beim Betrachten der Funktionssignaturen fällt auf, dass uns noch eine Funktion fehlt, um den Algorithmus zu starten. Die fehlende Funktion erzeugt N neue Punkte, basierend auf einem Startpunkt. Diese Funktion nennen wir generate.

Mit generate und den vorher definierten Funktionen, können wir nun unseren initialen Simplex berechnen.
<h2Zusammenfassung

Durch das strikte Typensystem und dadurch, dass wir alle relevanten Typen gleich zu Beginn festgelegt haben, haben wir viel Sicherheit gewonnen für die Implementierung. Wenn die Typen beim Implementieren an einer Stelle nicht mehr zusammen gepasst haben, dann ist irgendetwas falsch gelaufen und muss korrigiert werden.
Zusätzlich sind wir auf natürliche Weise zu einer Funktionsbibliothek gelangt, die es uns erlaubt hat unsere Daten zwischen den verschiedenen Typen hin und her zu transformieren. Immer mit der Garantie, dass das Ergebnis korrekt ist. Durch die Komposition dieser Funktionen, konnten wir dann den Downhill-Simplex einfach implementieren. Den kompletten Quellcode findet ihr github-simplex.

Danke für’s Lesen.