日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

学位論文

Analyses of Evolutionary Algorithms

MPS-Authors
/persons/resource/persons44584

Happ,  Edda
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

External Resource
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)
公開されているフルテキストはありません
付随資料 (公開)
There is no public supplementary material available
引用

Happ, E. (2009). Analyses of Evolutionary Algorithms. PhD Thesis, Universität des Saarlandes, Saarbrücken.


引用: https://hdl.handle.net/11858/00-001M-0000-0027-B4B2-2
要旨
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 naturally arising from this
representation has a better runtime than previously analyzed EAs.