One strength of Genetic Algorithms (GAs) is their robustness, which mainly is caused by the fact that they deal with a sample of candidate solutions to an optimization problem at a time, and that these solutions are encoded in a problem independent representation. In most cases this genotype coding is a string (chromosome) of elementary data-types, preferably bits or floats. During the optimization process, new candidate solutions are composed using more or less standard mutation and crossover operators. When solving discrete real-world optimization problems by a GA, it is often necessary to use a complex (non string) genotype representation and operators which only generate admissible solutions. Problem-specific knowledge is often used for hillclimbing during the search.
After finding a feasible coding and implementing the operators, the `only' work to do is to find a set of control parameters, that enable the GA to reach a global optimum and to minimize the time needed for convergence. Because these parameters depend on the representation and on the specific application, and might be changed during the evolution process, it is useful to add a self-adaptation mechanism for the values of these parameters.
In this paper, a parallel GA for a combinatorial optimization problem arising during the computer aided design of microchips is presented. The main feature of this algorithm is a tree-structured genotype representation with problem-specific operators. The paper is organized as follows: It starts with a description of the application and the chosen representation. After the outline of the genetic operators, the strategy adaptation is explained and results for real-world circuits are presented.