Bergsteigeralgorithmus

An einem lokalen Maximum bricht der Algorithmus ab, ohne das globale Maximum gefunden zu haben.

Bergsteigeralgorithmus (engl. hill climbing) ist ein einfaches, heuristisches Optimierungsverfahren. Es besteht dabei eine Analogie zu einem Bergsteiger, der im dichten Nebel den Gipfel sucht und dazu seine Schritte möglichst steil bergauf lenkt. Geht es nach allen Richtungen nur noch nach unten, ist er auf einem Gipfel angekommen.

Ebenso wird im Bergsteigeralgorithmus 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 (Nebengipfel). 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:

Pseudocode-Beispiel

Algo (Hill Climbing):
    bestEval = -INF
    currentNode = startNode
    bestNode = None
    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

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:

Selektionsstrategie

Wann soll die Selektion auf einzelne Bergsteiger angewandt werden?

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?

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 07.01. 2021