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.
