Grundlegende Konzepte für die Optimierung

Um Optimierungsprobleme zu verstehen, müssen Sie zunächst einige grundlegende Begriffe und Konzepte lernen.

Kostenfunktion

Eine Kostenfunktion ist eine mathematische Beschreibung eines Problems, das Ihnen bei der Auswertung den Wert dieser Lösung angibt. In der Regel suchen wir bei Optimierungsproblemen nach der Lösung mit dem niedrigsten Wert für ein Problem. In anderen Worten, wir versuchen, die Kosten zu minimieren.

Suchbereich

Der Suchbereich enthält alle möglichen Lösungen für ein Optimierungsproblem. Jeder Punkt in diesem Suchbereich stellt eine gültige Lösung des Problems dar. Dabei entspricht jedoch nicht unbedingt der niedrigste Punkt der kostengünstigsten Lösung.

Optimierungslandschaft

Der Suchraum und die Kostenfunktion werden zusammen häufig als Optimierungslandschaft bezeichnet. Ein Problem mit zwei stetigen Variablen kann durchaus direkt mit einer solchen Landschaft beschrieben werden.

Erforschen wir ein paar verschiedene Optimierungslandschaften und sehen wir, welche davon gute Kandidaten für die Azure Quantum Optimierung sind.

Eine glatte, konvexe Landschaft

Betrachten Sie das folgende Plot einer Kostenfunktion, die einem durchgehenden glatten Tal ähnelt:

Eine Optimierungslandschaft mit einer glatten Vertiefung

Ein solches Problem lässt sich einfach mit Techniken wie einem Gradientenabstieg lösen, bei dem Sie ausgehend von einem Startpunkt direkt zu einer Lösung mit geringeren Kosten absteigen. Nach einigen Schritten konvergiert die Lösung im globalen Minimum. Das globale Minimum ist der niedrigste Punkt in der Optimierungslandschaft. Die Azure Quantum Optimierungslöser bieten bei diesen einfachen Problemen keine Vorteile gegenüber anderen Techniken.

Strukturierte, zerklüftete Landschaft

Azure Quantum funktioniert am besten bei Problemen, bei denen die Landschaft zerklüftet ist, mit vielen Hügeln und Vertiefungen. Im folgenden Beispiel werden zwei stetige Variablen betrachtet.

Eine Optimierungslandschaft mit vielen Hügeln und Vertiefungen

Eine der größten Herausforderungen diesem Szenario besteht darin, zu verhindern, dass Sie an einem suboptimalen lokalen Minimum stecken bleiben. Eine zerklüftete Landschaft kann mehrere Täler aufweisen. Alle diese Täler weisen einen tiefsten Punkt auf – das lokale Minimum. Einer davon ist der absolut tiefste Punkt und stellt somit das globale Minimum dar. Solche zerklüfteten Landschaften stellen Situationen dar, in denen Azure Quantum anderen Techniken überlegen ist.

Unstrukturierte, zufällige Landschaft

Bisher haben wir glatte und zerklüftete Kostenfunktionen betrachtet. Was aber, wenn überhaupt keine Struktur vorhanden ist? Im folgenden Diagramm wird eine solche Landschaft abgebildet:

Eine Optimierungslandschaft, die streuende Punkte ohne Muster anzeigt

In solchen Fällen, in denen eine Zufallsverteilung der Lösungen vorliegt, ist eine Algorithmus-Verbesserung bei einer Brute-Force-Suche nicht möglich.

Das Definieren einer Kostenfunktion

Wie bereits erwähnt, stellt die Kostenfunktion die zu minimierende Menge dar. Mit dieser Funktion sollen in erster Linie die einzelnen Konfigurationen eines Problems einer Zahl zugeordnet werden. Dadurch kann der Optimierer mögliche Lösungen problemlos vergleichen und so die am besten geeignete Lösung ermitteln. Beim Erstellen einer Kostenfunktion für ein Problem geht es darum, zu erkennen, durch welche Parameter des Systems die gewählten Kosten beeinflusst werden.

Im Prinzip könnte die Kostenfunktion eine beliebige mathematische Funktion sein wie $f = f(x_0, x_1, \dots)$, wobei die Funktionsvariablen $x_1, x_2, \dots$ die verschiedenen Konfigurationen codieren. Die weiter oben dargestellte glatte Landschaft könnte zum Beispiel mit einer quadratischen Funktion zweier stetiger Variablen wie folgt erstellt werden: $f(x, y) = x^2 + y^2$. Für bestimmte Optimierungsmethoden muss die Kostenfunktion jedoch ein bestimmtes Format aufweisen. Die Solver von Azure Quantum erwarten beispielsweise ein binäres Optimierungsproblem. Für diesen Problemtyp müssen Konfigurationen anhand binärer Variablen mit $x_i \in {0, 1}$ ausgedrückt werden, und viele Probleme sind von ihrer Natur her geeignet, in dieser Form ausgedrückt zu werden.

Variablen

Schauen wir uns an, wie man die Kostenfunktion für ein einfaches Problem definiert. Erstens verfügen wir über eine Reihe von Variablen. Wir können diese Variablen x benennen, und wenn wir i-Variablen haben, können wir sie wie folgt einzeln indizieren:

$$ x_{i} $$

Zum Beispiel, wenn wir 5 Variablen hätten, könnten wir wie folgt indizieren:

$$ x_{0}, x_{1}, x_{2}, x_{3}, x_{4} $$

Diese Variablen können bestimmte Werte aufnehmen, und im Fall eines binären Optimierungsproblems können sie nur zwei aufnehmen. Insbesondere, wenn Ihr Problem diese Variablen als Spins betrachtet, wie im Ising-Modell, dann können die Werte der Variablen entweder +1 oder -1 sein.

Beispiel:

$$ x_{0} = 1, x_{1} = 1, x_{2} = -1, x_{3} = -1, x_{4} = 1 $$

In anderen Fällen können die Variablen einfach 1 oder 0 zugewiesen werden, wie im Quadratic Unconstrained Binary Optimization (Quadratische Ungebundene Binäre Optimierung - QUBO) oder Polynomial Unconstrained Binary Optimization (Polynomielle Uneingeschränkte Binäre Optimierung - PUBO)-Modell.

Beispiel:

$$ x_{0} = 1, x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 1 $$

Hinweis

Weitere Informationen zu Kostenfunktionen und binären Optimierungsmodellen wie Ising und PUBO finden Sie im Artikel Kostenfunktionen.

Weights

Betrachten wir einige Variablen. Jede dieser Variablen hat ein zugeordnetes Gewicht, welches ihren Einfluss auf die Gesamtkostenfunktion bestimmt.

Wir können diese Gewichte als w schreiben, und wenn wir i-Variablen haben, kann das zugeordnete Gewicht dann für diese einzelnen Variablen wie folgt indiziert werden

$$ w_{i} $$

Hätten wir 5 Gewichte, könnten wir sie wie folgt indizieren:

$$ w_{0}, w_{1}, w_{2}, w_{3}, w_{4} $$

Eine Gewicht kann eine beliebige reell-wertige Zahl sein. Beispielsweise könnten wir diesen Gewichten die folgenden Werte zuordnen:

$$ w_{0} = 50, w_{1} = -2, w_{2} = 7, w_{3} = 24, w_{4} = -10 $$

Begriffe

Begriffe sind die Kombination aus Gewichten und Variablen. Sie sehen wie folgendermaßen aus:

$$ w_{i}x_{i} $$

Betrachten wir beispielsweise einen Begriff mit einem Index 0, ein Gewicht von 50 und einer Variablenzuordnung von 1:

$$ w_{0}x_{0} = 50(1) = 50 $$

Hierbei handelte es sich um ein Beispiel für die Bewertung der Kosten eines Begriffs.

Kostenfunktionsformulierung

Um auf unsere Definition einer Kostenfunktion zurückzukommen: Es handelt sich um eine mathematische Beschreibung eines Problems, die, wenn sie ausgewertet wird, den Wert dieser Lösung angibt.

Um eine Kostenfunktion zu schreiben, schreiben wir also eine Summe von Begriffen. Das heißt, die Summe dieser Gewichte und Variablen.

Diese sieht folgendermaßen aus:

$$ \Large\sum_{i}w_{i}x_{i} $$

Mit 5 Variablen würde dies folgendermaßen erweitert werden:

$$ w_ {0} x_{0}+ w_{1} x_{1} + w_ {2} x_{2} + w_ {3}x_{3} + w_{4}x_{4}$$

Grad und „k-lokal"

Bei den Kostenfunktionen, mit denen Sie arbeiten werden, handelt es sich um polynomiale Funktionen unterschiedlichen Grades. Die Variablen selbst sind binär ($x_i \in \{\pm1\ }$ für Ising und $x_i \in \{0, 1\ }$ für QUBO/PUBO-Probleme), wodurch diese binären Optimierungsprobleme verursacht werden.

In einigen Fällen ist die Kostenfunktion linear. Das bedeutet, dass die höchste Potenz jeglicher der Begriffe erhöht wird auf 1 erhöht wird. $x + y + 1$ ist ein Beispiel für eine lineare Funktion. Angeblich weisen lineare Begriffe einen Grad von 1 auf.

In anderen Fällen haben Sie möglicherweise eine quadratische Kostenfunktion. In diesem Fall ist die höchste Potenz, auf die jegliche der Begriffe erhöht wird, 2. $x^2 + y^2 + x + 1$ ist ein Beispiel einer quadratischen Funktion. Diese Funktion weist daher einen Grad von 2 auf (diese werden möglicherweise als Quadratic Unconstrained Binary Optimization (Quadratische Ungebundene Binäre Optimierung - QUBO) -Probleme bezeichnet).

Wenn eine Kostenfunktion Begriffe enthält, die auf höhere Potenzen als 2 erhöht sind, bezeichnen wir sie als Polynomial Unconstrained Binary Optimization (Polynomielle Uneingeschränkte Binäre Optimierung-PUBO) oder Higher Order Binary Optimization (HOBO) -Probleme. Diese Kostenfunktionen haben Grade die höher sind als 2. $x^3 + xy + x^2 + y^2 + x + 1$ ist ein Beispiel für eine polynomiale Funktion höherer Ordnung.

Im Allgemeinen spricht man oft vom maximalen Grad, k, und bezeichnet sie als k-lokale Probleme. Beispielsweise kann ein QUBO auch als 2-lokales Problem bezeichnet werden. Sie können eine polynomiale Funktion höherer Ordnung in eine niedrigere Reihenfolge reduzieren, indem Sie weitere Variablen einführen, wodurch sich die Problemgröße erhöht. Dieses Verfahren wird als Gradverminderung bezeichnet.

In Azure Quantum wird der Begriff PUBO verwendet, um Probleme mit einem maximalen Grad von k zu beschreiben. Dies schließt QUBO-Probleme ein, da es sich bei QUBOs nur um PUBOs mit Grad 2 handelt.

Heuristik

Bei der Heuristik handelt es sich um ein Verfahren zum Suchen einer ungefähren Lösung, wenn es zu lange dauern kann, die genaue Lösung zu finden. Wenn wir uns dies im Hinblick auf unsere oben beschriebene Optimierungslandschaft überlegen, kann es sehr lange dauern, bis wir die kostengünstigste Lösung finden. Wir können jedoch in einem angemessenen Zeitraum eine Lösung finden, die in etwa optimal ist. Dies führt häufig zu Experimenten: Das Ausprobieren verschiedener Techniken mit unterschiedlichen Parametern und Laufzeiten, um herauszufinden, was gute Ergebnisse liefert.

_Walker

Wir können uns eine Person oder einen Partikel in unserem Suchbereich vorstellen, und jeder Schritt erstellt einen Pfad durch die Optimierungslandschaft. Häufig wird dies als Walker bezeichnet. Walker können auf verschiedene Weisen verwendet werden, z. B. können Sie viele Walker vom gleichen Startpunkt aus starten lassen oder sie von verschiedenen Orten aus starten lassen, usw.

Konvertieren Sie Ihr Problems in ein Ising- oder QUBO-Modell

Das Dokument Ising formulations of many NP problems von Professor Andrew Lucas ist eine gute Zusammenfassung, wie man ein NP-Problem in das QIO, QUBO oder Ising-Modell umwandelt. Sie können das Dokument über den bereitgestellten Link herunterladen. Nachdem Sie Ihr Feldproblem in das Ising- oder QUBO-Modell konvertiert haben, wird empfohlen, Begriffe mit der gleichen Variablenliste in einem einzelnen Begriff zusammen zu führen. Als Beispiel: $$ w_{0}x_{0}x_{1}, w_{1}x_{1}x_{0} $$ kann zusammengeführt werden mit

$$ (w_{0} + w_{1})x_{0}x_{1} $$

Ausgedrückt als Code (mit dem QIO Python SDK):

term1 = Term(c=2, indices=[0,1])
term2 = Term(c=3, indices=[1,0])

kann es zusammengeführt werden mit:

merged_term = Term(c=5, indices=[0,1])

Das Zusammenführen von Begriffen kann die Leistung von QIO erheblich verbessern, wenn Ihr Problem sehr viele solcher Begriffe enthält. Sie können entweder eine Hash-Mappierung oder einen Sortieralgorithmus zum Zusammenführen verwenden.