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.

Inhaltsverzeichnis

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?


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bergsteiger-Algorithmus — 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… …   Deutsch Wikipedia

  • Chemieinformatik — Chemoinformatik, Cheminformatik oder Chemieinformatik (engl. chemoinformatics, cheminformatics, chemical informatics oder chemiinformatics) bezeichnet einen Wissenschaftszweig, der das Gebiet der Chemie mit Methoden der Informatik verbindet mit… …   Deutsch Wikipedia

  • Cheminformatik — Chemoinformatik, Cheminformatik oder Chemieinformatik (engl. chemoinformatics, cheminformatics, chemical informatics oder chemiinformatics) bezeichnet einen Wissenschaftszweig, der das Gebiet der Chemie mit Methoden der Informatik verbindet mit… …   Deutsch Wikipedia

  • Computerchemie — Chemoinformatik, Cheminformatik oder Chemieinformatik (engl. chemoinformatics, cheminformatics, chemical informatics oder chemiinformatics) bezeichnet einen Wissenschaftszweig, der das Gebiet der Chemie mit Methoden der Informatik verbindet mit… …   Deutsch Wikipedia

  • Fujiyama-Landschaft — Eine Fujiyama Landschaft bezeichnet in der Mathematik eine Wertelandschaft mit genau einem lokalen Maximum. Das heißt unter anderem: Es gibt genau ein globales Maximum in dieser Landschaft. Der Bergsteigeralgorithmus (hill climbing) funktioniert… …   Deutsch Wikipedia

  • Globale Optimierung — Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines meist komplexen Systems zu finden. „Optimal“ bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen… …   Deutsch Wikipedia

  • Gradientenabstieg — Das Verfahren des steilsten Abstiegs, auch Gradientenverfahren genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblemes) von einem… …   Deutsch Wikipedia

  • Gradientenabstiegsverfahren — Das Verfahren des steilsten Abstiegs, auch Gradientenverfahren genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblemes) von einem… …   Deutsch Wikipedia

  • Hill-climbing — Dieser Artikel befasst sich mit einer Motorradsportart. Für die Autosportart siehe Bergrennen (engl. Hillclimbing) und für das Optimierungsverfahren siehe Bergsteigeralgorithmus. Hillclimbing Obersaxen 2003 Hillclimbing ist eine Motorradsportart …   Deutsch Wikipedia

  • Hill Climbing — Dieser Artikel befasst sich mit einer Motorradsportart. Für die Autosportart siehe Bergrennen (engl. Hillclimbing) und für das Optimierungsverfahren siehe Bergsteigeralgorithmus. Hillclimbing Obersaxen 2003 Hillclimbing ist eine Motorradsportart …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”