next up previous contents
Nächste Seite: Simulated Annealing Aufwärts: Genetische Algorithmen im Vergleich Vorherige Seite: Zufallssuche   Inhalt

Gradientensuche

Eine Anzahl verschiedener Methoden wurde entwickelt, um für einfache, unimodale Suchräume die Information über die Steigung eines Punktes auszuwerten. Durch die Berechnung von Funktionsableitungen kann der Fokus der Suche in die Richtung der stärksten Steigung im aktuellen Punkt bewegt werden, weshalb diese Gruppe von Verfahren auch Hillclimber oder -crawler genannt wird. Sie stellen in der Grundform ein rein exploitatives Verfahren dar, da keinerlei Zufallselemente in der Suche enthalten sind und der nächste Zug nur von der zur Verfügung stehenden Information abhängt.

Wenn die Ableitung aus mathematischen oder anderen Gründen nicht berechnet werden kann, so bleibt als Annäherung an diese Methode jeweils nur die Möglichkeit, durch die Evaluierung einiger ausgesuchter Punkte in der Nachbarschaft den jeweils besten als Suchrichtung zu benutzen. Auch in diesem Fall handelt es sich immer noch um reine Exploitation von zur Verfügung stehender Information.

Der Nachteil dieser Verfahren liegt gleichzeitig in ihrer Effizienz, nahegelegene Optima mehr oder weniger direkt zu erreichen. Bei multimodalen Suchräumen zeichnen sich diese Methoden durch ihr Unvermögen aus, einmal gefundene und unter Umständen nur lokale Optima zu verlassen und weiterzusuchen. Sie bleiben darin stecken.

Aus diesem Grund werden Gradientensucher sehr oft mit abgeschwächten Versionen explorativer brute force Methoden kombiniert. Zum Beispiel kann ein konvergierter Hillclimber per Zufall ein neues Suchgebiet zugewiesen bekommen, um dort nach einem anderen Optimum zu suchen. Jedoch werden bei diesen iterativen Läufen keinerlei Daten weitergereicht. Ein kumulativer Lerneffekt kann so nicht eintreten.

Die Einfachheit dieses Systems macht es jedoch zu einem beliebten Verfahren, um Suchräume stichprobenartig anzutesten.


next up previous contents
Nächste Seite: Simulated Annealing Aufwärts: Genetische Algorithmen im Vergleich Vorherige Seite: Zufallssuche   Inhalt
2001-07-08