In der Informatik ist lokale Suche eine metaheuristic Methode, um rechenbetont harte Optimierungsprobleme zu lösen. Lokale Suche kann auf Problemen verwendet werden, die als Entdeckung einer Lösung formuliert werden können, die ein Kriterium unter mehreren Kandidat-Lösungen maximiert. Die lokale Suchalgorithmus-Bewegung von der Lösung bis Lösung im Raum von Kandidat-Lösungen (der Suchraum) durch die Verwendung lokaler Änderungen, bis zu einer Lösung hat für optimal gehalten wird gefunden, oder ein fristgebundener wird vergangen.

Lokale Suchalgorithmen werden auf zahlreiche harte rechenbetonte Probleme, einschließlich Probleme von der Informatik (besonders künstliche Intelligenz), Mathematik, Operationsforschung, Technik und bioinformatics weit angewandt. Beispiele von lokalen Suchalgorithmen sind WalkSAT, und die 2 - wählen Algorithmus für das Handelsreisender-Problem.

Beispiele

Einige Probleme, wo lokale Suche angewandt worden ist, sind:

1. Das Scheitelpunkt-Deckel-Problem, in dem eine Lösung ein Scheitelpunkt-Deckel eines Graphen und das Ziel ist, soll eine Lösung mit einer minimalen Zahl von Knoten finden
2. Das Handlungsreisender-Problem, in dem eine Lösung ein Zyklus ist, der alle Knoten des Graphen und des Ziels enthält, soll die Gesamtlänge des Zyklus minimieren
3. Der boolean satisfiability Problem, in dem eine Kandidat-Lösung eine Wahrheitsanweisung und das Ziel ist, soll die Zahl von durch die Anweisung zufriedenen Klauseln maximieren; in diesem Fall ist die Endlösung von Nutzen nur, wenn es alle Klauseln befriedigt
4. Die Krankenschwester, die Problem plant, wo eine Lösung eine Anweisung von Krankenschwestern zu Verschiebungen ist, die alle feststehenden Einschränkungen befriedigt
5. Sich sammelndes Problem des k-medoid und andere zusammenhängende Möglichkeitspositionsprobleme, für die lokale Suche die am besten bekannten Annäherungsverhältnisse von einer Grenzfall-Perspektive anbietet

Beschreibung

Die meisten Probleme können in Bezug auf den Suchraum und das Ziel in mehreren verschiedenen Manieren formuliert werden. Zum Beispiel für das Handlungsreisender-Problem kann eine Lösung ein Zyklus sein, und das Kriterium, um zu maximieren, ist eine Kombination der Zahl von Knoten und der Länge des Zyklus. Aber eine Lösung kann auch ein Pfad sein, und ein Zyklus zu sein, ist ein Teil des Ziels.

Ein lokaler Suchalgorithmus fängt von einer Kandidat-Lösung an und bewegt sich dann wiederholend zu einer Nachbarlösung. Das ist nur möglich, wenn eine Nachbarschaft-Beziehung auf dem Suchraum definiert wird. Als ein Beispiel ist die Nachbarschaft eines Scheitelpunkt-Deckels ein anderer Scheitelpunkt-Deckel, der sich nur durch einen Knoten unterscheidet. Für boolean satisfiability sind die Nachbarn einer Wahrheitsanweisung gewöhnlich die Wahrheitsanweisungen, die sich nur davon durch die Einschätzung einer Variable unterscheiden. Dasselbe Problem kann vielfache verschiedene Nachbarschaft darauf definieren lassen; die lokale Optimierung mit der Nachbarschaft, die das Ändern bis zu einschließt

k Bestandteile der Lösung wird häufig k-opt genannt.

Gewöhnlich hat jede Kandidat-Lösung mehr als eine Nachbarlösung; dessen Wahl, sich dazu zu bewegen, mit nur die Information über die Lösungen in der Nachbarschaft der aktuellen, folglich der Name lokale Suche genommen wird. Wenn die Wahl der Nachbarlösung durch die Einnahme von derjenigen getan wird, die lokal das Kriterium maximiert, nimmt der metaheuristic das Namenhügel-Klettern.

Wenn keine sich verbessernden Konfigurationen in der Nachbarschaft da sind, wird lokale Suche an einem lokal optimalen Punkt durchstochen.

Dieses Problem der lokalen Optima kann durch das Verwenden von Wiederanfängen geheilt werden (hat lokale Suche mit verschiedenen anfänglichen Bedingungen wiederholt), oder kompliziertere Schemas, die auf Wiederholungen, wie wiederholte lokale Suche, auf dem Gedächtnis, wie reaktive Suchoptimierung, auf dem Speicher-weniger stochastische Modifizierungen wie das vorgetäuschte Ausglühen gestützt sind.

Die Beendigung der lokalen Suche kann auf einem fristgebundenen basieren. Eine andere allgemeine Wahl ist zu enden, als die beste durch den Algorithmus gefundene Lösung in einer gegebenen Zahl von Schritten nicht verbessert worden ist. Lokale Suche ist jederzeit Algorithmus:

es kann eine gültige Lösung zurückgeben, selbst wenn es jederzeit unterbrochen wird, bevor es endet.

Lokale Suchalgorithmen sind normalerweise Annäherung oder unvollständige Algorithmen, weil die Suche anhalten kann, selbst wenn die beste durch den Algorithmus gefundene Lösung nicht optimal ist. Das kann geschehen, selbst wenn Beendigung wegen der Unmöglichkeit ist, die Lösung zu verbessern, wie die optimale Lösung weit von der Nachbarschaft der durch die Algorithmen durchquerten Lösungen lügen kann.

Für spezifische Probleme ist es möglich, Nachbarschaft auszudenken, die, vielleicht exponential nach Größen geordnete sehr groß ist. Wenn die beste Lösung innerhalb der Nachbarschaft effizient gefunden werden kann, werden solche Algorithmen sehr groß angelegte Nachbarschaft-Suchalgorithmen genannt.

Siehe auch

Lokale Suche ist ein Teilfeld:

• Metaheuristics
• Stochastische Optimierung
• Optimierung

Felder innerhalb der lokalen Suche schließen ein:

• Hügel, der klettert
• Das vorgetäuschte Ausglühen (angepasst entweder für die lokale oder für globale Suche)
• Tabu Suche
• Reaktive Suchoptimierung (Maschine verbindend, die erfährt und lokale Suchheuristik)

Reellwertige Suchräume

Mehrere Methoden bestehen, um lokale Suche von reellwertigen Suchräumen durchzuführen:

• Luus-Jaakola sucht lokal das Verwenden einer Rechteckverteilung und einer exponential abnehmenden Suchreihe.
• Zufällige Optimierung sucht lokal das Verwenden einer Normalverteilung.
• Zufällige Suche sucht lokal durch die Stichprobenerhebung eines Hyperbereichs, der die aktuelle Position umgibt.
• Muster-Suche unternimmt entlang den Äxten des Suchraums Schritte, der exponential verwendet, Schritt-Größen vermindernd.

Bibliografie

• Hoos, H.H. und Stutzle, T. (2005) stochastische lokale Suche: Fundamente und Anwendungen, Morgan Kaufmann.
• Vijay Arya und Naveen Garg und Rohit Khandekar und Adam Meyerson und Kamesh Munagala und Vinayaka Pandit, (2004): Lokale Suchheuristik für die K-Mittellinie und Möglichkeitspositionsprobleme, Siam Zeitschrift, 33 (3) Zu rechnen.

Links

• SINTEF Optimierung