K-Opt-Heuristik

Klasse von Algorithmen zum nährungsweisen 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.

Inhaltsverzeichnis

1 Verfahren 2 Struktur 3 Algorithmen 3.1 Strategien 3.2 Algorithmen zur Bestimmung der Startlösung 3.3 Werte für k 3.4 Algorithmen 4 Literatur

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.

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 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 , die besser ist als f
• steepest descent (engl: steilster Abstieg)
  • wählt die Lösung g aus , die die größte Verbesserung bietet

Algorithmen zur Bestimmung der Startlösung

• Farthest Insertion
• Nearest Insertion
• Algorithmus von Christofides

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 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, B.W. Kernighan: An effective heuristic algorithm for the travelling salesman problem. In: Oper. Res. 31/1973. S. 489-516

See also: K-Opt-Heuristik, Brian W. Kernighan, FARIN, Heuristik, NEARIN, Problem des Handlungsreisenden, Zeitkomplexität, S. Lin, Lin-Kernighan-Algorithmus