Lokale Suche

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.[1] 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

[Bearbeiten | Quelltext bearbeiten]

Eine Instanz eines Optimierungsproblems ist ein Paar , bei der die Menge die Menge aller zulässigen Lösungen bezeichnet und die Funktion jeder Lösung einen Qualitätswert zuweist. Ziel der Optimierung ist es (bei einem Maximierungsproblem), eine Lösung zu finden, so dass gilt: . Eine solche Lösung wird auch als globales Optimum bezeichnet. Von einem lokalen Optimum spricht man hingegen, wenn gilt: .[2] Wegen 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 -dimensionalen kombinatorischen Optimierungsproblems ist die Menge aller Permutationen einer -elementigen Basismenge der zu permutierenden Objekte. Im Falle eines Parameteroptimierungsproblems kann folgendermaßen definiert werden:[2] , wobei für die typischerweise gilt: oder .

Die lokale Suche geht folgendermaßen vor:

  1. Bestimme eine Startlösung .
  2. Definiere eine Nachbarschaft von zu „ä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. 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 Kanten und Hinzunahme von 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 -dimensionalen Optimierungsproblem mit 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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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. a b 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. a b c 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.