Autor(en): Witt, Carsten
Titel: Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung
Sprache (ISO): de
Zusammenfassung: 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.
Schlagwörter: Theoretische Analyse
Randomisierte Suchheuristiken
Evolutionäre Algorithmen
Kombinatorische Optimierung
URI: http://hdl.handle.net/2003/19662
http://dx.doi.org/10.17877/DE290R-255
Erscheinungsdatum: 2004-12-14
Provinienz: Universität Dortmund
Enthalten in den Sammlungen:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
WITT.PDFDNB1.5 MBAdobe PDFÖffnen/Anzeigen
WITT.PS2.45 MBPostscriptÖffnen/Anzeigen
ZUSAMMENFASSUNGWitt.PDFZusammenfassung31.13 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org