Lokale Suche
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.
