Bergsteigeralgorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
An einem lokalen Maximum bricht der Algorithmus ab, ohne das globale Maximum gefunden zu haben.

Bergsteigeralgorithmus (engl. hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Wie die Analogie des Bergsteigers nahelegt, wird eine potenzielle Lösung für ein gegebenes Problem Schritt für Schritt verbessert. Dabei wird jeweils eine lokale Veränderung durchgeführt und nur übernommen, wenn der entstandene Lösungskandidat besser geeignet ist. Das Verfahren endet, wenn vom aktuellen Punkt aus keine Verbesserung mehr möglich ist – analog ist der Bergsteiger auf einem Hügel angekommen. Der gefundene Punkt ist im besten Fall das globale Maximum (Bergspitze) oder nur ein lokales. Der Bergsteigeralgorithmus kann als simpler evolutionärer Algorithmus aufgefasst werden, wobei es nur ein Individuum, keine Rekombination und eine Mutations-Operation gibt. Für das Problem der lokalen Maxima gibt es folgende Ansätze:

  • Eine ganze Population von Bergsteigern beginnt an verschiedenen Startpunkten, sodass verschiedene Maxima erklommen werden.
  • Ein lokales Maximum wird durch eine einmalige starke Mutation verlassen, durch abermaliges Bergsteigen kann dann ein anderes Maximum gefunden werden.

Eine ausführliche Implementierung eines Bergsteigeralgorithmus ist im Artikel Downhill-Simplex-Verfahren beschrieben.

Python-Beispiel[Bearbeiten]

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;

Fragestellungen[Bearbeiten]

Schrittweite[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

Abbruchkriterium[Bearbeiten]

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