Hill-climbing

Dieser Text beschreibt Hill-climbing.

Hill Climbing ist ein einfaches, heuristisches Optimierungsverfahren. Von einer gegebenen Startlösung aus wird solange zu dem besten Punkt aus der Nachbarschaft der aktuellen Lösung gegangen bis keine Verbesserung deAbsichtfunktionswertes mehr möglich ist. Da das Verfahren sehr leicht in lokalen Optima steckenbleibt wird das Verfahren meist mit zufällig ausgewählten Startpunkten wiederholt.

Anschaulich gesprochen wird ein virtueller Bergsteiger auf eine bestimmte Stelle in die Wertelandschaft gesetzt. Von allen benachbarten Stellen dieser Stelle sucht er sich nun

1. diejenige aus, die am höchsten ist oder
2. eine aus denjenigen heraus, die höher sind als die aktuelle Stelle. (schwächer)

Wenn es zur neuen Stelle bergauf geht,

• dann geht der Bergsteiger diesen Weg und führt das Verfahren erneut aus,
• sonst hört er auf und beendet das Verfahren.

Die Ausgabe des Hill-climbing ist damit die Position des Bergsteigers in der Wertelandschaft. Es ist klar, dass diese Position eine Stelle eines lokalen Maximums entspricht. Da es bei vielen Problemen viele lokale Maxima gibt, ist damit ein globales Maximum , was häufig die Absicht der Lösung eines Optimierungsproblems ist, nicht notwendigerweise gefunden.

Hill-climbing kann als simpler evolutionärer Algorithmus aufgefasst werden, wobei es ca. ein Individuum , keine Rekombination und eine "seltsame" Mutations-Operation gibt.

Das Problem, dass Hill-climbing ca. ein lokales Maximum liefert, wird zu dem Beispiel so angegangen:

• mehrere Bergsteiger (eine ganze Population davon) an verschiedenen Startpunkten
• ein zufälliger großer Hüpfer (Mutation) der aktuellen Position in eine beliebige Richtung, danach erneutes Hill-climbing liefert mit gewisser wahrscheinlichkeit ein höheres lokales Maximum.