Bergsteiger-Algorithmus

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 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 "seltsame" 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

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

Abbruchkriterium

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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

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

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

  • Evolutionären Optimierung — Eine Wertelandschaft ist der etwas blumige Ausdruck für eine mathematische Funktion , wobei D eine (frei wählbare) Menge ist. Meist wird eine Funktion Wertelandschaft im Zusammenhang mit Optimierungsproblemen gebraucht, wo ein (globales) Optimum… …   Deutsch Wikipedia

  • Fitnesslandschaft — Eine Wertelandschaft ist der etwas blumige Ausdruck für eine mathematische Funktion , wobei D eine (frei wählbare) Menge ist. Meist wird eine Funktion Wertelandschaft im Zusammenhang mit Optimierungsproblemen gebraucht, wo ein (globales) Optimum… …   Deutsch Wikipedia

  • Werte-Landschaft — Eine Wertelandschaft ist der etwas blumige Ausdruck für eine mathematische Funktion , wobei D eine (frei wählbare) Menge ist. Meist wird eine Funktion Wertelandschaft im Zusammenhang mit Optimierungsproblemen gebraucht, wo ein (globales) Optimum… …   Deutsch Wikipedia

  • BMC — steht als Abkürzung für: Baseboard Management Controller, eine spezielle Hardwarekomponente bei Hauptplatinen die Statusinformationen an ein Betriebssystem liefern kann. Best Master Clock Algorithmus , ein spezieller Algorithmus zur Auswahl einer …   Deutsch Wikipedia

  • Anatoli Alexejewitsch Karazuba — (russisch Анатолий Алексеевич Карацуба, englische Transkription Anatolii Alexeevich Karatsuba; * 31. Januar 1937 in Grosny; † 28. September 2008 in Moskau) war ein russischer Mathematiker, der sich mit Informatik, Zahlentheorie und Analysis… …   Deutsch Wikipedia

  • Arthur Cayley — (* 16. August 1821 in Richmond upon Thames, Surrey; † 26. Januar 1895 in Cambridge) war ein englischer Mathematiker. Er befasste sich mit sehr vielen Gebieten der Mathematik von der Analysis, Algebra, Geo …   Deutsch Wikipedia

  • Liste der Biografien/Cas — Biografien: A B C D E F G H I J K L M N O P Q …   Deutsch Wikipedia

  • Liste der Biografien/Hol — Biografien: A B C D E F G H I J K L M N O P Q …   Deutsch Wikipedia

Share the article and excerpts

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