Verbesserungsverfahren

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Ein Verbesserungsverfahren ist eine zum Beispiel im Operations Research verwendete Methode, deren Ziel darin besteht, iterativ für eine gegebene Startlösung eines Optimierungsproblems eine bessere Lösung zu finden. Dieses kann mit einem Approximationsalgorithmus (wie z. B. einer k-Opt-Heuristik) zu einer Näherungslösung oder bei exakten Verfahren (wie z. B. der Stepping-Stone-Methode) stets zu einer Optimallösung führen.

Verbesserungsverfahren versuchen in jedem Schritt, in einer Umgebung der bisher besten Löung eine möglichst bessere zu finden, bis das Verfahren in einem lokalen oder im globalen Optimum endet oder ein anderes Abbruchkriterium erfüllt wird. Damit Verfahren nicht jedes Mal abbrechen, wenn sie ein lokales Optimum erreicht haben, müssen sie zwischenzeitlich auch schlechtere Lösungen akzeptieren können.

Mit Eröffnungsverfahren können bereits gute Startlösungen gefunden werden. Gute Startlösungen führen zu einer kürzeren Laufzeit des danach angewandten Verbesserungsverfahrens, im Falle von Approximationsalgorithmen auch zu besseren Näherungslösungen.