Data Representation

In many GA optimizations a genome is represented as a binary string of elements (so-called genes), each of which can assume a value of 0 or $1$. The number of genes in the genome thereby determines the dimension of the optimization problem. Fig. 5.11 depicts this kind of data representation.

Figure 5.11: Binary representation of a genome. Each gene can assume a value of 0 or $1$.

For TCAD optimization applications a binary representation is not suitable to represent an optimization parameter, since most of the parameters can assume arbitrary values (as opposed to discrete values of the binary representation) within given bounds. Therefore, a gene is represented by a floating point number^5.5. Fig. 5.12

Figure 5.12: Population and representation of a $14$ dimensional optimization problem.

depicts a population with $10$ genomes, where each genome consists of $14$ genes. This representation corresponds to an optimization with a $14$ dimensional parameter vector. The chosen representation influences the crossover algorithm the mutation algorithm and also the algorithm to generate random numbers.

The genetic algorithm implemented in SIESTA is based on the library GALIB [100], which defines a set of C++ classes that help in implementing genetic algorithms. The library supports various data representations and defines crossover, mutation, and random number generation algorithms on these representations. To implement a genetic algorithm with galib, one needs to select a suitable representation and one of four supported genetic algorithms. The algorithms differ in the way individuals are selected for mating, dying, and surviving. The library supports the following genetic algorithms

• SIMPLE (as described in [101]). This algorithm replaces the whole population in each generation. The new individuals are created by means of genetic reproduction.

• STEADY-STATE. This algorithm replaces only a part of the population ( $P_{replace}$). Some of the individuals survive into the next generation. New individuals are created by means of genetic reproduction. The STEADY-STATE algorithm defines as additional input parameter the crossover probability ${\ensuremath P_{\!cr\!oss}}$ that is used to decide whether the parents or their children are taken over into the next generation.

• INCREMENTAL. In this variant in each generation only one or two children are introduced.

• DEME. This algorithm evolves several populations independently each with a STEADY-STATE algorithm. Each generation some individuals are migrated across the populations.

2003-03-27