W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


K-Opt-Heuristik

*** Shopping-Tipp: K-Opt-Heuristik

{{Korrekter Titel|k-Opt-Heuristik}} '''K-Opt-Heuristiken''' sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problem des Handlungsreisenden Problems des Handlungsreisenden (PdH). Die k-Opt-Heuristiken gehören zu den Post-Optimization Post-Optimization-Algorithmen ''(engl.: Nach-Optimierung)'', die sich dadurch auszeichnen, dass sie eine bereits gefundene Lösung weiter verbessern. Die Grundidee besteht darin, k Kanten aus einer gegebenen Tour zu entfernen und gegen k andere Kanten auszutauschen, so dass sich wieder eine Tour ergibt. Ist die neue Tour kürzer als die alte, wird sie als neue Lösung verwendet.

Verfahren
Die Nachoptimierung beim PdH besteht darin, eine durch Zufall oder Heuristik Heuristiken gefundene Rundtour so abzuwandeln, dass die Summe der Kantenbewertungen entlang der Tour reduziert wird. Das k-Opt-Verfahren zeichnet sich dadurch aus, dass es eine bestimmte Menge von Kanten aus der aktuellen Lösung entfernt, um danach neue Kanten einzufügen, die die entstandenen Lücken schließen. Die k-Opt-Heuristiken verwenden das Verfahren der lokale Suche lokalen Suche in Nachbarschaften. Die ''Nachbarschaft'' N\,(f) zu einer gegebenen Lösung '''f''' ist definiert als die Menge aller Lösungen, die man durch gewisse festgelegte Veränderungen an '''f''' erhält. Im Falle der k-Opt-Heuristik wird eine ''k-Tausch-Nachbarschaft'' N_k\,(f) definiert als Menge aller gültigen Lösungen, die entstehen, wenn man '''k''' Kanten aus '''f''' entfernt und danach '''k''' neue Kanten einfügt. Um die Gültigkeit der Lösung zu gewährleisten müssen die neuen Kanten die Rundtour schließen.

Struktur
Folgendes Schema charakterisiert die Klasse der k-Opt-Heuristiken: #Wähle eine Rundtour '''f''' (durch Zufall oder eine Heuristik) #Solange es eine bessere Lösung '''g''' in der Nachbarschaft N_k\,(f) gibt #:*Wähle '''g''' als neues '''f''' #Return '''f'''

Algorithmen
Die verschiedenen Algorithmen der Klasse k-Opt werden durch mehrere Eigenschaften charakterisiert. Zum einen ist die Wahl der Strategie von Bedeutung, nach der ein neues '''g''' bestimmt wird. Ein weiterer Faktor ist die Entscheidung über ein Verfahren zum Bestimmen der Startlösung '''f'''. Zuletzt hat die Wahl des Parameters k einen großen Einfluss auf die Zeitkomplexität des Algorithmus. Im Folgenden seien einige Eigenschaften genannt, die sich im Zusammenhang mit k-Opt-Heuristiken etabliert haben:

Strategien
*'''first improvement''' ''(engl: erste Verbesserung)'' **wählt die erstbeste Lösung '''g''' aus N_k\,(f), die besser ist als '''f''' *'''steepest descent''' ''(engl: steilster Abstieg)'' **wählt die Lösung '''g''' aus N_k\,(f), die die größte Verbesserung bietet

Algorithmen zur Bestimmung der Startlösung
*FARIN Farthest Insertion *NEARIN Nearest Insertion *Christofides-Heuristik Algorithmus von Christophides

Werte für k
*'''k = 2''' **Der einfachste Fall. Zwei Kanten werden entfernt und kreuzweise wieder eingefügt *'''k = 3''' **Laut Lin (1965) der Fall, der die besten Ergebnisse erzielt.

Algorithmen
Der wohl bekannteste k-Opt Algorithmus ist der von S. Lin und Brian W. Kernighan B. W. Kernighan (1973). Er arbeitet in der Praxis sehr effizient, kann aber in Einzelfällen exponentielle Zeitkomplexität aufweisen. Das besondere am Lin-Kernighan-Algorithmus ist, dass er mit einem variablen k-Wert arbeitet, der in jeder Iteration neu bestimmt wird.

Literatur
* Dieter Jungnickel: ''Graphs, Networks and Algorithms.'' Springer, 1999, 3-540-63760-5, S. 444ff * S. Lin: ''Computer solutions for the travelling salesman problem.'' In: ''Bell Systems Tech. J.'' 44/1965. S. 2245-2269 * S. Lin, Brian W. Kernighan B.W. Kernighan: ''An effective heuristic algorithm for the travelling salesman problem.'' In: ''Oper. Res.'' 31/1973. S. 489-516 Kategorie:Graphentheorie

*** Shopping-Tipp: K-Opt-Heuristik




[Der Artikel zu K-Opt-Heuristik stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels K-Opt-Heuristik zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite