Lokale Suche

Die lokale Suche ist ein Oberbegriff für eine Reihe von metaheuristischen Suchverfahren der kombinatorischen Optimierung. Die Verfahren werden in vielen Variationen dafür genutzt, komplizierte Optimierungsprobleme näherungsweise zu lösen (z. B. das Problem des Handlungsreisenden). Das Grundprinzip besteht darin, ausgehend von einer gegebenen Startlösung eine bessere Lösung zu finden, indem durch eine lokale Änderung der aktuellen Lösung eine bessere Lösung aus der gerade betrachteten Nachbarschaft gefunden wird[1].

Formale Definition

Eine Instanz eines kombinatorischen Optimierungsproblems ist ein Paar $(L,f)$ , bei der die Menge $L$ die Menge aller möglicher Lösungen bezeichnet und die Funktion $f\colon L\rightarrow \mathbb {R}$ jeder Lösung einen Kostenwert zuweist. Ziel der Optimierung ist es (bei einem Minimierungsproblem), eine Lösung $i\in L$ zu finden, so dass $f(i)\leq f(u)$ für alle $u\in L$ gilt. Die lokale Suche geht folgendermaßen vor:

Bestimme eine Startlösung $i\in L$ .
Definiere eine Nachbarschaft von zu $i$ „ähnlichen“ Lösungen.
Suche diese Nachbarschaft oder einen Teil davon ab und bestimme die beste Lösung.

Die genaue Art der lokalen Suche bestimmt sich dadurch, wie eine Startlösung generiert wird (z. B. zufällig generiert oder durch eine Konstruktionsheuristik), wie der Nachbarschaftsbegriff definiert ist und wie die Abbruchbedingungen festgelegt sind. Diese Festlegungen sind in aller Regel problemspezifisch. Im Folgenden sollen einige Beispiele für Nachbarschaftsfunktionen genannt werden:

Bei den K-Opt-Heuristiken für das Problem des Handlungsreisenden sind zwei Lösungen (in diesem Fall Rundreisen) benachbart, wenn durch Entfernen von $k$ Kanten und Hinzunahme von $k$ anderen Kanten in der einen Tour die andere Tour konstruiert werden kann.
Bei ganzzahligen linearen Programmen können zwei Lösungen benachbart sein, wenn eine bestimmte Menge von Variablen in beiden Lösungen den gleichen Wert besitzt. Eine mögliche lokale Suchstrategie ist hier, diese Variablen auf den gemeinsamen Wert zu fixieren und das restliche Problem exakt zu lösen.

Algorithmen

Literatur

Local Search in Combinatorial Optimization, Emile Aarts and Jan Karel Lenstra, John Wiley & Sons, 1997, ISBN 0471948225

Einzelnachweise

Juraj Hromkovic, Theoretische Informatik: S. 279

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Juraj Hromkovic, Theoretische Informatik: S. 279