Globale Optimierung


Click here for english version

Im Rahmen meiner Diplomarbeit, die sich mit stochastischen Verfahren zur globalen Optimierung auseinandergesetzt hat, werden hier einige Ergebnisse präsentiert.

Ein wesentlicher Teil bestand im Test von Programmen. Dabei wurden alle Tests auf 20000 Funktionsauswertungen beschränkt
In den unten angegebenen Tabellen stehen nicht die echten Funktionswerte f, sondern modifizierte f ':

f ' = (f - f*) / (fm- f* )

Dabei ist f* der kleinste von allen Funktionswerten eines Testproblems, die von den Programmen bestimmt wurden. fm wird gebildet, indem von jedem Programm der Median aller Funktionsauswertungen des aktuellen Testproblems gebildet wird und danach der Median dieser Mediane bestimmt wird.

In dieser Tabelle stehen die besten gefundenen Funktionswerte nach 1000, 2500, 5000, 10000 und 20000 Auswertungen. Die besten überhaupt gefundenen Funktionswerte eines Testproblems sind dabei unterstrichen. Nicht alle Programme erreichten immer die nötige Anzahl von Funktionsauswertungen. In diesem Fall steht in der Tabelle der beste vom Programm gefundene Wert.
Die folgenden zwei Links führen zu zwei Tabellen, die mit folgendem Abbruchkriterium gewonnen wurden:

Sei fk der bis zur k-ten Funktionsauswertung beste Funktionswert.
q = p * ( fk'' - fk' ) / ( fk' - fk )
q schätzt den zu erwartenden Fortschritt, wobei p mit Hilfe der Methode der kleinsten Quadrate gefunden wurde. k, k' und k'' sind dabei drei aufeinanderfolgende Werte der Gestalt:
k = 20000 / 2s
Zuerst wird ein Programm so lange laufen gelassen, bis k Funktionsauswertungen gemacht wurden. Dann wird überprüft, ob
q < 1
gilt. Ist dies Der Fall, so wird das Programm abgebrochen und der beste gefundenen Funktionswert ausgegeben. Andernfalls wird zur folgenden Marke k (s wird um eins verkleinert) übergegangen und entsprechend viele Funtkionsauswertungen weiteroptimiert. Dieser Vorgang wird so lange wiederholt, bis q < 1 wird oder ein anderes Abbruchkriterium erfüllt ist.
Bei dieser Tabelle wurden mindestens 156 Funktionsauswertungen durchgeführt. Für die Methode der kleinsten Quadrate wurde als kleinste verwendete Marke k'' = 20000 / 211 verwendet und für
dieser Tabelle wurden mindestens 312 Funktionsauswertungen durchgeführt. Für die Methode der kleinsten Quadrate wurde als kleinste verwendete Marke k'' = 20000 / 29 verwendet.
In beiden Fällen sind die kleinsten gefundenen Funktionswerte (von allen Programmen und mit Abbruchbedingung) unterstrichen. Hätte ein Programm nach 20000 Funktionsauswertungen noch weiterminimiert, so ist dies durch einen * gekennzeichnet.
Wegen der Modifikation erkennt man in diesen beiden Tabellen auch die überhaupt besten Funktionswerte (aller Programme aber ohne Abbruchbedingung) daran, am Eintrag 0 in der Tabelle.

Im Rahmen der Arbeit wurde auch eine von Neumaier und Huyer veröffentlichte Tabelle zum Dixon-Szegö-Testset erweitert. Die Eintragungen entsprechen der Anzahl der Funktionsauswertungen, die benötigt wurden um ein Optimum mit einer Genauigkeit von 0.01 Prozent relativem Fehler zu erreichen. Maximal 12000 Funktionsauswertungen waren zugelassen.

Hier ist eine kurze
Beschreibung der Testfunktionen zu finden, eine Einteilung der Funktionen in Klassen, welche die Schwierigkeit der Funktion repräsentieren sollen (gemessen daran, wie gut die Programme in der Lage waren, ein Optimum zu finden), und dieser Link führt zu den
getesteten Programmen (inkl. Links) .

Auf der Seite meines Betreuers über globale Optimierung -- Global Optimization (Arnold Neumaier) -- sind noch viele weitere Informationen zu diesem Thema abrufbar.


vpk@mat.univie.ac.at