Design und Analyse randomisierter Suchheuristiken
Loading...
Date
2007-03-06T09:24:34Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Table of contents
Keywords
Analyse, Randomisierte Suchheuristik, Population, Clique