Next: Biologisch motivierte Suchmethoden
Up: Konventionelle Suchmethoden
Previous: Monte-Carlo -Methode : Zufalls-Suche
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:
- Es besteht keine Garantie ein globales Optimum zu finden, da immer nur das nächst
gelegene Optimum gefunden wird.
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:
- Wenn die Bestimmung einzelner Werte sehr aufwendig oder teuer ist,
- die Beschaffenheit der Suchlandschaft und ein günstiger Ausgangspunkt bekannt
sind, bzw. die Suchlandschaft so einfach ist (nur ein Optimum), daß dieses Verfahren
als ausreichend betrachtet wird,
- man sich sicher ist, bereits nahe am gesuchten (globalen) Optimum zu sein, und
nur die letzten Schritte zum Optimum fehlen,
- das Suchen des globalen Optimums nicht möglich oder nicht notwendig ist (z.B.
im Falle der Optimierung von Ausbeuten chemischer Prozesse, wo schon eine deutliche
Verbesserung zum nächsten lokalen Optimum als Erfolg gewertet werden kann).
Next: Biologisch motivierte Suchmethoden
Up: Konventionelle Suchmethoden
Previous: Monte-Carlo -Methode : Zufalls-Suche
root
1999-11-02