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 alle ähnlichen Lösungen in einer geeignet definierten Nachbarschaft abzusuchen und von diesen die beste auszuwählen.

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: 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:

1. Bestimme eine Startlösung $i \in L$.
2. Definiere eine Nachbarschaft von zu i „ähnlichen“ Lösungen.
3. 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 Problems 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

• Simulierte Abkühlung
• Tabu Search

Referenzen

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