The main problem in the development of a genetic algorithm is to find good encodings
for the individuals (genotypes) and the genetic operators.
Here each individual describes a correct layout for the circuit of the VLSI chip.
This layout is encoded by a binary tree (cf. Fig. 1).
The leaves of this tree represent the building blocks of the layout and
the inner nodes of the tree describe meta-blocks (partial layouts), which have the same representation
like the basic blocks.
When building such a meta-block out of two blocks or meta-blocks, the total (detailed)
routing inside this block can be done.
Building the tree in a bottom-up fashion, the root of this tree represents the layout for the complete
chip.
The mutation and crossover operators operate on the tree by exchanging leaves or changing the
wiring-routes inside a meta-block (mutation) and combining subtrees of two individuals to a new
solution (crossover).
The convergence-ratio of the fitness (layout-area) is increased by using shape-functions also for the
meta-blocks, so that every inner node of the tree -- including the root -- describes more than
one layout alternative, provided that the blocks have different aspect ratios.
For real-world VLSI chips there are 10 to 50 building blocks and up to 500 nets (full custom design).
The actual implementation includes a visualization of the layout by showing
the blocks and the routing space.
Future versions will include a visualization of the detailed routing, too,
and an efficient parallelization of the genetic algorithm.
This project is part of the BMBF-project `HYBRID--Applications of Parallel Genetic Algorithms in Combinatorial Optimization'. It has started in April 1994 and will end in December 1996.