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.