Lokale Suche

Eine lokale Suche wird von numerischen Verfahren, Heuristiken oder Metaheuristiken durchgeführt, die eine gewisse Umgebung eines Startpunktes nach einem Optimum durchsuchen. Die Definition der Umgebung und die Art der Suche kennzeichnen dabei ein lokales Suchverfahren. Meist wird von einem Startpunkt oder einer Startlösung ausgegangen. Lokale Suchverfahren finden in der Regel ein lokales Optimum und können keinesfalls garantieren, das globale zu finden. Sie werden in vielen Variationen dafür genutzt, komplizierte Optimierungsprobleme näherungsweise zu lösen (z. B. das Problem des Handlungsreisenden). Das Grundprinzip besteht darin, ausgehend von einer gegebenen Startlösung eine bessere Lösung zu finden, indem durch eine lokale Änderung der aktuellen Lösung eine bessere aus der gerade betrachteten Nachbarschaft gefunden wird. Der Vorgang wird wiederholt, bis die gesamte Nachbarschaft abgesucht ist oder innerhalb einer vorgegebenen Anzahl von hintereinander ausgeführten Iterationen keine oder nur noch geringe Verbesserungen erreicht werden oder ein vorgegebenes Laufzeitende oder eine Iterationsobergrenze erreicht ist.