Lokale Suche: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[gesichtete Version][Markierung ausstehend]
(→‎Nachbarschaftsrelation)
 
(5 dazwischenliegende Versionen von einem anderen Benutzer werden nicht angezeigt)
Zeile 1: Zeile 1:
−
=Lokale Suche=
+
 
  
 
==Allgemein==
 
==Allgemein==
Zeile 5: Zeile 5:
 
===Idee===
 
===Idee===
  
−
Die Idee der lokalen Such ist es die lokalen Nachbarn einer gegebenen Lösung si im Suchraum S zu betrachten.
+
Die Idee der lokalen Suche ist, die lokalen Nachbarn einer gegebenen Lösung si im Suchraum S zu betrachten.
  
−
Wenn eine benachbarte Lösungen einen besseren Zielfunktionswert f(sj) als f(si) aufweist wird die aktuelle Lösung durch die bessere Lösung ersetzt und die Suche mit der neuen Lösung sj fortgesetzt.
+
Wenn eine benachbarte Lösungen einen besseren Zielfunktionswert f(sj) als f(si) aufweist, wird die aktuelle Lösung durch die bessere Lösung ersetzt und die Suche mit der neuen Lösung sj fortgesetzt.
  
−
===Nachbarschaftsrelation===
+
==Nachbarschaftsrelation==
  
 
Um eine gegebene Lösung in eine neue Lösung zu transformieren wird die Nachbarschaftsrelation N⊆SxS verwendet. Diese Nachbarschaftsrelation ist abhängig von dem gestellten Problem und wird am Anfang der lokalen Suche durch den Modellierer definiert.
 
Um eine gegebene Lösung in eine neue Lösung zu transformieren wird die Nachbarschaftsrelation N⊆SxS verwendet. Diese Nachbarschaftsrelation ist abhängig von dem gestellten Problem und wird am Anfang der lokalen Suche durch den Modellierer definiert.
Zeile 17: Zeile 17:
 
Bei zu großen Nachbarschaften müssen in jedem Schritt der Suche zu viele Nachbarn untersucht und bewertet werden, wodurch im Extremfall die lokale Suche zu einer zufälligen Suche wird.  
 
Bei zu großen Nachbarschaften müssen in jedem Schritt der Suche zu viele Nachbarn untersucht und bewertet werden, wodurch im Extremfall die lokale Suche zu einer zufälligen Suche wird.  
  
−
Bei zu kleinen Nachbarschaften ist jedoch die Wahrscheinlichkeit größer das die Suche in einem lokalen Optimum festsitzt aus der die lokale Suchmethode nicht mehr entkommen kann.
+
Bei zu kleinen Nachbarschaften ist jedoch die Wahrscheinlichkeit größer, dass die Suche in einem lokalen Optimum festsitzt aus der die lokale Suchmethode nicht mehr entkommen kann.
  
−
==k-opt-Methode==
+
===k-opt-Methode===
  
−
Die k-opt-Methode ist eine Nachbarschaftrelation welche auf Kantenaustausch-Operatoren beruht und wohl die bekannteste Klasse von Optimierungsmethoden für ein TSP darstellt.
+
Die k-opt-Methode ist eine Nachbarschaftsrelation welche auf Kantenaustausch-Operatoren beruht und wohl die bekannteste Klasse von Optimierungsmethoden für ein TSP darstellt.
  
−
Bei einer k-Opt-Methode wird dich Nachbarschaft dadurch erzeugt, dass k Kanten mit k anderen Kanten ausgetauscht werden und anschließend die Tour auf Verbesserung überprüft wird.
+
Bei einer k-Opt-Methode wird die Nachbarschaft dadurch erzeugt, dass k Kanten mit k anderen Kanten ausgetauscht werden und anschließend die Tour auf Verbesserung überprüft wird.
  
 
Der wohl am meisten verbreitet Operator ist hierbei wohl der 2-Change (bzw. 2-opt oder Inversion) Operator.
 
Der wohl am meisten verbreitet Operator ist hierbei wohl der 2-Change (bzw. 2-opt oder Inversion) Operator.
 +
 +
==Ablauf==
 +
 +
# Generierung einer zufälligen Ausgangslösung Si
 +
# Erzeugen einer neuen Lösung Sj mit Hilfe der Nachbarschaftsrelation
 +
# Wenn die neue Lösung Sj besser ist (z.B. geringere Kosten hat) dann ersetzte die Lösung Si (Si = Sj) und gehe zu 2.
 +
# Wenn Sj schlechter oder gleich gut ist, dann stoppt der Algorithmus und gibt als Lösung Sj zurück
 +
 +
==Beispiel==
 +
 +
Problem:
 +
 +
[[image:BSP_LS_Problem.jpg]]
 +
 +
Generierung der Ausgangslösung:
 +
 +
[[image:BSP_LS_1.jpg]]
 +
 +
Kosten: 4+3+2+5+5+3=22
 +
 +
Austausch der Kanten E-D und A-F mit A-E und F-D
 +
 +
[[image:BSP_LS_2.jpg]]
 +
 +
Neue Lösung:
 +
 +
[[image:BSP_LS_3.jpg]]
 +
 +
Kosten: 4+3+2+1+5+1=16
 +
 +
16<22, daraus folgt neue Lösung wird übernommen und als neue Startlösung verwendet
 +
 +
Austausch der Kanten F-E und A-B mit F-A und B-E
 +
 +
[[image:BSP_LS_4.jpg]]
 +
 +
Neue Lösung:
 +
 +
[[image:BSP_LS_5.jpg]]
 +
 +
Kosten: 1+2+3+2+1+3=12
 +
 +
12<16, daraus folgt neue Lösung wird übernommen und als neue Startlösung verwendet
 +
 +
Austausch der Kanten E-B und D-C mit D-B und C-E
 +
 +
[[image:BSP_LS_6.jpg]]
 +
 +
Neue Lösung:
 +
 +
[[image:BSP_LS_7.jpg]]
 +
 +
Kosten: 1+4+3+4+1+3=16
 +
 +
16>12, daraus folgt neue Lösung wird nicht übernommen und Algortihmus stoppt.
 +
 +
Optimallösung ist somit:
 +
 +
[[image:BSP_LS_5.jpg]]

Aktuelle Version vom 5. September 2012, 17:23 Uhr


Allgemein

Idee

Die Idee der lokalen Suche ist, die lokalen Nachbarn einer gegebenen Lösung si im Suchraum S zu betrachten.

Wenn eine benachbarte Lösungen einen besseren Zielfunktionswert f(sj) als f(si) aufweist, wird die aktuelle Lösung durch die bessere Lösung ersetzt und die Suche mit der neuen Lösung sj fortgesetzt.

Nachbarschaftsrelation

Um eine gegebene Lösung in eine neue Lösung zu transformieren wird die Nachbarschaftsrelation N⊆SxS verwendet. Diese Nachbarschaftsrelation ist abhängig von dem gestellten Problem und wird am Anfang der lokalen Suche durch den Modellierer definiert.

Bei der Wahl der Nachbarschaftsrelation sollte beachtet werden, das die generierte Nachbarschaft weder zu groß noch zu klein ist.

Bei zu großen Nachbarschaften müssen in jedem Schritt der Suche zu viele Nachbarn untersucht und bewertet werden, wodurch im Extremfall die lokale Suche zu einer zufälligen Suche wird.

Bei zu kleinen Nachbarschaften ist jedoch die Wahrscheinlichkeit größer, dass die Suche in einem lokalen Optimum festsitzt aus der die lokale Suchmethode nicht mehr entkommen kann.

k-opt-Methode

Die k-opt-Methode ist eine Nachbarschaftsrelation welche auf Kantenaustausch-Operatoren beruht und wohl die bekannteste Klasse von Optimierungsmethoden für ein TSP darstellt.

Bei einer k-Opt-Methode wird die Nachbarschaft dadurch erzeugt, dass k Kanten mit k anderen Kanten ausgetauscht werden und anschließend die Tour auf Verbesserung überprüft wird.

Der wohl am meisten verbreitet Operator ist hierbei wohl der 2-Change (bzw. 2-opt oder Inversion) Operator.

Ablauf

  1. Generierung einer zufälligen Ausgangslösung Si
  2. Erzeugen einer neuen Lösung Sj mit Hilfe der Nachbarschaftsrelation
  3. Wenn die neue Lösung Sj besser ist (z.B. geringere Kosten hat) dann ersetzte die Lösung Si (Si = Sj) und gehe zu 2.
  4. Wenn Sj schlechter oder gleich gut ist, dann stoppt der Algorithmus und gibt als Lösung Sj zurück

Beispiel

Problem:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Generierung der Ausgangslösung:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Kosten: 4+3+2+5+5+3=22

Austausch der Kanten E-D und A-F mit A-E und F-D

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Neue Lösung:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Kosten: 4+3+2+1+5+1=16

16<22, daraus folgt neue Lösung wird übernommen und als neue Startlösung verwendet

Austausch der Kanten F-E und A-B mit F-A und B-E

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Neue Lösung:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Kosten: 1+2+3+2+1+3=12

12<16, daraus folgt neue Lösung wird übernommen und als neue Startlösung verwendet

Austausch der Kanten E-B und D-C mit D-B und C-E

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Neue Lösung:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Kosten: 1+4+3+4+1+3=16

16>12, daraus folgt neue Lösung wird nicht übernommen und Algortihmus stoppt.

Optimallösung ist somit:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Lokale_Suche&oldid=2916“