k-Opt-Heuristik

Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (TSP). 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.

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 $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:

1. Wähle eine Rundtour f (durch Zufall oder eine Heuristik)
2. Solange es eine bessere Lösung g in der Nachbarschaft $N_{k},(f)$ gibt

   • Wähle g als neues f

3. 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

• Farthest Insertion
• Nearest Insertion
• Algorithmus von Christofides

Werte für k

Streiche die sich kreuzenden Kanten und ersetze sie durch die beiden grünen.

• k = 2
  • Der einfachste Fall. Zwei Kanten werden entfernt und kreuzweise wieder eingefügt.

Bei Vorliegen der Dreiecksungleichung, was eine praxisnahe Voraussetzung ist, kann man zeigen, dass das Ergebnis der 2-Opt-Heuristik eine überkreuzungsfreie Tour ist. Liegt nämlich eine Überkreuzung vor, so kann man, wie in nebenstehender Skizze angedeutet, die sich überkreuzenden Kanten entfernen und durch zwei andere sich nicht überkreuzende ersetzen. Wegen der Dreiecksungleichung erzielt man so eine echte Verbesserung.

• k = 3
  • Laut Lin (1965) der Fall, der die besten Ergebnisse im Verhältnis zum Zeitaufwand erzielt.

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.

Literatur

• Dieter Jungnickel: Graphs, Networks and Algorithms. Springer, Berlin u. a. 1999, ISBN 3-540-63760-5, (Algorithms and computation in mathematics 5), S. 444ff.
• S. Lin: Computer solutions for the travelling salesman problem. In: The Bell system technical journal 44, 1965, , S. 2245–2269.
• S. Lin, B. W. Kernighan: An effective heuristic algorithm for the travelling salesman problem. In: Operations research 31, 1973. S. 489–516.