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:

  • 2-opt — En optimisation, 2 opt est un algorithme de recherche locale proposé par Croes en 1958[1] pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. Sommaire 1 L algorithme 1.1 Principe …   Wikipédia en Français

  • 2-opt — In optimization, 2 opt is a simple local search algorithm first proposed by Croes in 1958 for solving the traveling salesman problem. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. O O O O… …   Wikipedia

  • opt — /opt/, v.i. 1. to make a choice; choose (usually fol. by for). 2. opt out, to decide to leave or withdraw: to opt out of the urban rat race and move to the countryside. [1875 80; < F opter to choose, divide < L optare to wish for, desire, pray… …   Universalium

  • opt — /ɒpt / (say opt) phrase 1. opt for, to decide in favour of; choose. 2. opt out, a. (sometimes followed by of) to decide not to participate: *Tasmania has argued that states should be able to opt out of the national laws. –aap news, 2000. b. to… …   Australian English dictionary

  • opt — verb 1》 make a choice. 2》 (opt out) choose not to participate.     ↘Brit. (of a school or hospital) decide to withdraw from local authority control. Origin C19: from Fr. opter, from L. optare choose …   English new terms dictionary

  • 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 (Permission Marketing) — Opt out (engl. to opt (for something) ‚optieren‘, ‚sich für etwas entscheiden‘) bezeichnet im Permission Marketing die im Gegensatz zum Opt in Verfahren automatische Aufnahme in eine Verteilerliste für Newsletter, beispielsweise nach dem Kauf in… …   Deutsch Wikipedia

  • 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

Share the article and excerpts

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