Lokale Suche (Constraint-Zufriedenheit) - Local search (constraint satisfaction)

Bei der Erfüllung von Einschränkungen ist die lokale Suche eine unvollständige Methode, um eine Lösung für ein Problem zu finden . Es basiert auf der iterativen Verbesserung einer Zuordnung der Variablen, bis alle Einschränkungen erfüllt sind. Insbesondere ändern lokale Suchalgorithmen typischerweise den Wert einer Variablen in einer Zuweisung bei jedem Schritt. Die neue Zuordnung befindet sich im Zuweisungsbereich in der Nähe der vorherigen, daher der Name lokale Suche .

Alle lokalen Suchalgorithmen verwenden eine Funktion, die die Qualität der Zuweisung bewertet, z. B. die Anzahl der Einschränkungen, gegen die die Zuweisung verstößt. Dieser Betrag wird die angerufene Kosten der Zuordnung. Das Ziel der lokalen Suche besteht darin, eine Zuordnung mit minimalen Kosten zu finden, die gegebenenfalls eine Lösung darstellt.

Punkt A ist keine Lösung, aber kein lokaler Umzug von dort senkt die Kosten. Am Punkt B existiert jedoch eine Lösung.

Es gibt zwei Klassen lokaler Suchalgorithmen. Der erste ist der von gierigen oder nicht randomisierten Algorithmen. Diese Algorithmen ändern die aktuelle Zuordnung, indem sie immer versuchen, ihre Kosten zu senken (oder zumindest nicht zu erhöhen). Das Hauptproblem dieser Algorithmen ist das mögliche Vorhandensein von Plateaus , die Bereiche des Zuweisungsraums sind, in denen keine lokale Bewegung die Kosten senkt. Die zweite Klasse lokaler Suchalgorithmen wurde erfunden, um dieses Problem zu lösen. Sie entkommen diesen Plateaus durch zufällige Bewegungen und werden als randomisierte lokale Suchalgorithmen bezeichnet.

Gierige Algorithmen

Berg steigen

Die grundlegendste Form der lokalen Suche basiert auf der Auswahl der Änderung, die die Kosten der Lösung maximal senkt. Diese als Bergsteigen bezeichnete Methode läuft wie folgt ab: Zunächst wird eine zufällige Zuordnung gewählt; Dann wird ein Wert geändert, um die Qualität der resultierenden Zuordnung maximal zu verbessern. Wenn nach einer bestimmten Anzahl von Änderungen keine Lösung gefunden wurde, wird eine neue zufällige Zuordnung ausgewählt. Hill Climbing-Algorithmen können einem Plateau nur entkommen, indem sie Änderungen vornehmen, die die Qualität der Aufgabe nicht ändern. Infolgedessen können sie in einem Plateau stecken bleiben, in dem die Qualität der Zuordnung lokale Maxima aufweist.

GSAT (Greedy Sat) war der erste lokale Suchalgorithmus für Erfüllbarkeit und ist eine Form des Bergsteigens.

Constraint-Gewichtungs- oder Breakout-Methode

Eine Methode, um einem lokalen Minimum zu entkommen, besteht darin, eine gewichtete Summe von verletzten Einschränkungen als Maß für die Kosten zu verwenden und einige Gewichte zu ändern, wenn keine Verbesserung der Bewegung verfügbar ist. Genauer gesagt, wenn keine Änderung die Kosten der Zuweisung verringert, erhöht der Algorithmus das Gewicht der Einschränkungen, gegen die die aktuelle Zuweisung verstößt.

Auf diese Weise werden sie durch jede Bewegung, die sonst die Kosten der Lösung nicht ändern würde, verringert. Darüber hinaus nimmt das Gewicht von Einschränkungen, die für eine große Anzahl von Zügen verletzt bleiben, weiter zu. Daher steigen während einer Anzahl von Zügen, die eine Einschränkung nicht erfüllen, die Kosten für Züge zu Zuweisungen, die diese Einschränkung erfüllen, weiter an.

Tabu-Suche

Ein Nachteil des Bergsteigens mit Bewegungen, die die Kosten nicht senken, besteht darin, dass Aufgaben mit denselben Kosten überfahren werden können. Die Tabu-Suche überwindet dieses Problem, indem eine Liste "verbotener" Zuweisungen geführt wird, die als Tabu-Liste bezeichnet wird . Insbesondere enthält die Tabu-Liste normalerweise nur die neuesten Änderungen. Genauer gesagt enthält es das letzte Variablen-Wert-Paar, sodass die Variable kürzlich dem Wert zugewiesen wurde.

Diese Liste wird jedes Mal aktualisiert, wenn die Zuordnung geändert wird. Wenn einem Wert eine Variable zugewiesen wird, wird das Variablen-Wert-Paar zur Liste hinzugefügt und das älteste Paar daraus entfernt. Auf diese Weise enthält die Liste nur die neuesten Zuordnungen zu einer Variablen. Befindet sich ein Variablen-Wert-Paar in der Tabu-Liste, ist das Ändern der aktuellen Zuordnung durch Setzen der Variablen auf den Wert verboten. Der Algorithmus kann nur den besten Zug unter denjenigen auswählen, die nicht verboten sind. Auf diese Weise kann nicht dieselbe Lösung durchlaufen werden, es sei denn, die Anzahl der Züge in diesem Zyklus ist größer als die Länge der Tabu-Liste.

Zielloser Spaziergang

Ein Random-Walk- Algorithmus bewegt sich manchmal wie ein gieriger Algorithmus, manchmal aber auch zufällig. Dies hängt von einem Parameter ab , bei dem es sich um eine reelle Zahl zwischen 0 und 1 handelt. Bei jeder Bewegung verhält sich der Algorithmus mit der Wahrscheinlichkeit wie ein gieriger Algorithmus und versucht, die Kosten der Zuweisung maximal zu senken. Mit der Wahrscheinlichkeit wird die Lösung jedoch auf eine andere Weise geändert, was einen gewissen Grad an Zufälligkeit mit sich bringt. ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle 1-p}$

WalkSAT

Die zufällige Bewegung von WalkSAT ändert den Wert einer Zufallsvariablen einer zufällig verletzten Einschränkung. Für die propositionale Erfüllbarkeit von Formeln der konjunktiven Normalform , die die ursprünglichen Einstellungen dieses Algorithmus sind, ändert jede solche Bewegung den Wert der Variablen von wahr zu falsch oder umgekehrt und erzeugt die Erfüllbarkeit der verletzten Einschränkung. Wie bei allen Random-Walk-Strategien wird eine zufällige Bewegung nur mit einer bestimmten Wahrscheinlichkeit ausgeführt, und eine Bewegung, die die Kosten maximal senkt, wird ansonsten ausgeführt.

Simuliertes Glühen

Die Technik des simulierten Temperns basiert auf der Änderung der Wahrscheinlichkeit einer zufälligen Bewegung über eine, die die Kosten maximal senkt. Insbesondere stammt der Name aus der Strategie, die Wahrscheinlichkeit von zufälligen Bewegungen während der Ausführung des Algorithmus zu verringern und so den Suchraum praktisch "einzufrieren".

Insbesondere wenn die Verbesserung der Kosten eines Umzugs negativ ist (der Umzug erhöht die Kosten), erfolgt dieser Umzug mit Wahrscheinlichkeit , wobei es sich um eine reelle Zahl handelt. Da die Wahrscheinlichkeit, diese Bewegung auszuführen, mit zunimmt , wird dieser Parameter als Temperatur bezeichnet . Durch simuliertes Tempern wird diese Temperatur im Laufe der Zeit gesenkt, wodurch mehr zufällige Bewegungen zu Beginn und weniger nach der Zeit möglich sind. ${\ displaystyle d}$${\ displaystyle e ^ {- d \ cdot T}}$${\ displaystyle T}$${\ displaystyle T}$

Lokale Suche in einem Zyklus-Cutset

Die lokale Suche funktioniert normalerweise für alle Variablen und verbessert deren vollständige Zuordnung. Die lokale Suche kann jedoch auch für eine Teilmenge von Variablen ausgeführt werden, wobei ein anderer Mechanismus für die anderen Variablen verwendet wird. Ein vorgeschlagener Algorithmus arbeitet mit einem Zyklus-Cutset , bei dem es sich um eine Reihe von Variablen handelt, die, wenn sie aus dem Problem entfernt werden, azyklisch werden.

Für jede Zuordnung der Variablen der Trenngruppe, hat das verbleibende Problem , einen Wald als Ur - Graph. Dadurch kann es effizient gelöst werden. Um die lokale Suche zu steuern, wird anstelle eines Erfüllbarkeitsalgorithmus für den for-Forest-Teil des Problems ein Algorithmus verwendet, der die minimale Anzahl von Einschränkungen erkennt, gegen die verstoßen werden kann.

Diese minimale Anzahl wird ermittelt, indem die Kosten für jede Variablenzuweisung ermittelt werden. Diese Kosten sind die minimale Anzahl von Einschränkungen, die durch eine Zuweisung der Variablen in dem auf der Variablen verwurzelten Teilbaum verletzt werden, wenn die Variable den angegebenen Wert annimmt. Diese Kosten können wie folgt berechnet werden. Wenn die Kosten der Aufgabe angegeben werden und deren Kinder untergeordnet sind , gilt die folgende Formel. In dieser Formel ist die 0 oder 1 abhängig davon, ob die Zuweisung die Einschränkung zwischen und verletzt . ${\ displaystyle Cost (x = a)}$${\ displaystyle x = a}$${\ displaystyle y_ {1}, \ ldots, y_ {n}}$${\ displaystyle x}$${\ displaystyle Violates (x = a, y_ {i} = b)}$${\ displaystyle x = a, y_ {i} = b}$${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle Cost (x = a) = \ sum _ {i = 1, \ ldots, n} \ min _ {y_ {i} = b} (Cost (y_ {i} = b) + Violates (x = a , y_ {i} = b))}$

Die Kosten für Variablen im Cutset sind Null, und es wird angenommen, dass diese Variablen nur ihren angegebenen Wert annehmen dürfen. Mit diesen Annahmen ermöglicht die obige Formel die Berechnung der Kosten aller variablen Bewertungen, indem iterativ von unten nach oben von den Blättern zu den Wurzeln des Waldes vorgegangen wird.

Die Kosten für variable Auswertungen können durch lokale Suche zur Berechnung der Kosten einer Lösung verwendet werden. Die Kosten der Werte der Wurzeln des Waldes sind in der Tat die minimale Anzahl von verletzten Einschränkungen im Wald für diese gegebenen Werte. Diese Kosten können daher verwendet werden, um die Kosten der Zuordnung zu den Cutset-Variablen zu bewerten und die Kosten ähnlicher Zuweisungen für die Cutset-Variablen zu schätzen.

Externe Links

• Erzwungene zufriedenstellende CSP- und SAT-Benchmarks des Modells RB

Verweise

• Dechter, Rina (2003). Constraint-Verarbeitung . Morgan Kaufmann. ISBN 978-1-55860-890-0.