Distributed Memetic Algorithms for Graph-Theoretical Combinatorial Optimization Problems

by 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.

327 pages, Paperback

First published April 29, 2009

About the author

Thomas Fischer, Jahrgang 1953, war bis April 2017 Vorsitzender Richter am Bundesgerichtshof in Karlsruhe. Sein jährlicher Kommentar zum Strafgesetzbuch, die Beckʼschen Kurzkommentare, gilt als die Bibel des Strafrechts. Mit seinen Kolumnen für ZEIT-ONLINE und den SPIEGEL wurde er einer breiteren Öffentlichkeit bekannt, zudem ist er Teil des SWR 2-Podcasts “Sprechen wir über Mord?!“.

---------------

Thomas Fischer, born in 1953, was presiding judge at the Federal Court of Justice in Karlsruhe until April 2017. His annual commentary on the German Criminal Law Code, the Beckʼschen Kurzkommentare, is considered the bible of criminal law. His columns for ZEIT-ONLINE and SPIEGEL have made him known to a wider public, and he is also part of the SWR 2 podcast " Sprechen wir über Mord?!".