For the application of genetic algorithms to optimize
combinatorial problems, the focal point is to find a proper genotype encoding
and all genetic operators, which are necessary to enable the
algorithm to reach a global optimum.
Solutions to real-world optimization problems are too complex for
being represented as a simple gene-string.
In the layout optimization process, due to the problem specific genotype
encoding as a binary tree, the genetic algorithm is able to compute
and optimize the routing on a chip concurrently with the placement of
the modules.
Usually in VLSI-CAD tools this is done in consecutive steps because
of the complexity of the single optimization problems.
But according to the strong interdependencies between the arrangement
of the modules and the routing of the interconnection nets,
it is wise to combine both steps.

The described application is a good example for the tasks which
research on genetic algorithms should deal with:
Because of the nondeterministic behaviour and the long runtimes, genetic
algorithms will never succeed against other optimization methods
for low complexity problems that allow fast greedy solutions.
But for high complexity problems without any known sophisticated solution techniques,
a genetic approach is well suited.
By solving such a hard and complex problem, critics can easily be convinced of the
power and the advantages of genetic algorithms.
When designing a genetic algorithm for such a special application, it
is important to withdraw from usual solution methods in
one part, but using hybrid approaches and problem specific knowledge
for hill-climbing in another.
By doing so, there always is the trade-off between directed search and
random search.
The designer has to find out, which part of the optimization
can be done `by hand', how the genetic algorithm can be supported during
the search process, and which tasks * must* be left for the
genetic algorithm to work on.

Mon Feb 19 14:44:56 MET 1996