Zur Analyse von randomisierten Suchheuristiken und Online-Heuristiken

Simple item page
dc.contributor.advisorWegener, Ingo
dc.contributor.authorGiel, Oliver
dc.contributor.refereeRudolph, Günter
dc.date.accepted2005-09-13
dc.date.accessioned2005-09-19T14:41:53Z
dc.date.available2005-09-19T14:41:53Z
dc.date.issued2005-09-19T14:41:53Z
dc.description.abstractDie Dissertation beschäftigt sich mit der theoretischen Analyse von Heuristiken. Im ersten und zweiten Teil werden randomisierte Heuristiken zur Optimierung im Black-Box-Szenario untersucht. Der dritte Teil befasst sich mit dem Seitenwechselproblem (Pagingproblem), das in der Regel im Online-Szenario zu lösen ist. Das Black-Box- und das Online-Szenario haben gemeinsam, dass die zu bearbeitende Probleminstanz erst im Laufe der Zeit bekannt wird, sodass Algorithmen nur heuristisch vorgehen können. Im ersten Teil wird die Laufzeit zweier einfacher evolutionärer Algorithmen, des (1+1)-EAs und der randomisierten lokalen Suche, am Beispiel des Matchingproblems im Black-Box-Szenario untersucht. Es wird gezeigt, dass beide Heuristiken effizient Maximummatchings approximieren können und dass sie zumindest für einfache Graphklassen in polynomieller erwarteter Zeit Maximummatchings finden. Andererseits gibt es Graphen, für die die Laufzeit beider Heuristiken mit einer überwältigenden Wahrscheinlichkeit exponentiell ist. Der zweite Teil untersucht einen grundlegenden evolutionären Algorithmus für mehrkriterielle Optimierungsprobleme im Black-Box-Szenario. Insbesondere wird die erwartete Laufzeit im Worst Case ermittelt und die Laufzeit für verschiedene zweikriterielle Probleme analysiert. Der dritte Teil befasst sich mit der Analyse von Heuristiken für das Seitenwechselproblem. Es werden zwei Modelle eingeführt, die unmittelbar die Analyse der Fehlerrate unter dem Aspekt der Anfragelokalität ermöglichen. In diesen Modellen werden Schranken für die Fehlerraten verschiedener deterministischer Seitenwechselstrategien bewiesen.de
dc.format.extent3140045 bytes
dc.format.extent2041529 bytes
dc.format.mimetypeapplication/postscript
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2003/21603
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-23
dc.identifier.urnurn:nbn:de:hbz:290-2003/21603-6
dc.language.isode
dc.subjectRandomisierte Suchheuristikende
dc.subjectEvolutionäre Algorithmende
dc.subjectMatchingproblemde
dc.subjectMehrkriterielle Optimierungde
dc.subjectPagingproblemde
dc.subject.ddc004
dc.titleZur Analyse von randomisierten Suchheuristiken und Online-Heuristikende
dc.typeTextde
dc.type.publicationtypedoctoralThesisen
dcterms.accessRightsopen access

Files

Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
DissOliverGiel.pdf
Size:
1.95 MB
Format:
Adobe Portable Document Format
Description:
DNB
Download
No Thumbnail Available
Name:
DissOliverGiel.ps
Size:
2.99 MB
Format:
Postscript Files
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.92 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen