Heute ist meine Paper mit dem Titel
“Adaptive Extremal Optimization by Detrended Fluctuation Analysis”
zur Publikation im Journal of Computational Physics akzeptiert worden.
In dieser Arbeit untersuche ich, wie die von 
Boettcher u.a. erarbeitete Methodik des Extremal Optimization auf ihre Dynamik hin untersucht werden kann. Unter Dynamik verstehe ich die Zeitreihe der Optima (Minima), welche vom jeweiligen Verfahren aufgesucht, d.h. auch als potentielle Lösung vorgeschlagen werden.
Extremal Optimization ist ein stochastisches Verfahren und hat - wie fast alle anderen Verfahren auch - einen oder mehrere interne Parameter, die die Performance des Verfahrens massiv beeinflußen. Ist ein solcher interner Parameter schlecht gewählt, verliert das Verfahren extrem an Leistungsfähigkeit, d.h. die Rechenzeit steigt massiv an - eine Entwicklung, die man natürlich vermeiden möchte.
Nun gibt es viele Arbeiten, die zeigen, daß die ‘richtige’ Wahl des Optimierungsverfahrens sehr von dem zugrundeliegenden Optimierungsproblem abhängt. Je nach Problem gibt es jeweils ein anderes, effizientes Verfahren (sog. Free-Lunch-Theoreme). Dasselbe gilt natürlich erst recht für verschiedene Parameterwahlen bei ein und demselben Verfahren: manchemal ist der eine Parameterwert gut, mal der andere. Selbst beim selben Problem, nur mit unterschiedlicher Größe (etwa Anzahl der Städte beim Traveling-Salesperson-Problem) kann der beste Werte variieren.
Was also tun? Nun, wenn die Dynamik verstanden wird, so kann man ebenso zu verstehen versuchen, wie effizient ein Verfahren sich eigentlich im Lösungsraum ‘bewegt’. Oder besser gesagt ‘navigiert’. Denn wenn das Verfahren sich zu einem Random-Walk entwickelt, dann ist dies sicherlich kein ‘Navigieren’, sondern plumpes Raten. Und Raten kann ich ja selber auch, dafür braucht man keinen Computer. Wenn also die Dynamik eher dem eines Random-Walk gleicht, dann bedeutet dies, daß meine Parameterwahl suboptimal war.
Diese Einsicht kann ich nun nutzen, um die Parameterwahl zu automatisieren: setze einen Wert per Zufall; schau auf Dynamik (hier mit Detrended Fluctuation Analysis); ist die Dynamik schlecht, so ändere den Parameterwert (in meiner Arbeit aufgrund eines plausiblierten Modells für die Parametersituation) und starte von vorn.
Dieses Vorgehen hat sich bereits beim Stochastic Tunneling [eingef&uum;hrt in Phys. Rev. Lett. 82(15):3003-3007, 1999; Phys. Rev. E, 59(1):938-941, 1999] bewährt [siehe Europhys.Lett. 74(6):944, 2006 für diese Studie].
Ebenso hat sich die Detrended Fluctuation Analysis auch bewährt Optimierungsverfahren grundsätzlich zu untersuchen [z.B. Physica A 378(2):307-314, 2007].
Weiteres gibt es noch auf meiner Publikationsliste.