imported>Wilfried Jakob: Subreferenzen eingeführt

2025-12-14T11:28:56Z

Subreferenzen eingeführt

Neue Seite

Eine '''lokale Suche''' wird von [[Numerische Mathematik|numerischen Verfahren]], [[Heuristik]]en oder [[Metaheuristik]]en 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 [[Optimum#Suboptimal|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.<ref>{{Literatur |Autor=Juraj Hromkovič |Titel=Theoretische Informatik |Auflage=5. |Verlag=Springer Fachmedien |Ort=Wiesbaden |Datum=2014 |ISBN=978-3-658-06432-7 |DOI=10.1007/978-3-658-06433-4 |Kapitel=Algorithmik für schwere Probleme |Seiten=217-240}}</ref> Der Vorgang wird wiederholt, bis die gesamte Nachbarschaft abgesucht ist oder innerhalb einer vorgegebenen Anzahl von hintereinander ausgeführten [[Iteration]]en 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 <math>(L, f)</math>, bei der die Menge <math>L</math> die Menge aller zulässigen Lösungen bezeichnet und die Funktion <math>f\colon L \rightarrow \mathbb{R}</math> jeder Lösung einen Qualitätswert zuweist. Ziel der Optimierung ist es (bei einem Maximierungsproblem), eine Lösung <math>i \in L</math> zu finden, so dass gilt: <math>f(i) \geq f(u) \ \forall u \in L</math>. Eine solche Lösung wird auch als ''globales Optimum'' bezeichnet. Von einem ''lokalen Optimum'' <math>\widehat{i} </math> spricht man hingegen, wenn gilt: <math>\exists \epsilon > 0 \ \forall u \in L : \ \parallel u - \widehat{i} \parallel < \epsilon \Rightarrow f(\widehat{i}) \geq f(u) </math>.<ref name=":0" /> Wegen <math>\max{f(u)} = -\min{-f(u)}</math> 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 <math>n</math>-dimensionalen [[Kombinatorische Optimierung|kombinatorischen Optimierungsproblems]] ist <math>L</math> die Menge aller [[Permutation]]en einer <math>n</math>-elementigen Basismenge der zu permutierenden Objekte. Im Falle eines Parameteroptimierungsproblems kann <math>L</math> folgendermaßen definiert werden:<ref name=":0">{{Literatur |Autor=Thomas Bäck, Frank Hoffmeister, Hans-Paul Schwefel |Titel=A Survey of Evolution Strategies |Hrsg=Richard K. Belew, Lashon B. Booker |Sammelwerk=Conf. Proc. of the 4th Int. Conf. on Genetic Algorithms (ICGA) |Verlag=Morgan Kaufmann |Ort=San Francisco, CA, USA |Datum=1991 |ISBN=1-55860-208-9 |Seiten=2-9 |Fundstelle=S. 2 |Online=https://www.researchgate.net/publication/220885669_A_Survey_of_Evolution_Strategies |Abruf=2024-01-13}}</ref> <math>L \subseteq L_1 \times \cdots \times L_n, \ L \neq 0</math>, wobei für die <math>L_i</math> typischerweise gilt: <math>L_i \subseteq \mathbb{R}</math> oder <math>L_i \subseteq \mathbb{Z}</math>.

== Algorithmen ==
Die lokale Suche geht folgendermaßen vor:

# Bestimme eine Startlösung <math>s \in L</math>.
# Definiere eine ''Nachbarschaft'' von zu <math>s</math> „ähnlichen“ Lösungen.
# Suche diese Nachbarschaft oder einen Teil davon ab und bestimme die beste Lösung <math>i </math>.

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-Heuristik]]en für das kombinatorische [[Problem des Handlungsreisenden]] sind zwei Lösungen (in diesem Fall Rundreisen) benachbart, wenn durch Entfernen von <math>k</math> [[Kante (Graphentheorie)|Kanten]] und Hinzunahme von <math>k</math> anderen Kanten in der einen Tour die andere Tour konstruiert werden kann.
* Bei den [[Bergsteigeralgorithmus|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,
** [[Einschränkung|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.<ref name=":1" details="Hill climbing Strategies, S. 23–85">{{Literatur |Autor=Hans-Paul Schwefel |Titel=Evolution and Optimum Seeking |Auflage=1. |Verlag=Wiley & Sons |Ort=New York |Datum=1995 |Reihe=Sixth-generation computer technology series |ISBN=978-0-471-57148-3 |Online=https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking}}</ref>
* Das [[Simplex-Verfahren|Downhill-Simplex-Verfahren]] von Nelder und Mead<ref>{{Literatur |Autor=J. A. Nelder, R. Mead |Titel=A Simplex Method for Function Minimization |Sammelwerk=The Computer Journal |Band=7 |Nummer=4 |Datum=1965-01-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/7.4.308 |Seiten=308–313}}</ref>, das nicht mit dem [[Simplex-Verfahren|Simplex-Verfahren der linearen Programmierung]] von G. Danzig verwechselt werden darf, arbeitet bei einem <math>n</math>-dimensionalen Optimierungsproblem mit <math>n+1</math> Punkten, die einen [[Simplex (Mathematik)|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 [[Metaheuristik#Klassifikation|populationsbasierten Metaheuristiken]]. Erwähnenswert ist noch die Restriktionen berücksichtigende Variante des Verfahrens von M. J. Box names Complex (COnstrained siMPLEX).<ref>{{Literatur |Autor=M. J. Box |Titel=A New Method of Constrained Optimization and a Comparison With Other Methods |Sammelwerk=The Computer Journal |Band=8 |Nummer=1 |Datum=1965-04-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/8.1.42 |Seiten=42–52}}</ref><ref name=":1" details="Complex Strategy of Box, S. 61–65" />
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 [[Robert Hooke|Hooke]] und Jeeves<ref>{{Literatur |Autor=Robert Hooke, T. A. Jeeves |Titel="Direct Search" Solution of Numerical and Statistical Problems |Sammelwerk=Journal of the ACM |Band=8 |Nummer=2 |Datum=1961-04 |ISSN=0004-5411 |DOI=10.1145/321062.321069 |Seiten=212–229}}</ref><ref name=":1" details="Hill climbing Strategies, S. 23–85" />
* Verfahren nach [[Michael J. D. Powell|Powell]]<ref>{{Literatur |Autor=M. J. D. Powell |Titel=An efficient method for finding the minimum of a function of several variables without calculating derivatives |Sammelwerk=The Computer Journal |Band=7 |Nummer=2 |Datum=1964-02-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/7.2.155 |Seiten=155–162}}</ref>
* Verfahren von Rosenbrock<ref>{{Literatur |Autor=H. H. Rosenbrock |Titel=An Automatic Method for Finding the Greatest or Least Value of a Function |Sammelwerk=The Computer Journal |Band=3 |Nummer=3 |Datum=1960-03-01 |ISSN=0010-4620 |DOI=10.1093/comjnl/3.3.175 |Seiten=175–184}}</ref><ref name=":1" details="Hill climbing Strategies, S. 23–85" />

== 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: ''[https://aima.cs.berkeley.edu/ 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]]: ''[https://www.researchgate.net/publication/220690578_Evolution_and_Optimum_Seeking 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]]

== Einzelnachweise ==
<references></references>

[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Suchalgorithmus]]

Lokale Suche - Versionsgeschichte

imported>Wilfried Jakob: Subreferenzen eingeführt