Lokale Suche

Eine Instanz eines Optimierungsproblems ist ein Paar ${\displaystyle (L,f)}$, bei der die Menge ${\displaystyle L}$ die Menge aller zulässigen Lösungen bezeichnet und die Funktion ${\displaystyle f\colon L\rightarrow \mathbb {R} }$ jeder Lösung einen Qualitätswert zuweist. Ziel der Optimierung ist es (bei einem Maximierungsproblem), eine Lösung ${\displaystyle i\in L}$ zu finden, so dass gilt: ${\displaystyle f(i)\geq f(u)\ \forall u\in L}$. Eine solche Lösung wird auch als globales Optimum bezeichnet. Von einem lokalen Optimum ${\displaystyle {\widehat {i}}}$ spricht man hingegen, wenn gilt: ${\displaystyle \exists \epsilon >0\ \forall u\in L:\ \parallel u-{\widehat {i}}\parallel <\epsilon \Rightarrow f({\widehat {i}})\geq f(u)}$.[2] Wegen ${\displaystyle \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 ${\displaystyle n}$-dimensionalen kombinatorischen Optimierungsproblems ist ${\displaystyle L}$ die Menge aller Permutationen einer ${\displaystyle n}$-elementigen Basismenge der zu permutierenden Objekte. Im Falle eines Parameteroptimierungsproblems kann ${\displaystyle L}$ folgendermaßen definiert werden:[2] ${\displaystyle L\subseteq L_{1}\times \cdots \times L_{n},\ L\neq 0}$, wobei für die ${\displaystyle L_{i}}$ typischerweise gilt: ${\displaystyle L_{i}\subseteq \mathbb {R} }$ oder ${\displaystyle L_{i}\subseteq \mathbb {Z} }$.

Die lokale Suche geht folgendermaßen vor:

1. Bestimme eine Startlösung ${\displaystyle s\in L}$.
2. Definiere eine Nachbarschaft von zu ${\displaystyle s}$ „ähnlichen“ Lösungen.
3. Suche diese Nachbarschaft oder einen Teil davon ab und bestimme die beste Lösung ${\displaystyle 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 ${\displaystyle k}$ Kanten und Hinzunahme von ${\displaystyle 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.[3]
• Das Downhill-Simplex-Verfahren von Nelder und Mead[4], das nicht mit dem Simplex-Verfahren der linearen Programmierung von G. Danzig verwechselt werden darf, arbeitet bei einem ${\displaystyle n}$-dimensionalen Optimierungsproblem mit ${\displaystyle 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).[5][6]

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[7][3]
• Verfahren nach Powell[8]
• Verfahren von Rosenbrock[9][3]

• 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

1. Juraj Hromkovič: Theoretische Informatik. 5. Auflage. Springer Fachmedien, Wiesbaden 2014, ISBN 978-3-658-06432-7, Algorithmik für schwere Probleme, S. 217–240, doi:10.1007/978-3-658-06433-4.
2. Thomas Bäck, Frank Hoffmeister, Hans-Paul Schwefel: A Survey of Evolution Strategies. In: Richard K. Belew, Lashon B. Booker (Hrsg.): Conf. Proc. of the 4th Int. Conf. on Genetic Algorithms (ICGA). Morgan Kaufmann, San Francisco, CA, USA 1991, ISBN 1-55860-208-9, S. 2–9, S. 2 (researchgate.net [abgerufen am 13. Januar 2024]).
3. Hans-Paul Schwefel: Evolution and Optimum Seeking (= Sixth-generation computer technology series). 1. Auflage. Wiley & Sons, New York 1995, ISBN 978-0-471-57148-3, Hill climbing Strategies, S. 23–85 (researchgate.net).
4. J. A. Nelder, R. Mead: A Simplex Method for Function Minimization. In: The Computer Journal. Band 7, Nr. 4, 1. Januar 1965, ISSN 0010-4620, S. 308–313, doi:10.1093/comjnl/7.4.308.
5. M. J. Box: A New Method of Constrained Optimization and a Comparison With Other Methods. In: The Computer Journal. Band 8, Nr. 1, 1. April 1965, ISSN 0010-4620, S. 42–52, doi:10.1093/comjnl/8.1.42.
6. Hans-Paul Schwefel: Evolution and Optimum Seeking (= Sixth-generation computer technology series). Wiley & Sons, New York 1995, ISBN 978-0-471-57148-3, S. 61–65, Complex Strategy of Box (researchgate.net).
7. Robert Hooke, T. A. Jeeves: "Direct Search" Solution of Numerical and Statistical Problems. In: Journal of the ACM. Band 8, Nr. 2, April 1961, ISSN 0004-5411, S. 212–229, doi:10.1145/321062.321069.
8. M. J. D. Powell: An efficient method for finding the minimum of a function of several variables without calculating derivatives. In: The Computer Journal. Band 7, Nr. 2, 1. Februar 1964, ISSN 0010-4620, S. 155–162, doi:10.1093/comjnl/7.2.155.
9. H. H. Rosenbrock: An Automatic Method for Finding the Greatest or Least Value of a Function. In: The Computer Journal. Band 3, Nr. 3, 1. März 1960, ISSN 0010-4620, S. 175–184, doi:10.1093/comjnl/3.3.175.