Implementierte Algorithmen

Geneva unterstützt neben Evolutionären Algorithmen (ohne ausschließliche Festlegung auf Floating Point oder Boolean-Parameter) verschiedene andere metaheuristische Optimierungsverfahren. Dies sind aktuell

• Schwarmalgorithmen
• Simulated Annealing (erweitert um die Möglichkeit mehrerer gleichzeitiger Bewertungen)
• Einfache Gradientenabstiege (nicht Conjugate Gradient). Hierbei wird in jedem Schritt der Gradient auf der Basis des Differenzenquotienten ermittelt und so näherungsweise die Richtung des steilsten Abfalls der Qualitätsoberfläche bestimmt

Zusätzlich werden Parameter Scans unterstützt, entweder auf einem regelmäßigen Gitter oder mit Hilfe von über den gesamten Parameterraum gleichverteilten, zufälligen Kandidatenlösungen. Ein Scan der „Noisy Parabola“ ${\displaystyle f\left(x_{1},x_{2},\ldots ,x_{n}\right)=\left(cos\left(\sum _{i=1}^{n}x_{i}^{2}\right)+2\right)*\sum _{i=1}^{n}x_{i}^{2}}$ (einer in Geneva für Testzwecke verwendeten Funktion mit einer sehr hohen Zahl lokaler Optima) auf einem Gitter ist beispielhaft auf der rechten Seite zu sehen. Dem Scan in Rot überlagert ist eine Optimierung mit Hilfe einer Evolutionsstrategie unter Verwendung von Geneva. Nur einen Teil des Parameterraums unterzieht der evolutionäre Algorithmus der Bewertungsfunktion. Da die Menge zu scannender Raumpunkte exponentiell mit der Zahl der Parameter steigt, stellt die parametrische Optimierung für viele hochdimensionale Problemstellungen den einzig gangbaren Weg zur Lösung dar. Die Geneva-Bibliothek kann hierbei auch mit Problemen mit sehr hohen Zahlen an Parametern umgehen (vgl. hierzu auch Film 1).

Kopplung von Algorithmen

Optimierungsalgorithmen können miteinander gekoppelt werden, wobei die besten Lösungen des Vorgängeralgorithmus zum Startwert des folgenden Algorithmus werden. Ein Nutzungsbeispiel ist die Suche nach geeigneten Startpunkten der Optimierung mit Hilfe eines groben Parameterscans, gefolgt von einer Evolutionsstrategie. Der Austausch der besten Kandidatenlösungen zwischen verschiedenen Algorithmen erlaubt grundsätzlich auch die Unterteilung des Optimierungslaufs in Grob- und Fein-Optimierung mit unterschiedlichen Algorithmen.

Behandlung von Randbedingungen

Randbedingungen können den gültigen Teil des Parameterraums stark einschränken. Optimierungsalgorithmen müssen solche Bereiche so weit wie möglich vermeiden, einerseits um schneller ein gültiges Optimum zu erreichen und andererseits, um potentiell fehlerhafte Rückgabewerte der Bewertungsfunktion für ungültige Parameterwerte zu umgehen. Die Geneva Bibliothek unterstützt einerseits die Beschränkung des Wertebereichs einzelner Parameter. Ferner besteht die Möglichkeit, Abhängigkeiten der Randbedingungen einzelner Parameter von den Werten anderer Variablen durch eine Rückführung auf eine gemeinsame Qualitätsoberfläche für ungültige und gültige Lösungen zu behandeln. Ein Beispiel für eine solche Problemstellung wären zwei Parameter x und y, deren Summe einen gegebenen, konstanten Bereich nicht überschreiten darf. Zwar kann in diesem Beispiel grundsätzlich jede Variable variiert werden. Gültige Parameterwerte hängen aber vom aktuellen Wert der jeweils anderen Variable ab.

Das hierbei von Geneva eingesetzte Verfahren bewertet zunächst die Gültigkeit eines Parametersatzes. Gültige Lösungen werden mit Hilfe einer Sigmoid-Funktion transformiert, so dass die Bewertung gültiger Parametersätze eine obere und untere Grenze nicht über- respektive unterschreiten kann. Kann der Nutzer nun für jede verletzte Randbedingung numerisch angeben, wie schwerwiegend deren Verletzung ist, so berechnet Geneva eine Ersatzbewertung (Invalidity), die an die Stelle des Aufrufs der Bewertungsfunktion tritt. Dies geschieht z. B., in dem das Produkt aller Invalidities mit der oberen (bei Minimierung) oder unteren (bei Maximierung) Grenze der Sigmoidfunktion multipliziert wird. Die so entstehende Ersatz-Qualitätsoberfläche fällt in Richtung gültiger Wertebereiche ab. Die durch den Optimierungsalgorithmus gefundenen Lösungen werden so in die Richtung gültiger Werte „gezogen“.

Monitoring

Aktuelle Parameter der Optimierungsalgorithmen sowie der Kandidatenlösungen können während der laufenden Optimierung extrahiert und in Form eines Eingabescripts für das Datenanalysepaket ROOT ausgegeben werden. ROOT sorgt dann für die Konvertierung in gewünschte Bildformate, etwa PNG oder PDF. Ferner ist mit diesem Werkzeug eine Nachbearbeitung (z. B. durch Anmerkungen) außerhalb von Geneva möglich. Daten können entweder mit Algorithmen-spezifischen, vordefinierten Optimierungsmonitoren gesammelt werden, oder mit Hilfe von leichtgewichtigeren, meist Benutzer-definierten Pluggable Optimization Monitors. Abbildung 1 wurde auf diese Weise erzeugt, wobei eine Nachbearbeitung stattgefunden hat.

Parallelisierung und Größe der unterstützten Problemstellungen

Metaheuristische Optimierungsalgorithmen verlaufen in Zyklen, wobei aufeinanderfolgende Iterationen auf den Ergebnissen der Vorgängeriteration aufbauen. Meist erfolgen pro Iteration mehrere Bewertungen, und viele Optimierungsalgorithmen benötigen bei einer Erhöhung der Zahl an Kandidatenlösungen bei gleicher Problemgröße weniger Iterationen bis zu einer zufriedenstellenden Lösung. Die Optimierung von Problemstellungen mit komplexen Qualitätsoberflächen profitiert umgekehrt von zusätzlichen Optimierungszyklen und – insofern vom gewählten Optimierungsalgorithmus unterstützt – pro Iteration der Bewertung einer möglichst großen Anzahl an Kandidatenlösungen.

Die sinnvolle Menge an Iterationen und an Kandidatenlösungen pro Iteration wird insbesondere durch die verfügbare Rechenzeit beschränkt. Durch eine Parallelisierung auf der Ebene der Bewertung von Kandidatenlösungen kann eine Beschleunigung der Optimierungsrechnung erreicht werden. Hierbei ist hilfreich, dass die Einzelbewertungen unterschiedlicher Kandidatenlösungen im Regelfall unabhängig voneinander sind. Für große Populationen an Kandidatenlösungen nähert sich die parametrische Optimierung hinsichtlich der Parallelisiertbarkeit insofern "trivial parallelen" Problemstellungen an.

Der für die Optimierung benötigte Bewertungsschritt kann in Geneva parallel in mehreren Threads oder verteilt in Clustern, Grid oder Cloud erfolgen. Hierbei wird außer der lokalen Berechenbarkeit für gegebene Parametersätze keine inhaltliche Voraussetzung über die verwendeten Bewertungsfunktionen gemacht. Jedoch entstehen durch die gewählte Art der Parallelisierung Anforderungen an die Implementation der Bewertungsfunktion. Bei der Ausführung im Netzwerk ist zudem zu beachten, dass auf Grund der durch das Amdahl'sche Gesetz beschriebenen Einschränkungen sehr kurze Bewertungsfunktionen zu einer schlechten Skalierbarkeit führen.

Metaoptimierung

Es existiert die Möglichkeit, Konfigurationsparameter von Optimierungsalgorithmen (aktuell in Geneva implementiert nur für Evolutionären Algorithmen) direkt zu optimieren, nach Nutzerwahl entweder zwecks Minimierung der Zahl der Aufrufe der Bewertungsfunktion bis zum Erreichen einer vorgegebenen Qualität, oder zur effizienteren Suche nach möglichst guten Optima. Das Verfahren ist durch die Notwendigkeit vieler Optimierungsläufe sehr rechenintensiv und eignet sich nicht für rechenaufwändige Bewertungsfunktionen. Es kann jedoch dazu genutzt werden, anhand schnell zu berechnender mathematischer Funktionen geeignete Konfigurationsparameter auch für sehr verrauschte Qualitätsoberflächen zu bestimmen. Ferner werden durch die Möglichkeit, Optimierungsalgorithmen in Individuen zu kapseln, Multipopulationen unterstützt – sie erlauben es, Optimierungsalgorithmen zum Gegenstand der Optimierung zu machen.

Brokering und Netzwerkkommunikation

Alle für die Netzwerkkommunikation und allgemeiner die Verteilung von Rechenaufträgen benötigte Funktionalität ist in der libcourtier implementiert.

Die aktuell auf der Boost ASIO-Bibliothek sowie der Boost Beast-Bibliothek basierende Netzwerkkommunikation implementiert eine einfache Client-Server-Architektur. Sie setzt auf Seiten der Clients lediglich die Erreichbarkeit des Servers voraus. Netzwerkverbindungen werden im Fall von ASIO für jeden Transfer von Parametersätzen oder Bewertungsergebnissen neu geöffnet und nach dem erfolgreichen Transfer der Daten wieder geschlossen. Durch dieses Design muss auf Bibliotheksseite keine Information über die Dauer der Bewertungsfunktion existieren – diese können ggf. auch über viele Stunden aktiv sein. Die Ausführung im Netzwerk stellt je nach Bewertungsfunktion auf Grund einer hohen Frequenz an Client-Server Verbindungen jedoch ähnliche Anforderungen an den Server wie ein Webserver, erfordert also ggf. eine auf Geneva angepasste Konfiguration. Die auf Boost Beast basierende Implementierung verwendet im Vergleich Websockets, so dass Verbindungen über längere Zeit aufrechterhalten werden. Die für die Netzwerkkommunikation notwendige Serialisierung von Objekten ist über die Boost.Serialization Bibliothek implementiert.

Rechenaufträge können durch mehrere Erzeuger an einen Broker übergeben werden, der über Plugins für die Verteilung an Interessenten sowie die Rückübergabe fertiger Rechenaufträge an die Erzeuger sorgt. Neben der Netzwerkkommunikation sind andere Konsumenten möglich. So wurden die Einzelschritte hinter Film 1 etwa mit einem GPGPU-Backend auf Basis von OpenCL erzeugt.

Erzeugung von Zufallszahlen

Viele stochastische Optimierungsverfahren, wie etwa Evolutionäre Algorithmen, benötigen für eine erfolgreiche Optimierung große Mengen an Zufallszahlen – im Fall Evolutionärer Algorithmen meist mit einer Normalverteilung. Da die Optimierung jedoch in Zyklen verläuft, unterliegt die über die Zeit benötigte Rechenleistung periodischen Schwankungen. Entsprechend gibt es Zeiten niedriger Auslastung, die für die Erzeugung von Zufallszahlen verwendet werden können. Die Geneva Bibliothek nutzt dies im Rahmen einer „Zufallszahlenfabrik“ aus, die im Hintergrund in mehreren Threads Puffer mit im Intervall ${\displaystyle [0,1[}$ gleichverteilten Zufallszahlen füllt (bis zu einer vorgegebenen Grenze). „Proxy-Objekte“ in den Konsumenten können einer Queue der Zufallszahlenfabrik Pakete von Zufallszahlen entnehmen. Diese werden den Konsumenten bei Bedarf einzeln transparent zur Verfügung gestellt – die Proxy-Objekte sehen für diese wie Zufallszahlengeneratoren aus. Hierbei kann bei Bedarf auch die Umrechnung in vom Konsument benötigte Zufallsverteilungen erfolgen. Durch das kontinuierliche Füllen von Puffern mit Zufallszahlen können insbesondere Zeiten niedriger Aktivität besser genutzt werden. Ferner entfallen Probleme mit dem Setzen der Seeds der Generatoren, die dann auftreten würden, wenn jeder der (möglicherweise tausenden von) Konsumenten einen eigenen Generator verwenden würde. Diese Funktionalität ist in der libhap implementiert.