Design und Analyse randomisierter Suchheuristiken

Abstract

Das Design von Algorithmen und ihre Analyse gehören zu den fundamentalen Aufgaben der Informatik. Dabei ist das Berechnen der Optima einer Funktion eines der wichtigsten Probleme - in Theorie wie Praxis. In dieser Dissertation werden verschiedene randomisierte Suchheuristiken, zu denen die evolutionären Algorithmen gehören, zur Optimierung pseudoboolescher Funktionen theoretisch untersucht. Zum Beginn werden die Effekte der Wahl der Plus- und Komma-Selektion auf die Laufzeit eines einfachen evolutionären Algorithmus bei unterschiedlichen Nachkommenpopulationsgrößen betrachtet. Bei kleinen Nachkommenpopulationen ist die Komma-Selektion bereits zur Optimierung einfacher Funktionen völlig ungeeignet, wohingegen bei großen Nachkommenpopulationen die Plus- und die Komma-Selektion sich sehr ähnlich verhalten. Für Nachkommenpopulationen, die weder klein noch groß sind, wird exemplarisch die wesentliche Effizienzsteigerung durch Einsatz der Komma- gegenüber der Plus-Selektion bewiesen. Des Weiteren werden die Effekte der Wahl der Elternpopulationsgröße auf die Laufzeit eines einfachen evolutionären Algorithmus betrachtet. Neben dem Vergleich der Auswirkungen der Diversität auf die Effizienz zur Optimierung einfacher Funktionen wird ein starkes Hierarchieresultat für die Elternpopulationsgröße gezeigt. Bereits die Vergrößerung der Population um eins kann von totaler Ineffizienz zu Effizienz führen. Des Weiteren betrachten wir detailliert die Effekte von Transformationen der zu optimierenden Funktionen sowohl für die unterschiedlichen Komponenten und Klassen von randomisierten Suchheuristiken als auch für die Black-Box-Komplexität. Diesbezüglich kann eine Klassifizierung aller Suchheuristiken und Transformationen vorgenommen sowie für einfache Algorithmen konkretisiert werden. Zum Schluss werden einfache randomisierte Suchheuristiken zur Approximierung und Optimierung des Cliquenproblems untersucht. Dies geschieht nicht nur für beliebige Graphen erschöpfend, sondern auch für spezielle Klassen von Graphen. Den semizufälligen Graphen kommt eine besondere Bedeutung zu. Hier gelingt es schließlich in einer sehr allgemeinen Form, die wesentliche Steigerung der Effizienz einer randomisierten Suchheuristik durch den Einsatz einer großen Population nachzuweisen. Für planare und zufällige planare Graphen wird abschließend durch die Betrachtung der Black-Box-Komplexität die Optimalität eines Metropolis-Algorithmus zur Berechnung einer größten Clique bewiesen.