next up previous
Next: Strategy Adaptation Up: Genetic Layout Optimization Previous: Genotype Representation

Genetic Operators

During the optimization process the placement of the blocks has to be changed and the routing has to be updated. The genetic operators directly work on the tree-structure by combining subtrees of different individuals (crossover) and modifying the tree of an individual (mutation).

The crossover operator takes two individuals out of which one offspring is composed by combining two disjunct subtrees of both parents. Unfortunately, these parts usually do not add up to a complete layout. After the combination of the two subtrees, the missing blocks have to be added to the tree to ensure that the offspring finally represents a correct layout. Here the iterated matching is used again to ensure that inside the added part of the layout highly connected cells are located near together.

A set of different mutation operators is used. The simplest operator changes the orientation of a block or a meta-block. Another operator exchanges subtrees inside the tree of the mutated individual. A distinction is made between exchanging simple blocks, a block (leaf) with a meta-block (subtree), and exchanging two meta-blocks. These cases represent the exchange of two cells, a cell with a partial layout, and the exchange of two partial layouts on the layout surface. Another mutation operator modifies the structure of the slicing tree by removing a subtree or a single block from the tree and inserting it at a different position. This corresponds to moving partial layouts or cells on the layout surface.

Mon Jun 10 11:25:16 MET DST 1996