Lokale Suche: Unterschied zwischen den Versionen
[Markierung ausstehend] | [Markierung ausstehend] |
(→Lokale Suche) |
Goeke (Diskussion | Beiträge) |
||
Zeile 5: | Zeile 5: | ||
===Idee=== | ===Idee=== | ||
− | Die Idee der lokalen | + | 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== | ||
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 | + | 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=== | ||
Zeile 23: | Zeile 23: | ||
Die k-opt-Methode ist eine Nachbarschaftsrelation 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 | + | 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. |
Aktuelle Version vom 5. September 2012, 17:23 Uhr
Inhaltsverzeichnis
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
- 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:
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
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: