2-opt

2-opt

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

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

Algorithmen zur Bestimmung der Startlösung

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 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, 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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

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

  • Opt-in — (von engl. to opt (for something) ‚optieren‘, ‚sich für etwas entscheiden‘) ist ein Verfahren aus dem Permission Marketing, bei dem der Endverbraucher Werbekontaktaufnahmen vorher – meist durch E Mail, Telefon oder SMS – explizit bestätigen muss …   Deutsch Wikipedia

  • opt — OPT, (1) num. card., (2) opturi, s.n. 1. num. card. Numărul care în numărătoare are locul între şapte şi nouă. ♢ (Adjectival) Copilul are opt ani. ♢ (Substantivat) Mănâncă cât opt. (Cu valoare de num. ord.) Etajul opt. ♢ (Precedat de câte ,… …   Dicționar Român

  • opt-out — ˈopt out noun [singular] when a country or organization decides not to join a group or system: • Britain s opt out from the European agreement • The company secured an opt out clause in the proposed law. * * * opt out UK US noun [C] ► a situation …   Financial and business terms

  • Opt-in — Article connexe : Opt out. Opt In, terme marketing ou légal qualifiant une adresse courriel. Une adresse courriel Opt In active signifie que l utilisateur de cette adresse a eu préalablement un accord, de la part du propriétaire de l adresse …   Wikipédia en Français

  • Opt In — Article connexe : Opt out. Opt In, terme marketing ou légal qualifiant une adresse courriel. Une adresse courriel Opt In active signifie que l utilisateur de cette adresse a eu préalablement un accord, de la part du propriétaire de l adresse …   Wikipédia en Français

  • Opt Out — Article connexe : Opt in. Opt Out, terme marketing ou légal qualifiant une adresse électronique. On parle également de permission marketing. Ce terme est généralement utilisé en marketing direct pour qualifier l usage d un fichier courriel.… …   Wikipédia en Français

  • Opt out — Article connexe : Opt in. Opt Out, terme marketing ou légal qualifiant une adresse électronique. On parle également de permission marketing. Ce terme est généralement utilisé en marketing direct pour qualifier l usage d un fichier courriel.… …   Wikipédia en Français

  • opt in — To choose to take part • • • Main Entry: ↑opt * * * ˌopt ˈin ˌopt ˈinto [intransitive] [present tense I/y …   Useful english dictionary

  • opt — [ɔpt US a:pt] v [Date: 1800 1900; : French; Origin: opter, from [i]Latin optare to choose ] to choose one thing or do one thing instead of another opt for ▪ We finally opted for the wood finish. opt to do sth ▪ Many young people are opting to go… …   Dictionary of contemporary English

  • Opt-out — ou en français option de retrait (à[1]) est un terme marketing ou légal qualifiant une adresse électronique. On parle également de permission marketing. Ce terme est généralement utilisé en marketing direct pour qualifier l usage d un fichier… …   Wikipédia en Français

  • Opt — may refer to: /opt, a directory in the Filesystem Hierarchy Standard Opt out, in broadcasting, when a nation or region splits from the main national output Opt out, to avoid receiving unsolicited product or service information Opting out, a… …   Wikipedia

Share the article and excerpts

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