Bergsteigeralgorithmus

Hill-climbing ist ein einfaches Optimierungsverfahren. Dabei 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 das Ziel der Lösung eines Optimierungsproblems ist, nicht notwendigerweise gefunden.

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

Das Problem, dass Hill-climbing nur ein lokales Maximum liefert, wird zum Beispiel so angegangen:

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