Thomas Fischer

Distributed Memetic Algorithms for Graph-theoretical Combinatorial Optimization Problems Thomas Fischer

In this thesis, three different graph-theoretical combinatorial optimization problems have been addressed by memetic and distributed algorithms. These three problems include the well-known 'Travelling Salesman Problem' (TSP) and the two communication problems 'Optimum Communication Spanning Tree Problem' (OCST) and 'Routing and Wavelength Assignment Problem' (RWA). The focus of the research presented in this thesis was on developing techniques to handle large instances of the above problems, where 'large' refers to problem sizes larger than those addressed in related works or large enough to pose a challenge for state-of-the-art heuristic solvers. For the TSP, a large number of publications and algorithms are available, so here research centers on how to solve large problem instances either by reducing the size of problem instances by fixing edges of a problem instance or by distributing the computation in sets of cluster nodes. For the OCST, a given local search algorithm was modified to handle large problem instances. The new local search algorithm was embedded into a distributed memetic algorithm with problem-specific recombination operators. For the RWA, most components of a distributed memetic algorithm were developed for this thesis, including local search, recombination, and distribution. To handle large problem instances, the algorithm was enhanced by a multilevel component to reduce the problem size.