One of the main feature of a genetic algorithm applied to an optimization problem is the fact, that
it does not deal with the problem itself, but with encodings of solutions for this problem.
Thus the genetic algorithm explores the space of these encodings rather than
the solution space itself.
For continuous parameter optimization problems, both spaces are identically.
A straight-forward genotype encoding in this case is a string of genes, which are simple floats.
Each gene represents an element of the vector defining a point in the solution space.
The standard mutation operator randomly modifies single genes,
and crossover is done by direct merging of two gene strings, which results in
two offspring.
All offspring represent correct encodings and these encodings define admissible
solutions to the given optimization problem, because of the one-to-one (genotype to phenotype) mapping
between both spaces.
For discrete problems with string type
genotype encoding, not every possible string
represents a correct solution.
It is even worse that simple crossing-over of two individuals does not necessarily
lead to a correct offspring.
There some repairment has to be done after crossing, which reduces the parent
to offspring correlation.
For solving discrete real-world optimization problems,
there has to be an application specific genotype encoding and
`intelligent' operators, which only create admissible individuals.
During the application of these operators, problem specific
knowledge can be used to generate high quality offspring.
Here - in contrast to function optimization for example - bad genes,
which would never be a building-block in a global optimal solution, could be recognized.
The designer of a genetic algorithm can take care that these
bad genes are not included in the population by hill-climbing strategies,
which could be integrated in the construction of the initial individuals or during
the application of the operators.
In opposite to this, one could not know the good genes, i. e. the
building-blocks which construct the optimal solution.
Therefore, the designer has to support the genetic algorithm by
presenting a pool of good genes.
From this pool the algorithm can compose some good and (hopefully)
eventually the optimal solution to the given optimization problem.
In the following, after a short description of the physical design process of VLSI-chips, a problem specific genetic algorithm for the layout generation is described. This approach takes into account the previous mentioned items by covering the following features: