Lokale Suche

Eine lokale Suche wird von numerischen Verfahren, Heuristiken oder Metaheuristiken durchgeführt, die eine gewisse Umgebung eines Startpunktes nach einem Optimum durchsuchen. Die Definition der Umgebung und die Art der Suche kennzeichnen dabei ein lokales Suchverfahren. Meist wird von einem Startpunkt oder einer Startlösung ausgegangen. Lokale Suchverfahren finden in der Regel ein lokales Optimum und können keinesfalls garantieren, das globale zu finden. Sie 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 aus der gerade betrachteten Nachbarschaft gefunden wird. Der Vorgang wird wiederholt, bis die gesamte Nachbarschaft abgesucht ist oder innerhalb einer vorgegebenen Anzahl von hintereinander ausgeführten Iterationen keine oder nur noch geringe Verbesserungen erreicht werden oder ein vorgegebenes Laufzeitende oder eine Iterationsobergrenze erreicht ist.

Formale Definition

Eine Instanz eines Optimierungsproblems ist ein Paar $(L,f)$, bei der die Menge $L$ die Menge aller zulässigen Lösungen bezeichnet und die Funktion $f\colon L\rightarrow \mathbb {R}$ jeder Lösung einen Qualitätswert zuweist. Ziel der Optimierung ist es (bei einem Maximierungsproblem), eine Lösung $i\in L$ zu finden, so dass gilt: $f(i)\geq f(u)\ \forall u\in L$. Eine solche Lösung wird auch als globales Optimum bezeichnet. Von einem lokalen Optimum ${\widehat {i}}$ spricht man hingegen, wenn gilt: $\exists \epsilon >0\ \forall u\in L:\ \parallel u-{\widehat {i}}\parallel <\epsilon \Rightarrow f({\widehat {i}})\geq f(u)$. Wegen $\max {f(u)}=-\min {-f(u)}$ kann ein Minimierungsproblem leicht in die hier zu Grunde gelegte Maximierungsaufgabe überführt werden. Somit stellt dies keine Einschränkung der Allgemeinheit dar.

Im Falle eines $n$-dimensionalen kombinatorischen Optimierungsproblems ist $L$ die Menge aller Permutationen einer $n$-elementigen Basismenge der zu permutierenden Objekte. Im Falle eines Parameteroptimierungsproblems kann $L$ folgendermaßen definiert werden: $L\subseteq L_{1}\times \cdots \times L_{n},\ L\neq 0$, wobei für die $L_{i}$ typischerweise gilt: $L_{i}\subseteq \mathbb {R}$ oder $L_{i}\subseteq \mathbb {Z}$.

Algorithmen

Die lokale Suche geht folgendermaßen vor:

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

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. Ein Teil dieser Festlegungen ist meist problemspezifisch. Im Folgenden sollen einige Beispiele für lokale Suchverfahren genannt werden:

• Bei den K-Opt-Heuristiken für das kombinatorische 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 den Hillclimbing-Verfahren, die für Parameteroptimierungsprobleme entwickelt wurden, wird so lange der Richtung des stärksten Anstiegs gefolgt, bis keine weitere Verbesserung des Qualitätswertes mehr möglich ist. Die Nachbarschaft besteht somit vor allem aus allen Punkten, die besser sind als der aktuelle. Es gibt eine Fülle unterschiedlicher Verfahren, die sich größtenteils darin unterscheiden, ob sie
  • mit der Qualitätsfunktion auskommen oder auch deren Ableitung benötigen,
  • Restriktionen berücksichtigen können oder nicht,
  • einfach aufgebaut sind, so dass die nächsten Testpunkte schnell berechnet werden können oder ob die Suche komplexer und damit rechenzeitintensiver gestaltet ist.
• Das Downhill-Simplex-Verfahren von Nelder und Mead, das nicht mit dem Simplex-Verfahren der linearen Programmierung von G. Danzig verwechselt werden darf, arbeitet bei einem $n$-dimensionalen Optimierungsproblem mit $n+1$ Punkten, die einen Simplex im Suchraum bilden. Bei der Suche wird der Simplex entsprechend der Qualität der Eckpunkte Reflexions-, Kontraktions- und Expansions-Operationen unterworfen, die eine Kontraktion des Simplex bei einem (lokalen) Optimum zum Ziel haben. Da das Verfahren unter Umständen auch kleinere Täler überspringen kann, führt es streng genommen keine rein lokale Suche durch. Es liegt damit zwischen den eigentlichen lokalen Suchverfahren und den global suchenden, wie z. B. den populationsbasierten Metaheuristiken. Erwähnenswert ist noch die Restriktionen berücksichtigende Variante des Verfahrens von M. J. Box names Complex (COnstrained siMPLEX).

Die nachstehende Liste enthält einige weitere lokale Suchverfahren, wobei nur solche aufgelistet sind, die mit dem Wert der Qualitätsfunktion auskommen. Algorithmen, die zusätzlich deren Ableitung benötigen, gehören zu den Gradientenverfahren und sind in dem entsprechenden Artikel zu finden.

• Simulierte Abkühlung
• Tabu Search
• Gauß-Seidel-Verfahren
• Verfahren von Hooke und Jeeves
• Verfahren nach Powell
• Verfahren von Rosenbrock

Literatur

• Emile Aarts, Jan Karel Lenstra: Local Search in Combinatorial Optimization. John Wiley & Sons, New York 1997, ISBN 0-471-94822-5 doi: 10.2307/j.ctv346t9c
• Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit: Local search heuristic for k-median and facility location problems. In: Conf. Proc of the 33rd annual ACM symposium on Theory of computing (STOC '01), ACM 2001, S. 21–29 ISBN 978-1-58113-349-3 doi:10.1145/380752.380755
• Stuart J. Russell, Peter Norvig: Artificial Intelligence: A Modern Approach. Prentice Hall series in artificial intelligence, Prentice Hall, Hoboken, NJ, USA 2020, 4. Auflage, Kapitel „Solving Problems by Searching“ und „Search in Complex Environments“, S. 63–145, ISBN 978-0-13-461099-3
• Hans-Paul Schwefel: Evolution and Optimum Seeking. Wiley & Sons, New York 1995, Kapitel „Hill climbing Strategies“, S. 23–85 ISBN 0-471-57148-2.
• Holger Hoos, Thomas Stützle: Stochastic Local Search: Foundations & Applications. Morgan Kaufmann, San Francisco CA, USA 2004 ISBN 978-1-55860-872-6 doi:10.1016/B978-155860872-6/50021-4
• Wil Michiels, Jan Korst, Emile Aarts: Theoretical Aspects of Local Search. Springer, Berlin, Heidelberg 2006, ISBN 978-3-540-35853-4 doi:10.1007/978-3-540-35854-1