Technical Report No. 125 - Abstract

C. Matuszewski, F. Schmiedle, R. Schönfeld
Channel Routing with Genetic Algorithms

The present report gives an overview and a description of a software environment for Routing with Genetic Algorithms. Within the scope of a research project supported by the DFG under grant \mbox{Be1176/12-1} and \mbox{Mo645/5-1} this work was carried out as a joint project of the research groups of Prof.~Dr.~Bernd~Becker at the Albert-Ludwigs-University of Freiburg and Prof.~Dr.~Paul~Molitor at the Martin Luther University of Halle-Wittenberg from 1998 to 1999. The authors describe the present status of the software they have developed, including internal data structures, main features and some basic interfaces. They also provide a user manual in order to simplify handling. All tools have been implemented in a C/C++ environment, if not explicitly stated otherwise. In Chapter 2 the routing environment MaDRE is presented. Within the same data structure several routing strategies are included as Basic Optimization Modules (BOMs). BOMs are essential for the heuristic learning approach. Furthermore, an implementation of a completely different routing strategy, the Exact Routing approach, is introduced. Genetic Algorithms (GAs) are the key issue of Chapter 3. The software library GAME that provides an environment to perform genetic algorithms is described. It allows a wide range for choosing parameters, genetic operators, selection/survival strategies etc. Also a mapping on a parallel computer system is possible. MaDRE and GAME are combined for the heuristic learning approach. Chapter 4 describes an implementation that has been produced so far. In Chapter 5 we provide a collection of routing instances that are to be used for benchmarking our methods. Finally we present a tool for visualization that enables the user to illustrate the routed channels generated by the diverse strategies.