Lokale Suche

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

Referenzen

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


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mensch: Auf der Suche nach den Ursprüngen des typisch Menschlichen —   Auf die Frage, was eigentlich im Verhalten uns Menschen von Tieren unterscheidet, hat es in der Geschichte der Philosophie und Anthropologie die vielfältigsten Antworten gegeben. Ursprünglich und lange Zeit glaubte man beispielsweise, dass… …   Universal-Lexikon

  • Auf der Suche nach der verlorenen Zeit — Der Roman Auf der Suche nach der verlorenen Zeit (frz. Original: À la recherche du temps perdu. geschrieben 1908/09 bis 1922 und erschienen zwischen 1913 und 1927) ist das Hauptwerk von Marcel Proust. gedruckter Vorabzug mit handschriftlichen… …   Deutsch Wikipedia

  • Simulated Annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… …   Deutsch Wikipedia

  • Simulated annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… …   Deutsch Wikipedia

  • Simuliertes Ausglühen — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… …   Deutsch Wikipedia

  • Meta-Heuristik — Eine Metaheuristik ist in der Mathematik ein Algorithmus zur näherungsweisen Lösung eines kombinatorischen Optimierungsproblems. Im Gegensatz zu problemspezifischen Heuristiken, die nur auf ein bestimmtes Optimierungsproblem angewendet werden… …   Deutsch Wikipedia

  • Telegate AG — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Diskrete Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Optimierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

  • Ganzzahlige Programmierung — Die Ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die Lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”