Dissertation (Metadaten)
Titel:Combinatorial optimization and the analysis of randomized search heuristics
Autor:Frank Neumann
Fakultät:Technische Fakultät
DDC Sachgebiet:510 Mathematik
Datum der mdl. Prüfung:19.07.2006
Referent(in):Prof. Dr. Rudolf Berghammer
Korreferent(en) Korreferentin:Prof. Dr. Ingo Wegener, Priv.-Doz. Dr. Benjamin Doerr
Beschreibung:Randomized search heuristics have widely been applied to complex engineering problems as well as to problems from combinatorial optimization. We investigate the runtime behavior of randomized search heuristics and present runtime bounds for these heuristics on some well-known combinatorial optimization problems. Such analyses can help to understand better the working principle of these algorithms on combinatorial optimization problems as well as help to design better algorithms for a newly given problem. Our analyses mainly consider evolutionary algorithms that have achieved good results on a wide class of NP-hard combinatorial optimization problems. We start by analyzing some easy single-objective optimization problems such as the minimum spanning tree problem or the problem of computing an Eulerian cycle of a given Eulerian graph and prove bounds on the runtime of simple evolutionary algorithms. For the minimum spanning tree problem we also investigate a multi-objective model and show that randomized search heuristics find minimum spanning trees easier in this model than in a single-objective one. Many polynomial solvable problems become NP-hard when a second objective has to be optimized at the same time. We show that evolutionary algorithms are able to compute good approximations for such problems by examining the NP-hard multi-objective minimum spanning tree problem. Another kind of randomized search heuristic is ant colony optimization. Up to now no runtime bounds have been achieved for this kind of heuristic. We investigate a simple ant colony optimization algorithm and present a first runtime analysis. At the end we turn to classical approximation algorithms. Motivated by our investigations of randomized search heurisitics for the minimum spanning tree problem, we present a multi-objective model for NP-hard spanning tree problems and show that the model can help to speed up approximation algorithms for this kind of problems.
Schlagworte:combinatorial optimization, randomized search heuristics, evolutionary algorithms, ant colony optimization, runtime analysis, multi-objective optimization, approximation algorithms
d1808.pdf (934 kB)    ZIP generieren   Details >>