Lokale Suche (Optimierung) - Local search (optimization)

In der Informatik ist die lokale Suche eine heuristische Methode zur Lösung von rechenintensiven Optimierungsproblemen . Lokale Suche kann auf Probleme verwendet werden , die als Suche nach einer Lösung zu maximieren ein Kriterium unter mehrere formuliert werden können Kandidatenlösungen . Lokale Suchalgorithmen bewegen sich im Raum von Kandidatenlösungen (dem Suchraum ) von Lösung zu Lösung, indem lokale Änderungen angewendet werden, bis eine als optimal erachtete Lösung gefunden wird oder eine Zeitgrenze verstrichen ist.

Lokale Suchalgorithmen werden häufig auf zahlreiche harte Rechenprobleme angewendet, darunter Probleme aus der Informatik (insbesondere der künstlichen Intelligenz ), der Mathematik , der Betriebsforschung , den Ingenieurwissenschaften und der Bioinformatik . Beispiele für lokale Suchalgorithmen sind WalkSAT , der 2-Opt-Algorithmus für das Travelling Salesman Problem und der Metropolis-Hastings-Algorithmus .

Beispiele

Einige Probleme, bei denen die lokale Suche angewendet wurde, sind:

  1. Das Vertex - Cover Problem , bei dem eine Lösung ist eine Knotenüberdeckung eines Graphen , und das Ziel ist es, eine Lösung mit einer minimalen Anzahl von Knoten zu finden ,
  2. Das Travelling-Salesman-Problem , bei dem eine Lösung ein Zyklus ist , der alle Knoten des Graphen enthält und das Ziel darin besteht, die Gesamtlänge des Zyklus zu minimieren
  3. Das boolesche Erfüllbarkeitsproblem , bei dem eine Kandidatenlösung eine Wahrheitszuweisung ist und das Ziel darin besteht, die Anzahl der durch die Zuweisung erfüllten Klauseln zu maximieren ; In diesem Fall ist die endgültige Lösung nur von Nutzen, wenn sie alle Klauseln erfüllt
  4. Das Problem der Pflegeplanung, bei dem eine Lösung eine Zuweisung von Pflegekräften zu Schichten ist, die alle festgelegten Einschränkungen erfüllt
  5. Das k-medoide Clustering-Problem und andere verwandte Facility-Location- Probleme, für die die lokale Suche aus Worst-Case-Perspektive die besten bekannten Approximationsverhältnisse bietet
  6. Das Hopfield Neural Networks Problem, für das stabile Konfigurationen im Hopfield Netzwerk gefunden werden .

Beschreibung

Die meisten Probleme können hinsichtlich des Suchraums und des Ziels auf verschiedene Weise formuliert werden. Zum Beispiel kann eine Lösung für das Problem des Handlungsreisenden ein Zyklus sein, und das Kriterium für die Maximierung ist eine Kombination aus der Anzahl der Knoten und der Länge des Zyklus. Eine Lösung kann aber auch ein Weg sein, und ein Kreislauf zu sein ist Teil des Ziels.

Ein lokaler Suchalgorithmus beginnt mit einer Kandidatenlösung und bewegt sich dann iterativ zu einer Nachbarlösung . Dies ist nur möglich, wenn eine Nachbarschaftsbeziehung auf dem Suchraum definiert ist. Als Beispiel ist die Nachbarschaft einer Scheitelpunktüberdeckung eine andere Scheitelpunktüberdeckung, die sich nur um einen Knoten unterscheidet. Bei der booleschen Erfüllbarkeit sind die Nachbarn einer Wahrheitszuordnung in der Regel die Wahrheitszuordnungen, die sich von ihr nur durch die Auswertung einer Variablen unterscheiden. Für dasselbe Problem können mehrere verschiedene Nachbarschaften definiert sein; lokale Optimierung mit Nachbarschaften, die das Ändern von bis zu k Komponenten der Lösung beinhalten, wird oft als k-opt bezeichnet .

Typischerweise hat jede Kandidatenlösung mehr als eine Nachbarlösung; die Auswahl, zu der man wechselt, wird nur anhand von Informationen über die Lösungen in der Nähe der aktuellen getroffen, daher der Name lokale Suche. Wenn die Auswahl der Nachbarlösung unter Verwendung derjenigen erfolgt, die das Kriterium lokal maximiert, nimmt die Metaheuristik den Namen Hill Climbing an . Wenn in der Nachbarschaft keine sich verbessernden Konfigurationen vorhanden sind, bleibt die lokale Suche an einem lokal optimalen Punkt hängen . Dieses lokale Optima-Problem kann durch Neustarts (wiederholte lokale Suche mit unterschiedlichen Anfangsbedingungen) oder komplexere Schemata basierend auf Iterationen, wie iterierte lokale Suche , auf Speicher, wie reaktive Suchoptimierung, auf speicherlosen stochastischen Modifikationen, wie simuliertes Glühen .

Die Beendigung der lokalen Suche kann auf einer Zeitgrenze basieren. Eine andere übliche Wahl ist die Beendigung, wenn die beste vom Algorithmus gefundene Lösung in einer gegebenen Anzahl von Schritten nicht verbessert wurde. Die lokale Suche ist ein jederzeitiger Algorithmus : Sie kann eine gültige Lösung zurückgeben, auch wenn sie zu einem beliebigen Zeitpunkt unterbrochen wird, bevor sie endet. Lokale Suchalgorithmen sind typischerweise Approximations- oder unvollständige Algorithmen , da die Suche auch dann anhalten kann, wenn die beste vom Algorithmus gefundene Lösung nicht optimal ist. Dies kann selbst dann passieren, wenn der Abbruch aufgrund der Unmöglichkeit der Lösungsverbesserung erfolgt, da die optimale Lösung weit von der Nachbarschaft der von den Algorithmen durchquerten Lösungen liegen kann.

Für spezielle Probleme ist es möglich, Nachbarschaften zu entwerfen, die sehr groß sind, möglicherweise exponentiell groß. Wenn die beste Lösung innerhalb der Nachbarschaft effizient gefunden werden kann, werden solche Algorithmen als sehr groß angelegte Nachbarschaftssuchalgorithmen bezeichnet .

Siehe auch

Die lokale Suche ist ein Unterfeld von:

Felder in der lokalen Suche umfassen:

Reellwertige Suchräume

Es gibt mehrere Methoden, um eine lokale Suche von reellwertigen Suchräumen durchzuführen:

Verweise

Literaturverzeichnis