Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26016
Titel: Random combinatorial structures and randomized search heuristics
Verfasser: Johannsen, Daniel
Sprache: Englisch
Erscheinungsjahr: 2010
SWD-Schlagwörter: Heuristik
Randomisierung
Stochastik
Evolutionärer Algorithmus
Laufzeit
Freie Schlagwörter: Suchheuristik
stochastic
evolutionary algorithms
random structures
search heuristics
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: This thesis is concerned with the probabilistic analysis of random combinatorial structures and the runtime analysis of randomized search heuristics. On the subject of random structures, we investigate two classes of combinatorial objects. The first is the class of planar maps and the second is the class of generalized parking functions. We identify typical properties of these structures and show strong concentration results on the probabilities that these properties hold. To this end, we develop and apply techniques based on exact enumeration by generating functions. For several types of random planar maps, this culminates in concentration results for the degree sequence. For parking functions, we determine the distribution of the defect, the most characteristic parameter. On the subject of randomized search heuristics, we present, improve, and unify different probabilistic methods and their applications. In this, special focus is given to potential functions and the analysis of the drift of stochastic processes. We apply these techniques to investigate the runtimes of evolutionary algorithms. In particular, we show for several classical problems in combinatorial optimization how drift analysis can be used in a uniform way to give bounds on the expected runtimes of evolutionary algorithms.
Diese Dissertationsschrift beschäftigt sich mit der wahrscheinlichkeitstheoretischen Analyse von zufälligen kombinatorischen Strukturen und der Laufzeitanalyse randomisierter Suchheuristiken. Im Bereich der zufälligen Strukturen untersuchen wir zwei Klassen kombinatorischer Objekte. Dies sind zum einen die Klasse aller kombinatorischen Einbettungen planarer Graphen und zum anderen eine Klasse diskreter Funktionen mit bestimmten kombinatorischen Restriktionen (generalized parking functions). Für das Studium dieser Klassen entwickeln und verwenden wir zählkombinatorische Methoden die auf erzeugenden Funktionen basieren. Dies erlaubt uns, Konzentrationsresultate für die Gradsequenzen verschiedener Typen zufälliger kombinatorischer Einbettungen planarer Graphen zu erzielen. Darüber hinaus erhalten wir Konzentrationsresultate für den charakteristischen Parameter, den Defekt, zufälliger Instanzen der untersuchten diskreten Funktionen. Im Bereich der randomisierten Suchheuristiken präsentieren und erweitern wir verschiedene wahrscheinlichkeitstheoretische Methoden der Analyse. Ein besonderer Fokus liegt dabei auf der Analyse der Drift stochastischer Prozesse. Wir wenden diese Methoden in der Laufzeitanalyse evolutionärer Algorithmen an. Insbesondere zeigen wir, wie mit Hilfe von Driftanalyse die erwarteten Laufzeiten evolutionärer Algorithmen auf verschiedenen klassischen Problemen der kombinatorischen Optimierung auf einheitliche Weise abgeschätzt werden können.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-35296
hdl:20.500.11880/26072
http://dx.doi.org/10.22028/D291-26016
Erstgutachter: Doerr, Benjamin
Tag der mündlichen Prüfung: 15-Jul-2010
SciDok-Publikation: 26-Jan-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_3166_Joha_Dani_2010.pdf1,38 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.