Bergsteigeralgorithmus

Bergsteigeralgorithmus (englisch hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Von einer gegebenen Startlösung aus wird solange zum besten Punkt - aus der Nachbarschaft der aktuellen Lösung - gegangen, bis keine Verbesserung des Zielfunktionswertes 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 Bergsteigeralgorithmus ist damit die Position des Bergsteigers in der Wertelandschaft. Es ist klar, dass diese Position einer 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.

Der Bergsteigeralgorithmus kann als simpler evolutionärer Algorithmus aufgefasst werden, wobei es nur ein Individuum, keine Rekombination und eine Mutations-Operation gibt.

Das Problem, dass der Bergsteigeralgorithmus nur ein lokales Maximum liefert, wird zum 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 ein erneutes Anwenden des Bergsteigeralgorithmus liefert mit gewisser Wahrscheinlichkeit ein höheres lokales Maximum.

Eine praktische Implementierung so eines Bergsteigeralgorithmus mit Schrittweitensteuerung ist im Artikel Downhill-Simplex-Verfahren beschrieben. Die erwähnten Maßnahmen zum Vermeiden lokaler Optima lassen sich dort genauso ergänzen.

Fragestellungen

Algo (Hill Climbing)
   bestEval = -INF;
   currentNode = startNode;
   bestNode = NULL;
   for MAX times
      if (EVAL(currentNode) > bestEval)
          bestEval = EVAL(currentNode);
          bestNode = currentNode;
      L = NEIGHBORS(currentNode);
      tempMaxEval = -INF;
      for all x in L
         if (EVAL(x) > tempMaxEval)
              currentNode = x;
              tempMaxEval = EVAL(x);
   return currentNode;

Schrittweite

Existiert eine Abstandsfunktion auf der Definitionsmenge der Wertelandschaft, so stellt sich oft die Frage, wie groß einer der Schritte (von einer Stelle zur nächsten) sein soll, zum Beispiel:

• immer gleich groß
• zufällig groß (wird angewendet zur Vermeidung des Festlaufens in lokalen Extrema)
• kleiner werdend (wenn der Algorithmus erkennt, dass das Optimum in der Nähe sein muss und sich auf dieses konzentrieren muss)
• größer werdend (wenn die Richtung erfolgversprechend erscheint)
• abhängig vom Individuum

Selektionsstrategie

Wann soll die Selektion auf einzelne Bergsteiger angewandt werden?

• nach jedem Schritt
• nach jedem Bergauf-Schritt
• wenn ein lokales Maximum erreicht wurde
• erst nach größeren Zeiträumen (um das Überwinden von "Durststrecken" zu ermöglichen)

Individuenanzahl

Wie viele Individuen sollen verwendet werden, um eine gute Lösung zu erreichen?

Abbruchkriterium

Wie viele Generationen soll es geben, bis die Suche nach besseren Lösungen aufgegeben wird?