Authors: Witt, Carsten
Title: Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung
Language (ISO): de
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.
Subject Headings: Theoretische Analyse
Randomisierte Suchheuristiken
Evolutionäre Algorithmen
Kombinatorische Optimierung
URI: http://hdl.handle.net/2003/19662
http://dx.doi.org/10.17877/DE290R-255
Issue Date: 2004-12-14
Publisher: Universität Dortmund
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
WITT.PDFDNB1.5 MBAdobe PDFView/Open
WITT.PS2.45 MBPostscriptView/Open
ZUSAMMENFASSUNGWitt.PDFZusammenfassung31.13 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.