Bergsteigeralgorithmus

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:

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.

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 einer Funktion, 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?

Literatur

Stuart Russel, Peter Norvig: Artificial Intelligence: A Modern Approach. Third Edition. Prentice Hall, Upper Saddle River, NJ 2010, ISBN 978-0-13-604259-4, S. 122–125.