Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung

Abstract

Der Entwurf und die Analyse von Algorithmen für die kombinatorische Optimierung zählen zu den zentralen Aufgaben der Informatik. In dieser Dissertation werden in der Praxis erfolgreiche Suchheuristiken, speziell evolutionäre Algorithmen, theoretisch untersucht. Außerdem enthält die Dissertation einen Beitrag zum Entwurf von Algorithmen für ein aktuelles kombinatorisches Optimierungsproblem. Der erste Teil der Dissertation widmet sich einfachen randomisierten Suchheuristi­ken, die zu jedem Zeitpunkt lediglich einen Suchpunkt vorhalten. Diese werden auf der Funktionenklasse der so genannten monotonen Polynome und einem NP­harten Partitionsproblem untersucht. Neben der Analyse der erwarteten Optimierungszeit wird auch die Approximationsgüte studiert, die die Suchheuristiken in Polynomialzeit mit guter Wahrscheinlichkeit erreichen. Im zweiten Teil werden populationsbasierte evolutionäre Algorithmen, die zu jedem Zeitpunkt eine Menge von Suchpunkten vorhalten, betrachtet. Es wird bewiesen, dass die Größe einer solchen Population die Optimierungszeit von evolutionären Algorithmen entscheidend beeinflussen kann. Darüber hinaus wird ein klassischer populationsbasierter evolutionärer Algorithmus auf drei Beispielfunktionen untersucht. Dabei wird der funktionale Zusammenhang zwischen Populationsgröße und erwarteter Optimierungszeit erhellt. Die ersten beiden Teile der Dissertation enthalten fundamental neue Methoden zur Analyse randomisierter Suchheuristiken. Der dritte Teil der Dissertation stellt schließlich problemspezifische Algorithmen für das kombinatorische Optimierungsproblem des integrierten Prefetchings und Cachings vor. Es gelingt der Entwurf eines ersten kombinatorischen Polynomialzeitalgorithmus für einen Spezialfall des Optimierungsproblems. Für den allgemeinen Fall werden verbesserte Approximationsalgorithmen präsentiert.