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.