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.