berblick


(Contents)(Previous)(Next)

Überblick

Die bisher betrachteten, zielgerichteten Optimierungsverfahren streben mehr oder weniger schnell auf ein lokales Optimum zu. In vielen Fällen existieren aber viele lokale Optima, welche grossenteils nicht der gewünschten Lösung entsprechen. Zu beachten ist, dass nicht nur das globale Optimum, sondern auch ein oder mehrere lokale Optima oder gar Punkte in denen kein lokales Optimum existiert, brauchbar sein können. Dies wird schnell klar, wenn z.B. Kosten minimiert werden und gewünscht ist, dass die Kosten unter einem vorgegebenen Betrag liegen. Ausserdem kann es natürlich vorkommen, dass die Anforderungen an die Optimierung zu hoch, bzw. der vorgegebene Suchraum zu klein sind, so dass selbst das globale Optimum nicht brauchbar ist.

Findet man mit einem zielgerichteten Algorithmus ein lokales Optimum, so kann damit die Aufgabe erfüllt sein, weil die gefundene Lösung die gestellten Anforderungen erfüllt. Andernfalls muss man sich überlegen, ob bessere Lösungen existieren und wie diese gefunden werden können.

Sucht man beispielsweise das Minimum einer eindimensionalen Funktion, so kann man beim linken Ende des Definitionsbereichs starten und nach rechts suchen, bis das erste lokale Minimum gefunden ist. Erfüllt dieses die gestellten Anforderungen nicht, so kann man weiter nach rechts laufen, bis ein Maximum gefunden ist und rechts von diesem das nächste Minimum suchen. Dieses Verfahren lässt sich allerdings nicht einfach auf höherdimensionale Probleme übertragen, wie man bereits bei der Betrachtung von Funktionen mit zwei Variablen erkennt.

Naheliegend ist, den Algorithmus so lange von einem andern Ort des Suchraumes aus zu starten, bis eine brauchbare Lösung gefunden wird. Dabei kann man den Suchraum systematisch in Teilbereiche unterteilen und jeden Teilbereich absuchen. Dies ist aber bei n-dimensionalen Räumen mit hohem n unmöglich, weil sich beispielsweise bei einer Unterteilung jeder Koordinatenrichtung in m>1 Teile mn Teilbereiche ergeben. Die Situation ist hier ähnlich wie bei der numerischen Integration hochdimensionaler Funktionen. Ein Ausweg bietet dort das Monte Carlo Verfahren, bei dem völlig zufällig gesetzte Punkte verwendet werden. Ebenso kann man natürlich zielgerichtete Optimierungsverfahren an zufällig gewählten Orten des Suchraums starten. Damit ergeben sich einfache Verfahren mit einem stochastischen Anteil. Letzterer garantiert, dass sich die Suche von einem einmal gefundenen, lokalen Optimum lösen kann und allenfalls sogar das globale Optimum findet sofern ausreichend viele Iterationen durchgeführt werden können. Da die Anzahl Iterationen praktisch beschränkt ist, findet man mit derartigen (und allen andern) stochastischen Verfahren das globale Optimum immer nur mit einer gewissen Wahrscheinlichkeit.

Die meisten, heute gebräuchlichen stochastischen Verfahren basieren nicht auf zielgerichteten Verfahren, sondern auf Prinzipien, die man gewissermassen der Natur abgeschaut hat. Dazu gehören physikalische, aber vor allem biologische Beobachtungen. So ergibt sich aus der Beobachtung der Abkühlung von Flüssigkeiten das "Simulated Annealing" Verfahren, während sich aus biologischen Beobachtungen verschiedenartigste Verfahren mit den Adjektiven "evolutionär", "genetisch" und "neuronal" ergeben. Dabei ist es unerheblich, ob die vermuteten biologischen Grundlagen tatsächlich stimmen ob z.B. die Evolution tatsächlich einem Optimierungsprozess entspricht - und ob sie richtig in ein numerisches Verfahren übersetzt werden. Wichtig ist, dass die Betrachtung der Natur als Ideenquelle für die stochastische Optimierung sehr fruchtbar war. Da die so erhaltenen Verfahren auf schwachen theoretischen Grundlagen basieren, besteht vielfach das Bedürfnis nach einer sauberen mathematischen Analyse und Beschreibung der resultierenden Algorithmen. Um dieses Bedürfnis zu befriedigen, müssen allerdings Vereinfachungen vorgenommen werden, welche die praktische Tauglichkeit der Algorithmen beeinträchtigen. Andererseits sind wir für die Lösung schwieriger Optimierungsprobleme gezwungen, die Effizienz dieser Algorithmen so rasch wie möglich markant zu steigern. Dies geht vermutlich nur durch die experimentelle Entwicklung strukturell viel komplizierterer Algorithmen unter Verzicht auf theoretische Grundlagen. Wir werden uns deshalb auf die Darstellung der Prinzipien beschränken und überlassen die theoretische Ausarbeitung Mathematikern.


(Contents)(Previous)(Next)