Hill-Climbing ist eines der einfachsten Optimierungsverfahren: Man startet bei einer Lösung und verbessert sie schrittweise, indem man immer einen besseren Nachbarn wählt. Der Name stammt vom Bild eines Bergsteigers, der in jedem Schritt bergauf geht — bis kein höherer Punkt in der Nähe mehr existiert.
So funktioniert Hill-Climbing
- Starte mit einer gültigen Lösung (z. B. zufällig oder per Greedy-Algorithmus konstruiert).
- Erzeuge Nachbarlösungen durch kleine Änderungen (z. B. Vertauschen zweier Elemente).
- Wähle den besten Nachbarn und mache ihn zur neuen Lösung.
- Wiederhole, bis kein Nachbar besser ist — dann befindet man sich in einem lokalen Optimum.
Varianten
- Steepest-Ascent: In jedem Schritt wird der beste aller Nachbarn gewählt.
- First-Choice: Es wird der erste gefundene bessere Nachbar übernommen — spart Rechenzeit bei großen Nachbarschaften.
- Random-Restart: Der Algorithmus startet mehrfach mit verschiedenen Anfangs-Algorithmen-Lösungen und liefert das beste Ergebnis aller Läufe.
- Stochastisches Hill-Climbing: Bessere Nachbarn werden mit hoher, schlechtere mit geringer Wahrscheinlichkeit gewählt.
Stärken und Schwächen
Hill-Climbing ist extrem einfach zu implementieren, schnell und benötigt weder Gedächtnis noch eine Population. Der Preis: Es bleibt leicht in lokalen Optima hängen — Lösungen, die besser als alle Nachbarn, aber schlechter als das globale Optimum sind. Auch Plateaus (Nachbarschaft ohne Verbesserung) und Grate erschweren die Suche.
Die Komplexität pro Schritt ist proportional zur Größe der Nachbarschaft. Mit Random-Restart und First-Choice lässt sich die Robustheit deutlich erhöhen, ohne den Grundgedanken aufzugeben.
Abgrenzung zu anderen Metaheuristiken
Hill-Climbing ist der elementare Vertreter der lokalen Suche und Grundlage vieler stärkerer Verfahren: Simulated Annealing akzeptiert Verschlechterungen mit abklingender Wahrscheinlichkeit, Tabu-Suche merkt sich besuchte Lösungen, und ein Genetischer Algorithmus arbeitet mit einer ganzen Population. Gemeinsam ist allen der Rahmen einer Metaheuristik. In der Heuristik-Familie steht Hill-Climbing damit für reine lokale Verbesserung ohne Explorationsstrategie.
Typische Anwendungen: Näherungslösungen für das Handelsreisendenproblem, Feature-Auswahl, Hyperparameter-Tuning und einfache Layout-Probleme. Bei NP-vollständigen Problemen liefert Hill-Climbing wie alle Heuristiken keine Garantie für das Optimum — die Laufzeit bleibt aber in der Praxis oft weit unter der exakter Verfahren.