Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung

Witt, Carsten

Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung

dc.contributor.advisor	Wegener, Ingo	de
dc.contributor.author	Witt, Carsten	de
dc.contributor.referee	Vöcking, Berthold	de
dc.date.accepted	2004
dc.date.accessioned	2004-12-29T11:01:46Z
dc.date.available	2004-12-29T11:01:46Z
dc.date.created	2004-12-06	de
dc.date.issued	2004-12-14	de
dc.description.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 Suchheuristiken, die zu jedem Zeitpunkt lediglich einen Suchpunkt vorhalten. Diese werden auf der Funktionenklasse der so genannten monotonen Polynome und einem NPharten 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.	de
dc.format.extent	1602482 bytes
dc.format.extent	2513660 bytes
dc.format.mimetype	application/pdf
dc.format.mimetype	application/postscript
dc.identifier.uri	http://hdl.handle.net/2003/19662
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-255
dc.language.iso	de	de
dc.publisher	Universität Dortmund	de
dc.subject	Theoretische Analyse	de
dc.subject	Randomisierte Suchheuristiken	de
dc.subject	Evolutionäre Algorithmen	de
dc.subject	Kombinatorische Optimierung	de
dc.subject.ddc	004	de
dc.title	Über die Analyse randomisierter Suchheuristiken und den Entwurf spezialisierter Algorithmen im Bereich der kombinatorischen Optimierung	de
dc.type	Text	de
dc.type.publicationtype	doctoralThesis	de
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 4 of 4

Name:: WITT.PDF
Size:: 1.47 MB
Format:: Adobe Portable Document Format
Description:: DNB

Download

Name:: WITT.PS
Size:: 2.4 MB
Format:: Postscript Files

Download

Name:: ZUSAMMENFASSUNGWitt.PDF
Size:: 31.13 KB
Format:: Adobe Portable Document Format
Description:: Zusammenfassung

Download

Name:: license.txt
Size:: 1.85 KB
Format:: Item-specific license agreed upon to submission
Description:: Written by org.dspace.content.Item

Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen