Lokale Suche: Unterschied zwischen den Versionen
Vorlagen/Dateien wurden aktualisiert (nicht markierte Seiten sind in fett gekennzeichnet): Datei:BSP LS Problem.jpg, Datei:BSP LS 1.jpg, Datei:BSP LS 3.jpg, Datei:BSP LS 4.jpg, Datei:BSP LS 5.jpg, Datei:BSP LS 6.jpg, Datei:BSP LS 7.jpg
[gesichtete Version] | [Markierung ausstehend] |
(→Nachbarschaftsrelation) |
|||
Zeile 26: | Zeile 26: | ||
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. | ||
+ | |||
+ | |||
+ | ==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:Picture 3|C:\Users\Thomas\Desktop\Bior\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]] |
Version vom 3. September 2012, 10:18 Uhr
Inhaltsverzeichnis
Lokale Suche
Allgemein
Idee
Die Idee der lokalen Such ist es 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 das 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 Nachbarschaftrelation 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.
Der wohl am meisten verbreitet Operator ist hierbei wohl der 2-Change (bzw. 2-opt oder Inversion) Operator.
Beispiel
Problem:
Generierung der Ausgangslösung:
Kosten: 4+3+2+5+5+3=22
Austausch der Kanten E-D und A-F mit A-E und F-D
C:\Users\Thomas\Desktop\Bior\BSP_LS_2.jpg
Neue Lösung:
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
Neue Lösung:
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
Neue Lösung:
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: