4 Optimierungsstrategien für diskrete Parameterräume

4 Optimierungsstrategien für diskrete Parameterräume

Durch die Verwendung von gewichteten Medianfiltern müssen die im zweiten Kapitel beschriebenen numerischen Optimierungsstrategien an diskrete Parameterräume angepasst werden. In einem diskreten Parameterraum sind nur ganzzahlige Positionen des Raums erreichbar. Alle anderen Orte, die zwischen diesen Punkten liegen, sind nicht zugänglich.

4.1 Direkte Suchverfahren und Gradientenstrategien

Ähnlich wie kontinuierliche Suchverfahren tasten diskrete Suchverfahren den Parameterraum schrittweise ab. Die minimale Schrittweite ist in diesem Fall aber auf eins begrenzt. Auch die Anzahl der möglichen Suchrichtungen unterliegt dadurch größeren Einschränkungen. Verschiedene Suchstrategien sind denkbar und sollen näher untersucht werden:

Die einfachste Strategie tastet den Parameterraum in Richtung aller Koordinatenachsen ab. Dabei werden die Fitnesswerte der benachbarten Punkte mit dem Wert der Bewertungsfunktion des Ausgangspunktes verglichen. Der beste untersuchte Punkt wird neuer Startpunkt für den nächsten Tastschritt. Gleiche Werte der Bewertungsfunktion sind höchst unwahrscheinlich, wenn die Bewertungsfunktion auch im diskreten Parameterraum über einen kontinuierlichen Wertebereich verfügt. Besitzt keiner der überprüften Punkte einen besseren Fitnesswert als der Ausgangspunkt, ist die Suche an ihrem Ziel angelangt. Die Schrittweite bleibt während des gesamten Suchvorgangs konstant eins. Dieses Schema ist in Abbildung 4.1 dargestellt, den Algorithmus verdeutlicht Abbildung 4.2.


Schema
Abbildung 4.1: Schema des ersten Suchverfahrens

Algorithmus
Abbildung 4.2: Algorithmus des Suchverfahrens

Diese Strategie lässt sich dadurch erweitern, dass ausser den benachbarten Punkten auf den Achsen alle Nachbarpositionen des n-dimensionalen Parameterraumes überprüft werden. Auf diese Weise lässt sich die Anzahl der Tastschritte, die bis zum Erreichen des Optimierungsziels zurückgelegt werden, verringern. Ein Beispiel dafür ist in Abbildung 4.3 gegeben.


Schema
Abbildung 4.3: Schema des zweiten Suchverfahrens

Im Gegensatz zur zuerst vorgestellten Suchstrategie wird statt zweier Schritte nur noch ein Schritt benötigt, um den Zielpunkt des Beispiels zu erreichen. Die Schrittweite kann bei diesem Suchverfahren zwischen 1 und √n schwanken. Der Vorteil der im Vergleich zum ersten Verfahren größeren Schrittweite wird durch eine höhere Anzahl von zu testenden Punkten erkauft. Während im ersten Optimierungsverfahren zur Bestimmung des neuen Ausgangspunktes 2 · n Bewertungen durchgeführt werden, müssen im zweiten Fall 3n - 1 Funktionswerte berechnet werden. Das bedeutet, dass für ein n = 6 beim ersten Verfahren 2 · 6 = 12 Funktionswerte bestimmt werden müssen, im zweiten Fall sind jedoch schon 36 - 1 = 728 Berechnungen notwendig. Da die Bewertung der Güte eines Medianfilters sehr zeitaufwendig ist1, eignet sich diese Strategie aufgrund ihres hohen Rechenaufwandes nicht zur Optimierung des vorliegenden Problems.

Auch die Gradientenstrategie lässt sich an diskrete Parameterräume anpassen. Dazu wird ausgehend von einem Startpunkt der Gradient der Bewertungsfunktion nach Formel 2.4 gebildet. Zur Bestimmung des Gradienten sind nur n Berechnungen der Gütefunktion notwendig. Bei dieser Strategie wird der gleiche Algorithmus nach Abbildung 2.5 wie für kontinuierliche Parameterräume verwendet. Da sich der Zielpunkt des Gradientenvektors nicht mehr im diskreten Parameterraum befindet, muss er zur Bestimmung des neuen Startpunktes auf einen diskreten Wert abgebildet werden. Dieser Umstand wird durch Abbildung 4.4 erläutert.


Schema
Abbildung 4.4: Schema der diskreten Gradientenstrategie

Weil der Wert des Gradienten im allgemeinen sehr viel kleiner als eins ist (etwa 10-6 bis 10-4), erweist sich die Abbildung auf diskrete Werte in der Praxis als kompliziert. Zur Bestimmung des diskreten Zielwertes kann der Winkel α zwischen Gradientenvektor und den Koordinatenachsen verwendet werden, z. B. bei einem Winkel von -22,5° < α < 22,5° wird der rechte Nachbarpunkt zum neuen Startpunkt, bei 22,5° < α < 67,5° der diagonale Nachbarpunkt und zwischen 67,5° und 112,5° der obere Nachbar. Dies erfordert in höherdimensionalen Räumen eine große Anzahl von Vergleichen. Die Abbildung kann auch mittels einer sehr großen Schrittweite, die den Betrag des Gradientenvektors auf einen Wert in der Größenordnung von eins verlängert, und anschließendem Runden auf einen diskreten Wert erreicht werden. In beiden Fällen kommt der Schrittweite eine wichtige Rolle zu, da durch sie die Abbruchbedingung der Strategie gegeben wird. Durch eine zu niedrige Wahl der Abbruchschrittweite läuft die Suche weiter, obwohl kein neuer Punkt mehr erreicht werden kann, ist sie zu groß, wird die Suche vor dem besten zu erreichenden Zielpunkt beendet.

Aufgrund der beschriebenen Schwierigkeiten wurde in dieser Studienarbeit nur das zuerst beschriebene Verfahren der Koordinatenachsenabtastung verwendet. Die im Vergleich zur Gradientenstrategie doppelte Anzahl an Bewertungen wird durch die Einfachheit des Algorithmus und der leicht zu realisierenden Funktion wieder ausgeglichen.

Allen direkten Suchverfahren ist gemeinsam, dass sie nur das Optimum von unimodalen Problemen mit Sicherheit finden können. Auch kann das Optimum einer Funktion die Stufen oder Plateaus enthält nicht erreicht werden, da innerhalb der Schrittweite eine Änderung des Wertes der Bewertungsfunktion vorhanden sein muss. Mit diesen Einschränkungen können die drei beschriebenen Suchverfahren das dem Startpunkt nächstliegende Optimum der Zielfunktion erreichen.

4.2 Simulated Annealing

Das in Kapitel 2.3 vorgestellte Verfahren des Simulated Annealing kann für diskrete Parameterräume fast unverändert übernommen werden. Der Algorithmus nach Abbildung 2.6 lässt sich ohne Änderungen weiter verwenden. Die entscheidende Veränderung ist die Methode nach der ein neuer Tastschritt erfolgt. Im kontinuierlichen Fall wird eine neue Konfiguration pneu aus der alten Konfiguration palt durch

pneu = palt + gleich([-½, +½]) · dk

gebildet [Schwefel95]. Die Funktion gleich(x) erzeugt eine gleichverteilte Zufallszahl aus dem gegebenen Intervall, dk ist die aktuelle Streuweite. Für diskrete Parameterräume wird die neue Konfiguration entsprechend

Formel

erzeugt. Formel und Formel sind ganzzahlige Werte. Da durch eine Streubreite von [-½, +½] kein Nachbarpunkt im diskreten Raum erreicht werden kann, wird sie auf [-½ · MaxG, +½ · MaxG] ausgeweitet. MaxG entspricht der maximalen Gewichtung, die für einen Filterkoeffizienten zugelassen wird. Zusätzlich muss gewährleistet sein, dass die Parameter der neuen Konfiguration Formel größer als Null bleiben, weil negative Gewichtungen für Medianfilter nicht definiert sind. Die Bildung einer neuen Konfiguration wird durch Abbildung 4.5 verdeutlicht.


Konfiguration
Abbildung 4.5: Bildung einer neuen Konfiguration

4.3 Evolutionsstrategien

Die in Abschnitt 2.4 beschriebenen Evolutionsstrategien lassen sich relativ einfach an diskrete Parameterräume anpassen. Während die Objektvariablen xi nur noch diskrete Werte annehmen können, werden für die Streuparameter σi auch im diskreten Parameterraum reelle Zahlen gewählt. Die Mechanismen der Selektion bleiben unverändert. Bei der Rekombination ist es erforderlich den intermediären Fall durch Runden auf ganzzahlige Werte anzupassen. Da die diskrete Rekombination nur schon vorhandene Komponenten verwendet, kann diese direkt auf diskrete Parameterräume übertragen werden.

Die größten Änderungen erfährt die Mutation. Da im diskreten Parameterraum gaußverteilte Zufallszahlen nicht verwendet werden können, müssen andere Zufallsverteilungen gefunden werden. Unter Berücksichtigung der Gegebenheit, dass zwei Punkte im diskreten Parameterraum mindestens den Abstand eins besitzen, ist die Verwendung einer geometrischen Verteilung angebracht. Die Mutation nach Gleichung (2.6) ändert sich in

xi = xi + (g1 - g0) .

Die beiden geometrisch verteilten Zufallszahlen g0 und g1 werden durch

Formel

gebildet. u ist eine gleichverteilte Zufallszahl aus dem Intervall [0, 1[, p wird mittels

Formel

erzeugt. σi entspricht den Streuparametern eines Individuums, n bezeichnet die Dimension des Optimierungsproblems. Die Streuparameter werden weiterhin nach Gleichung (2.6) mutiert [Häring97].

4.4 Differential Evolution

Auch die Optimierungsmethode der Differential Evolution lässt sich relativ einfach an diskrete Parameterräume anpassen. Neue Individuen werden auf die gleiche Weise wie im kontinuierlichen Fall gebildet (Kapitel 2.5.1). Es folgt eine Begrenzung des Parameters auf die minimal und maximal zulässigen Werte. Im Grunde befinden sich die Parameter- und Differenzvektoren schon auf diskreten Positionen, aber durch die Multiplikation mit dem Gewichtungsfaktor F2 werden wieder neue zwischen den diskreten Punkten liegende Positionen erreicht. Daher wird der neugebildete Parameter auf den nächsten ganzzahligen Wert gerundet.


Parametervektor
Abbildung 4.6: Erzeugung eines neuen Parametervektors vneu

1 Eine ausführliche Beschreibung der Implementation der Filter und Bewertungsfunktion erfolgt in Kapitel 5.

2 siehe Gleichungen (2.7) bis (2.11)


Kapitel3 Zurück Kapitel5