Entwicklung einer Komplexitätstheorie für randomisierte Suchheuristiken: Black-Box-Modelle

Abstract

Randomisierte Suchheuristiken sind problemunabhängige Algorithmen, die sowohl im wissenschaftlichen als auch im industriellen Kontext zur Optimierung von schwierigen Problemen genutzt werden. Sie sind einfach zu implementieren, lassen sich vielseitig einsetzen und liefern überraschend häufig bereits in kurzer Zeit sehr gute Ergebnisse. Daher sind randomisierte Suchheuristiken weit verbreitet. Ein großes Problem in Anwendung von randomisierten Suchheuristiken ist jedoch die Tatsache, dass sich schwer vorhersagen lässt, ob sich das zu optimierende Problem gut durch eine geeignete Heuristik lösen lässt oder ob andere problemspezifische Verfahren deutliche besser geeignet sind. Mit meiner Dissertation leisten wir einen Beitrag zur Entwicklung einer Komplexitätstheorie für randomisierte Suchheuristiken. Unser langfristiges Ziel ist die Charakterisierung von Problemklassen in solche, die sich schnell und zuverlässig durch Suchheuristiken optimieren lassen und solche, für die grundsätzlich andere Methoden besser geeignet sind.