Grundzustandsstruktur ungeordneter Systeme und Dynamik von Optimierungsalgorithmen

Abstract

Kombinatorische Optimierungsprobleme aus der Theoretischen Informatik haben mit bestimmten magnetischen Materialien, den Spingläsern, die gemeinsame Eigenschaft, dass eine große Anzahl von Teilchen oder Variablen durch miteinander konkurrierende Wechselwirkungen gekoppelt sind. In dieser Arbeit werden drei derartige Systeme betrachtet, für die die Bestimmung der optimalen Zustände (genannt Grundzustände bzw. Lösungen), in denen möglichst viele Wechselwirkungen befriedigt sind, ein algorithmisch schwieriges Problem darstellt.Für dreidimensionale Ising-Spingläser wird mit Hilfe eines stark verbesserten Algorithmus zur Grundzustandsbestimmung die Energiedifferenz zwischen Grundzustand und erstem angeregten Zustand untersucht. Die Wahrscheinlichkeit einer systemweiten Anregung mit endlicher Energiedifferenz nimmt nicht mit wachsender Systemgröße ab, was mit den Voraussagen der Molekularfeldnäherung übereinstimmt.Für das Vertex-Cover-Problem aus der Theoretischen Informatik wird die Struktur der Grundzustände für ein bestimmtes Ensemble von Zufallsgraphen mit ursprünglich u. a. für Spinglser entwickelten numerischen Clusterungsmethoden betrachtet. In einem einem bestimmten Parameterbereich des Ensembles besteht die Grundzustandslandschaft aus einem einzigen Cluster, was mit bereits bekannten analytischen Ergebnissen übereinstimmt. Im anderen Bereich sind die Grundzustände in einer hierarchischen Clusterstruktur organisiert, was mit kontinuierlicher Replika-Symmetriebrechung kompatibel ist.Für ein anderes Optimierungsproblem, dem Erfüllbarkeitsproblem, wird die Dynamik eines Algorithmus zur Bestimmung von Lösungen analytisch beschrieben. Im dabei betrachteten Ensemble werden zwei Phasen identifiziert: In der einen findet der Algorithmus Lösungen schnell, d. h. in einer Zeit, die linear mit der Systemgröße steigt. In der anderen Phase steigt die Lösungszeit dagegen exponentiell. Die analytisch vorausgesagten Lösungszeiten stimmen qualitativ gut mit numerischen Simulationen berein.