30
Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Folie 38 Dr. Peter Merz Klassifikation von Heuristiken § Problembezogen: Problemspezifische Heuristiken Problemunabhängige Heuristiken § Nach Komplexität: Einfache Heuristiken Hybride Heuristiken § Nach Methodik: Konstruktionsheuristiken Verbesserungsheuristiken § Deterministisch vs. Zufallsgesteuert

Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

  • Upload
    others

  • View
    6

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 38 Dr. Peter Merz

Klassifikation von Heuristiken

§ Problembezogen:• Problemspezifische Heuristiken • Problemunabhängige Heuristiken

§ Nach Komplexität:• Einfache Heuristiken• Hybride Heuristiken

§ Nach Methodik:• Konstruktionsheuristiken• Verbesserungsheuristiken

§ Deterministisch vs. Zufallsgesteuert

Page 2: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 39 Dr. Peter Merz

Meta-Heuristiken

§ Was sind Meta-Heuristiken?• Kombinieren unterschiedliche Suchstrategien

- Intensifikation und Diversifikation- Lokale und globale Suche- Konstruktion und Verbesserung- Populations- und Individuensuche- Meta-Algorithmus steuert eingebetteten Algorithmus

• Problemunabhängigkeit- Kapselung der problemspezifischen Komponenten- Leichte Übertragung auf neue Probleme

Page 3: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 40 Dr. Peter Merz

Konstruktionsheuristiken

§ Vorgehen:• Eine Lösung wird schrittweise aufgebaut• In jedem Schritt wird eine Lösungskomponente gewählt• Wahl in Abhängigkeit von Regeln• Ziel der Regeln: Eine möglichst gute Lösung zu produzieren

à Maximierung der erwarteten Lösungsgüte

§ Häufig verwendete Strategie:• „Greedy“ (gierige) Auswahl der Lösungskomponenten, d.h.

momentane Gewinnmaximierung

Page 4: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 41 Dr. Peter Merz

GBP: Greedy-Heuristiken

§ Vorgehen:• Partitionierung der Knotenmenge durch schrittweises

Zuweisen der Knoten zu den zwei Mengen• Abwechselndes Hinzufügen von Knoten zu den 2 Mengen• Greedy-Strategien zur Wahl der Knoten:

- Minimierung der der neuen Kanten zwischen den Mengen (externe Kanten, Ei), bei mehreren Kandidaten: maximiere Kanten innerhalb der Mengen (interne Kanten, Ii)

- Minimierung der Differenz zwischen externen und internen Kanten

Page 5: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 42 Dr. Peter Merz

GBP: Differential Greedy (1)

§ Vorgehen (Wahl der Knoten):• Minimierung der Differenz

der neuen Kanten zwischen den Mengen (externe Kanten, Ei) und den Kanten innerhalb der Mengen (interne Kanten, Ii)

• Bei mehreren Kandidaten zufällige Auswahl

107

1

68

3

5

2

9

12

11

Rot:12, d(12)=E12-I12 =0–1= -1d(4)=-1, d(3)=0, d(6)=2

4

Page 6: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 43 Dr. Peter Merz

GBP: Differential Greedy (2)

107

1

68

3

5

2

9

12

11

Blau: 6, d(6)=E6-I6 =1-2=-1d(4)=1-0=1, d(3)=2-1=1

4§ Vorgehen

(Wahl der Knoten):• Minimierung der Differenz

der neuen Kanten zwischen den Mengen (externe Kanten, Ei) und den Kanten innerhalb der Mengen (interne Kanten, Ii)

• Bei mehreren Kandidaten zufällige Auswahl

Page 7: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 44 Dr. Peter Merz

TSP: Nächster-Nachbar Heuristik

§ Nearest Neighbor Heuristic:• Beginnend mit einem

Startknoten wird als nächstes der verfügbare Knoten mit der kürzesten Entfernung gesucht und Kante eingefügt

• Gierig, da aktuell bestmögliche Wahl getroffen wird

• Ein Endpunkt der Kante ist fix

107

1

6

4

8

3

5

2

9

Page 8: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 45 Dr. Peter Merz

TSP: Greedy Heuristik

§ Greedy Heuristic:• Beginnend mit der

kürzesten Kante werden schrittweise Kanten hinzugefügt, bis Tour komplett

• In jedem Schritt wird die kürzmöglichste Kante gewählt ohne die Constraints zu verletzen

• Gierig, da aktuell bestmögliche Wahl getroffen wird

2

107

1

6

4

8

3

5

9

Page 9: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 46 Dr. Peter Merz

TSP: Einfüge-Heuristiken (1)

§ Insertion Heuristics:• Beginnend mit einer Tour bestehend aus einer Stadt

werden Städte hinzugefügt bis alle Städte besucht sind• Verschiedene Strategien existieren:

- Nearest Insertion: Einfügen der Stadt mit geringster Distanz zu einer Stadt aus der Tour

- Farthest Insertion: Einfügen der Stadt, bei der die geringste Distanz zu einer Stadt aus der Tour maximal ist

- Cheapest Insertion: Einfügen der Stadt, die die geringste Zunahme der Tourlänge bewirkt

• Einfügeposition:- Wahl durch Minimierung der Tourlängenzunahme (insertion)- Nach der nächstgelegenen Stadt in der Tour (addition)

Page 10: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 47 Dr. Peter Merz

TSP: Einfüge-Heuristiken (2)

§ Insertion-Heuristik:• Beispiel der Nearest Insertion Strategie:

107

1

6

4

8

3

5

9

107

1

6

4

8

3

5

9

22

Einfügereihenfolge: 1, 10, 6, 3, 7, 8, 4, 9, 2, 5

Page 11: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 48 Dr. Peter Merz

TSP: Vergleich Konstruktionsheuristiken (1)

§ Wie wird verglichen:• Laufzeit: Durch Zeitkomplexität• Speicherbedarf: Speicherkomplexität• Vergleich anhand von TSP-Instanzen aus der TSPLIB• Lösungsgüte: Abweichung vom Optimum in Prozent

(Percentage Excess)

( )( ) 1 100%

( )heu

opt

L xq x

L x

= − ⋅

• q(x)=100%: Doppelte Tourlänge• q(x)=0.0%: Optimale Tourlänge

Page 12: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 49 Dr. Peter Merz

TSP: Vergleich Konstruktionsheuristiken (2)

§ Ergebnisse:• Aus Reinelt’94, gemittelt über 24 Instanzen (n=198 – 5934)

1. Nearest Neighbor: O(n2) O(n) 26.27%2. Greedy: O(n2 log n) O(n2) 11.96%3. Nearest Insertion: O(n2) O(n) 20.98%4. Farthest Insertion: O(n2) O(n) 13.99%5. Cheapest Insertion: O(n2 log n) O(n2) 17.23%

• Es existieren schelle Varianten, wie

1. Bentley‘s Greedy: O(n log n) O(n) ca. 16%2. Bentley‘s NN: O(n log n) O(n) ca. 26%

Page 13: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 50 Dr. Peter Merz

Verbesserungsheuristiken

§ Vorgehen:• Eine bestehende Lösung wird schrittweise verbessert, bis

keine Verbesserung mehr erreicht werden kann• IdR. wird geprüft, ob geringfügige Veränderungen bessere

Lösungen im Sinne der Zielfunktion liefernàLokale Suche (local search)

§ Lokale Suche:• Eigenschaft: Es werden lokal optimale Lösungen erzeugt• Globale Optima sind auch lokale Optima, aber nicht

umgekehrt• Voraussetzung: eine gültige Lösung

Page 14: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 51 Dr. Peter Merz

Lokale Suche

§ Algorithmus (Maximierung):1. Verändere Lösung x → x‘2. Wenn f(x‘) > f(x) x = x‘;3. Wenn für alle x‘ gilt: f(x‘) < f(x), dann stop 4. sonst weiter mit Schritt 1

§ Lösungsveränderung:• Veränderung mit geringfügiger Zielfunktionsveränderung• Veränderung einzelner Komponenten des Lösungsvektors• Beachtung der Nebenbedingungen

Page 15: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 52 Dr. Peter Merz

GBP: Lokale Suche

§ Lösungsveränderung durch• Tausch eines Knotens aus Menge 1 mit einem Knoten aus

Menge 2• Tausch von mehreren Knoten aus Menge 1 mit gleichviel

Knoten aus Menge 2à Mengen bleiben gleich groß

§ Berechnung des Gewinns:• Nach Tausch von i und j werden von i und j externe Kanten

zu internen Kanten und umgekehrt• Summe aus Differenz von externen und internen Kanten:

∆c = Ei – Ii + Ej - Ij – 2 aij

- aij ist die Adjazenzmatrix des Graphen

Page 16: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 53 Dr. Peter Merz

GBP: 2-opt Lokale Suche

§ 2-opt: (Pairwise Exchange)• Tausch eines Knotens aus Menge 1 mit einem Knoten aus Menge 2

107

1

6

4

8

3

5

2

9

12

11

Cut, c(vb,vr) = 3

107

1

6

4

8

3

5

2

9

12

11

Cut, c(vb,vr) = 6

∆c = E3 – I3 + E6 – I6 – 2 aij=2 – 1 + 3 – 1 + 0 = 3

Page 17: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 54 Dr. Peter Merz

GBP: Kernighan-Lin Lokale Suche

§ 2-opt: Austausch von 2 Knoten• O(n2) Möglichkeiten für Tausch (n=|V|)

§ k-opt: Austausch von k Knoten• O(nk) Möglichkeiten für Tausch• Laufzeitreduktion auf O(n2) durch Idee von Kernighan und Lin:

nur eine Teilmenge aller Möglichkeiten wird betrachtet in Abhängigkeit eines Gewinnkriteriums

• Durch geeignete Datenstrukturen kann Laufzeit auf O(|E|) pro Iteration reduziert werden

• Idee wird Kernighan-Lin Heuristik (1970) genannt• Ähnlich zur Lin-Kernighan Heuristik (1973) fürs TSP

Page 18: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 55 Dr. Peter Merz

TSP: Lokale Suche

§ Lösungsveränderung durch• Städtetausch (Knotentausch)• Entfernen und Einfügen eines Knoten an anderer Position• Entfernen und Einfügen einer Kante an anderer Position• Kantentausch (2 Kanten, 3 Kanten, k Kanten)

§ Berechnung des Gewinns • Gewinn (Tourlängenverkürzung) =

alte Tourlänge – neue Tourlänge =Summe der Kanten, die entfernt werden minus Summe der Kanten die hinzugefügt werden

Page 19: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 56 Dr. Peter Merz

TSP: Knotentausch (node exchange)

§ Bsp.: Knoten 6 und 3 werden vertauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,3) + d(3,4) + d(5,6) + d(6,7) – ( d(1,6) + d(6,4) + d(5,3) + d(3,7) )

Page 20: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 57 Dr. Peter Merz

TSP: Knotenwiedereinfügen (node insertion)

§ Bsp.: Knoten 3 wird zwischen 5 und 7 eingefügt

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(6,3) + d(3,4) + d(5,7) – ( d(6,4) + d(5,3) + d(3,7) )

Page 21: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 58 Dr. Peter Merz

TSP: Zwei-Kantentausch (2-opt)

§ Bsp.: Kanten (1,3) + (6,7) werden mit (1,6) + (3,7) getauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,3) + d(6,7) – ( d(1,6) + d(3,7) )

Page 22: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 59 Dr. Peter Merz

TSP: Drei-Kantentausch (3-opt)

§ Bsp.: Kanten (1,8) + (3,4) + (5,6) werden mit (1,6) + (4,8) + (3,5) getauscht

107

1

6

4

8

3

5

2

9

107

1

6

4

8

3

5

2

9

Gewinn:

g = d(1,8) + d(3,4) + d(5,6) – ( d(1,6) + d(4,8) + d(3,5) )

Page 23: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 60 Dr. Peter Merz

TSP: Lokale Suche im Vergleich

§ Ergebnisse:• Aus Reinelt’94, gemittelt über 24 Instanzen (n=198 – 5934)

Heuristik Zeit/Iteration Kanten q(x)

RT + Node exchange O(n2) 4 >100%RT + Node insertion (ni) O(n2) 3 97.18%NN + Node insertion (ni) O(n2) 3 16.59%RT + 2-opt O(n2) 2 14.67%NN + 2-opt O(n2) 2 8.42%RT + 2-opt/ni O(n2) 3 9.62%NN + 2-opt/ni O(n2) 3 5.80%RT + 3-opt O(n3) 3 8.01%NN + 3-opt O(n3) 3 5.00%

RT: Zufällige Startlösungen, NN: Nearest-Neighbor Lösungen

Heuristik Zeit/Iteration Kanten q(x)

RT + Node exchange O(n2) 4 >100%RT + Node insertion (ni) O(n2) 3 97.18%NN + Node insertion (ni) O(n2) 3 16.59%RT + 2-opt O(n2) 2 14.67%NN + 2-opt O(n2) 2 8.42%RT + 2-opt/ni O(n2) 3 9.62%NN + 2-opt/ni O(n2) 3 5.80%RT + 3-opt O(n3) 3 8.01%NN + 3-opt O(n3) 3 5.00%

RT: Zufällige Startlösungen, NN: Nearest-Neighbor Lösungen

Page 24: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 61 Dr. Peter Merz

TSP: Schnelle lokale Suche (1)

§ Ziel: Laufzeitreduktion auf O(n) pro Iteration

• 2-opt: d(t2,t1) + d(t4,t3) > d(t2,t3) + d(t4,t1)à d(t2,t3) < d(t2,t1) oder d(t4,t1) < d(t2,t1)

à Übertragung auf 3-opt möglich

à Kandidaten für t3 (t5) in aufsteigender Reihenfolge betrachten bis d(t2,t3) > d(t2,t1) oder bis k nächsten Nachbarn von t2 (t4)

Page 25: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 62 Dr. Peter Merz

TSP: Schnelle lokale Suche (2)

§ Zu Berechnen: Für jede Stadt k nächste Nachbarn• A priori durch Heapsort : O(n2 log k) • A priori durch 2-dim. Suchbäume: O(n log n + nk)

§ Weitere Laufzeitreduktion - don‘t look bits:• Wenn für ein t1 kein tourverkürzender Kantentausch gefunden

werden konnte, wird don‘t look bit für t1 gesetzt• Ein don‘t look bit für t1 wird gelöscht, wenn t1 Endpunkt einer

entfernten Kante ist• Alle Kandidaten für t1, deren don‘t look bit gesetzt ist, werden

nicht betrachtet• Anfangs sind alle don‘t look bits gelöscht

Page 26: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 63 Dr. Peter Merz

TSP: Konstruktionsheuristik + Lokale Suche

§ Ergebnisse:• Aus Merz’96, gemittelt über 18 Instanzen (n=51 – 3038)

Heuristik Ohne LS 2-optNearest Neighbor 20.75% 5.35%Nearest Insertion 21.70% 9.67%Farthest Insertion 10.38% 7.48%Cheapest Insertion 17.36% 7.79%

Heuristik Ohne LS 2-optNearest Neighbor 20.75% 5.35%Nearest Insertion 21.70% 9.67%Farthest Insertion 10.38% 7.48%Cheapest Insertion 17.36% 7.79%

• Aus Johnson’96, (n=1000)

Heuristik Ohne LS 2-opt 3-optRandom 2150% 7.9% 3.8%Nearest Neighbor 25.9% 6.6% 3.6%Greedy 17.6% 4.9% 3.1%

Heuristik Ohne LS 2-opt 3-optRandom 2150% 7.9% 3.8%Nearest Neighbor 25.9% 6.6% 3.6%Greedy 17.6% 4.9% 3.1%

Page 27: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 64 Dr. Peter Merz

TSP: Die Lin-Kernighan-Heuristik (1)

§ Idee von Lin-Kernighan (LK):• Statt 2 oder 3 Kanten wie in 2-opt/3-opt in jeder Iteration k

Kanten tauschen!• Lauftzeit sehr hoch: O(nk) Möglichkeiten

• Ab k=4 nicht mehr praktikabel und Tourlängenreduktion gering

• Betrachtung einer kleinen Teilmenge aller O(nk) Kombinationen à sequentieller Kantentausch

• Tiefensuche, k ist variabel• Tiefensuche besteht aus k Tauschoperationen, die zur

Verkürzung der Tour führen, einzelne Tauschop. Können Tour verlängern

Page 28: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 65 Dr. Peter Merz

TSP: Die Lin-Kernighan-Heuristik (2)

§ Algorithmus:

2 1 2 2 2 1

1

*1 2 1

Schrittweiser Tausch von gegen

Gewinn in Schritt : ( , ) ( , ) | | | |

Bedingung für Tiefensuche: 0

Effektiver Tausch nach Schritten: Kanten mit

( ,

i i

i i i i i i i

i

i kk

k k k

x y

i g d u u d u u x y

G g

n k

G G d u u

− +

=

− −

= − = −

= >

= +

2 2 1) ( , ) 0 maximal (2 )k kd u u k n− > ≤ ≤

Page 29: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 66 Dr. Peter Merz

TSP: Die Lin-Kernighan-Heuristik (3)

§ Backtracking: • Betrachtung von Alternativen zu y1, x2, y2

• Dadurch: Alle 2-opt und 3-opt Züge enthalten

§ Reduktion des Suchraums:• Nur

sequentieller Kantentausch, d.h. xi und yiteilen sich einen Endpunkt Nicht-Sequentieller Kantentausch

Page 30: Klassifikation von Heuristiken - uni-tuebingen.de · Folie 50 Dr. Peter Merz Moderne heuristische Optimierungsverfahren: Meta-Heuristiken Verbesserungsheuristiken §Vorgehen: •

Moderne heuristische Optimierungsverfahren: Meta-HeuristikenFolie 67 Dr. Peter Merz

TSP: Vergleich 3-opt und LK-Heuristik

§ Ergebnisse nach Johnson’96:• Startlösungen: Randomized Greedy• Zusätzliche Datentypen: (notwendig für große n)

- Cache für Distanzberechungen, keine Distanzmatrix- Two-Level Tree für Touren

Heuristik n=1000 10000 100000

3-opt <3.1% <3.0% <3.0%0.41s 4.7s 69s

Lin-Kernighan <2.0% <2.0% <2.0%0.77s 9.8s 151s

Heuristik n=1000 10000 100000

3-opt <3.1% <3.0% <3.0%0.41s 4.7s 69s

Lin-Kernighan <2.0% <2.0% <2.0%0.77s 9.8s 151s

• CPU-Zeiten: 150 MHz SGI Challenge