K-Opt-Heuristik
aus Wikipedia, der freien Enzyklopädie
K-Opt-Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (PdH). Die k-Opt-Heuristiken gehören zu den 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.
Inhaltsverzeichnis |
[Bearbeiten] Verfahren
Die Nachoptimierung beim PdH besteht darin, eine durch Zufall oder 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 lokalen Suche in Nachbarschaften. Die Nachbarschaft 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 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.
[Bearbeiten] 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 gibt
-
- Wähle g als neues f
-
- Return f
[Bearbeiten] 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:
[Bearbeiten] Strategien
- first improvement (engl: erste Verbesserung)
- wählt die erstbeste Lösung g aus , die besser ist als f
- steepest descent (engl: steilster Abstieg)
- wählt die Lösung g aus , die die größte Verbesserung bietet
[Bearbeiten] Algorithmen zur Bestimmung der Startlösung
[Bearbeiten] 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.
[Bearbeiten] Algorithmen
Der wohl bekannteste k-Opt Algorithmus ist der von S. Lin und 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.
[Bearbeiten] 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, B.W. Kernighan: An effective heuristic algorithm for the travelling salesman problem. In: Oper. Res. 31/1973. S. 489-516