next up previous contents
Next: Biologisch motivierte Suchmethoden Up: Konventionelle Suchmethoden Previous: Monte-Carlo -Methode : Zufalls-Suche

Hill Climbing

Eine sofort einsichtige Strategie ein zumindest lokales Optimum in einem Suchraum zu finden, ist, sich von einem beliebig gewählten Punkt immer in Richtung der größten Steigung (zum lokalen Optimum) zu orientieren. So ist garantiert, zumindest das nächstliegende lokale Optimum zu finden. Hierzu wird der SIMPLEX-Algorithmus verwendet.

Der SIMPLEX Algorithmus verwendet die kleinste geschlossene geometrische Figur, die ausreicht um die Steigung in einem Gebiet zu ermitteln, eben den sogenannten SIMPLEX: Im Falle einer zwei-dimensionalen Suchlandschaft (= zwei Parameter) ist dies ein Dreieck, im drei-dimensionalen Fall eine Pyramide. Wird nun z.B. ein Dreieck in eine zwei-dimensionale Landschaft gelegt so kann man anhand der Höhe der drei Eckpunkte des Dreiecks leicht die annähernde Richtung des nächsten Gipfels abschätzen. Die Suche nach dem Maximum oder Minimum erfolgt prinzipiell nach dem folgenden Schema :

1.
Ein initiales SIMPLEX (also im zwei-dimensionalen Fall ein Dreieck) wird an zufälliger Position in den Suchraum gelegt.
2.
Die Höhe der Eckpunkte wird ermittelt.
3.
Aus den Höhen der Eckpunkte kann nun die ungefähre Richtung des Optimums ermittelt werden. Ein neues SIMPLEX, das sich näher dem Optimum befindet wird ermittelt.
4.
Der Eckpunkt mit der schlechtesten Bewertung wird entlang der Verbindungslinie der besten Punkte gespiegelt. Der schlechteste Punkt im SIMPLEX wird durch den neuen (gespiegelten) Punkt ersetzt, wodurch ein neues SIMPLEX entsteht.
5.
Wiederholung ab Punkt 2. Sobald das Optimum erreicht ist, wird diese Prozedur abgebrochen.
Die Einschränkungen der Hill-Climbing Algorithmen stellen sich folgendermaßen dar:

Eine bessere Strategie ist,mehrere Suchläufe mit unterschiedlichen Ausgangspunkten durchzuführen. Wird immer dasselbe Optimum gefunden, so ist es wahrscheinlich , das globale Optimum gefunden zu haben. Sicherheit kann auch so nicht erzielt werden.

Trotzdem sind Hill-Climbing Strategien in vielen Fällen eine günstige Wahl:


next up previous contents
Next: Biologisch motivierte Suchmethoden Up: Konventionelle Suchmethoden Previous: Monte-Carlo -Methode : Zufalls-Suche
root
1999-11-02