Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25947
Titel: Analyses of evolutionary algorithms
Verfasser: Happ, Edda
Sprache: Englisch
Erscheinungsjahr: 2009
SWD-Schlagwörter: Evolutionärer Algorithmus
Laufzeit
Sortierverfahren
Freie Schlagwörter: Laufzeitanalyse
Crossover Operator
Sortierproblem
evolutionary algorithm
runtime analyses
Single Source Shortest Path Problem
All-Pairs Shortest Path Problem
sorting problem
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Evolutionary algorithms (EAs) are a highly successful tool commonly used in practice to solve algorithmic problems. This remarkable practical value, however, is not backed up by a deep theoretical understanding. Such an understanding would facilitate the application of EAs to further problems. Runtime analyses of EAs are one way to expand the theoretical knowledge in this field. This thesis presents runtime analyses for three prominent problems in combinatorial optimization. Additionally, it provides probability theoretical tools that will simplify future runtime analyses of EAs. The first problem considered is the Single Source Shortest Path problem. The task is to find in a weighted graph for a given source vertex shortest paths to all other vertices. Developing a new analysis method we can give tight bounds on the runtime of a previously designed and analyzed EA for this problem. The second problem is the All-Pairs Shortest Path problem. Given a weighted graph, one has to find a shortest path for every pair of vertices in the graph. For this problem we show that adding a crossover operator to a natural EA using only mutation provably decreases the runtime. This is the first time that the usefulness of a crossover operator was shown for a combinatorial problem. The third problem considered is the Sorting problem. For this problem, we design a new representation based on trees. We show that the EA nat- urally arising from this representation has a better runtime than previously analyzed EAs.
Evolutionäre Algorithmen (EAs) werden in der Praxis sehr erfolgreich eingesetzt. Bisher werden die theoretischen Grundlagen von EAs jedoch nicht zufriedenstellend verstanden. Laufzeitanalysen für einfache EAs sollen dieses Verständnis erweitern. Diese Dissertation enthält Laufzeitanalysen für EAs für drei wohlbekannte kombinatorische Probleme. Zusätzlich werden wahrscheinlichkeitstheoretische Hilfsmittel zur Analyse von EAs eingeführt. Zuerst behandeln wir das Single Source Shortest Path Problem. Die Aufgabe besteht darin, in einem gewichteten Graphen einen kürzesten Weg von einem Startknoten zu jedem anderen Knoten zu finden. Durch die Entwick- lung einer neuen Analysemethode konnten wir scharfe Schranken für die Laufzeit eines bereits zuvor präsentierten und analysierten EAs angeben. Als nächstes betrachten wir das All-Pairs Shortest Path Problem. Hierbei will man für jedes Paar von Knoten in einem gewichteten Graphen einen kürzesten Weg berechnen. Für dieses Problem zeigen wir, dass das Hinzufügen eines Crossover Operators die Laufzeit gegenüber einem natürlichen EA, der nur Mutationen nutzt, verbessert. Dies ist das erste Mal, dass für ein kombinatorisches Problem bewiesen wurde, dass ein Crossover Operator die Laufzeit reduziert. Für das Sortierproblem entwickeln wir eine neue, auf Bäumen beruhende Repräsentation und zeigen, dass der natürlich daraus entstehende EA eine bessere Laufzeit hat als vorherige EAs.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-24273
hdl:20.500.11880/26003
http://dx.doi.org/10.22028/D291-25947
Erstgutachter: Doerr, Benjamin
Tag der mündlichen Prüfung: 1-Apr-2009
SciDok-Publikation: 16-Sep-2009
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_5712_Happ_Edda_2009.pdf880,2 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.